Méthode de newton Rafeson
En analyse numérique, la méthode de Newton ou méthode de Newton-
Raphson1 est, dans son application la plus simple, un algorithme
efficace pour trouver numériquement une approximation précise d'un
zéro (ou racine) d'une fonction réelle d'une variable réelle.
Présentation :
Sous sa forme moderne, l'algorithme peut être présenté brièvement
comme suit : à chaque itération, la fonction dont on cherche un zéro
est linéarisée en l'itéré (ou point) courant et l'itéré suivant est pris égal
au zéro de la fonction linéarisée.
Cette description sommaire indique qu'au moins deux conditions sont
requises pour la bonne marche de l'algorithme : la fonction doit être
dérivable aux points visités ; et les dérivées ne doivent pas s'y annuler;
s'ajoute à ces conditions la contrainte forte de devoir prendre le
premier itéré assez proche d'un zéro régulier de la fonction.
L'intérêt principal de l'algorithme de Newton est sa convergence
quadratique locale. En termes imagés mais peu précis, cela signifie
que le nombre de chiffres significatifs corrects des itérés double à
chaque itération, asymptotiquement. Comme le nombre de chiffres
significatifs représentables par un ordinateur est d’environ 15 chiffres
décimaux.
Fonction réelle d'une variable réelle :
L'algorithme
On va donc chercher à construire une bonne approximation d'un zéro
de la fonction d'une variable réelle f(x) en considérant son
développement de Taylor au premier ordre. Pour cela, partant d'un
point x0 que l'on choisit de préférence proche du zéro à trouver (en
faisant des estimations grossières par exemple), on approche la
fonction au premier ordre, autrement dit, on la considère
asymptotiquement égale à sa tangente en ce point :
Partant de là, pour trouver un zéro de cette fonction d'approximation,
il suffit de calculer l'intersection de la droite tangente avec l'axe des
abscisses, c'est-à-dire résoudre l'équation affine :
On obtient alors un point x1 qui en général a de bonnes chances d'être
plus proche du vrai zéro de f que le point x0 précédent. Par cette
opération, on peut donc espérer améliorer l'approximation par
itérations successives (voir illustration) : on approche à nouveau la
fonction par sa tangente en x1pour obtenir un nouveau point x2, etc.
Formellement, on part d'un point x0 appartenant à l'ensemble de
définition de la fonction et on construit par récurrence la suite :
Où f ' désigne la dérivée de la fonction f. Le point xk+1 est bien la
solution de l'équation affine :
Exemple
Pour illustrer la méthode, recherchons le nombre positif x vérifiant
cos(x) = x3. Reformulons la question pour introduire une fonction
devant s'annuler : on recherche le zéro positif (la racine) de f(x) =
cos(x) – x3. La dérivation donne f '(x) =–sin(x) – 3x2.
Comme cos(x) ⩽ 1 pour tout x et x3>1 pour x>1, nous savons que
notre zéro se situe entre 0 et 1. Nous essayons une valeur de départ de
x0 = 0,5.
Les 7 premiers chiffres de cette valeur coïncident avec les 7 premiers
chiffres du vrai zéro.
Convergence
La vitesse de convergence d'une suite xn obtenue par la méthode de
Newton peut être obtenue comme application de la formule de Taylor-
Lagrange. Il s'agit d'évaluer une majoration de log|xn – a|.
F est une fonction définie au voisinage de a et deux fois continûment
différentiable. On suppose que a se trouve être un zéro de f qu'on
essaie d'approcher 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-Lagrange s'écrit :
Partant de l'approximation x, la méthode de Newton fournit au bout
d'une itération :
Par récurrence immédiate, il vient
Où K = M2/2m1. En passant au logarithme :
Méthode de Newton approchée :
Il arrive parfois que la dérivée (ou la matrice jacobéenne pour un
système d'équations à plusieurs variables) de la fonction f soit
coûteuse à calculer. La dérivée peut alors être approchée au moyen de
différences finies. Par exemple, en approchant la dérivée f '(xk) par :
On obtient la méthode de la sécante. La convergence de cette méthode
n'est plus quadratique, mais reste sur-linéaire :
Méthode de Newton non lisse :
Lorsque la fonction dont on cherche une racine est non-différentiable,
mais seulement semi-lisse, la méthode de Newton ne génère pas
nécessairement une suite {xk} convergente, même si les itérés sont
des points de différentiable de f, arbitrairement proches d'un zéro de F.
Un contre-exemple est donné par Kummer
Programmation sur Fortran
Ce programme consiste à déterminer la valeur de X0
La solution du programme
X0=0.785
X0=1,57
X0=0,523