Méthode de Newton

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

En analyse numérique, la méthode de Newton, ou méthode de Newton-Raphson, est un algorithme efficace pour trouver des approximations du zéro (ou racine) d'une fonction à valeurs réelles. En fait, c'est un exemple d'algorithme de recherche d'un zéro d'une fonction.

[modifier] Histoire

La méthode de Newton a été découverte par Isaac Newton et publiée dans Method of Fluxions en 1736. Bien que la méthode soit décrite par Joseph Raphson dans Analysis Aequationum en 1690, les sections d'intérêt de Method of Fluxions avaient déjà été écrites, en 1671.

[modifier] La méthode

L'approche graphique est la suivante : On choisit une valeur d'abscisse raisonnablement proche du vrai zéro. On remplace alors la courbe par sa tangente et on calcule le zéro de l'approximation affine associée à la tangente (ce qui se réalise facilement avec l'analyse élémentaire). Ce zéro de la tangente sera généralement plus proche du zéro de la fonction, et la méthode peut être réitérée.

En pratique, voici les opérations à poser pour f : [a, b] → R, fonction définie et dérivable et sur l'intervalle [a, b], et à valeurs réelles. Choisissons une valeur arbitraire x₀ (le plus près du zéro est le mieux). On définit alors, par récurrence pour chaque nombre naturel n :

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

où f ' désigne la dérivée de la fonction f.

On peut prouver que, si f ' est continue et 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.

[modifier] Exemples

Considérons le problème de trouver le nombre positif x vérifiant cos(x) = x³. Reformulons la question pour introduire une fonction devant s'annuler : on recherche le zéro 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)} & = & \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,867\,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}$

et les 12 premiers chiffres de cette valeur coincident avec les 12 premiers chiffres du vrai zéro.

Exemple en JavaScript.

Pour le lancer, copier le texte - y compris les tags du script - dans un nouveau fichier, le nommer avec l'extension .html et l'ouvrir dans un navigateur.

 <script>
  
  function NewtonIterationFnct(x) {
     return  x - (Math.cos(x) - x*x*x) / (-Math.sin(x) - 3*x*x)     
  }  

  x = 0.5
  
  for (i=0; i<=99; i++) {
 document.write("Iteration " + i + ": ")
 document.write(x)
 document.write('<br>')
        xold = x
 x = NewtonIterationFnct(x) 
        if (x == xold) break 
  }
 </script>

[modifier] Considérations pratiques

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,68) 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 implémentation pratique de la méthode de Newton doit inclure un code de contrôle du nombre d'itérations.

[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] 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éthodes de résolution d'équations
Méthodes de 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
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 la fausse position