Méthode de Newton-Raphson

Méthode de Newton

Isaac Newton

En analyse numérique, la méthode de Newton, ou méthode de Newton-Raphson^[1], est un algorithme efficace pour trouver des approximations d'un zéro (ou racine) d'une fonction d'une variable réelle à valeurs réelles. L'algorithme consiste à linéariser une fonction $f$ 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 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 (1643-1727) et Joseph Raphson, qui furent les premiers à la décrire pour l'appliquer à la recherche des zéros d'une équation polynomiale.

Sommaire

1 Pour les fonctions d'une variable réelle
2 Convergence
- 2.1 Exemple de non convergence
- 2.2 Convergence quadratique locale
3 Critère d'arrêt
4 D'autres exemples d'application
5 Généralisations/variantes
- 5.1 Méthode de Newton approchée
- 5.2 Systèmes d'équations à plusieurs variables
6 Références
7 Voir aussi
- 7.1 Articles connexes
- 7.2 Liens externes

Pour les fonctions d'une variable réelle

Histoire

John Wallis

La méthode de Newton fut décrite de manière satisfaisante par le mathématicien anglais Isaac Newton (1643-1727) dans De analysi per aequationes numero terminorum infinitas, écrit en 1669 et publié en 1711 par William Jones (1675-1749). Elle fut à nouveau décrite dans De metodis fluxionum et serierum infinitarum (De la méthode des fluxions et des conséquences infinies), écrit en 1671, traduit et publié sous le titre Methods of Fluxions en 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 $X 3 - 2 X 2 - 3 X + 6$ et donc peut être pris comme un zéro approximatif de $P (X) = X 3 - 2 X 2 - 3 X + 7$ . Une petite perturbation doit s'écrire $2 + Y$ . Or, $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 $P$ par $2 + Y$ impose $Y = 1 / 7$ .

Cette méthode fut l'objet de publications antérieures. En 1685, John Wallis (1616-1703) en publia une première description dans A Treatise of Algebra both Historical and Practical. En 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 que Thomas Simpson (1710-1761) 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 à des problèmes d'optimisation. Arthur Cayley (1821-1895) fut le premier à noter la difficulté de généraliser la méthode de Newton aux variables complexes en 1879^[2], par exemple aux polynomes de degré supérieur à 3.

Interprétation et construction formelle

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

$f(x)\cong f(x_0) + f'(x_0)(x-x_0)$ .

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

0 = f (x 0) + f'(x 0)(x - x 0)

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

Illustration de la méthode de Newton

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 0$ appartenant à l'ensemble de définition de la fonction et on construit par récurrence la suite : $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ où $f'$ désigne la dérivée de la fonction $f$ . Le point $x n + 1$ est bien la solution de l'équation affine $f (x n) + f'(x n)(x - x n) = 0$ .

Il se peut que la récurrence doivent se terminer, si à l'étape $n$ , $x n$ n'appartient pas au domaine de définition ou si la dérivée $f'(x n)$ est nulle, dans ce cas, la méthode a échoué.

Si le zéro inconnu $α$ est isolé, alors il existe un voisinage de $α$ tel que pour toutes les valeurs de départ $x 0$ dans ce voisinage, la suite $(x n)$ va converger vers $α$ . De plus, si $f'(α)$ 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 $x$ vérifiant $cos(x) = x 3$ . Reformulons la question pour introduire une fonction devant s'annuler : on recherche le zéro positif (la racine) de $f (x) = cos(x) - x 3$ . La dérivation donne $f'(x) = - sin(x) - 3 x 2$ .

Comme $\cos(x)\le 1$ pour tout $x$ et $x 3 > 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 = 0,5$ .

$\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 coincident avec les 7 premiers chiffres du vrai zéro.

Convergence

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. Il s'agit d'évaluer une majoration de $log | x n - a |$ .

$f$ est une fonction continument différentiable deux fois définie au voisinage de $a$ . On suppose que $a$ se trouve être un zéro de $f$ qu'on essaie d'approximer 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 s'écrit :

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

ξ

entre

x

a

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

$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 : $\textstyle m_1= \min_{x \in I} |f'(x) |$ ainsi que $\textstyle M_2= \max_{x \in I} |f '' (x) |$ . Alors, pour tout $x \in I$ :

$\Bigl|N_f (x) - a \Bigr| \le \frac{M_2}{2m_1} |x-a|^2$ .

Par récurrence immédiate, il vient :

$K\Bigl|x_n-a\Bigr|<(K|x_0-a|)^{2^n}$

où $K=\tfrac{M_2}{2m_1}$ . En passant au logarithme :

$\log\Bigl|x_n-a\Bigr|<2^n\log (K|x_0-a|)-\log(K)$

La convergence de $x n$ vers $a$ est donc quadratique.

Exemple de non convergence

Convergence quadratique locale

Critère d'arrêt

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

$\| f(x_n)\|< \varepsilon_1\qquad\mathrm{ou}\qquad \| x_{n+1}-x_n\|<\varepsilon_2$

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

D'autres exemples d'application

Calcul de la racine carrée

Un cas particulier de la méthode de Newton est l'algorithme de Babylone, aussi connu sous le nom de méthode de Héron : il s'agit de l'appliquer à la résolution de

f (x) = x 2 - a

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

$x_{n+1}:=x_n-\frac{x_n^2 - a}{2x_n}=\frac12 \left(x_n + \frac{a}{x_n}\right)$ .

Cette méthode converge pout tout $a\geq0$ et tout point de départ $x_0 \neq 0$ .

Intersection des graphes de deux fonctions

De la même façon, on peut déterminer l'intersection des graphes de deux fonctions réelles dérivables $f (x)$ et $g (x)$ , c'est à dire l'ensemble de points $x$ où on a $f (x) = g (x)$ , en appliquant la méthode de Newton à la fonction

f (x) - g (x)

Pour les fonctions complexes

La méthode de Newton appliquée au polynôme

z 3 - 1

à variable complexe

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 appliquée pour trouver des zéros de fonctions complexes . Dans ce cadre, on connait bien les comportements que peuvent avoir la suite des itérés de Newton . On peut citer :

convergence vers un zéro,
convergence vers l'infini,
la suite admet un cycle limite autrement dit, la suite peut être découpée en $p$ sous-suites disjointes de la forme $(z_{n_0+kp})_k$ qui chacune convergent vers des points distincts (qui ne sont pas des zéros de $f$ ) formant un cycle périodique pour la fonction $z-\frac{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 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 dynamique des fractions rationnelles et a été une des motivations récentes de l'étude de la dynamique holomorphe.

Généralisations/variantes

Méthode de Newton approchée

Systèmes d'équations à plusieurs variables

On peut aussi vouloir utiliser la méthode de Newton pour résoudre des systèmes de $k$ équations (non nécessairement linéaires), ce qui revient à trouver les zéros de fonctions continûment dérivables $F$ de $\R^k$ dans $\R^k$ . Dans la formulation donnée ci-dessus, il faut multiplier par l'inverse de la matrice jacobienne $F'(x n)$ au lieu de diviser par $f'(x n)$ . 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

$F\,'(x_n) (x_{n+1} - x_n) = -F(x_n)$

pour l'inconnue $x n + 1 - x n$ . Encore une fois, cette méthode ne fonctionne que pour une valeur initiale $x 0$ 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.

Références

↑ Joseph Louis Lagrange et Louis Poinsot, Traité de la résolution des équations numériques de tous les degrés
↑ Arthur Cayley, The Newton-Fourier imaginary problem, 1789.

Voir aussi

Liens externes

Méthode de Newton sur maTh-linux.com.

Méthodes de résolution d'équations
Résolution d'équations polynomiales	Méthode de Bézout · Méthode de Cardan · Méthode de Sotta · Méthode de Ferrari · Méthode de Descartes · Méthode de Tschirnhaus · Méthode d'Hermite
Recherche d'un zéro	Méthode de dichotomie · Méthode de Newton · Méthode de la sécante · Méthode de Müller · Méthode de Brent · Méthode de la fausse position · Méthode de Héron · Méthode de Laguerre · Méthode du cercle de séparation · Méthode de Halley · Méthode de Householder . Méthode de Quasi-Newton

Portail des mathématiques

Ce document provient de « M%C3%A9thode de Newton ».

Catégories : Algorithme de recherche d'un zéro d'une fonction | Algorithme d'optimisation | Analyse numérique | Isaac Newton

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Méthode de Newton-Raphson de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

Methode de Newton — Méthode de Newton Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro … Wikipédia en Français
Méthode De Newton — Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro … Wikipédia en Français
Méthode de newton — Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro … Wikipédia en Français
Méthode de Newton — Isaac Newton En analyse numérique, la méthode de Newton ou méthode de Newton Raphson[1] est, dans son application la plus simple, un algorithme efficace pour trouver numériquement une approximation précise d … Wikipédia en Français
Newton-Raphson-Verfahren — Das Newtonsche Näherungsverfahren, auch Newton Raphsonsche Methode, (benannt nach Sir Isaac Newton 1669 und Joseph Raphson 1690) ist in der Mathematik das Standardverfahren zur numerischen Lösung von nichtlinearen Gleichungen und… … Deutsch Wikipedia
Methode de la corde — Méthode de Newton Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro … Wikipédia en Français
Méthode de la corde — Méthode de Newton Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro … Wikipédia en Français
Methode de Muller — Méthode de Müller En mathématiques, la méthode de Müller est un algorithme de recherche d un zéro d une fonction qui est basé sur la méthode de la sécante mais qui utilise une approximation quadratique d une partie de la fonction au lieu d une… … Wikipédia en Français
Méthode De Müller — En mathématiques, la méthode de Müller est un algorithme de recherche d un zéro d une fonction qui est basé sur la méthode de la sécante mais qui utilise une approximation quadratique d une partie de la fonction au lieu d une approximation… … Wikipédia en Français
Méthode de müller — En mathématiques, la méthode de Müller est un algorithme de recherche d un zéro d une fonction qui est basé sur la méthode de la sécante mais qui utilise une approximation quadratique d une partie de la fonction au lieu d une approximation… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Méthode de Newton-Raphson

Méthode de Newton

Sommaire