El método de Newton
De las perturbaciones de Newton en 1669 a la iteración con derivada, y lo que puede salir mal.
En la nota anterior vimos que hay mucha libertad para convertir la ecuación \(f(x)=0\) en un problema de punto fijo, y que Newton es una forma particular de elegir \(g\). Aquí vemos de dónde sale esa elección, siguiendo la idea con la que Newton la usó en De analysi (1669), y cómo se reescribe con derivadas.
1 La idea de Newton, a mano
Newton trabajó con \(f(x)=x^3-2x-5\), y tomamos la misma función. Como semilla elegimos \(x_0=2\). Como \(f(2)=-1\), el \(2\) no es raíz pero no está lejos: con \(x_0=1\) se obtiene \(f(1)=-6\) y con \(x_0=3\) se obtiene \(f(3)=16\), ambos mucho más lejos de cero.
Perturbamos un poco la semilla, escribiendo \(x=2+p\) con \(p\) pequeño:
\[f(2+p)=(2+p)^3-2(2+p)-5=p^3+6p^2+10p-1.\]
El \(-1\) es lo que le toca a \(f(2)\). Como \(p\) es pequeño, \(p^3\) y \(p^2\) son despreciables frente a \(10p\), y queda \(10p-1=0\), es decir \(p=0{,}1\). La nueva aproximación es \(x_1=2{,}1\), y \(f(2{,}1)=0{,}061\): mucho más cerca de cero que \(f(2)=-1\).
Pulimos ahora \(p\) con el mismo truco: escribimos \(p=0{,}1+q\) en el polinomio \(p^3+6p^2+10p-1\) y obtenemos
\[q^3+6{,}3\,q^2+11{,}23\,q+0{,}061.\]
Despreciando otra vez \(q^3\) y \(q^2\) queda \(q=-0{,}061/11{,}23\approx-0{,}0054319\), y \(x_2=2{,}1+q\approx2{,}094568\).
Podemos seguir así indefinidamente. Con \(x_2\) el error relativo ya es bajo, cerca de \(8\cdot10^{-6}\), y el residuo es \(f(x_2)\approx1{,}9\cdot10^{-4}\). Existe además la solución exacta por Cardano, la que entrega un sistema de álgebra computacional,
\[r=\frac{\sqrt[3]{45-\sqrt{1929}}+\sqrt[3]{45+\sqrt{1929}}}{\sqrt[3]{18}}\approx2{,}0945515,\]
pero es de muy poca utilidad para efectos prácticos.
2 Newton con derivadas
Veamos lo mismo con derivadas. Desarrollando alrededor de \(x_0\) y quedándonos con el término lineal en \(p\) (que es lo que hacía Newton al despreciar las potencias altas de \(p\)),
\[0=f(x_0+p)=f(x_0)+f'(x_0)\,p+o(p)\quad\Longrightarrow\quad p\approx-\frac{f(x_0)}{f'(x_0)},\]
de modo que \(x_1=x_0+p=x_0-\dfrac{f(x_0)}{f'(x_0)}\). Repetimos desde \(x_1\): \(0=f(x_1+q)=f(x_1)+f'(x_1)\,q+o(q)\) da \(q\approx-f(x_1)/f'(x_1)\) y \(x_2=x_1+q=x_1-f(x_1)/f'(x_1)\). En general
\[x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}.\]
Los coeficientes que Newton iba obteniendo al reescribir el polinomio son justamente \(f\) y \(f'\) evaluadas en cada aproximación: en \(p^3+6p^2+10p-1\) el término independiente es \(f(2)=-1\) y el coeficiente de \(p\) es \(f'(2)=10\), y en el segundo paso son \(f(2{,}1)=0{,}061\) y \(f'(2{,}1)=11{,}23\).
Importante: que \(f'(x)\ne0\) en donde se están realizando las iteraciones. El siguiente ejercicio es un caso ideal en el que las hipótesis lo garantizan.
3 Un caso ideal: el ejercicio de Rudin
Sea \(f\) dos veces diferenciable en \([a,b]\) con \(f(a)<0<f(b)\), \(f'(x)\ge\delta>0\) y \(0\le f''(x)\le M\) para todo \(x\in[a,b]\). Es un caso ideal: hay un único cero de \(f\) en \([a,b]\), que llamamos \(\xi\). Tomemos \(x_1\in(\xi,b)\) y sea \(x_{n+1}=x_n-f(x_n)/f'(x_n)\).
(a) Interprete esta iteración gráficamente.
(b) Demuestre que \(x_{n+1}<x_n\) y que \(x_n\to\xi\).
(c) Use el teorema de Taylor para mostrar que \(x_{n+1}-\xi=\dfrac{f''(t_n)}{2f'(x_n)}\,(x_n-\xi)^2\) para algún \(t_n\in(\xi,x_n)\).
(d) Si \(A=M/(2\delta)\), deduzca que \(0\le x_{n+1}-\xi\le\dfrac1A\big[A(x_1-\xi)\big]^{2^n}\).
(e) Muestre que el método de Newton equivale a hallar un punto fijo de \(g(x)=x-f(x)/f'(x)\). ¿Cómo se comporta \(g'(x)\) cerca de \(\xi\)?
(f) Tome \(f(x)=x^{1/3}\) en \((-\infty,\infty)\) e intente el método de Newton. ¿Qué pasa?
(a) La tangente a la gráfica en \((x_n,f(x_n))\) es \(y=f(x_n)+f'(x_n)(x-x_n)\), y corta el eje horizontal en \(x_{n+1}=x_n-f(x_n)/f'(x_n)\). En la figura, el segmento de \(x_2\) a \(x_1\) sobre el eje mide \(f(x_1)/f'(x_1)\).
(b) Como \(f''\ge0\), \(f'\) es creciente: la función es cóncava hacia arriba. Probamos por inducción que \(\xi\le x_n\) y \(x_{n+1}\le x_n\) para todo \(n\). Para \(n=1\) se cumple \(\xi<x_1\) por hipótesis. Supongamos \(\xi\le x_n\). Como \(f\) es creciente y \(f(\xi)=0\), tenemos \(f(x_n)\ge0\), y como \(f'>0\),
\[x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\le x_n.\]
Falta ver que \(\xi\le x_{n+1}\). Si \(x_n=\xi\) no hay nada que probar. Si \(x_n>\xi\), por el teorema del valor medio, para algún \(t\in(\xi,x_n)\),
\[f(x_n)=f(x_n)-f(\xi)=f'(t)(x_n-\xi)\le f'(x_n)(x_n-\xi),\]
porque \(f'\) es creciente. Dividiendo por \(f'(x_n)>0\) queda \(f(x_n)/f'(x_n)\le x_n-\xi\), es decir \(x_{n+1}\ge\xi\). (Si \(f\) fuese lineal cerca de \(\xi\), Newton llegaría a \(\xi\) en un paso y la sucesión quedaría constante; por eso las desigualdades son estrictas solo mientras \(x_n>\xi\).)
Entonces \((x_n)\) es no creciente y acotada inferiormente por \(\xi\), así que converge a un \(x^\ast\ge\xi\). Pasando al límite en la recursión, \(x^\ast=x^\ast-f(x^\ast)/f'(x^\ast)\), luego \(f(x^\ast)=0\), y como \(\xi\) es el único cero de \(f\), \(x^\ast=\xi\).
(c) Por Taylor alrededor de \(x_n\), con \(t_n\) entre \(\xi\) y \(x_n\),
\[-f(x_n)=f(\xi)-f(x_n)=f'(x_n)(\xi-x_n)+\frac{f''(t_n)}{2}(\xi-x_n)^2.\]
Dividiendo por \(f'(x_n)\),
\[-\frac{f(x_n)}{f'(x_n)}=(\xi-x_n)+\frac{f''(t_n)}{2f'(x_n)}(x_n-\xi)^2,\]
y sumando \(x_n\),
\[x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=\xi+\frac{f''(t_n)}{2f'(x_n)}(x_n-\xi)^2, \qquad\text{es decir}\qquad x_{n+1}-\xi=\frac{f''(t_n)}{2f'(x_n)}(x_n-\xi)^2.\]
(d) Con \(A=M/(2\delta)\) se tiene \(0\le\dfrac{f''(t_n)}{2f'(x_n)}\le A\), y aplicando la cota una y otra vez,
\[0\le x_{n+1}-\xi\le A(x_n-\xi)^2=\frac1A\big(A(x_n-\xi)\big)^2\le\frac1A\Big(A\cdot\frac1A\big(A(x_{n-1}-\xi)\big)^2\Big)^2=\frac1A\big(A(x_{n-1}-\xi)\big)^{4}\le\cdots\le\frac1A\big(A(x_1-\xi)\big)^{2^n}.\]
(e) Los puntos fijos de \(g(x)=x-f(x)/f'(x)\) son los \(x\) con \(f(x)/f'(x)=0\), es decir los ceros de \(f\) (donde \(f'\ne0\)), y la iteración de Newton es exactamente \(x_{n+1}=g(x_n)\): aplicar Newton es buscar un punto fijo de \(g\).
(f) Con \(f(x)=x^{1/3}\) y \(f'(x)=\tfrac13x^{-2/3}\) (con la raíz cúbica real, \(f'(x)=\tfrac13|x|^{-2/3}\) para \(x\ne0\)), tomemos \(x_0>0\):
\[x_1=x_0-\frac{x_0^{1/3}}{\tfrac13x_0^{-2/3}}=x_0-3x_0=-2x_0\quad(\text{negativo}),\]
\[x_2=x_1-3x_1=-2x_0-3(-2x_0)=4x_0\quad(\text{positivo}),\]
\[x_3=x_2-3x_2=4x_0-12x_0=-8x_0,\qquad x_4=x_3-3x_3=-8x_0+24x_0=16x_0,\]
y en general \(x_n=(-1)^n2^nx_0\): cada vez se aleja más del cero. La función \(x^{1/3}\) tiene derivada positiva pero no está alejada de cero (tiende a \(0\) cuando \(|x|\to\infty\), así que no existe \(\delta>0\) con \(f'\ge\delta\)), y además cambia la concavidad en \(0\), de modo que tampoco vale \(f''\ge0\). Fallan las hipótesis del caso ideal.
Complete el inciso (e): calcule \(g'(x)\) y describa cómo se comporta cerca de \(\xi\). Haga todos los ejercicios de la sección de Método de Newton del texto guía.
4 Tablero: Newton en tres casos
El tablero reúne tres ejemplos: el polinomio de Newton, donde todo sale como en la teoría; la raíz cúbica, donde el método falla para toda semilla; y el arco tangente, donde la raíz es buena pero la iteración se vuelve inestable según la semilla. Elija el caso, mueva la semilla \(x_0\) y cambie el número de pasos; la tabla muestra el error y las cifras correctas de cada iterado.
La geometría es importante: en los tres casos el siguiente iterado es el punto donde la tangente corta el eje, y todo depende de cómo sea la curva entre un iterado y el siguiente.