Méthode de Halley

« Itération de Halley » redirige ici. Pour les autres significations, voir Itération (homonymie).

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, est une généralisation de la méthode de Newton ; elle est à convergence cubique.

Énoncé

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.

Obtention à partir de la méthode de Newton

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

Application au calcul d'une fonction réciproque

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.

Notes et références

Voir aussi