Méthode de Newton

Un article de Wikipédia, l'encyclopédie libre.

Isaac Newton

En analyse numérique, la méthode de Newton, ou méthode de Newton-Raphson, 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.

[modifier] 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 premiere 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 a des problemes 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^[1], par exemple aux polynomes de degré supérieur à 3.

[modifier] 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érations successives.

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 f : [a, b] → R définie et dérivable et sur l'intervalle [a, b], et à valeurs réelles. La régularité de f est ici minimale. Prenons x₀ un réel arbitraire. Par récurrence, on définit la suite x_n par :

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

où f ' désigne la dérivée de la fonction f. Il se peut que la récurrence se termine, si à l'étape n, x_n n'appartient pas au domaine de définition.

Si le zéro inconnu α est isolé, alors il existe un voisinage de α tel que pour toutes les valeurs de départ x₀ dans ce voisinage, la suite (x_n) va converger vers α. De plus, si f '(α) ≠ 0, 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.

[modifier] Exemple

Pour illustrer la méthode, recherchons le nombre positif x vérifiant cos(x) = x³. Reformulons la question pour introduire une fonction devant s'annuler : on recherche le zéro positif (la racine) de f(x) = cos(x) − x³. La dérivation donne f '(x) = − sin(x) − 3x².

Comme cos(x) ≤ 1 pour tout x et x³ > 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,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.

[modifier] Vitesse de 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 etre 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 et 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}$

ou $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.

[modifier] 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.

[modifier] Généralisation

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

[modifier] Références

↑ Arthur Cayley, The Newton-Fourier imaginary problem, 1789.

[modifier] Voir aussi

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

v · d · m 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