Encyclopedie - Méthode_de

Un article de Wikipedia.y-project.com.

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

[] 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'interêt de Method of Fluxions avaient déjà été écrites, en 1671.

[] 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'algèbre é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.

Image:Methode newton.png

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 :

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.

[] Exemple

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.

<math>\begin

 x_1 & = & x_0 - \frac & = & \frac{\cos(0.5) - 0.5^3}{-\sin(0.5) - 3 \times 0.5^2} & = & 1.1121416371 \\
 x_2 & = & x_1 - \frac & & \vdots & = & 0.909672693736 \\
 x_3 & & \vdots & & \vdots & = & 0.867263818209 \\
 x_4 & & \vdots & & \vdots & = & 0.865477135298 \\
 x_5 & & \vdots & & \vdots & = & 0.865474033111 \\
 x_6 & & \vdots & & \vdots & = & 0.865474033101 \\
 x_7 & & \vdots & & \vdots & = & 0.865474033102

\end </math>

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>

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

[] Généralisation

On peut aussi vouloir utiliser la méthode de Newton pour résoudre des systèmes de n équations (non 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

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 ou la fonction complexe est une fonction polynomiale, la méthode converge à partir de n'importe quelle valeur de départ sauf si le polynome admet des racines doubles.

[] Voir aussi

Méthode de la sécante
Méthode de la fausse position (ou Méthode Régula Falsi)

Image:Nuvola 64 apps edu mathematics blue.png

Portail des mathématiques ? Accédez aux articles de Wikipédia concernant les mathématiques.

Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/Méthode de Newton


	Saisir un mot clé:

Méthode_de_Newton