Voir la source de Méthode de Newton

{{Infobox Méthode scientifique
| image = Newton iteration.png
| légende = Une itération de la méthode de Newton.
}}En [[analyse numérique]], la '''méthode de Newton''' ou '''méthode de Newton-Raphson'''<ref>Joseph Louis Lagrange et Louis Poinsot, [https://books.google.com/books?id=6jHrhC7CuW4C&pg=PA124&dq=Joseph+Raphson&lr=lang_fr&as_brr=1&hl=fr ''Traité de la résolution des équations numériques de tous les degrés''].</ref> est, dans son application la plus simple, un [[Algorithmique|algorithme]] efficace pour trouver numériquement une [[approximation]] précise d'un [[Zéro d'une fonction|zéro]] (ou racine) d'une [[fonction réelle d'une variable réelle]]. Cette méthode doit son nom aux mathématiciens anglais [[Isaac Newton]] (1643-1727) et [[Joseph Raphson]] (peut-être 1648-1715), qui furent les premiers à la décrire pour la [[algorithme de recherche d'un zéro d'une fonction|recherche des solutions d'une équation polynomiale]]. [[Thomas Simpson]] (1710-1761) élargit considérablement le domaine d'application de l'algorithme en montrant, grâce à la notion de dérivée, comment on pouvait l'utiliser pour calculer une solution d'une [[équation]] [[non linéaire]], pouvant ne pas être un polynôme, et d'un système formé de telles équations.

== Présentation ==
Sous sa forme moderne, l'algorithme peut être présenté brièvement comme suit : à chaque itération, la fonction dont on cherche un zéro est linéarisée en l'itéré (ou point) courant et l'itéré suivant est pris égal au zéro de la fonction linéarisée. Cette description sommaire indique qu'au moins deux conditions sont requises pour la bonne marche de l'algorithme : la fonction doit être dérivable aux points visités (pour pouvoir y linéariser la fonction) et les dérivées ne doivent pas s'y annuler (pour que la fonction linéarisée ait un zéro) ; s'ajoute à ces conditions la contrainte forte de devoir prendre le premier itéré ''assez proche'' d'un zéro ''régulier'' de la fonction (i.e., en lequel la dérivée de la fonction ne s'annule pas), pour que la convergence du processus soit assurée.

L'intérêt principal de l'algorithme de Newton est sa [[Vitesse de convergence des suites#Convergence q-quadratique|convergence quadratique]] locale. En termes imagés mais peu précis, cela signifie que le nombre de [[Chiffre significatif|chiffres significatifs]] corrects des itérés double à chaque itération, ''asymptotiquement''. Comme le nombre de chiffres significatifs représentables par un ordinateur est d’environ 15 [[système décimal|chiffres décimaux]] (sur un ordinateur qui respecte la norme [[IEEE_754|IEEE-754]]), on peut simplifier grossièrement les propriétés de convergence de l'algorithme de Newton en disant que, soit il converge en moins de 10 itérations, soit il diverge. En effet, si l'itéré initial n'est pas pris suffisamment proche d'un zéro, la suite des itérés générée par l'algorithme a un comportement erratique, dont la convergence éventuelle ne peut être que le fruit du hasard (un des itérés est ''par chance'' proche d'un zéro).

L'importance de l'algorithme a incité les numériciens à étendre son application et à proposer des remèdes à ses défauts. Par exemple, l'algorithme permet également de trouver un zéro d'une [[fonction de plusieurs variables]] à valeurs vectorielles, voire définie entre [[espace vectoriel|espaces vectoriels]] de dimension infinie ; la méthode conduit d'ailleurs à des résultats d'existence de zéro (utilisés dans certaines preuves du [[théorème des fonctions implicites]], les théorèmes de [[Leonid Kantorovitch|Kantorovitch]]). On peut aussi l'utiliser lorsque la fonction est différentiable dans un sens plus faible (fonction différentiable par morceaux, [[Fonction B-différentiable|B-différentiable]], [[Fonction semi-lisse|semi-lisse]], obliquement différentiable, ''etc''), ainsi que pour résoudre des systèmes d'inégalité non linéaire, des problèmes d'[[inclusion fonctionnelle]], d'équations différentielles ou aux dérivées partielles, d’[[inéquation variationnelle|inéquations variationnelles]], de [[complémentarité]], ''etc''. On a également mis au point des ''techniques de globalisation'' de l'algorithme, lesquelles ont pour but de forcer la convergence des suites générées à partir d'un itéré initial arbitraire (non nécessairement proche d'un zéro), comme la [[algorithme à directions de descente|recherche linéaire]] et les [[algorithme à régions de confiance|régions de confiance]] agissant sur une fonction de mérite (souvent la fonction de moindres-carrés). Dans les versions dites ''inexactes'' ou ''tronquées'', on ne résout le système linéaire à chaque itération que de manière approchée. Enfin, la famille des [[Méthode de Quasi-Newton|algorithmes de quasi-Newton]] propose des techniques permettant de se passer du calcul de la dérivée de la fonction. Toutes ces améliorations ne permettent toutefois pas d'assurer que l'algorithme trouvera un zéro existant, quel que soit l'itéré initial.

Appliqué à la dérivée d'une fonction réelle, cet algorithme permet d'obtenir des [[point critique (mathématiques)|points critiques]] (i.e., des zéros de la fonction dérivée). Cette observation est à l'origine de son utilisation en [[Optimisation (mathématiques)|optimisation]] sans ou avec contraintes.

== Éléments d'histoire ==

[[Image:John Wallis by Sir Godfrey Kneller, Bt.jpg|thumb|left|John Wallis.]]
[[Fichier:Isaac Newton, English School, 1715-20.jpg|vignette|Isaac Newton.]]
La méthode de Newton fut décrite par le mathématicien anglais [[Isaac Newton]] dans ''De analysi per aequationes numero terminorum infinitas'', écrit en [[1669 en science|1669]] et publié en [[1711 en science|1711]] par [[William Jones (mathématicien)|William Jones]]. Elle fut à nouveau décrite dans ''{{lang|la|De metodis fluxionum et serierum infinitarum}}'' (''De la méthode des [[Fluxion (analyse)|fluxions]] et des suites infinies''), écrit en [[1671 en science|1671]], traduit et publié sous le titre ''Methods of Fluxions'' en [[1736 en science|1736]] par [[John Colson]]. Toutefois, Newton n'appliqua la méthode qu'aux seuls polynômes. Comme la notion de dérivée et donc de linéarisation n'était pas définie à cette époque, son approche diffère de celle décrite dans l'introduction : Newton cherchait à affiner une approximation grossière d'un zéro d'un polynôme par un calcul polynomial.

L'exemple que Newton donne<ref>Dans ''Methodus fluxionum et serierum infinitorum'' selon J.-L. Chabert et al. (1994). Ypma (1995) renvoie aux pages 219-220 du volume II chez Whiteside (1967-1976).</ref> est celui du calcul de la racine réelle de l'[[équation cubique]]
<center>
<math>
x^3-2x-5=0
</math>,
</center>
en prenant comme itéré initial le point {{math|''x''{{ind|1}} {{=}} 2}}. qui diffère de moins de {{math|0,1}} de la vraie valeur de l'unique racine réelle. Il écrit alors {{math|''x'' {{=}} 2 + ''d''{{ind|1}}}}, où {{math|''d''{{ind|1}}}} est donc l'accroissement à donner à {{math|2}} pour obtenir la racine {{mvar|x}}. Il remplace {{mvar|x}} par {{math|2 + ''d''{{ind|1}}}} dans l'équation, qui devient
<center>
<math>
d_1^3+6\,d_1^2+10\,d_1-1=0
</math>
</center>
et dont il faut trouver la racine pour l'ajouter à {{math|2}}. Il néglige {{math|''d''{{ind|1}}{{3}} + 6''d''{{ind|1}}{{2}}}} à cause de sa petitesse (on suppose que {{math|{{!}}''d''{{ind|1}}{{!}} << 1}}), si bien qu'il reste {{math|10 ''d''{{ind|1}} – 1 {{=}} 0}} ou {{math|''d''{{ind|1}} {{=}} 0,1}}, ce qui donne comme nouvelle approximation de la racine {{math|''x''{{ind|2}} {{=}} ''x''{{ind|1}} + ''d''{{ind|1}} {{=}} 2,1}}. Il écrit ensuite {{math|''d''{{ind|1}} {{=}} 0,1 + ''d''{{ind|2}}}}, où {{math|''d''{{ind|2}}}} est donc l'accroissement à donner à {{math|''d''{{ind|1}}}} pour obtenir la racine du polynôme précédent. Il remplace donc {{math|''d''{{ind|1}}}} par {{math|0,1 + ''d''{{ind|2}}}} dans le polynôme précédent pour obtenir
<center>
<math>
d_2^3+6{,}3\,d_2^2+11{,}23\,d_2+0{,}061=0
</math>.
</center>
On obtiendrait la même équation en remplaçant {{mvar|x}} par {{math|2,1 + ''d''{{ind|2}}}} dans le polynôme initial. Négligeant les deux premiers termes, il reste {{math|11,23 ''d''{{ind|2}}+ 0,061 {{=}} 0}} ou {{math|''d''{{ind|2}} ≈ –0,0054}}, ce qui donne comme nouvelle approximation de la racine {{math|''x''{{ind|3}} {{=}} ''x''{{ind|2}} + ''d''{{ind|2}} ≈ 2,0946}}. On peut poursuivre les opérations aussi longtemps qu'il convient.
<!--
Par exemple, 2 est un zéro exact de {{math|''X''{{3}} – 2''X''{{2}} – 3''X'' + 6}} et donc peut être pris comme un zéro approximatif de {{math|''P''(''X'') {{=}} ''X''{{3}} – 2''X''{{2}} – 3''X'' + 7}}. Une petite perturbation doit s'écrire {{formule|2 + ''Y''}}. Or, {{math|''P''(2+''Y'') {{=}} 1 – 7''Y'' + 2''Y''{{2}} +''Y''{{3}} ≈ 1 – 7''Y''}} en négligeant les termes d'ordre au moins 2. L'annulation de {{formule|''P''}} par {{formule|2+''Y''}} impose {{formule|''Y''={{fraction|1|7}}}}.
-->

Cette méthode fut l'objet de publications antérieures. En [[1685 en science|1685]], [[John Wallis]] en publia une première description<ref>{{MathWorld|nom_url=WallissConstant|titre=Wallis's Constant}}.</ref> dans ''A Treatise of Algebra both Historical and Practical''. En [[1690 en science|1690]], [[Joseph Raphson]] en publia une description simplifiée dans ''Analysis aequationum universalis''. Raphson considérait la méthode de Newton toujours comme une méthode purement algébrique et restreignait aussi son usage aux seuls polynômes. Toutefois, il mit en évidence le calcul récursif des approximations successives d'un zéro d'un polynôme au lieu de considérer comme Newton une [[suite de polynômes]].

C'est [[Thomas Simpson]] ([[1710 en science|1710]]-[[1761 en science|1761]]) qui généralisa cette méthode au calcul itératif des solutions d'une équation non linéaire, en utilisant les dérivées (qu'il appelait [[Fluxion (analyse)|fluxions]], comme Newton)<ref>Voir Simpson (1740), pages 83-84, selon Ypma (1995).</ref>. Simpson appliqua la méthode de Newton à des systèmes de deux équations non linéaires à deux inconnues<ref>Voir Simpson (1740), page 82, selon Ypma (1995).</ref>, en suivant l'approche utilisée aujourd'hui pour des systèmes ayant plus de 2 équations, et à des problèmes d'optimisation sans contrainte en cherchant un zéro du gradient<ref>{{en}} T. Simpson (1737), ''A New Treatise of Fluxions''.</ref>. [[Arthur Cayley]] fut le premier à noter la difficulté de généraliser la méthode de Newton aux variables complexes en [[1879 en science|1879]]<ref>{{en}} Arthur Cayley (1789). ''The Newton-Fourier imaginary problem''.</ref>, par exemple aux polynômes de degré supérieur à 3.

On pourra consulter l'article de Ypma (1995) pour d'autres informations sur l'historique de l'algorithme. Cet auteur attribue l'absence de reconnaissance aux autres contributeurs de l'algorithme au livre influent de Fourier, intitulé ''Analyse des Équations Déterminées'' (1831), lequel décrivait ''la méthode newtonienne'' sans faire référence à Raphson ou Simpson.

== Fonction réelle d'une variable réelle ==

=== L'algorithme ===

On va donc chercher à construire une bonne approximation d'un zéro de la fonction d'une variable réelle {{formule|''f''(''x'')}} en considérant son [[Théorème de Taylor|développement de Taylor]] au premier ordre. Pour cela, partant d'un point {{formule|''x''<sub>0</sub>}} 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 (géométrie)|tangente]] en ce point :
<center>
<math>
f(x)\simeq f(x_0) + f'(x_0)(x-x_0).
</math>
</center>
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 :
<center>
<math>
0=f(x_0) + f'(x_0)(x-x_0).
</math>
</center>
On obtient alors un point {{math|''x''{{ind|1}}}} qui en général a de bonnes chances d'être plus proche du vrai zéro de {{mvar|f}} que le point {{formule|''x''<sub>0</sub>}} précédent.
Par cette opération, on peut donc espérer améliorer l'approximation par [[itération]]s successives (voir illustration) : on approche à nouveau la fonction par sa tangente en <math>x_1</math> pour obtenir un nouveau point {{math|''x''{{ind|2}}}}, etc.

[[Image:Methode newton.png|thumb|right|300px|Illustration de la méthode de Newton.]]
[[Image:NewtonIteration Ani.gif|thumb|right|300px|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 {{mvar|f}} soit [[dérivable]].

Formellement, on part d'un point {{formule|''x''<sub>0</sub>}} appartenant à l'ensemble de définition de la fonction et on construit par récurrence la suite :
<center>
<math>
x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)},
</math>
</center>
où {{mvar|f {{'}}}} désigne la [[dérivée]] de la fonction {{mvar|f}}.
Le point {{formule|''x''<sub>''k''+1</sub>}} est bien la solution de l'équation affine
<math>f(x_k)+f'(x_k)(x-x_k)=0</math>.

Il se peut que la récurrence doive se terminer, si à l'étape {{mvar|k}}, {{mvar|x<sub>k</sub>}} n'appartient pas au [[Ensemble de définition|domaine de définition]] ou si la dérivée {{math|''f {{'}}''(''x{{ind|k}}'')}} est nulle ; dans ces cas, la méthode échoue.

Si le zéro inconnu {{mvar|α}} est isolé, alors il existe un [[Voisinage (mathématiques)|voisinage]] de {{mvar|α}} tel que pour toutes les valeurs de départ {{formule|''x''<sub>0</sub>}} dans ce voisinage, la [[suite (mathématiques)|suite]] {{math|(''x<sub>k</sub>'')}} va [[Limite de suite|converger]] vers {{mvar|α}}. De plus, si {{math|''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.

=== Exemple ===
Pour illustrer la méthode, recherchons le nombre positif <math>x</math> vérifiant <math>\cos(x)=x^3</math>.
Reformulons la question pour introduire une fonction devant s'annuler :
on recherche le zéro positif (la racine) de <math>f(x) = \cos(x)-x^3</math>.
La dérivation donne <math> f'(x) = -\sin(x) - 3x^2 </math>.

Comme <math>\cos(x)\leqslant 1</math> pour tout <math>x</math> et <math>x^3>1</math> pour <math>x>1</math>,
nous savons que notre zéro ne peut être supérieur à 1.
<br>
Comme de plus <math>\cos(0) = 1 > 0 = 0^3</math> et <math>\cos(1) < \cos(\pi/4) < 1 = 1^3</math>,
nous savons que notre zéro appartient à l'intervalle <math>[0,1]</math>.
<br>
Nous prenons comme valeur de départ <math>x_0 = 0{,}5</math> :
:<math>\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\,097\,2 \\
  x_2 & = & x_1 - \frac{f(x_1)}{f'(x_1)}
                 & & \cdots & \simeq & 0{,}909\,672\,693\,736\,8 \\
  x_3 & & \cdots & & \cdots & \simeq & 0{,}866\,263\,818\,208\,8 \\
  x_4 & & \cdots & & \cdots & \simeq & 0{,}865\,477\,135\,298\,2 \\
  x_5 & & \cdots & & \cdots & \simeq & 0{,}865\,474\,033\,110\,9 \\
  x_6 & & \cdots & & \cdots & \simeq & 0{,}865\,474\,033\,101\,6 \\
  x_7 & & \cdots & & \cdots & \simeq & 0{,}865\,474\,033\,101\,6
\end{matrix}
</math>
Les 13 chiffres significatifs affichés de l'approximation <math>x_7</math> coïncident avec les 13 premiers chiffres du zéro exact.
En réalité, les nombres de chiffres significatifs exacts après la virgule (à l'arrondi près) à partir de <math>x_1</math> sont 0, 1, 2, 5, 10, 21, 43,
avec à peu près un doublement à chaque itération,
ce qui illustre le caractère quadratique de la convergence exposé ci-après.

=== Convergence ===
La [[Vitesse de convergence des suites|vitesse de convergence]] d'une suite {{mvar|x<sub>n</sub>}} obtenue par la méthode de Newton peut être obtenue comme application de la [[Théorème de Taylor|formule de Taylor-Lagrange]]. Il s'agit d'évaluer une majoration de {{math|log{{!}}''x{{ind|n}}'' – ''a''{{!}}}}.

{{mvar|f}} est une fonction définie au voisinage de {{mvar|a}} et deux fois continûment différentiable. On suppose que {{mvar|a}} se trouve être un zéro de {{mvar|f}} qu'on essaie d'approcher par la méthode de Newton. On fait l'hypothèse que {{mvar|a}} est un zéro d'ordre 1, autrement dit que {{math|''f {{'}}''(''a'')}} est non nul. La [[Théorème de Taylor|formule de Taylor-Lagrange]] s'écrit :
<center><math>0=f (a) =f (x) +f'(x) (a-x) + \frac{ f '' (\xi)}{2}{ (a-x) ^2}</math>, avec {{mvar|ξ}} entre {{mvar|x}} et {{mvar|a}}.</center>
Partant de l'approximation {{formule|''x''}}, la méthode de Newton fournit au bout d'une itération :
<center><math>N_f (x) -a=x-\frac{f (x)}{f'(x)} - a= \frac{f '' (\xi)}{2 \, f'(x)}(x-a) ^2</math>.</center>
Pour un intervalle compact {{mvar|I}} contenant {{mvar|x}} et {{mvar|a}} et inclus dans le domaine de définition de {{mvar|f}}, on pose : {{math|''m''{{ind|1}} {{=}} min{{ind|''x'' ∈ ''I''}} {{!}}''f {{'}}''(''x'') {{!}}}} ainsi que {{math|''M''{{ind|2}} {{=}} max{{ind|''x'' ∈ ''I''}} {{!}}''f {{''}}''(''x''){{!}}}}. Alors, pour tout {{math|''x'' ∈ ''I''}} :
<center><math>\left|N_f (x) - a \right| \leqslant \frac{M_2}{2m_1} |x-a|^2</math>.</center>
Par récurrence immédiate, il vient :
<center><math>K\left|x_n-a\right| \leqslant (K|x_0-a|)^{2^n}</math></center>
où {{math|''K'' {{=}} {{sfrac|''M''{{ind|2}}|2''m''{{ind|1}}}}}}. En passant au [[logarithme]] :
<center><math>\log\left|x_n-a\right| \leqslant 2^n\log (K|x_0-a|)-\log(K) </math></center>
La convergence de {{mvar|x<sub>n</sub>}} vers {{mvar|a}} est donc quadratique, à condition que {{math|{{!}}''x''<sub>0</sub> – ''a''{{!}} < 1/''K''}}.

=== Exemples de non-convergence ===

[[Image:NewtonsMethodConvergenceFailure.svg|thumb|300px|Les tangentes à la courbe représentant la fonction <math>x\mapsto x^3-2x+2</math> en 0 et en 1 coupent l'axe des {{mvar|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 {{math|''x''{{ind|*}} {{=}} 0}} de la fonction <math>x\in\R\mapsto|x|^{1/2}</math> en prenant un itéré initial {{math|''x''{{ind|0}} ≠ 0}}, on constate que, pour tout <math>k\in\mathbb{N}</math>, {{formule|''x''<sub>''k''+1</sub>{{=}}–''x''<sub>''k''</sub>}} ; la suite générée ne converge donc pas, même localement (c'est-à-dire même si {{formule|''x''<sub>0</sub>}} est pris proche du zéro {{math|''x''{{ind|*}} {{=}} 0}}). Le problème provient ici, en particulier, de la non-dérivabilité de la fonction en l'unique zéro {{math|''x''{{ind|*}} {{=}} 0}}.
<!--
{{...}}
=== Convergence quadratique locale ===
{{...}}
-->
<!-- Déjà démontré ci-dessus -->

=== Critère d'arrêt ===

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

<center><math>\| f(x_k)\|< \varepsilon_1\qquad\mathrm{ou}\qquad
\| x_{k+1}-x_k\|<\varepsilon_2</math></center>

où
<math> \varepsilon_1,\varepsilon_2\in\mathbb{R}^+ </math>
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.

=== Autres exemples ===

==== Racine carrée ====
[[Fichier:Heron visuel.gif|vignette|Construction de la suite de Héron à partir du graphe de <math>x\mapsto\frac12\left(x+\frac2x\right)</math>.]]
Un cas particulier de la méthode de Newton est la [[méthode de Héron]], aussi appelée méthode [[Mathématiques mésopotamiennes|babylonienne]] : il s'agit, pour calculer la [[racine carrée]] de {{mvar|a}}, d'appliquer la méthode de Newton à la fonction {{mvar|f}} définie par

: <math>f(x) = x^2 - a</math>.

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

:<math>
x_{k+1}:=x_k-\frac{x_k^2 - a}{2x_k}=\frac12 \left(x_k + \frac a{x_k}\right)
</math>.

Pour tout {{math|''a'' ≥ 0}} et tout point de départ {{formule|''x''<sub>0</sub> > 0}}, [[Méthode de Héron#Principe|cette méthode converge vers {{sqrt|''a''}}]].

On peut l'étendre au calcul de toute [[Racine d'un nombre|racine {{mvar|n}}-ième d'un nombre]] {{mvar|a}} avec la formule :

:<math>x_{k+1}:=x_k-\frac{x_k^n - a}{nx_k^{n-1}}=\frac1n\left({(n-1)x_k+\frac a{x_k^{n-1}}}\right)</math>.
[[Fichier:Inverse par Newton.gif|vignette|Construction de la suite convergeant vers <math>1/a</math> à partir du graphe de <math>x\mapsto x(2-ax) </math>.]]

==== Inverse ====
A partir de <math>f(x)=\frac1x-a</math>, on obtient l'itération <math>
x_{k+1}:=x_k(2-ax_k)
</math> qui converge vers l'inverse de {{mvar|a}} > 0. Cette méthode a l’intérêt de ne faire intervenir que des sommes ou produits. Elle est utilisée pour calculer l'inverse intervenant dans la méthode de Héron.

==== Intersection de graphes ====

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

== Fonctions holomorphes ==

[[Image:Julia-set N z3-1.png|thumb|220px|La méthode de Newton appliquée au polynôme {{math|''z''{{3}} – 1}} à variable complexe {{mvar|z}} converge à partir de tous les points du plan (des nombres complexes) colorés en rouge, vert ou bleu vers l'une des trois racines de ce polynôme, chacune des couleurs correspondant à une racine différente. Les points restants, se trouvant sur la structure plus claire — appelée fractale de Newton — sont les points de départ pour lesquels la méthode ne converge pas.]]
La méthode peut aussi être utilisée pour trouver des zéros de [[Fonction holomorphe|fonctions holomorphes]].
Dans ce cadre, on connaît bien les comportements que peut avoir la suite des itérés de Newton. On peut citer :
* convergence vers un zéro ;
* limite infinie ;
* la suite admet un cycle limite autrement dit, la suite peut être découpée en {{mvar|p}} sous-suites disjointes de la forme {{math|(''z''{{ind|''n''{{ind|0}} + ''kp''}}){{ind|''k''}}}} qui chacune convergent vers des points distincts (qui ne sont pas des zéros de {{mvar|f}}) formant un cycle périodique pour la fonction {{math|''z'' – {{sfrac|''f''(''z'')|''f {{'}}''(''z'')}}}} ;
* la suite se rapproche de l'ensemble des zéros de la fonction sans qu'il n'y ait toutefois de cycle limite, et à chaque étape de l'itération, on se retrouve proche d'un zéro différent des précédents ;
* la suite a un comportement [[théorie du chaos|chaotique]], etc.

{{Article détaillé|Fractale de Newton}}
L'ensemble des points à partir desquels peut être obtenue une suite qui converge vers un zéro fixé s'appelle le ''bassin d'attraction'' de ce zéro. Pour beaucoup de fonctions complexes, le bassin d'attraction est une [[fractale]].

L'étude de la méthode de Newton pour les polynômes à variables complexes trouve naturellement sa place dans l'étude [[Théorie des systèmes dynamiques|dynamique]] des [[fraction rationnelle|fractions rationnelles]] et a été une des motivations récentes de l'étude de la [[dynamique holomorphe]].

== Généralisations/variantes ==

=== Systèmes d'équations à plusieurs variables ===

On peut aussi utiliser la méthode de Newton pour résoudre un système de {{mvar|n}} équations (non linéaires) à {{mvar|n}} inconnues {{math|''x'' {{=}} (''x''{{ind|1}},...,''x{{ind|n}}'')}}, ce qui revient à trouver un zéro d'une fonction {{mvar|F}} de <math>\R^n</math> dans <math>\R^n</math>, qui devra être différentiable. Dans la formulation donnée ci-dessus, il faut multiplier par l'inverse de la [[matrice jacobienne]] {{math|''F {{'}}''(''x{{ind|k}}'')}} au lieu de diviser par {{math|''f {{'}}''(''x{{ind|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
<center>
<math>
F\,'(x_k) (x_{k+1} - x_k) = -F(x_k)
</math>
</center>
en l'inconnue {{math|''x''{{ind|''k''+1}} – ''x{{ind|k}}''}}. Encore une fois, cette méthode ne fonctionne que pour une valeur initiale {{math|''x''<sub>0</sub>}} suffisamment proche d'un zéro de {{mvar|F}}.
<!--Ainsi, on peut commencer par localiser une région favorable par une méthode grossière ou par un préconditionnement de la matrice, puis appliquer la méthode de Newton pour peaufiner la précision.-->

=== Méthode de Newton approchée ===

Il arrive parfois que la dérivée (ou la matrice jacobienne pour un système d'équations à plusieurs variables) de la fonction {{mvar|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 {{math|''f {{'}}''(''x{{ind|k}}'')}} par
<center><math>
\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}},
</math></center>
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 {{math|''φ'' {{=}} {{sfrac|1 + {{racine|5}}|2}} ≈ 1,618}}).

=== Méthode de Newton non lisse ===

Lorsque la fonction dont on cherche une racine est non-différentiable, mais seulement [[fonction semi-lisse|semi-lisse]], la méthode de Newton ne génère pas nécessairement une suite {{math|{''x{{ind|k}}''} }} convergente, même si les itérés sont des points de différentiabilité de {{mvar|f}}, arbitrairement proches d'un zéro de {{mvar|F}}. Un contre-exemple est donné par Kummer (1988<ref>{{en}} B. Kummer (1988). ''Newton’s method for nondifferentiable functions''. In {{ouvrage|lang=en|auteur1=J. Guddat|auteur2=B. Bank|auteur3=H. Hollatz|auteur4=P. Kall|auteur5=D. Klatte|auteur6=B. Kummer|auteur7=K. Lommatzsch|auteur8=L. Tammer|auteur9=M. Vlach|auteur10=K. Zimmerman|titre=Advances in Mathematical Optimization|pages=114–125|éditeur=Akademie-Verlag|lieu=Berlin}}.</ref>).

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

{{Bloc emphase|espacement=1.5ex|<math>x_{k+1}:=x_k-J_k^{-1}f(x_k),</math>}}

où {{mvar|J{{ind|k}}}} est une jacobienne inversible du [[Différentiel généralisé#Différentiel de Clarke|différentiel de Clarke]] {{math|∂{{ind|CF}}(''x{{ind|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 {{math|''x''{{ind|*}}}} est suffisamment lisse : elle doit être [[Fonction semi-lisse|semi-lisse]]. Il faut aussi qu'en ce zéro la fonction ait ses « pentes » qui ne s'annulent pas en {{math|''x''{{ind|*}}}} ; ceci s'exprime par l'hypothèse de [[Différentiel généralisé#C-régularité|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.

{{Théorème|Convergence locale de l'algorithme de Newton semi-lisse|Supposons que {{mvar|f}} soit [[Fonction semi-lisse|semi-lisse]] en une solution C-régulière {{math|''x''{{ind|*}}}} de l'équation {{math|''f''(''x'') {{=}} 0}}. Alors,
* il existe un voisinage {{mvar|V}} de {{math|''x''{{ind|*}}}} tel que si le premier itéré {{math|''x''{{ind|1}} ∈ ''V''}}, l'algorithme de Newton semi-lisse est bien défini et génère une suite {{math|{''x{{ind|k}}''} }} dans {{mvar|V}}, qui converge super-linéairement vers {{math|''x''{{ind|*}}}},
* la convergence est quadratique si {{mvar|f}} est fortement semi-lisse en {{math|''x''{{ind|*}}}}.}}

Un état de l'art est donné par Izmailov et Solodov<ref>{{article|lang=en|auteur1=A. F. Izmailov|auteur2=M. V. Solodov|année=2014|titre=Newton-Type Methods for Optimization and Variational Problems|périodique=Springer Series in Operations Research and Financial Engineering|éditeur=Springer}}.</ref>.

=== Méthode de Newton par intervalles ===
{{pertinence section|date=janvier 2019}}
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<ref>{{ouvrage|lang=en|auteur=RE Moore|année=1979|titre=Methods and applications of interval analysis|volume=2|éditeur=Siam}}</ref>{{,}}<ref>{{article|lang=en|auteur=E. Hansen|année=1978|titre=Interval forms of Newtons method|périodique=Computing|numéro=20|volume=2|pages=153-163}}</ref>.

On considère <math>f \in \mathcal{C}^1(X)</math>, avec {{mvar|X}} un intervalle réel, et on suppose que l'on a une extension par intervalles {{mvar|F'}} de {{mvar|f '}}, c'est-à-dire une fonction {{mvar|F '}} prenant en entrée un intervalle {{math|''Y'' ⊆ ''X''}} et renvoyant un intervalle {{math|''F{{'}}''(''Y'')}} tel que :
<center><math>\begin{align}
    F'([y,y]) &= \{f'(y)\}\\
    F'(Y) &\supseteq \{f'(y)~|~y \in Y\}
\end{align}</math>.</center>
On suppose également que <math>0 \notin F'(X)</math>, donc en particulier {{mvar|f}} a au plus un zéro sur {{mvar|X}}.
On peut maintenant définir l'opérateur :
<center><math>N(Y) = m + \frac{f(m)}{F'(Y)} = \left\{\left. m + \frac{f(m)}{z} ~\right|~ z \in F'(Y)\right\}</math></center>
pour tout intervalle {{mvar|y}} de centre {{mvar|m}}. On notera que l'hypothèse sur {{mvar|F'}} implique que {{math|''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 :
<center><math>
\begin{align}
X_0 &= X\\
X_{k+1} &= N(X_k) \cap X_k
\end{align}
</math>.</center>
Le [[théorème des accroissements finis]] certifie que, s'il y a un zéro de {{mvar|f}} dans {{mvar|X{{ind|k}}}}, alors il est encore dans {{math|''X''{{ind|''k''+1}}}}. De plus, l'hypothèse de positivité sur {{mvar|F'}} implique que la taille de {{math|''X''{{ind|''k''+1}}}} est au plus la moitié de celle de {{mvar|X{{ind|k}}}}, donc la séquence converge vers le singleton {{math|{''x''{{exp|*}}<nowiki/>} }}, où {{math|''x''{{exp|*}}}} est le zéro de {{mvar|f}} sur {{mvar|X}}.

== Annexes ==

=== Notes ===

{{Références|colonnes=2}}

=== Articles connexes ===

* [[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 Halley]] (méthode de Newton appliquée à <math>f/\sqrt{f'}</math>)
* [[Méthode de Quasi-Newton|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]]

=== Liens externes ===

* J. Ch. Gilbert, ''[http://www-rocq.inria.fr/~gilbert/ensta/optim.html Éléments d'Optimisation Différentiable — Théorie et Algorithmes]'', syllabus de cours à l'[[École nationale supérieure de techniques avancées|ENSTA ParisTech]], Paris.
* N. Soualem (2006). ''[http://www.math-linux.com/spip.php?article65 Méthode de Newton]'' sur math-linux.com.

=== Références ===

* {{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, [[Claudia Sagastizábal|C. Sagastizábal]] (2006), ''Numerical Optimization - Theoretical and Practical Aspects'' {{détail des éditions|Référence:Optimisation (Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006)}}.
* J.-L. Chabert, É. Barbin, M. Guillemot, A. Michel-Pajus, J. Borowczyk, A. Djebbar, [[Jean-Claude Martzloff|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), [http://www.ece.northwestern.edu/~nocedal/book/num-opt.html 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.

{{Palette|Méthodes de résolution|Analyse Numérique|Optimisation}}
{{portail|analyse}}

{{DEFAULTSORT:Methode de Newton}}
[[Catégorie:Itération|Newton]]
[[Catégorie:Algorithme de recherche d'un zéro d'une fonction|Newton]]
[[Catégorie:Algorithme d'optimisation|Newton]]
[[Catégorie:Isaac Newton]]