Ceci est une traduction automatique ; le texte anglais constitue la version originale. Lire l'original
La méthode de Newton peut doubler son erreur à chaque étape, alors que la réponse se trouvait à 0,01
Commencez à 0,01 de la réponse. Vingt étapes plus tard, vous vous retrouvez à −5 242,88, et chaque étape a été calculée correctement.
Résolvez x³ − x − 2 = 0. Il n'y a pas de formule élégante qui vaille la peine d'être retenue, alors faites ce que fait tout logiciel de calcul numérique : devinez, puis laissez la méthode de Newton corriger l'estimation.
Partez de 1,5. Trois itérations plus tard, vous obtenez 1,52138, et la fonction y est évaluée à 5,89387 × 10⁻⁷ — à moins d'un millionième de zéro. Trois étapes. Chaque étape double approximativement le nombre de chiffres corrects, c'est pourquoi cette méthode se trouve dans votre calculatrice, votre logiciel de CAO et le solveur de votre tableur.
Maintenant, demandez-lui quelque chose de plus simple. Résolvez ∛x = 0.
Vous connaissez la réponse. C'est zéro, et c'est la seule. Partez de 0,01 — déjà à un centième près — et observez :
0,01 → −0,02 → 0,04 → −0,08 → 0,16 → −0,32 → 0,64 → −1,28 → 2,56 → …
Après vingt itérations, l'estimation est de −5 242,88. Le résidu, qui commençait à 0,215, est désormais de 17,37. La méthode n'a ni stagné ni erré ; elle s'est éloignée de la réponse en suivant un raisonnement parfaitement rectiligne, doublant l'erreur et inversant le signe à chaque étape.
Rien ne s'est mal passé
La tentation est de chercher un bug. Il n'y en a pas, et le calcul vaut la peine d'être fait tant il est court.
L'étape de Newton est x − f(x)/f′(x). Pour f(x) = x1/3, la dérivée est (1/3)x−2/3, donc
f(x)/f′(x) = x1/3 ÷ ⅓x−2/3 = 3x
et la prochaine estimation est x − 3x = −2x. Pas approximativement : exactement. Chaque itération multiplie l'estimation par −2, à partir de n'importe quel point de départ, pour toujours. C'est de là que vient −5 242,88 — c'est 0,01 × (−2)19, et vous pouvez lire toute la suite géométrique dans le tableau d'itérations du Newton's Method Explorer sous son préréglage diverge.
Ce qu'a fait la racine cubique, c'est briser l'hypothèse sur laquelle repose la méthode. La méthode de Newton remplace la courbe par sa droite tangente et saute là où cette droite s'annule. Près d'une racine, c'est une excellente approximation — c'est le premier terme du développement de Taylor, et les termes négligés décroissent de façon quadratique, ce qui est exactement la raison pour laquelle le nombre de chiffres double. Mais ∛x possède une tangente verticale en zéro. Sa dérivée ne se contente pas d'y devenir petite, elle devient infinie, et la courbe n'est localement droite à aucun grossissement. Les droites tangentes près de zéro sont presque verticales, de sorte que le point où elles coupent l'axe se trouve presque trois fois plus loin que votre point de départ.
Observez les deux colonnes l'une à côté de l'autre dans le tableau : f(x) grandit tandis que f′(x) rétrécit vers 0,001. Le pas étant leur rapport, il grandit d'autant plus.
Le second échec est pire, car il ressemble à un succès
La divergence a au moins le mérite de s'annoncer. Voici l'échec qui ne prévient pas.
Prenons f(x) = x³ − x, dont les racines sont −1, 0 et +1. Partons de 0,57. La méthode converge proprement, treize itérations, résidu de 2,3 × 10⁻¹¹ — et la racine qu'elle renvoie est −1.
Regardez où se situe 0,57. Il est à 0,43 de +1 et à 1,57 de −1. Il n'est également qu'à 0,57 de la racine située en zéro. La méthode de Newton renvoie celle qui est la plus éloignée, après être passée directement au-dessus de deux racines plus proches, et affiche un succès total avec onze décimales correctes.
Maintenant, partez plutôt de 0,58. Quinze itérations, et la réponse est +1.
Un centième de changement dans l'estimation initiale, et le solveur atterrit à l'autre extrémité de la fonction. Entre ces deux points de départ se trouve 1/√3 ≈ 0,5774, où la dérivée de x³ − x est nulle. La tangente y est horizontale et coupe l'axe bien plus loin ; approchez ce point d'un côté ou de l'autre et la première étape est énorme, dans des directions opposées. Chaque zone plate sur une courbe est un tremplin, et la région dans laquelle elle vous projette n'a rien à voir avec la proximité.
C'est cette propriété qui fait de « quelle racine vais-je obtenir ? » une question sans réponse de manière générale. Pour les polynômes sur les nombres complexes, les ensembles de points de départ menant à chaque racine sont appelés bassins d'attraction, et leurs frontières sont fractales : arbitrairement près d'un point qui converge vers une racine se trouve un point qui converge vers une autre. Hubbard, Schleicher et Sutherland ont montré en 2001 que l'on peut néanmoins construire un ensemble fini de points de départ garantissant de trouver chaque racine d'un polynôme donné — un résultat remarquable, et une mesure de la somme de travail que la formule « utilisez simplement la méthode de Newton » dissimule discrètement.
Ce que cela change dans son utilisation
Trois conséquences pratiques en découlent, et toutes trois sont visibles sur la page.
Premièrement, un faible résidu n'est pas un certificat de garantie. Dans l'exécution diverge ci-dessus, le résidu est de 17,37 et augmente, ce cas est donc repéré. Mais dans l'exécution avec 0,57, le résidu est de 2 × 10⁻¹¹ et la réponse est une très bonne racine — seulement pas celle que la personne posant la question souhaitait. Les tests de convergence peuvent vous indiquer que vous avez trouvé une solution. Rien dans la méthode ne peut vous indiquer qu'il s'agit de la solution.
Deuxièmement, les limites du nombre d'itérations sont cruciales. L'explorateur s'arrête à vingt par défaut, ce qui est la seule raison pour laquelle l'exécution divergente a une fin plutôt qu'un dépassement de capacité. Les solveurs utilisés en production font la même chose, et ce nombre n'est pas arbitraire : une itération de Newton saine sur une fonction bien élevée atteint la précision machine en cinq à dix étapes ; ainsi, tout calcul tournant encore à vingt itérations ne converge pas lentement, il ne converge pas du tout.
Troisièmement, le remède à un mauvais départ n'est généralement pas un meilleur algorithme, mais un encadrement. La dichotomie ne peut pas diverger — si la fonction change de signe sur un intervalle, la règle du point milieu ne peut pas en sortir — et elle ne peut pas choisir la mauvaise racine, car il n'y en a qu'une seule à l'intérieur de l'encadrement. Elle est simplement lente, gagnant un bit par étape plutôt que de doubler le nombre de chiffres. La plupart des solveurs réels utilisent donc une approche hybride : appliquer la dichotomie jusqu'à ce que l'estimation soit prouvée comme proche, puis laisser Newton terminer en trois étapes. Vous obtenez la vitesse là où les hypothèses se vérifient et la garantie là où elles ne se vérifient pas.
Il y a une note de bas de page concernant le nom. La méthode propre de Newton, datant d'environ 1669, n'utilisait pas de dérivées et était écrite pour les polynômes sous forme d'une suite de substitutions ; Raphson l'a simplifiée en 1690 ; la forme enseignée aujourd'hui, avec f′ et une fonction dérivable f quelconque, est celle de Simpson datant de 1740. Ypma a retracé toute cette filiation en 1995. L'algorithme qui échoue de manière si instructive sur la racine cubique est une simplification du XIXe siècle d'une recette du XVIIe siècle, et il fait partie de toute boîte à outils numérique depuis lors — d'où l'intérêt de savoir précisément où il flanche.