Algorithme de Newton
Un article de Haypo.
Retour aux articles de mathématiques
L'algorithme de Newton permet de rechercher les zéros d'une fonction, c'est à dire les valeurs pour lesquelles la fonction s'annule.
Sommaire |
[modifier] Principe
On utilise la relation suivante :
xn+1 = xn - f(x)/f'(x)
On prend un intervalle [a;b]. On part de b en se dirigeant vers a pour trouver le premier zéro (il peut en avoir plusieurs). Graphiquement, on trace la tangente en x0 (qui est égal à b) qui coupe l'axe horizontal en x1, on recommence ainsi ce suite ...
Condition : il faut que la fonction f(x) soit deux fois dérivables : f'(x) et f''(x) existent, c'est le cas de la plupard des polynômes et fonctions usuelles (x², cos(x), arctan(x), cosh(x), etc.).
En pratique, on voit qu'on sort de l'intervalle dans certains cas (pente trop faible) : il faut réduire l'intervalle, changer d'intervalle ou ... partir de l'autre côté (il suffit de prendre x0=a).
[modifier] Exemples
[modifier] Calcul de l'inverse d'un nombre
- f(x) = 1/x - a pour a: nombre réel (différent de zéro)
- f'(x) = -1/x^2
- Relation : xn+1 = 2 xn - a × xn²
[modifier] Racine carré d'un nombre
- f(x) = x^2 - a pour a: nombre réel positif
- f'(x) = 2x
- Relation : xn+1 = (xn + a/xn) / 2
[modifier] Racine carré d'un nombre, sans division!
Enfin, avec une division par deux, ce qui est très facile à calculer.
- f(x) =1/x^2 - a pour a : nombre réel positif
- f'(x) = -2/x^3
- Relation : xn+1 = xn/2 × (3 - a × xn^2)
- Résultat = xn × a
[modifier] Voir aussi
[modifier] Articles connexes
[modifier] Liens externes
- Chronomaths: Explication théorique de l'algorithme (page Javascript, numéro 43 : Méthode de Newton pour la résolutionde f(x)=0)
- Rapport de recherche de Paul Zimmerman: Rapport de recherche écrit par Paul ZIMMERMAN sur le calcul de la racine carré d'un nombre sans division en utilisant l'algorithme de Karastuba.
