El método de Halley.

En análisis numérico , el método de Halley es un algoritmo de búsqueda de raíces utilizado para funciones de una variable real con una segunda derivada continua. Edmond Halley fue un matemático y astrónomo inglés que introdujo el método que ahora lleva su nombre.

El algoritmo ocupa el segundo lugar en la clase de métodos de Householder , después del método de Newton . Al igual que este último, produce de forma iterativa una secuencia de aproximaciones a la raíz; su tasa de convergencia a la raíz es cúbica. Existen versiones multidimensionales de este método. ^{[ cita necesaria ]}

El método de Halley encuentra exactamente las raíces de una aproximación de Padé lineal sobre lineal a la función, en contraste con el método de Newton o el método de la secante que aproxima la función linealmente, o el método de Muller que aproxima la función cuadráticamente. ^[1]

Método

El método de Halley es un algoritmo numérico para resolver la ecuación no lineal f ( x ) = 0 . En este caso, la función f tiene que ser función de una variable real. El método consta de una secuencia de iteraciones:

${\displaystyle x_{n+1}=x_{n}-{\frac {2f(x_{n})f'(x_{n})}{2{[f'(x_{n})]}^{2}-f(x_{n})f''(x_{n})}}}$

comenzando con una suposición inicial x ₀ . ^[2]

Si f es una función tres veces continuamente diferenciable y a es un cero de f pero no de su derivada, entonces, en una vecindad de a , las iteraciones x _n satisfacen:

${\displaystyle |x_{n+1}-a|\leq K\cdot {|x_{n}-a|}^{3},{\text{ for some }}K>0.}$

Esto significa que las iteraciones convergen a cero si la estimación inicial es lo suficientemente cercana y que la convergencia es cúbica. ^[3]

La siguiente formulación alternativa muestra la similitud entre el método de Halley y el método de Newton. La expresión se calcula sólo una vez y es particularmente útil cuando se puede simplificar: ${\displaystyle f(x_{n})/f'(x_{n})}$ ${\displaystyle f''(x_{n})/f'(x_{n})}$

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})-{\frac {f(x_{n})}{f'(x_{n})}}{\frac {f''(x_{n})}{2}}}}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\left[1-{\frac {f(x_{n})}{f'(x_{n})}}\cdot {\frac {f''(x_{n})}{2f'(x_{n})}}\right]^{-1}.}$

Cuando la segunda derivada es muy cercana a cero, la iteración del método de Halley es casi la misma que la iteración del método de Newton.

Derivación

Considere la función

${\displaystyle g(x)={\frac {f(x)}{\sqrt {|f'(x)|}}}.}$

Cualquier raíz r de f que no sea raíz de su derivada es una raíz de g (es decir, cuando ), y cualquier raíz r de g debe ser raíz de f siempre que la derivada de f en r no sea infinita. Aplicando el método de Newton a g se obtiene ${\displaystyle g(r)=0}$ ${\displaystyle f(r)=0\neq {\sqrt {|f'(r)|}}}$

${\displaystyle x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}}$

con

${\displaystyle g'(x)={\frac {2[f'(x)]^{2}-f(x)f''(x)}{2f'(x){\sqrt {|f'(x)|}}}},}$

y el resultado sigue. Observe que si f ′( c ) = 0 , entonces no se puede aplicar esto en c porque g ( c ) no estaría definido. ^{[ Se necesita más explicación ]}

Convergencia cúbica

Supongamos que a es raíz de f pero no de su derivada. Y supongamos que la tercera derivada de f existe y es continua en una vecindad de a y x _n está en esa vecindad. Entonces el teorema de Taylor implica:

${\displaystyle 0=f(a)=f(x_{n})+f'(x_{n})(a-x_{n})+{\frac {f''(x_{n})}{2}}(a-x_{n})^{2}+{\frac {f'''(\xi )}{6}}(a-x_{n})^{3}}$

y también

${\displaystyle 0=f(a)=f(x_{n})+f'(x_{n})(a-x_{n})+{\frac {f''(\eta )}{2}}(a-x_{n})^{2},}$

donde ξ y η son números que se encuentran entre a y x _n . Multiplica la primera ecuación por y resta la segunda ecuación para obtener: ${\displaystyle 2f'(x_{n})}$ ${\displaystyle f''(x_{n})(a-x_{n})}$

${\displaystyle {\begin{aligned}0&=2f(x_{n})f'(x_{n})+2[f'(x_{n})]^{2}(a-x_{n})+f'(x_{n})f''(x_{n})(a-x_{n})^{2}+{\frac {f'(x_{n})f'''(\xi )}{3}}(a-x_{n})^{3}\\&\qquad -f(x_{n})f''(x_{n})(a-x_{n})-f'(x_{n})f''(x_{n})(a-x_{n})^{2}-{\frac {f''(x_{n})f''(\eta )}{2}}(a-x_{n})^{3}.\end{aligned}}}$

Cancelar y reorganizar términos produce: ${\displaystyle f'(x_{n})f''(x_{n})(a-x_{n})^{2}}$

${\displaystyle 0=2f(x_{n})f'(x_{n})+\left(2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})\right)(a-x_{n})+\left({\frac {f'(x_{n})f'''(\xi )}{3}}-{\frac {f''(x_{n})f''(\eta )}{2}}\right)(a-x_{n})^{3}.}$

Coloque el segundo término en el lado izquierdo y divídalo por

${\displaystyle 2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})}$

Llegar:

${\displaystyle a-x_{n}={\frac {-2f(x_{n})f'(x_{n})}{2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})}}-{\frac {2f'(x_{n})f'''(\xi )-3f''(x_{n})f''(\eta )}{6(2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n}))}}(a-x_{n})^{3}.}$

De este modo:

${\displaystyle a-x_{n+1}=-{\frac {2f'(x_{n})f'''(\xi )-3f''(x_{n})f''(\eta )}{12[f'(x_{n})]^{2}-6f(x_{n})f''(x_{n})}}(a-x_{n})^{3}.}$

El límite del coeficiente en el lado derecho cuando x _n → a es:

${\displaystyle -{\frac {2f'(a)f'''(a)-3f''(a)f''(a)}{12[f'(a)]^{2}-6f(a)f''(a)}}.}$

Si tomamos que K es un poco mayor que el valor absoluto de esto, podemos tomar valores absolutos de ambos lados de la fórmula y reemplazar el valor absoluto del coeficiente por su límite superior cerca de a para obtener:

${\displaystyle |a-x_{n+1}|\leq K|a-x_{n}|^{3}}$

que es lo que había que demostrar.

Para resumir,

${\displaystyle \Delta x_{i+1}={\frac {3(f'')^{2}-2f'f'''}{12(f')^{2}}}(\Delta x_{i})^{3}+O[\Delta x_{i}]^{4},\qquad \Delta x_{i}\triangleq x_{i}-a.}$^[4]

Referencias

1. Boyd, JP (2013). "Encontrar los ceros de una ecuación univariada: buscadores de raíces proxy, interpolación de Chebyshev y la matriz complementaria". Revisión SIAM . 55 (2): 375–396. doi :10.1137/110838297.
2. Scavo, TR; Bueno, JB (1995). "Sobre la geometría del método de Halley". Mensual Matemático Estadounidense . 102 (5): 417–426. doi :10.2307/2975033. JSTOR  2975033.
3. Alefeld, G. (1981). "Sobre la convergencia del método de Halley". Mensual Matemático Estadounidense . 88 (7): 530–536. doi :10.2307/2321760. JSTOR  2321760.
4. Proinov, Petko D.; Ivanov, Stoil I. (2015). "Sobre la convergencia del método de Halley para el cálculo simultáneo de ceros polinomiales". J. Número. Matemáticas . 23 (4): 379–394. doi :10.1515/jnma-2015-0026. S2CID  10356202.

enlaces externos

• Weisstein, Eric W. "El método de Halley". MundoMatemático .
• Método de Newton e iteraciones de alto orden , Pascal Sebah y Xavier Gourdon, 2001 (el sitio tiene un enlace a una versión Postscript para una mejor visualización de la fórmula)