C.2 El comportamiento de error del método de Newton

El método de Newton suele funcionar espectacularmente bien, siempre que tu suposición inicial esté razonablemente cerca de una solución de$f(x)=0\text{.}$ Una buena manera de seleccionar esta suposición inicial es bosquejar la gráfica de Ahora$y=f(x)\text{.}$ explicamos por qué “el método de Newton suele funcionar espectacularmente bien, siempre que tu suposición inicial sea razonablemente cerca de una solución de$f(x)=0$”.

$r$Sea cualquier solución de$f(x)=0\text{.}$ Entonces$f(r)=0\text{.}$ Supongamos que ya hemos calculado$x_n\text{.}$ El error en$x_n$ es Ahora$\big|x_n-r\big|\text{.}$ derivamos una fórmula que relaciona el error después del siguiente paso,$\big|x_{n+1}-r\big|\text{,}$ a$\big|x_n-r\big|\text{.}$ Hemos visto en (3.4.32) que

\ begin {reunir*} f (x) =f (x_n) +f' (x_n) (x-x_n) +\ frac {1} {2} f "(c) (x-x_n) ^2\ end {reunir*}

para algunos$c$ entre$x_n$ y$x\text{.}$ En particular, elegir$x=r\text{,}$

$$0=f(r)=f(x_n)+f'(x_n)(r-x_n)+\frac{1}{2} f''(c)(r-x_n)^2 \tag{E1} \nonumber$$

Recordemos que$x_{n+1}$ es la solución de$0=f(x_n)+f'(x_n)(x-x_n)\text{.}$ So

$$0=f(x_n)+f'(x_n)(x_{n+1}-x_n) \tag{E2} \nonumber$$

Necesitamos obtener una expresión para$x_{n+1}-r\text{.}$ restar (E2) de (E1) da

\ begin {align*} 0=f' (x_n) (r-x_ {n+1}) +\ frac {1} {2} f "(c) (r-x_n) ^2\ &\ implica\ x_ {n+1} -r=\ frac {f" (c)} {2f' (x_n)} (x_n-r) ^2\\ &\ implica\\ big|x_ {n+1} -r\ big| =\ frac {|f "(c) |} {2|f' (x_n) |} |x_n-r|^2\ end {align*}

Si la conjetura$x_n$ es cercana a$r\text{,}$ entonces$c\text{,}$ que debe estar entre$x_n$ y también$r\text{,}$ está cerca de$r$ y vamos a tener$f''(c)\approx f''(r)$ y$f'(x_n)\approx f'(r)$ y

$$\big|x_{n+1}-r\big| \approx\frac{|f''(r)|}{2|f'(r)|}|x_n-r|^2 \tag{E3} \nonumber$$

Incluso cuando no$x_n$ está cerca de$r\text{,}$ si sabemos que hay dos números$L,M\gt 0$ tales que$f$ obedece:

1. $\big|f'(x_n)\big|\ge L$
2. $\big|f''(c)\big|\le M$

(veremos ejemplos de esto a continuación) entonces tendremos

$$\big|x_{n+1}-r\big| \le\frac{M}{2L}|x_n-r|^2 \tag{E4} \nonumber$$

Denotemos por$\varepsilon_1$ el error,$|x_1-r|\text{,}$ de nuestra suposición inicial. De hecho, denotemos por$\varepsilon_n$ el error,$|x_n-r|\text{,}$ en$x_n\text{.}$ Entonces (E4) dice

$$\varepsilon_{n+1}\le \frac{M}{2L}\varepsilon_n^2 \nonumber$$

En particular

\ begin {alignat*} {3}\ varepsilon_2&\ le\ frac {M} {2L}\ varepsilon_1^2\\ varepsilon_3&\ le\ frac {M} {2L}\ varepsilon_2^2 & &\ le\ frac {M} {2L}\ izquierda (\ frac {M} {2L}\ varepsilon_1^2\ derecha) ^2 & & =\ izquierda (\ frac {M} {2L}\ derecha) ^3\ varepsilon_1^4\\ varepsilon_4&\ le\ frac {M} {2L}\ varepsilon_3^2 & & amp;\ le\ frac {M} {2L}\ izquierda [\ izquierda (\ frac {M} {2L}\ derecha) ^3\ varepsilon_1^4\ derecha] ^2 & & =\ izquierda (\ frac {M} {2L}\ derecha) ^7\ varepsilon_1^8\\ varepsilon_5& le\\ frac {M} {2L}\ varepsilon_4^2 & &\ le\ frac {M} {2L}\ izquierda [\ izquierda (\ frac {M} {2L}\ derecha) ^7\ varepsilon_1^8\ derecha] ^2 & & =\ izquierda (\ frac {M} {2L}\ derecha) ^ {15}\ varepsilon_1^ {16}\ end {alignat*}

A estas alturas podemos ver la formación de un patrón, que se verifica fácilmente por inducción ¹ La inducción matemática es una técnica para probar una secuencia$S_1\text{,}$ $S_2\text{,}$ $S_3\text{,}$ $\cdots$ of statements. That technique consists of first proving that $S_1$ is true, and then proving that, for any natural number $n\text{,}$ if $S_n$ is true then $S_{n+1}$ is true..

$$\varepsilon_n\le \left( \frac{M}{2L}\right)^{2^{n-1}-1}\varepsilon_1^{2^{n-1}} =\frac{2L}{M}\left(\frac{M}{2L}\varepsilon_1\right)^{2^{n-1}} \tag{E5} \nonumber$$

Siempre y cuando$\frac{M}{2L}\varepsilon_1\lt 1$ (lo que nos da una idea cuantitativa de lo buena que tiene que ser nuestra primera suposición para que el método de Newton funcione), esto va a cero extremadamente rápido a medida que$n$ aumenta. Por ejemplo, supongamos que$\frac{M}{2L}\varepsilon_1\le \frac{1}{2}\text{.}$ Entonces

$$\varepsilon_n\le \frac{2L}{M}\left(\frac{1}{2}\right)^{2^{n-1}} \le \frac{2L}{M}\cdot\begin{cases} 0.25 & \text{if }n=2 \\ 0.0625& \text{if }n=3 \\ 0.0039=3.9\times 10^{-3}& \text{if }n=4 \\ 0.000015=1.5\times 10^{-5}& \text{if }n=5 \\ 0.00000000023=2.3\times 10^{-10}& \text{if }n=6 \\ 0.000000000000000000054=5.4\times 10^{-20} & \text{if }n=7 \end{cases} \nonumber$$

Cada vez que$n$ aumentas en uno, el número de ceros después del decimal se duplica aproximadamente. Se puede ver por qué desde (E5). Desde

$$\left(\frac{M}{2L}\varepsilon_1\right)^{2^{(n+1)-1}} =\left(\frac{M}{2L}\varepsilon_1\right)^{2^{n-1}\times 2} =\left[\left(\frac{M}{2L}\varepsilon_1\right)^{2^{n-1}}\right]^2 \nonumber$$

tenemos, en términos muy generales,$\varepsilon_{n+1}\approx\varepsilon_n^2\text{.}$ Este comportamiento cuadrático es la razón por la que el método de Newton es tan útil.

Ejemplo C.2.1 (Ejemplo C.1.2, continuación).

Consideremos, como hicimos en el Ejemplo C.1.2,$f(x)=x^2-2\text{,}$ comenzando con$x_1=\frac{3}{2}\text{.}$ Entonces

$$f'(x)=2x\qquad f''(x)=2 \nonumber$$

Recordando, de (H1) y (H2), que$L$ es un límite inferior en$|f'|$ y$M$ es un límite superior en ciertamente$|f''|\text{,}$ podemos tomar$M=2$ y si, por ejemplo,$x_n\ge 1$ para todos$n$ (como sucedió en el Ejemplo C.1.2), podemos tomar$L=2$ también. Si bien no sabemos qué$r$ es, sí sabemos eso$1\le r\le 2$ (desde$f(1)=1^1-2\lt 0$ y$f(2)=2^2-2>0$). Como tomamos$x_1=\frac{3}{2}\text{,}$ tenemos$\varepsilon_1=|x_1-r|\le \frac{1}{2}\text{,}$ para que$\frac{M}{2L}\varepsilon_1\le\frac{1}{4}$ y

$$\varepsilon_{n+1}\le \frac{2L}{M}\left(\frac{M}{2L}\varepsilon_1\right)^{2^{n-1}} \le 2\left(\frac{1}{4}\right)^{2^{n-1}} \tag{E6} \nonumber$$

Esto tiende a cero muy rápidamente a medida que$n$ aumenta. Además, este es un límite superior en el error y no en el error real. De hecho (E6) es un límite superior muy crudo. Por ejemplo, la configuración$n=3$ da el límite

$$\varepsilon_4\le 2\left(\frac{1}{4}\right)^{2^2} = 7\times 10^{-3} \nonumber$$

y vimos en el Ejemplo C.1.2 que el error real en$x_4$ era menor que$5\times 10^{-10}\text{.}$

Ejemplo C.2.2 (Ejemplo C.1.3, continuación).

Consideremos, como hicimos en el Ejemplo C.1.3,$f(x)=\sin x\text{,}$ comenzando con$x_1=3\text{.}$ Entonces

\ begin {reunir*} f' (x) =\ cos x\ qquad f "(x) =-\ sin x\ fin {reunir*}

Como ciertamente$|-\sin x|\le 1\text{,}$ podemos tomar$M=1\text{.}$ En el Ejemplo C.1.3, todos$x_n$ estaban entre$3$ y$3.2\text{.}$ Desde (a tres decimales)

\ comenzar {reunir*}\ sin (3) =0.141>0\ qquad\ sin (3.2) =-0.058\ lt 0\ end {reunir*}

el IVT (teorema del valor intermedio) nos dice que$3\lt r\lt 3.2$ y$\varepsilon_1=|x_1-r|\lt 0.2\text{.}$

Así$r$ y todos$x_n$ y por lo tanto todos$c$ se encuentran en el intervalo$(3,3.2)\text{.}$ Desde

\ begin {reunir*} -0.9990=\ cos (3)\ lt\ cos c\ lt\ cos (3.2) =- 0.9983\ end {reunir*}

necesariamente tenemos$\big|f'(c)\big|=\big|\cos c\big|\ge 0.9$ y podemos tomar$L=0.9\text{.}$ tan

\ begin {reunir*}\ varepsilon_ {n+1}\ le\ frac {2L} {M}\ izquierda (\ frac {M} {2L}\ varepsilon_1\ derecha) ^ {2^ {n-1}}\ le\ frac {2\ tiempos0.9} {1}\ izquierda (\ frac {1} {2\ tiempo0.9} 0.2\ derecha) ^ {2^ {n-1}}\ le 2\ izquierda (\ frac {1} {9}\ derecha) ^ {2^ {n-1}}\ end {reunir*}

Esto tiende a cero muy rápidamente a medida que$n$ aumenta.

Ahora hemos visto dos procedimientos para encontrar raíces de una función$f(x)$: el método de la bisección (que no usa la derivada de$f(x)\text{,}$ pero que no es muy eficiente) y el método de Newton (que utiliza la derivada de$f(x)\text{,}$ y que es muy eficiente). De hecho, hay toda una constelación de otros métodos ² ¿Qué dice de los matemáticos que han desarrollado tantas formas de encontrar cero? y el lector interesado debe buscar su camino hacia, por ejemplo, el artículo de Wikipedia sobre algoritmos de búsqueda de raíces. Aquí, solo mencionaremos otros dos métodos, siendo uno una variante del método de la bisección y el otro una variante del método de Newton.