Méthode de Halley

En analyse numérique, la méthode de Halley est un algorithme de recherche d'un zéro d'une fonction de variable réelle deux fois dérivable et à dérivée seconde continue (i.e. C²). La méthode, présentée par l'astronome Edmond Halley en 1694^[1], est une généralisation de la méthode de Newton ; elle est à convergence cubique.

Soit ${\displaystyle f}$ une fonction de classe C² et ${\displaystyle a}$ un zéro de ${\displaystyle f}$. La méthode de Halley consiste à itérer

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

à partir d'une valeur ${\displaystyle x_{0}}$ proche de ${\displaystyle a}$.

Au voisinage de ${\displaystyle a}$, la suite vérifie :

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

avec ${\displaystyle K>0}$ ; ce qui signifie que la convergence est donc (au pire) cubique.

La formulation suivante montre que la méthode de Halley est un raffinement de celle de Newton, et très proche de celle-ci si ${\displaystyle f''(a)=0}$.

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

On remarque que dans cette formulation l'expression ${\displaystyle f(x_{n})/f'(x_{n})}$ n'est calculée qu'une fois.

La formule se déduit de la méthode de Newton appliquée à la fonction ${\displaystyle g=f/{\sqrt {f'}}}$ ; en effet, celle-ci s'écrit  :

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

avec

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

d'où le résultat. Si ${\displaystyle f'(a)=0}$, ceci ne s'applique que si ${\displaystyle g}$ peut être prolongée par continuité en ${\displaystyle a}$.

Appliquée à la fonction ${\displaystyle F(x)=f(x)-y}$, cette méthode conduit à une suite récurrente convergeant vers ${\displaystyle f^{-1}(y)}$.

Ceci peut être utilisé pour le calcul d'une racine n-ième, avec ${\displaystyle F(x)=x^{n}-A}$ ; la suite récurrente définie par ${\displaystyle x_{k+1}={\frac {x_{k}((n-1)(x_{k})^{n}+(n+1)A)}{(n+1)(x_{k})^{n}+(n-1)A}}}$ converge vers ${\displaystyle {\sqrt[{n}]{A}}}$.

En particulier pour une racine carrée, la récurrence s'écrit ${\displaystyle x_{k+1}={\frac {x_{k}(x_{k}^{2}+3A)}{3x_{k}^{2}+A}}}$.

La méthode de Halley est aussi utilisée pour calculer un logarithme népérien, en inversant la fonction exponentielle.

• Méthode de Newton
• Méthode de Householder

• (en) Eric W. Weisstein, « Halley's Method », sur MathWorld
• (en) Newton's method and high order iterations, Pascal Sebah et Xavier Gourdon, 2001

• Portail de l'analyse