méthode de Halley

Imaginez un nombre placé près du point où une courbe coupe l’axe horizontal. La méthode de Halley le remplace par une meilleure estimation, puis recommence. À chaque tour, elle regarde la hauteur de la courbe, sa pente et la manière dont cette pente varie.

Ces trois informations permettent souvent de gagner très vite des chiffres exacts près d’un zéro. Ce progrès a un coût : il faut calculer deux dérivées, et pas seulement la première.

La méthode de Halley est un algorithme itératif qui approche un nombre α tel que f(α)=0. La fonction numérique étudiée est notée f. Sa dérivée première f′ mesure sa variation locale, tandis que sa dérivée seconde f″ décrit la variation de cette pente. À partir d’une estimation x_n, la méthode calcule l’estimation suivante x_n+1.

La mise à jour s’écrit : Le dénominateur doit être non nul au point considéré. Chaque itération demande donc les valeurs de f, f′ et f″ au même nombre x_n.

Pour une racine simple et un point de départ assez proche, avec la régularité nécessaire autour de la racine, l’erreur décroît localement de façon cubique. La méthode appartient à la famille des méthodes de Householder d’ordre supérieur. Son avantage sur Newton est ce gain local plus rapide ; sa contrepartie est le calcul de la dérivée seconde.

On choisit une estimation initiale x₀. À l’étape n, on calcule f(x_n), f′(x_n) et f″(x_n), puis on vérifie que le dénominateur suivant ne s’annule pas : $2[f^{\mathrm{\prime }}(x_n){]}^2-f(x_n)f^{\mathrm{\prime }\mathrm{\prime }}(x_n)2[f\text{'}(x\_n)]^2-f(x\_n)f\text{'}\text{'}(x\_n)$.

On applique alors : Les itérations s’arrêtent lorsque le résidu |f(x_n)| ou le déplacement |x_n+1−x_n| passe sous la tolérance choisie.

La fonction doit être définie et deux fois dérivable dans la zone parcourue, avec une dérivée seconde continue. Les trois valeurs f(x_n), f′(x_n) et f″(x_n) doivent pouvoir être calculées à chaque étape. Pour obtenir la convergence cubique annoncée, on vise une racine simple et on choisit x₀ assez près d’elle, avec une fonction suffisamment régulière dans ce voisinage.

Il faut aussi contrôler le dénominateur $2[f^{\mathrm{\prime }}(x_n){]}^2-f(x_n)f^{\mathrm{\prime }\mathrm{\prime }}(x_n)2[f\text{'}(x\_n)]^2-f(x\_n)f\text{'}\text{'}(x\_n)$. S’il vaut zéro, l’itération de Halley n’est pas définie. Si le point initial est éloigné ou si la racine est multiple, le comportement cubique n’est plus garanti ; on peut alors changer de départ ou employer une méthode encadrant d’abord le zéro.

On cherche le zéro positif de la fonction f définie par f(x)=x²−2, c’est-à-dire √2. On part de x₀=3/2. Les dérivées sont f′(x)=2x et f″(x)=2.

1. Au point x₀=3/2, on obtient f(x₀)=1/4, f′(x₀)=3 et f″(x₀)=2.

2. Le dénominateur vaut 2×3²−(1/4)×2=35/2 ; il est donc non nul.

3. La première mise à jour donne :

4. Le contrôle est refaisable sans connaître √2 : f(99/70)=1/4900≈0,0002041. En une itération, le résidu est ainsi passé de 1/4 à environ deux dix-millièmes.

Pour approcher une racine carrée, on applique Halley à f(x)=x²−a. Cette option est intéressante lorsque les dérivées sont immédiates et qu’une estimation initiale raisonnable est disponible.

Dans un calcul numérique général, on compare le coût des dérivées au nombre d’itérations. Newton est souvent préférable si f″ est difficile ou coûteuse à obtenir ; Halley devient attractive lorsque f, f′ et f″ sont disponibles ensemble.

Le programme ne s’arrête pas sur le seul nombre d’itérations. Il surveille un résidu et un déplacement, fixe une tolérance, puis refuse la mise à jour si son dénominateur est nul ou numériquement trop petit.

Méthode de Newton. Newton utilise f et f′, avec la mise à jour $x_{n+1}=x_n-\frac{f(x_n)}{f^{\mathrm{\prime }}(x_n)}x\_\{n+1\}=x\_n-\backslash frac\{f(x\_n)\}\{f\text{'}(x\_n)\}$. Halley ajoute f″ : la présence effective de cette dérivée dans la correction tranche entre les deux méthodes.

Zéro de la fonction. Le zéro α est la valeur recherchée, caractérisée par f(α)=0. La méthode de Halley est la procédure qui produit des approximations successives de ce zéro ; une valeur x_n dont le résidu n’est pas nul reste une approximation.

Dénominateur nul ou presque nul. Si $2[f^{\mathrm{\prime }}(x_n){]}^2-f(x_n)f^{\mathrm{\prime }\mathrm{\prime }}(x_n)=02[f\text{'}(x\_n)]^2-f(x\_n)f\text{'}\text{'}(x\_n)=0$, la mise à jour est impossible. Une valeur très petite peut produire une correction de grande amplitude ou une instabilité numérique, selon la taille du numérateur : il faut contrôler un seuil et, si nécessaire, interrompre l’itération puis choisir un autre point ou une procédure de secours.

Racine multiple. La convergence cubique est un résultat local associé à une racine simple sous des hypothèses de régularité. Près d’une racine multiple, constater une baisse moins rapide du résidu n’est donc pas une contradiction ; il faut tenir compte de la multiplicité ou modifier la formule.

Bon départ non garanti. Une correction très précise près du zéro ne rend pas la méthode globalement convergente. Si les itérés s’éloignent, quittent le domaine de définition ou oscillent, on change le point initial ou on commence par encadrer un changement de signe.

Méthode de Newton. Comparer la correction fondée sur la seule dérivée première et sa convergence quadratique.

Zéro d’une fonction. Revenir à l’objet que les itérations cherchent à approcher et à sa lecture graphique.

Méthode de Householder. Situer Halley dans une famille de procédés itératifs d’ordre supérieur.