2.3 Méthode de Newton
51
lim
k→∞
x
(k+1)
− α
(x (k) − α) 2 =
f
(α)
2f (α)
(2.9)
Quand f
(α) = 0, on dit que la méthode de Newton a une convergence
quadratique ou d’ordre 2. En effet, pour des valeurs de k assez grande,
l’erreur à l’étape (k + 1) se comporte comme le carré de l’erreur à l’étape
k multiplié par une constante indépendante de k.
Pour des zéros de multiplicité m plus grande que 1, i.e. si f
(α) =
0, . . . , f
(m−1) (α) = 0, la méthode de Newton converge encore, mais
seulement si x
(0) est bien choisi et f
(x) = 0 ∀x ∈ I(α) \ {α}. Cependant, dans ce cas, la convergence est seulement d’ordre 1 (voir Exercice
2.15). On peut retrouver l’ordre 2 en modifiant la méthode originale (2.7)
comme suit
x
(k+1) = x
(k)
− m
f(x
(k) )
f (x (k) )
, k ≥ 0
(2.10)
en supposant f
(x
(k) ) = 0. Evidemment, cette méthode de Newton modifiée (2.10) requiert la connaissance a priori de m. Quand on ne connaît
pas m, on peut utiliser la méthode de Newton adaptative, qui est encore d’ordre 2. On trouvera les détails de cette méthode dans [QSS07,
paragraphe 6.6.2].
Exemple 2.3 La fonction f (x) = (x − 1) log(x) a un zéro unique α = 1 qui
est de multiplicité m = 2. Calculons le par les méthodes de Newton (2.7) et
de Newton modifiée (2.10). Sur la Figure 2.4, on a tracé l’erreur obtenue avec
ces deux méthodes en fonction du nombre d’itérations. Remarquer que, pour
la méthode de Newton classique, la convergence n’est que linéaire.
0
5
10
15
20
25
30
10
−10
10
−8
10
−6
10
−4
10
−2
10
0
10
2
Figure 2.4. Erreur en échelle semi-logarithmique en fonction du nombre d’itérations pour la fonction de l’Exemple 2.3. La ligne discontinue correspond à
la méthode de Newton (2.7), la ligne en trait plein à la méthode de Newton
modifiée (2.10) (avec m = 2)