Método de Newton

Para resolver $f(x) = 0$, sustituye $f$ por su recta tangente en la aproximación actual y salta a donde la tangente corta el cero: $x_{k+1} = x_k - f(x_k)/f'(x_k)$. Cerca de una raíz simple el número de cifras correctas se duplica en cada paso.

Ecuaciones como $\cos x = x$ o $x e^x = 3$ no tienen fórmula para su solución, y los sistemas no lineales de la ingeniería tienen miles de incógnitas. La idea de Newton: no sabemos resolver $f = 0$, pero sí resolver exactamente su aproximación lineal, y repetir.

Ponte en la curva en $(x_k, f(x_k))$, baja por la tangente hasta tocar el eje $x$ y sube otra vez a la curva. Si la curva es casi recta cerca de la raíz, cada tangente cae muy cerca. El paso $-f/f'$ es «cuánto falta, con la pendiente actual, para llegar a cero». Falla cuando la pendiente es casi plana (saltos enormes) o cuando se empieza en la cuenca equivocada.

x₀ → f(x₀), f'(x₀) → x₁ = x₀ − f(x₀)/f'(x₀) → x₂ → … → raíz

Teorema (convergencia cuadrática local). Sea $f \in C^2$ cerca de una raíz $x^\ast$ con $f'(x^\ast) \ne 0$. Entonces existe $\delta > 0$ tal que para todo $x_0$ con $|x_0 - x^\ast| < \delta$ los iterados convergen a $x^\ast$ y

Taylor en $x_k$: $0 = f(x^\ast) = f(x_k) + f'(x_k)(x^\ast - x_k) + \tfrac12 f''(\xi)(x^\ast - x_k)^2$. Divide entre $f'(x_k)$ y usa la definición de $x_{k+1}$: $x_{k+1} - x^\ast = \frac{f''(\xi)}{2f'(x_k)}(x_k - x^\ast)^2$.

x = x0
repetir:
    paso = f(x) / df(x)
    x = x - paso
hasta |paso| < tol·|x|  o  demasiadas iteraciones

En la práctica se añaden salvaguardas: volver a la bisección si el paso sale de un intervalo que horquilla la raíz, y amortiguar el paso ($x - \alpha\,f/f'$) lejos de la raíz.

$\sqrt 2$ como raíz de $x^2 - 2$: $x_{k+1} = \frac12\left(x_k + \frac{2}{x_k}\right)$, el método babilónico, de hace 4000 años. Desde $x_0 = 1$: $1{,}5$; $1{,}41667$; $1{,}4142157$; $1{,}41421356237469$; … Las cifras correctas van 1, 3, 6, 12: se duplican en cada paso.

El método de Newton está dentro de tu CPU (la división y la raíz cuadrada refinan una aproximación inicial con pasos de Newton), dentro de todo resolvedor no lineal del software de ingeniería, de los integradores físicos implícitos y de la cinemática inversa, y, aplicado a $\nabla f = 0$, es el prototipo de todos los métodos de optimización de segundo orden.