Méthode de Newton

On va donc chercher à construire une bonne approximation d'un zéro de la fonction d'une variable réelle f(x) en considérant son développement de Taylor au premier ordre. Pour cela, partant d'un point x₀ que l'on choisit de préférence proche du zéro à trouver (en faisant des estimations grossières par exemple), on approche la fonction au premier ordre, autrement dit, on la considère asymptotiquement égale à sa tangente en ce point :

Partant de là, pour trouver un zéro de cette fonction d'approximation, il suffit de calculer l'intersection de la droite tangente avec l'axe des abscisses, c'est-à-dire résoudre l'équation affine :

On obtient alors un point x₁ qui en général a de bonnes chances d'être plus proche du vrai zéro de f que le point x₀ précédent. Par cette opération, on peut donc espérer améliorer l'approximation par itérations successives (voir illustration) : on approche à nouveau la fonction par sa tangente en ${\displaystyle x_{1}}$ pour obtenir un nouveau point x₂, etc.

Illustration de la méthode de Newton.

Illustration animée de la méthode.

Cette méthode requiert que la fonction possède une tangente en chacun des points de la suite que l'on construit par itération, par exemple il suffit que f soit dérivable.

Formellement, on part d'un point x₀ appartenant à l'ensemble de définition de la fonction et on construit par récurrence la suite :

où f ' désigne la dérivée de la fonction f. Le point x_k+1 est bien la solution de l'équation affine ${\displaystyle f(x_{k})+f'(x_{k})(x-x_{k})=0}$.

Il se peut que la récurrence doive se terminer, si à l'étape k, x_k n'appartient pas au domaine de définition ou si la dérivée f '(x_k) est nulle ; dans ces cas, la méthode échoue.

Si le zéro inconnu α est isolé, alors il existe un voisinage de α tel que pour toutes les valeurs de départ x₀ dans ce voisinage, la suite (x_k) va converger vers α. De plus, si f '(α) est non nul, alors la convergence est (au moins) quadratique, ce qui signifie intuitivement que le nombre de chiffres corrects est approximativement doublé à chaque étape.

Bien que la méthode soit très efficace, certains aspects pratiques doivent être pris en compte. Avant tout, la méthode de Newton nécessite que la dérivée soit effectivement calculée. Dans les cas où la dérivée est seulement estimée en prenant la pente entre deux points de la fonction, la méthode prend le nom de méthode de la sécante, moins efficace (d'ordre 1,618 qui est le nombre d'or) et inférieure à d'autres algorithmes. Par ailleurs, si la valeur de départ est trop éloignée du vrai zéro, la méthode de Newton peut entrer en boucle infinie sans produire d'approximation améliorée. À cause de cela, toute mise en œuvre de la méthode de Newton doit inclure un code de contrôle du nombre d'itérations.

Pour illustrer la méthode, recherchons le nombre positif x vérifiant cos(x) = x³. Reformulons la question pour introduire une fonction devant s'annuler : on recherche le zéro positif (la racine) de f(x) = cos(x) – x³. La dérivation donne f '(x) = –sin(x) – 3x².

Comme ${\displaystyle \cos(x)\leqslant 1}$ pour tout x et x³>1 pour x>1, nous savons que notre zéro se situe entre 0 et 1. Nous essayons une valeur de départ de x₀ = 0,5.

${\displaystyle {\begin{matrix}x_{1}&=&x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}&=&0,5-{\frac {\cos(0,5)-0,5^{3}}{-\sin(0,5)-3\times 0,5^{2}}}&\simeq &1,112\,141\,637\,1\\x_{2}&=&x_{1}-{\frac {f(x_{1})}{f'(x_{1})}}&&\vdots &\simeq &0,909\,672\,693\,736\\x_{3}&&\vdots &&\vdots &\simeq &0,866\,263\,818\,209\\x_{4}&&\vdots &&\vdots &\simeq &0,865\,477\,135\,298\\x_{5}&&\vdots &&\vdots &\simeq &0,865\,474\,033\,111\\x_{6}&&\vdots &&\vdots &\simeq &0,865\,474\,033\,101\\x_{7}&&\vdots &&\vdots &\simeq &0,865\,474\,033\,102\end{matrix}}}$

Les 7 premiers chiffres de cette valeur coïncident avec les 7 premiers chiffres du vrai zéro.

La vitesse de convergence d'une suite x_n obtenue par la méthode de Newton peut être obtenue comme application de la formule de Taylor-Lagrange. Il s'agit d'évaluer une majoration de log|x_n – a|.

f est une fonction définie au voisinage de a et deux fois continûment différentiable. On suppose que a se trouve être un zéro de f qu'on essaie d'approcher par la méthode de Newton. On fait l'hypothèse que a est un zéro d'ordre 1, autrement dit que f '(a) est non nul. La formule de Taylor-Lagrange s'écrit :

${\displaystyle 0=f(a)=f(x)+f'(x)(a-x)+{\frac {f''(\xi )}{2}}{(a-x)^{2}}}$, avec ξ entre x et a.

Partant de l'approximation x, la méthode de Newton fournit au bout d'une itération :

${\displaystyle N_{f}(x)-a=x-{\frac {f(x)}{f'(x)}}-a={\frac {f''(\xi )}{2\,f'(x)}}(x-a)^{2}}$.

Pour un intervalle compact I contenant x et a et inclus dans le domaine de définition de f, on pose : m₁ = min_{x ∈ I} |f '(x) | ainsi que M₂ = max_{x ∈ I} |f ''(x) |. Alors, pour tout x ∈ I :

${\displaystyle \left|N_{f}(x)-a\right|\leqslant {\frac {M_{2}}{2m_{1}}}|x-a|^{2}}$.

Par récurrence immédiate, il vient :

${\displaystyle K\left|x_{n}-a\right|\leqslant (K|x_{0}-a|)^{2^{n}}}$

où K = M₂/2m₁. En passant au logarithme :

${\displaystyle \log \left|x_{n}-a\right|\leqslant 2^{n}\log(K|x_{0}-a|)-\log(K)}$

La convergence de x_n vers a est donc quadratique, à condition que |x₀ – a| < 1/K.

Les tangentes à la courbe représentant la fonction ${\displaystyle x\mapsto x^{3}-2x+2}$ en 0 et en 1 coupent l'axe des x en 1 et en 0 respectivement. Si l'on prend 0 ou 1 comme point de départ, la méthode oscille entre ces deux points et ne converge donc pas.

• La tangente à la courbe peut couper l'axe des abscisses hors du domaine de définition de la fonction.

• Si l'on utilise l'algorithme de Newton pour trouver l'unique zéro x_* = 0 de la fonction ${\displaystyle x\in \mathbb {R} \mapsto |x|^{1/2}}$ en prenant un itéré initial x₀ ≠ 0, on constate que, pour tout ${\displaystyle k\in \mathbb {N} }$, x_k+1=–x_k ; la suite générée ne converge donc pas, même localement (c'est-à-dire même si x₀ est pris proche du zéro x_* = 0). Le problème provient ici, en particulier, de la non-différentiabilité de la fonction en l'unique zéro x_* = 0.

Des critères d'arrêt possibles, déterminés relativement à une grandeur numériquement négligeable, sont :

${\displaystyle \|f(x_{k})\|<\varepsilon _{1}\qquad \mathrm {ou} \qquad \|x_{k+1}-x_{k}\|<\varepsilon _{2}}$

où ${\displaystyle \varepsilon _{1},\varepsilon _{2}\in \mathbb {R} ^{+}}$ représentent des erreurs d'approximations caractérisant la qualité de la solution numérique.

Dans tous les cas, il se peut que le critère d'arrêt soit vérifié en des points ne correspondant pas à des solutions de l'équation à résoudre.

Un cas particulier de la méthode de Newton est la méthode de Héron, aussi appelée méthode babylonienne : il s'agit, pour calculer la racine carrée de a, d'appliquer la méthode de Newton à la fonction f définie par

${\displaystyle f(x)=x^{2}-a}$.

On obtient alors, en utilisant la formule de la dérivée f '(x) = 2x, une méthode d'approximation de la solution √a donnée par la formule itérative suivante :

${\displaystyle x_{k+1}:=x_{k}-{\frac {x_{k}^{2}-a}{2x_{k}}}={\frac {1}{2}}\left(x_{k}+{\frac {a}{x_{k}}}\right)}$.

Pour tout a ≥ 0 et tout point de départ x₀ > 0, cette méthode converge vers √a.

On peut l'étendre au calcul de toute racine n-ième d'un nombre a avec la formule :

${\displaystyle x_{k+1}:=x_{k}-{\frac {x_{k}^{n}-a}{nx_{k}^{n-1}}}={\frac {1}{n}}\left({(n-1)x_{k}+{\frac {a}{x_{k}^{n-1}}}}\right)}$.

On peut déterminer une intersection des graphes de deux fonctions réelles dérivables f et g, c'est-à-dire un point x tel que f(x) = g(x), en appliquant la méthode de Newton à la fonction f–g.

On peut aussi utiliser la méthode de Newton pour résoudre un système de n équations (non linéaires) à n inconnues x = (x₁,...,x_n), ce qui revient à trouver un zéro d'une fonction F de ${\displaystyle \mathbb {R} ^{n}}$ dans ${\displaystyle \mathbb {R} ^{n}}$, qui devra être différentiable. Dans la formulation donnée ci-dessus, il faut multiplier par l'inverse de la matrice jacobienne F '(x_k) au lieu de diviser par f '(x_k). Évidemment, pour économiser du temps de calcul, on ne calculera pas l'inverse de la jacobienne, mais on résoudra le système d'équations linéaires suivant

en l'inconnue x_k+1 – x_k. Encore une fois, cette méthode ne fonctionne que pour une valeur initiale x₀ suffisamment proche d'un zéro de F.

Il arrive parfois que la dérivée (ou la matrice jacobienne pour un système d'équations à plusieurs variables) de la fonction f soit coûteuse à calculer. La dérivée peut alors être approchée au moyen de différences finies. Par exemple, en approchant la dérivée f '(x_k) par

${\displaystyle {\frac {f(x_{k})-f(x_{k-1})}{x_{k}-x_{k-1}}},}$

on obtient la méthode de la sécante. La convergence de cette méthode n'est plus quadratique, mais reste sur-linéaire (en fait, d'ordre φ = 1 + √5/2 ≈ 1,618).

Lorsque la fonction dont on cherche une racine est non-différentiable, mais seulement semi-lisse, la méthode de Newton ne génère pas nécessairement une suite {x_k} convergente, même si les itérés sont des points de différentiabilité de f, arbitrairement proches d'un zéro de F. Un contre-exemple est donné par Kummer (1988[8]).

Un algorithme analogue est encore possible en supposant un peu plus que la lipschitzianité de F, mais sa semi-lissité. L'algorithme de Newton pour une fonction f semi-lisse consiste alors à générer une suite ${\displaystyle \{x_{k}\}\subset \mathbb {E} }$, où le nouvel itéré x_k+1 est calculé à partir de l'itéré courant x_k par la récurrence suivante

${\displaystyle x_{k+1}:=x_{k}-J_{k}^{-1}f(x_{k}),}$

où J_k est une jacobienne inversible du différentiel de Clarke ∂_CF(x_k), qui est supposée exister.

Comme la méthode de Newton classique, l'algorithme de Newton semi-lisse converge sous deux conditions. La première spécifie que la fonction dont on cherche un zéro x_* est suffisamment lisse : elle doit être semi-lisse. Il faut aussi qu'en ce zéro la fonction ait ses « pentes » qui ne s'annulent pas en x_* ; ceci s'exprime par l'hypothèse de C-régularité du zéro. Il s'agit aussi d'un résultat de convergence locale, ce qui veut dire qu'il faut que le premier itéré soit choisi suffisamment près d'un zéro satisfaisant les conditions ci-dessus pour que la convergence ait lieu.

Un état de l'art est donné par Izmailov et Solodov[9].

Dans certains cas, il arrive que l'on veuille éviter la condition de proximité entre notre valeur de départ et le zéro de la fonction. Une solution est alors d'utiliser la méthode de Newton par intervalles[10]^,[11].

On considère ${\displaystyle f\in {\mathcal {C}}^{1}(X)}$, avec X un intervalle réel, et on suppose que l'on a une extension par intervalles F' de f ', c'est-à-dire une fonction F ' prenant en entrée un intervalle Y ⊆ X et renvoyant un intervalle F'(Y) tel que :

${\displaystyle {\begin{aligned}F'([y,y])&=\{f'(y)\}\\F'(Y)&\supseteq \{f'(y)~|~y\in Y\}\end{aligned}}}$.

On suppose également que ${\displaystyle 0\notin F'(X)}$, donc en particulier f a au plus un zéro sur X. On peut maintenant définir l'opérateur :

${\displaystyle N(Y)=m+{\frac {f(m)}{F'(Y)}}=\left\{\left.m+{\frac {f(m)}{z}}~\right|~z\in F'(Y)\right\}}$

pour tout intervalle y de centre m. On notera que l'hypothèse sur F' implique que N(Y) est bien défini et est un intervalle (voir arithmétique d'intervalles pour plus de détails là dessus). On peut maintenant créer la suite d'intervalles suivante :

${\displaystyle {\begin{aligned}X_{0}&=X\\X_{k+1}&=N(X_{k})\cap X_{k}\end{aligned}}}$.

Le théorème des accroissements finis certifie que, s'il y a un zéro de f dans X_k, alors il est encore dans X_k+1. De plus, l'hypothèse de positivité sur F' implique que la taille de X_k+1 est au plus la moitié de celle de X_k, donc la séquence converge vers le singleton {x^*} , où x^* est le zéro de f sur X.

• Algorithme de Josephy-Newton pour résoudre une inclusion fonctionnelle
• Algorithme de Newton semi-lisse
• Algorithme de Newton-min en complémentarité linéaire
• Algorithme du gradient
• Dynamique holomorphe
• Lemme de Hensel
• Méthode de la fausse position (ou méthode regula falsi)
• Méthode de la sécante
• Méthode de Müller
• Méthode de quasi-Newton
• Optimisation quadratique successive, qui est un algorithme newtonien pour résoudre des problèmes d'optimisation sous contrainte
• Vitesse de convergence des suites
• Algorithme de Jaumain

• J. Ch. Gilbert, Éléments d'Optimisation Différentiable — Théorie et Algorithmes, syllabus de cours à l'ENSTA ParisTech, Paris.
• N. Soualem (2006). Méthode de Newton sur math-linux.com.

• (en) D. P. Bertsekas (1995), Nonlinear Programming. Athena Scientific. (ISBN 978-1-886529-14-4).
• (en) J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, C. Sagastizábal (2006), Numerical Optimization - Theoretical and Practical Aspects [détail des éditions].
• J.-L. Chabert, É. Barbin, M. Guillemot, A. Michel-Pajus, J. Borowczyk, A. Djebbar, J.-C. Martzloff (1994). Histoire d’Algorithmes – Du Caillou à la Puce. Regards sur la Science. Belin, Paris.
• J.-P. Dedieu (2006). Points Fixes, Zéros et la Méthode de Newton. Mathématiques et Applications 54. Springer Verlag, Berlin.
• (en) P. Deuflhard (2004). Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms. Springer Series in Computational Mathematics, Vol. 35. Springer, Berlin, (ISBN 3-540-21099-7).
• (en) A. F. Izmailov, M. V. Solodov (2014). Newton-Type Methods for Optimization and Variational Problems. Springer Series in Operations Research and Financial Engineering. Springer.
• (en) J. Nocedal, S. J. Wright (2006), Numerical Optimization, Springer. (ISBN 978-0-387-30303-1).
• (en) J. M. Ortega, W. C. Rheinboldt (2000). Iterative Solution of Nonlinear Equations in Several Variables. Classics in Applied Mathematics. Society for Industrial and Applied Mathematics. (ISBN 0-89871-461-3).
• (en) T. Simpson (1740). Essays on Several Curious and Useful Subjects in Speculative and Mix'd Mathematicks, Illustrated by a Variety of Examples. Londres.
• (en) D. T. Whiteside, éditeur (1967-1976) The Mathematical Papers of Isaac Newton, Volumes I-VII, Cambridge University Press, Cambridge.
• (en) T. J. Ypma (1995). Historical development of the Newton-Raphson method. SIAM Review, 37, 531–551.

• Portail de l'analyse