« Méthode de Newton » : différence entre les versions
Contenu supprimé Contenu ajouté
Balises : Révocation manuelle Éditeur visuel |
m →Ensemble O_{x,\alpha}^n(h) d'Opérateurs Fraccionnels : suppression: contournement de Discussion:Calcul fraccional d'ensembles/Admissibilité |
||
| (11 versions intermédiaires par 8 utilisateurs non affichées) | |||
Ligne 1 :
{{Infobox Méthode scientifique
[[Fichier:Newton iteration.png|vignette|Une [[itération]] de la méthode de Newton.]]▼
| image = Newton iteration.png
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.▼
▲}}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 ==
Ligne 7 ⟶ 9 :
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.
Ligne 40 ⟶ 42 :
-->
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.
Ligne 80 ⟶ 82 :
<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.
Ligne 87 ⟶ 89 :
=== Exemple ===
Pour illustrer la méthode, recherchons le nombre positif
Reformulons la question pour introduire une fonction devant s'annuler : on recherche le zéro positif (la racine) de La dérivation donne Comme <math>\cos(x)\leqslant 1</math> pour tout
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\, x_2 & = & x_1 - \frac{f(x_1)}{f'(x_1)}
& & \ x_3 & & \
x_4 & & \
x_5 & & \
x_6 & & \
x_7 & & \
\end{matrix}
</math>
Les
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 ===
Ligne 109 ⟶ 126 :
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'')
<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 :
Ligne 147 ⟶ 164 :
==== 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
Ligne 162 ⟶ 180 :
:<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 ==
Ligne 284 ⟶ 308 :
* {{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}}
| |||