GuíaEcuaciones no linealesavanzado

Métodos de alto orden: Halley, Traub, Ostrowski y Jarratt

Tres técnicas para diseñar métodos iterativos más rápidos que Newton: fórmulas de cuadratura, composición de esquemas (con derivada congelada) y funciones peso, con las familias Chebyshev-Halley y King.

Composición: por qué no basta encadenar Newtons

Componer Newton consigo mismo (Newton doble) da orden 44, pero exige 4 evaluaciones por iteración (ff y f′f' en dos puntos): no es óptimo. Congelar la derivada permite reutilizar f′(xk)f'(x_k) en el segundo paso y gastar una evaluación menos, aunque se pierde algo de orden. El resultado es el método de Traub (o Potra-Pták), de orden 3 con 3 evaluaciones:

yk=xk−f(xk)f′(xk)xk+1=yk−f(yk)f′(xk)\begin{aligned} y_k&=x_k-\frac{f(x_k)}{f'(x_k)}\\ x_{k+1}&=y_k-\frac{f(y_k)}{f'(x_k)} \end{aligned}
Método de Traub (Potra-Pták): orden 3 con derivada congelada.

Fórmulas de cuadratura

Igual que en los métodos para EDO, se puede escribir f(x)=f(xk)+∫xkxf′(t) dtf(x)=f(x_k)+\int_{x_k}^{x}f'(t)\,dt y aproximar la integral con distintas cuadraturas, usando Newton como predictor yk=xk−f(xk)f′(xk)y_k=x_k-\frac{f(x_k)}{f'(x_k)}. Con la regla del trapecio sale el método de los trapecios; con el punto medio y con Simpson, sus análogos:

xk+1=xk−2f(xk)f′(yk)+f′(xk)x_{k+1}=x_k-\frac{2f(x_k)}{f'(y_k)+f'(x_k)}
Método de los trapecios.
xk+1=xk−f(xk)f′(xk+yk2)x_{k+1}=x_k-\frac{f(x_k)}{f'\bigl(\tfrac{x_k+y_k}{2}\bigr)}
Método del punto medio.
xk+1=xk−6f(xk)f′(xk)+4f′(xk+yk2)+f′(yk)x_{k+1}=x_k-\frac{6f(x_k)}{f'(x_k)+4f'\bigl(\tfrac{x_k+y_k}{2}\bigr)+f'(y_k)}
Método de Simpson.

La familia Chebyshev-Halley

Usando el grado de convexidad logarítmica Lf(xk)=f(xk)f′′(xk)f′(xk)2L_f(x_k)=\frac{f(x_k)f''(x_k)}{f'(x_k)^2} se construye una familia uniparamétrica de métodos de orden 3 con segunda derivada:

xk+1=xk−f(xk)f′(xk)[1+12 Lf(xk)1−βLf(xk)]x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}\left[1+\frac{1}{2}\,\frac{L_f(x_k)}{1-\beta L_f(x_k)}\right]
Familia Chebyshev-Halley, parámetro β\beta.
  • β=0\beta=0: método de Chebyshev, xk+1=xk−ff′[1+Lf2]x_{k+1}=x_k-\frac{f}{f'}\bigl[1+\frac{L_f}{2}\bigr].
  • β=12\beta=\tfrac12: método de Halley, xk+1=xk−ff′[1+Lf2−Lf]x_{k+1}=x_k-\frac{f}{f'}\bigl[1+\frac{L_f}{2-L_f}\bigr].
  • β=1\beta=1: método Super-Halley, xk+1=xk−ff′[1+Lf−22(Lf−1)]x_{k+1}=x_k-\frac{f}{f'}\bigl[1+\frac{L_f-2}{2(L_f-1)}\bigr].
  • β→∞\beta\to\infty: se recupera el método de Newton.

Funciones peso: King, Ostrowski y Jarratt

La tercera técnica multiplica el segundo paso de Traub por una función peso H(μ)H(\mu) de la variable μ=f(yk)f(xk)\mu=\frac{f(y_k)}{f(x_k)}:

yk=xk−f(xk)f′(xk)xk+1=yk−H(μk) f(yk)f′(xk)\begin{aligned} y_k&=x_k-\frac{f(x_k)}{f'(x_k)}\\ x_{k+1}&=y_k-H(\mu_k)\,\frac{f(y_k)}{f'(x_k)} \end{aligned}

Eligiendo H(μ)=1+βμ1+(β−2)μH(\mu)=\frac{1+\beta\mu}{1+(\beta-2)\mu} (que cumple las tres condiciones para todo β\beta) se obtiene la familia de King, óptima de orden 4:

xk+1=yk−f(xk)+βf(yk)f(xk)+(β−2)f(yk) f(yk)f′(xk)x_{k+1}=y_k-\frac{f(x_k)+\beta f(y_k)}{f(x_k)+(\beta-2)f(y_k)}\,\frac{f(y_k)}{f'(x_k)}
Familia de King. Con β=0\beta=0 se obtiene el método de Ostrowski.
yk=xk−23 f(xk)f′(xk)xk+1=xk−12(3f′(yk)+f′(xk)3f′(yk)−f′(xk))f(xk)f′(xk)\begin{aligned} y_k&=x_k-\frac{2}{3}\,\frac{f(x_k)}{f'(x_k)}\\ x_{k+1}&=x_k-\frac{1}{2}\left(\frac{3f'(y_k)+f'(x_k)}{3f'(y_k)-f'(x_k)}\right)\frac{f(x_k)}{f'(x_k)} \end{aligned}
Método de Jarratt, también óptimo de orden 4 (dos derivadas y una evaluación de ff).

El comportamiento real de todos estos métodos sobre funciones de prueba se analiza en la comparativa numérica.