240
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
on peut ´ ecrire (6.36) sous la forme
x
(k) = x
(k)
−
(x
(k) )
2
2 x (k−1) ,
k ≥ 2.
(6.37)
Cette ´ ecriture explique pourquoi (6.36) est aussi appel´ ee m´ ethode
2 d’Aitken.
Pour analyser la convergence de la m´ ethode d’Aitken, il est commode d’´ ecrire
(6.36) comme une m´ ethode de point fixe (6.17), en introduisant la fonction
d’it´ eration
φ (x) =
xφ(φ(x)) − φ
2 (x)
φ(φ(x)) − 2φ(x) + x
.
(6.38)
Ce quotient est ind´ etermin´ e en x = α car φ(α) = α ; n´ eanmoins, on v´ erifie facilement (en appliquant par exemple la r` egle de l’Hˆ opital) que lim x→α φ (x) =
α sous l’hypoth` ese que φ est diff´ erentiable en α et φ
(α) = 1. Ainsi, φ est
bien d´ efinie et continue en α, et c’est aussi vrai si α est une racine multiple
de f. On peut de plus montrer que les points fixes de (6.38) co¨ ıncident avec
ceux de φ mˆ eme dans le cas o` u α est une racine multiple de f (voir [IK66], p.
104-106).
On d´ eduit de (6.38) que la m´ ethode d’Aitken peut ˆ etre appliqu´ ee ` a une
m´ ethode de point fixe x = φ(x) d’ordre arbitraire. On a en effet le r´ esultat de
convergence suivant :
Propri´ et´ e 6.7 (convergence de la m´ ethode d’Aitken) Soit x
(k+1) =
φ(x
(k) ) une m´ ethode de point fixe d’ordre p ≥ 1 pour l’approximation d’un
z´ ero simple α d’une fonction f. Si p = 1, la m´ ethode d’Aitken converge vers
α avec un ordre 2, tandis que si p ≥ 2 l’ordre de convergence est 2p − 1.
En particulier, si p = 1, la m´ ethode d’Aitken est convergente mˆ eme si la
m´ ethode de point fixe ne l’est pas. Si α est de multiplicit´ e m ≥ 2 et si la
m´ ethode x
(k+1) = φ(x
(k) ) est convergente et du premier ordre, alors la m´ ethode
d’Aitken converge lin´ eairement avec un facteur de convergence C = 1 − 1/m.
Exemple 6.9 Consid´ erons le calcul du z´ ero simple α = 1 de la fonction f (x) =
(x − 1)e
x . Nous utilisons pour cela trois m´ ethodes de point fixe dont les fonctions
d’it´ eration sont φ0(x) = log(xe
x ), φ1(x) = (e
x + x)/(e
x + 1) et φ2(x) = (x
2 −
x + 1)/x (pour x = 0). Remarquer que |φ
0 (1)| = 2; la m´ ethode de point fixe
correspondante n’est donc pas convergente. Dans les deux autres cas les algorithmes
sont respectivement d’ordre 1 et 2.
V´ erifions les performances de la m´ ethode d’Aitken en ex´ ecutant le Programme 51
avec x
(0) = 2, tol = 10
−10 et en utilisant l’arithm´ etique complexe. Remarquer que
dans le cas de φ0, elle produit des nombres complexes si x
(k) est n´ egatif. En accord
avec la Propri´ et´ e 6.7, la m´ ethode d’Aitken appliqu´ ee ` a la fonction d’it´ eration φ0
converge en 8 ´ etapes vers la valeur x
(8) = 1.000002 + i 0.000002. Dans les deux
autres cas, la m´ ethode d’ordre 1 converge vers α en 18 it´ erations, contre 4 it´ erations
pour la m´ ethode d’Aitken, tandis qu’avec φ2 la convergence a lieu en 7 it´ erations
contre 5 pour la m´ ethode d’Aitken.
•
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
on peut ´ ecrire (6.36) sous la forme
x
(k) = x
(k)
−
(x
(k) )
2
2 x (k−1) ,
k ≥ 2.
(6.37)
Cette ´ ecriture explique pourquoi (6.36) est aussi appel´ ee m´ ethode
2 d’Aitken.
Pour analyser la convergence de la m´ ethode d’Aitken, il est commode d’´ ecrire
(6.36) comme une m´ ethode de point fixe (6.17), en introduisant la fonction
d’it´ eration
φ (x) =
xφ(φ(x)) − φ
2 (x)
φ(φ(x)) − 2φ(x) + x
.
(6.38)
Ce quotient est ind´ etermin´ e en x = α car φ(α) = α ; n´ eanmoins, on v´ erifie facilement (en appliquant par exemple la r` egle de l’Hˆ opital) que lim x→α φ (x) =
α sous l’hypoth` ese que φ est diff´ erentiable en α et φ
(α) = 1. Ainsi, φ est
bien d´ efinie et continue en α, et c’est aussi vrai si α est une racine multiple
de f. On peut de plus montrer que les points fixes de (6.38) co¨ ıncident avec
ceux de φ mˆ eme dans le cas o` u α est une racine multiple de f (voir [IK66], p.
104-106).
On d´ eduit de (6.38) que la m´ ethode d’Aitken peut ˆ etre appliqu´ ee ` a une
m´ ethode de point fixe x = φ(x) d’ordre arbitraire. On a en effet le r´ esultat de
convergence suivant :
Propri´ et´ e 6.7 (convergence de la m´ ethode d’Aitken) Soit x
(k+1) =
φ(x
(k) ) une m´ ethode de point fixe d’ordre p ≥ 1 pour l’approximation d’un
z´ ero simple α d’une fonction f. Si p = 1, la m´ ethode d’Aitken converge vers
α avec un ordre 2, tandis que si p ≥ 2 l’ordre de convergence est 2p − 1.
En particulier, si p = 1, la m´ ethode d’Aitken est convergente mˆ eme si la
m´ ethode de point fixe ne l’est pas. Si α est de multiplicit´ e m ≥ 2 et si la
m´ ethode x
(k+1) = φ(x
(k) ) est convergente et du premier ordre, alors la m´ ethode
d’Aitken converge lin´ eairement avec un facteur de convergence C = 1 − 1/m.
Exemple 6.9 Consid´ erons le calcul du z´ ero simple α = 1 de la fonction f (x) =
(x − 1)e
x . Nous utilisons pour cela trois m´ ethodes de point fixe dont les fonctions
d’it´ eration sont φ0(x) = log(xe
x ), φ1(x) = (e
x + x)/(e
x + 1) et φ2(x) = (x
2 −
x + 1)/x (pour x = 0). Remarquer que |φ
0 (1)| = 2; la m´ ethode de point fixe
correspondante n’est donc pas convergente. Dans les deux autres cas les algorithmes
sont respectivement d’ordre 1 et 2.
V´ erifions les performances de la m´ ethode d’Aitken en ex´ ecutant le Programme 51
avec x
(0) = 2, tol = 10
−10 et en utilisant l’arithm´ etique complexe. Remarquer que
dans le cas de φ0, elle produit des nombres complexes si x
(k) est n´ egatif. En accord
avec la Propri´ et´ e 6.7, la m´ ethode d’Aitken appliqu´ ee ` a la fonction d’it´ eration φ0
converge en 8 ´ etapes vers la valeur x
(8) = 1.000002 + i 0.000002. Dans les deux
autres cas, la m´ ethode d’ordre 1 converge vers α en 18 it´ erations, contre 4 it´ erations
pour la m´ ethode d’Aitken, tandis qu’avec φ2 la convergence a lieu en 7 it´ erations
contre 5 pour la m´ ethode d’Aitken.
•