« Méthode de Newton » : différence entre les versions
Contenu supprimé Contenu ajouté
Fonctionnalité de suggestions de liens : 3 liens ajoutés. Balises : Éditeur visuel Modification par mobile Modification par le web mobile Tâche pour novices Suggéré : ajouter des liens |
m →Ensemble O_{x,\alpha}^n(h) d'Opérateurs Fraccionnels : suppression: contournement de Discussion:Calcul fraccional d'ensembles/Admissibilité |
||
(10 versions intermédiaires par 7 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 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}}
|