Cet article est une traduction automatique ; la version originale en anglais fait foi. Lire l'original
La méthode de Newton peut doubler son erreur à chaque étape, alors que la solution n'était qu'à 0,01
Partez à 0,01 de la solution. Vingt étapes plus tard, vous êtes à −5242,88, et chaque étape a été calculée correctement.
Résolvez x³ − x − 2 = 0. Il n'existe aucune formule simple qui vaille la peine d'être retenue ; faites donc ce que fait tout logiciel de calcul numérique : partez d'une estimation, puis laissez la méthode de Newton la corriger.
Commencez à 1,5. Trois itérations plus tard, vous obtenez 1,52138, et la fonction évaluée en ce point vaut 5,89387 × 10⁻⁷, à moins d'un millionième de zéro. Trois étapes. Chaque étape double approximativement le nombre de chiffres exacts, et c'est pourquoi cette méthode se trouve à l'intérieur de votre calculatrice, de votre logiciel de CAO et du solveur de votre tableur.
Demandez-lui maintenant quelque chose de plus simple. Résolvez ∛x = 0.
Vous connaissez la solution. 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 −5242,88. Le résidu, qui avait commencé à 0,215, est à présent de 17,37. La méthode n'a ni calé ni erré ; elle s'est éloignée de la solution selon un fil de raisonnement parfaitement rectiligne, doublant l'erreur et inversant le signe à chaque étape sans exception.
Rien ne s'est mal passé
La tentation est de chercher un bogue. Il n'y en a pas, et le calcul vaut la peine d'être fait tant il est court.
L'itération 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 l'estimation suivante est x − 3x = −2x. Non pas de manière approchée : exactement. Chaque itération multiplie l'estimation par −2, quel que soit le point de départ, indéfiniment. C'est de là que provient −5242,88 : il s'agit de 0,01 × (−2)19, et vous pouvez lire toute la suite géométrique dans le tableau des itérations de Newton's Method Explorer sous son préréglage diverge.
Ce qu'a fait la racine cubique, c'est mettre en défaut l'hypothèse sur laquelle repose la méthode. La méthode de Newton remplace la courbe par sa tangente et saute au point où cette droite coupe l'axe des abscisses. Au voisinage d'une racine, c'est une excellente approximation : il s'agit du premier terme du développement de Taylor, et les termes négligés décroissent de manière quadratique, ce qui explique précisément pourquoi le nombre de chiffres exacts double. Mais ∛x possède une tangente verticale en zéro. Sa dérivée n'y devient pas seulement petite, elle devient infinie, et la courbe n'est localement rectiligne à aucun grossissement. Près de zéro, les tangentes pointent presque à la verticale, et l'intersection avec l'axe tombe toujours en −2x : deux fois plus loin de la racine que le point de départ, de l'autre côté.
Observez les deux colonnes côte à côte dans le tableau : f(x) croît tandis que f′(x) décroît vers 0,001. Le pas étant leur rapport, il augmente doublement.
Le second échec est pire, car il ressemble à un succès
La divergence, au moins, s'annonce d'elle-même.
Prenons f(x) = x³ − x, dont les racines sont −1, 0 et +1. Commençons à 0,57. La méthode converge proprement, en treize itérations, avec un 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 en zéro. La méthode de Newton renvoie celle qui est la plus éloignée, après être passée directement devant deux racines plus proches, et affiche une réussite totale avec onze décimales exactes.
Partez plutôt de 0,58. Quinze itérations, et la solution est +1.
Un simple écart d'un centième sur 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 loin de là ; approchez-vous de ce point d'un côté ou de l'autre, et la première étape est gigantesque, dans des directions opposées. Chaque méplat sur une courbe est une rampe de lancement, et la région dans laquelle il vous propulse n'a aucun rapport avec la proximité.
C'est cette propriété qui fait de « quelle racine vais-je obtenir ? » une question généralement sans réponse. Pour les polynômes sur les nombres complexes, les ensembles de points de départ conduisant à chaque racine sont appelés bassins d'attraction, et leurs frontières sont fractales : arbitrairement près d'un point convergeant 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, qui donne la mesure de tout le travail que dissimule discrètement l'injonction « il suffit d'utiliser la méthode de Newton ».
Ce que cela change à son utilisation
Trois conséquences pratiques en découlent, et les deux premières sont visibles sur cette page.
Premièrement, un faible résidu n'est pas un certificat. Dans l'exécution diverge ci-dessus, le résidu vaut 17,37 et augmente, ce cas est donc détecté. Mais dans l'essai partant de 0,57, le résidu est de 2 × 10⁻¹¹ et le résultat est une racine parfaitement valable, simplement pas celle que quiconque 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 affirmer qu'il s'agit de la solution.
Deuxièmement, le plafonnement des itérations est un élément porteur. L'explorateur s'arrête par défaut à vingt, ce qui est la seule raison pour laquelle le calcul divergent se termine au lieu de déborder. Les solveurs en production font de même, et ce nombre n'est pas arbitraire : une itération de Newton saine sur une fonction régulière atteint la précision machine en cinq à dix étapes ; ainsi, tout calcul qui tourne encore à vingt étapes n'est pas en train de converger lentement, il ne converge pas.
Troisièmement, le remède à un mauvais point de 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 méthode du point médian ne peut pas le quitter — et elle ne peut pas choisir la mauvaise racine, car il n'y en a qu'une seule dans l'encadrement. Elle est simplement lente, ne gagnant qu'un bit par étape au lieu de doubler le nombre de chiffres. La plupart des solveurs réels utilisent donc une méthode hybride : procéder par dichotomie jusqu'à ce que l'estimation soit de façon démontrable assez proche, puis laisser Newton terminer en trois étapes. On obtient ainsi la rapidité là où les hypothèses sont vérifiées, et la garantie là où elles ne le sont pas.
Il existe une note historique concernant ce nom. La méthode propre à Newton, qui remonte aux alentours de 1669, n'utilisait pas de dérivées et s'écrivait pour les polynômes sous la forme d'une suite de substitutions ; Raphson l'a simplifiée en 1690 ; la forme enseignée aujourd'hui, avec f′ et une fonction différentiable quelconque f, est due à Simpson en 1740. Ypma en a retracé toute la filiation en 1995. Ce qui échoue de manière si instructive sur la racine cubique est une remise en ordre au dix-huitième siècle d'une recette du dix-septième siècle, présente depuis dans toutes les boîtes à outils numériques — une excellente raison de savoir précisément où elle se brise.