Méthode de Newton
26650
31060776
2008-06-27T09:21:01Z
E Bernal
401608
[[http://books.google.com/books?id=6jHrhC7CuW4C&pg=PA124&dq=Joseph+Raphson&lr=lang_fr&as_brr=1&hl=fr ] résolution des équations numériques de tous les degrés
[[Image:GodfreyKneller-IsaacNewton-1689.jpg|thumb|right|Isaac Newton]] En [[analyse numérique]], la '''méthode de Newton''', ou '''méthode de Newton-Raphson'''<ref>[http://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 De Joseph Louis Lagrange, Louis Poinsot]</ref>, est un [[Algorithmique|algorithme]] efficace pour trouver des [[approximation]]s d'un zéro (ou racine) d'une [[fonction (mathématiques)|fonction]] d'une variable réelle à valeurs réelles. L'algorithme consiste à linéariser une fonction <math>f</math> en un point et de prendre le point d'annulation de cette linéarisation comme approximation du zéro recherché. On réitère cette procédure en l'approximation obtenue. Dans les cas favorables, les approximations successives obtenues convergent avec une vitesse quadratique. De manière informelle, le nombre de décimales correctes double à chaque étape.
Appliqué à la dérivée d'une fonction, cet algorithme permet d'obtenir une évaluation des [[point critique|points critiques]]. La méthode de Newton se généralise en dimension supérieure. La raison réside en une utilisation du [[théorème du point fixe]], qui cependant n'est pas nécessaire pour comprendre le sens du résultat.
Cette méthode porte le nom des mathématiciens anglais [[Isaac Newton]] <small>(1643-1727)</small> et Joseph Raphson, qui furent les premiers à la décrire pour l'appliquer à la [[algorithme de recherche d'un zéro d'une fonction|recherche des zéros d'une équation polynomiale]].
==Histoire==
[[Image:John Wallis.jpg|thumb|left|John Wallis]] La méthode de Newton fut décrite de manière satisfaisante par le mathématicien anglais [[Isaac Newton]] <small>([[1643 en science|1643]]-[[1727 en science|1727]])</small> 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]] <small>([[1675 en science|1675]]-[[1749 en science|1749]])</small>. Elle fut à nouveau décrite dans ''De metodis fluxionum et serierum infinitarum'' (De la méthode des [[Fluxion]]s et des conséquences 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 polynomes. Comme la notion de dérivée et donc de linéarisation n'était pas définie à cette époque, l'approche adoptée diffère : Newton cherchait à affiner une approximation grossière d'un zéro d'un polynome par un calcul polynomial.
Par exemple, 2 est un zéro exact de <math>X^3-2X^2-3X+6</math> et donc peut être pris comme un zéro approximatif de <math>P(X)=X^3-2X^2-3X+7</math>. Une petite perturbation doit s'écrire <math>2+Y</math>. Or, <math>P(2+Y)=1-7Y+2Y^2+Y^3=1-7Y</math> en négligeant les termes d'ordre au moins 2. L'annulation de <math>P</math> par <math>2+Y</math> impose <math>Y=1/7</math>.
Cette méthode fut l'objet de publications antérieures. En [[1685 en science|1685]], [[John Wallis]] <small>([[1616 en science|1616]]-[[1703 en science|1703]])</small> en publia une premiere description dans ''A Treatise of Algebra both Historical and Practical''. En [[1690 en science|1690]], [[Joseph Raphson]] en publia une description simplifiee 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 polynomes. Toutefois, il mit en évidence le calcul récursif des approximations successives d'un zéro d'un polynome au lieu de considérer comme Newton une suite de polynomes.
Ce n'est qu'en [[1740 en science|1740]] que [[Thomas Simpson]] <small>([[1710 en science|1710]]-[[1761 en science|1761]])</small> décrivit cette méthode de calcul itératif pour approcher les solutions d'une équation non linéaire, utilisant le calcul fluxionnel. Simpson appliqua la méthode de Newton a des problemes d'optimisation. [[Arthur Cayley]] <small>([[1821 en science|1821]]-[[1895 en science|1895]])</small> fut le premier à noter la difficulté de généraliser la méthode de Newton aux variables complexes en [[1789 en science|1879]]<ref>Arthur Cayley, The Newton-Fourier imaginary problem, 1789.</ref>, par exemple aux polynomes de degré supérieur à 3.
== La méthode ==
Partant d'une valeur approximative raisonnable d'un zéro d'une fonction d'une variable réelle, on approxime au premier ordre la fonction par sa tangente en ce point. Cette tangente est une [[fonction affine]] dont on sait trouver l'unique zéro (analyse élémentaire). Ce zéro de la tangente sera généralement plus proche du zéro de la fonction. Par cette opération, on peut donc espérer améliorer l'approximation par [[itération]]s successives.
[[Image:Methode newton.png|thumb|Illustration de la méthode de Newton]]
L'avantage de cette méthode est de pouvoir être expliquée graphiquement. Cependant, l'implantation d'un programme demande d'expliciter les calculs à effectuer. Soit une fonction <math>f</math> de <math>[a, b]</math> dans <math>\R</math> définie et [[dérivée|dérivable]] et sur l'[[Intervalle (mathématiques)|intervalle]] <math>[a, b]</math>, et à valeurs [[nombre réel|réelles]]. La régularité de <math>f</math> est ici minimale. Prenons <math>x_0</math> un réel arbitraire. Par récurrence, on définit la suite <math>x_n</math> par :
<center><math>x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}</math></center>
où <math>f'</math> désigne la [[dérivée]] de la fonction <math>f</math>. Il se peut que la récurrence se termine, si à l'étape <math>n</math>, <math>x_n</math> n'appartient pas au domaine de définition.
Si le zéro inconnu <math>\alpha</math> est isolé, alors il existe un [[voisinage]] de <math>\alpha</math> tel que pour toutes les valeurs de départ <math>x_0</math> dans ce voisinage, la [[suite (mathématiques)|suite]] <math>(x_{n})</math> va [[limite|converger]] vers <math>\alpha</math>. De plus, si <math>f'(\alpha)</math> est non nul, alors la convergence est 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)\le 1</math> pour tout <math>x</math> et <math>x^3>1</math> pour <math> x>1</math>, nous savons que notre zéro se situe entre 0 et 1. Nous essayons une valeur de départ de <math>x_0=0,5</math>.
<center><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\,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}
</math></center>
Les 7 premiers chiffres de cette valeur coincident avec les 7 premiers chiffres du vrai zéro.
===Vitesse de convergence===
La vitesse de convergence d'une suite <math>x_n</math> obtenue par la méthode de Newton peut être obtenue comme application de la formule de Taylor. Il s'agit d'évaluer une majoration de <math>\log|x_n-a|</math>.
<math>f </math> est une fonction continument différentiable deux fois définie au voisinage de <math>a</math>. On suppose que <math>a</math> se trouve etre un zéro de <math>f</math> qu'on essaie d'approximer par la méthode de Newton. On fait l'hypothèse que <math>a</math> est un zéro d'ordre 1, autrement dit que <math>f '(a)</math> est non nul. La formule de Taylor s'écrit :
<center><math>0=f (a) =f (x) +f'(x) (a-x) + \frac{ f '' (\xi)}{2}{ (a-x) ^2}</math>, avec <math>\xi</math> entre <math>x</math> et <math>a</math>.</center>
Partant de l'approximation <math>x</math>, 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 <math>I</math> contenant <math>x</math> et <math>a</math> et inclus dans le domaine de définition de <math>f</math>, on pose : <math>\textstyle m_1= \min_{x \in I} |f'(x) |</math> ainsi que <math>\textstyle M_2= \max_{x \in I} |f '' (x) |</math>. Alors, pour tout <math>x \in I</math> :
<center><math>\Bigl|N_f (x) - a \Bigr| \le \frac{M_2}{2m_1} |x-a|^2</math>.</center>
Par récurrence immédiate, il vient :
<center><math>K\Bigl|x_n-a\Bigr|<(K|x_0-a|)^{2^n}</math></center>
où <math>K=\tfrac{M_2}{2m_1}</math>. En passant au [[logarithme]] :
<center><math>\log\Bigl|x_n-a\Bigr|<2^n\log (K|x_0-a|)-\log(K) </math></center>
La convergence de <math>x_n</math> vers <math>a</math> est donc quadratique.
===Variable complexe===
La méthode peut s'appliquer sans difficulté aux fonctions d'une variable complexe. Les problèmes de convergence deviennent plus sérieux. On doit mentionner d'autres comportements limites :
* La suite obtenue par récurrence diverge vers l'infini ;
* La suite présente des cycles limites autrement dit, elle converge alternativement vers des points qui ne sont pas des zéros de la fonction considérée ;
* La suite peut se rapprocher asymptotiquement des zéros de la fonction, mais à chaque étape de l'itération, on se retrouve vers un nouveau zéro.
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.
== Généralisation ==
On peut aussi vouloir utiliser la méthode de Newton pour résoudre des systèmes de <math>k</math> équations (non nécessairement linéaires), ce qui revient à trouver les zéros de fonctions continûment dérivables <math>F</math> de <math>\R^k</math> dans <math>\R^k</math>. Dans la formulation donnée ci-dessus, il faut multiplier par l'inverse de la [[matrice (mathématiques)|matrice]] [[jacobienne]] <math>F'(x_n)</math> au lieu de diviser par <math>f'(x_n)</math>.
Plutôt que de calculer maintenant l'inverse de la matrice, on peut économiser du temps en résolvant le [[système d'équations linéaires]]
<center><math>F\,'(x_n) (x_{n+1} - x_n) = -F(x_n)</math></center>
pour l'inconnue <math>x_{n+1}-x_n</math>.
Encore une fois, cette méthode ne fonctionne que pour une valeur initiale <math>x_0</math> suffisamment proche du vrai zéro. Ainsi, on peut commencer par localiser une région favorable par une méthode grossière, puis appliquer la méthode de Newton pour peaufiner la précision.
La méthode peut aussi être appliquée pour trouver des zéros de [[analyse complexe |fonctions complexes ]]. Pour beaucoup de fonctions complexes, l'ensemble de toutes les valeurs de départ qui permettent à la méthode de converger vers le vrai zéro (le « bassin d'attraction ») est une [[fractale]]. Dans le cas particulier où la fonction complexe est une fonction polynômiale, la méthode converge à partir de n'importe quelle valeur de départ sauf si le polynôme admet des racines doubles.
== Références ==
<references/>
== Voir aussi ==
* [http://www.math-linux.com/spip.php?article65 Méthode de Newton] sur maTh-linux.com.
* [[Méthode de la sécante]]
* [[Méthode de la fausse position]] (ou Méthode Régula Falsi)
* [[Méthode de Quasi-Newton]]
{{Méthodes de résolution}}
[[Catégorie:Algorithme de recherche d'un zéro d'une fonction]]
[[Catégorie:Algorithme d'optimisation]]
[[Catégorie:Isaac Newton]]
{{Portail mathématiques}}
{{lien BA|de}}
[[ar:طريقة نيوتن]]
[[bg:Метод на Нютон]]
[[ca:Mètode de Newton]]
[[cs:Metoda tečen]]
[[da:Newtons metode]]
[[de:Newton-Verfahren]]
[[en:Newton's method]]
[[es:Método de Newton]]
[[fi:Newtonin menetelmä]]
[[he:שיטת ניוטון-רפסון]]
[[it:Metodo delle tangenti]]
[[ja:ニュートン法]]
[[nl:Newton-Raphson]]
[[pl:Metoda Newtona]]
[[pt:Método de Newton]]
[[ru:Метод Ньютона]]
[[sv:Newtons metod]]
[[zh:牛顿法]]