El método de Halley

En análisis numérico , el método de Halley es un algoritmo para encontrar raíces que se utiliza 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 iterativamente una secuencia de aproximaciones a la raíz; su tasa de convergencia a la raíz es cúbica. Existen versiones multivariadas de este método.

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

También existe el método irracional de Halley , que se describe a continuación.

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 debe ser una función de una variable real. El método consiste en una secuencia de iteraciones:

${\displaystyle x_{n+1}=x_{n}-{\frac {\ f(x_{n})\ f'(x_{n})\ }{\ \left[\ f'(x_{n})\ \right]^{2}-{\tfrac {1}{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 un entorno de a , las iteraciones x _n satisfacen:

${\displaystyle |x_{n+1}-a|\leq K\cdot {|x_{n}-a|}^{3},\quad {\text{ para algún }}\quad K>0~.}$

Esto significa que las iteraciones convergen a cero si la estimación inicial es 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 razón${\displaystyle \ f(x_{n})/f'(x_{n})\ }$solo necesita calcularse una vez, y esta forma es particularmente útil cuando la otra razón,${\displaystyle \ f''(x_{n})/f'(x_{n})\ ,}$puede reducirse a una forma más simple:

${\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 {1}{2}}\cdot {\frac {f(x_{n})}{\ f'(x_{n})\ }}\cdot {\frac {\ f''(x_{n})\ }{f'(x_{n})}}\ \right]^{-1}~.}$

Cuando la segunda derivada ,${\displaystyle \ f''(x_{n})\ ,}$es muy cercano a cero, la iteración del método de Halley es casi la misma que la iteración del método de Newton.

Al derivar el método de Newton, una demostración comienza con la aproximación. $${\displaystyle 0=f(x_{n+1})\approx f(x_{n})+f'(x_{n})(x_{n+1}-x_{n})}$$ calcular $${\displaystyle x_{n+1}-x_{n}=-{\frac {f(x_{n})}{f'(x_{n})}}\,.}$$ De manera similar, para el método de Halley, una demostración comienza con $${\displaystyle 0=f(x_{n+1})\approx f(x_{n})+f'(x_{n})(x_{n+1}-x_{n})+{\frac {f''(x_{n})}{2}}(x_{n+1}-x_{n})^{2}\,.}$$ Para el método racional de Halley, esto se reorganiza para dar $${\displaystyle x_{n+1}-x_{n}=-{\frac {f(x_{n})}{f'(x_{n})+{\frac {f''(x_{n})}{2}}(x_{n+1}-x_{n})}}\,}$$ donde x _{n +1} − x _n aparece en ambos lados de la ecuación. Sustituyendo el valor del método de Newton para x _{n +1} − x _n en el lado derecho de esta última fórmula se obtiene la fórmula para el método de Halley, $${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})-{\frac {f''(x_{n})f(x_{n})}{2f'(x_{n})}}}}\,.}$$

Véase también la motivación y las demostraciones de la clase más general de métodos de Householder .

Supongamos que a es una raíz de f pero no de su derivada. Y supongamos que la tercera derivada de f existe y es continua en un entorno de a, y que x _n está en ese entorno. 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 comprendidos entre a y x _n . Multiplica la primera ecuación por${\displaystyle 2f'(x_{n})}$y réstale la segunda ecuación por${\displaystyle f''(x_{n})(a-x_{n})}$dar:

${\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}}}$

Cancelado${\displaystyle f'(x_{n})f''(x_{n})(a-x_{n})^{2}}$y reorganizando los términos se obtiene:

${\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}.}$

Coloca el segundo término en el lado izquierdo y divide 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 del 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 K un poco mayor que el valor absoluto de esto, podemos tomar los 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 era lo que había que demostrar.

En resumen,

${\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 ]}

El método racional de Halley aplicado a la función de valor real f ( x ) es el mismo que aplicar el método de Newton. $${\displaystyle x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}}$$ para encontrar los ceros de la función $${\displaystyle g(x)={\frac {f(x)}{\sqrt {|kf'(x)|}}}\,,}$$ donde k es cualquier constante distinta de cero. Aplicar el método de Newton a g ( x ) dará convergencia cúbica (o mejor), mientras que el método de Newton aplicado directamente a f ( x ) generalmente dará convergencia cuadrática.

Por ejemplo, usar el método de Halley para encontrar un cero de f ( x ) = y − e ^x , que es útil para estimar de manera eficiente y precisa x = ln( y ) , es lo mismo que usar el método de Newton para encontrar un cero de g ( x ) = ye ^{− x /2} − e ^{x /2} .

Halley desarrolló dos métodos de búsqueda de raíces de tercer orden. El anterior, que utiliza solo una división, se conoce como el método racional de Halley . Un segundo método, "irracional", también utiliza una raíz cuadrada. ^{[ 5 ] [ 6 ]} Comienza con

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

y resuelve${\displaystyle f(x_{n+1})\approx 0}$por el valor${\displaystyle (x_{n+1}-x_{n})}$utilizando la forma de la fórmula cuadrática para${\displaystyle a(x_{n+1}-x_{n})^{2}+b(x_{n+1}-x_{n})+c=0}$que tiene el radical en el denominador ,

${\displaystyle x_{n+1}=x_{n}-{\frac {2c}{b\left(1+{\sqrt {1-4ac/b^{2}}}\right)}}=x_{n}-{\frac {2f(x_{n})}{f'(x_{n})\left(1+{\sqrt {1-{\frac {2f(x_{n})f''(x_{n})}{f'(x_{n})^{2}}}}}\right)}}.}$

El signo para el radical se elige de manera que${\displaystyle x_{n+1}}$¿Está la raíz más cerca de?${\displaystyle x_{n}}$.

^{Halley [ 6 ]} prefirió esta iteración "merecidamente" al método racional porque tiende a tener aproximadamente la mitad del error del método racional, un beneficio que se multiplica a medida que se itera.

Esta formulación se reduce al método racional de Halley bajo la aproximación de que${\displaystyle {\sqrt {1-z}}\approx 1-z/2}$El método de Muller podría considerarse una modificación de este método. Por lo tanto, este método puede utilizarse para hallar raíces complejas.

El método de Halley se ha adaptado a múltiples variables, ^{[ 7 ]} donde el objetivo es encontrar una raíz${\displaystyle {\vec {x}}}$de${\displaystyle {\vec {f}}({\vec {x}})={\vec {0}}}$para alguna función${\displaystyle f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}}$con un entero positivo n . En este caso, el método de Newton utiliza los términos constantes y lineales de la serie de Taylor multivariada y resuelve la ecuación. $${\displaystyle {\vec {0}}={\vec {f}}({\vec {x}}_{n+1})\approx {\vec {f}}({\vec {x}}_{n})+M({\vec {x}}_{n+1}-{\vec {x}}_{n})}$$ con matriz${\displaystyle M_{ij}=\left.{\frac {\partial f_{i}}{\partial x_{j}}}\right|_{{\vec {x}}={\vec {x}}_{n}}}$ dar $${\displaystyle {\vec {x}}_{n+1}={\vec {x}}_{n}-M^{-1}{\vec {f}}({\vec {x}}_{n})}$$ utilizando la inversión de matrices . Siguiendo la motivación para el caso de una variable, el método de Halley da $${\displaystyle {\vec {x}}_{n+1}={\vec {x}}_{n}-\left(M-{\frac {1}{2}}\sum _{k}{\frac {\partial M}{\partial x_{k}}}\left(M^{-1}{\vec {f}}({\vec {x}}_{n})\right)_{k}\right)^{-1}{\vec {f}}({\vec {x}}_{n})}$$ donde el subíndice k indica la k -ésima coordenada del vector asociado.

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