2.5 Accélération par la méthode d’Aitken
63
0
100
200
300
400
500
10
−12
10
−10
10
−8
10
−6
10
−4
10
−2
10
0
(1)
(2)
Figure 2.10. Valeur absolue de l’erreur (traits pleins) et valeur absolue de la
différence entre deux itérées successives (traits discontinus), tracées en fonction
du nombre d’itérations, pour l’Exemple 2.8. La courbe (1) correspond à m =
11, la courbe (2) à m = 21
2.5 Accélération par la méthode d’Aitken
Dans ce paragraphe, nous décrivons une technique qui permet d’accélérer
la convergence d’une suite construite par une méthode de point fixe. On
suppose donc que x
(k) = φ(x
(k−1) ), k ≥ 1. Si la suite {x
(k)
} converge
linéairement vers un point fixe α de φ, on déduit de (2.21) que, pour un
certain k, il y a un λ (à déterminer) tel que
φ(x
(k) ) − α = λ(x
(k)
− α),
(2.25)
où on a volontairement évité d’identifier φ(x
(k) ) avec x
(k+1) . L’idée de
la méthode d’Aitken consiste en effet à définir une nouvelle valeur de
x
(k+1) (et donc une nouvelle suite) qui soit une meilleure approximation
de α que celle donnée par φ(x
(k) ). On déduit de (2.25) que
α =
φ(x
(k) ) − λx
(k)
1 − λ
=
φ(x
(k) ) − λx
(k) + x
(k)
− x
(k)
1 − λ
ou encore
α = x
(k) + (φ(x
(k) ) − x
(k) )/(1 − λ)
(2.26)
On doit à présent calculer λ. Pour ce faire, on introduit la suite
λ
(k) =
φ(φ(x
(k) )) − φ(x
(k) )
φ(x (k) ) − x (k)
(2.27)
et on vérifie qu’on a la propriété suivante
Lemme 2.1 Si la suite définie par x
(k+1) = φ(x
(k) ) converge vers
α, alors lim
k→∞
λ
(k) = φ
(α).
63
0
100
200
300
400
500
10
−12
10
−10
10
−8
10
−6
10
−4
10
−2
10
0
(1)
(2)
Figure 2.10. Valeur absolue de l’erreur (traits pleins) et valeur absolue de la
différence entre deux itérées successives (traits discontinus), tracées en fonction
du nombre d’itérations, pour l’Exemple 2.8. La courbe (1) correspond à m =
11, la courbe (2) à m = 21
2.5 Accélération par la méthode d’Aitken
Dans ce paragraphe, nous décrivons une technique qui permet d’accélérer
la convergence d’une suite construite par une méthode de point fixe. On
suppose donc que x
(k) = φ(x
(k−1) ), k ≥ 1. Si la suite {x
(k)
} converge
linéairement vers un point fixe α de φ, on déduit de (2.21) que, pour un
certain k, il y a un λ (à déterminer) tel que
φ(x
(k) ) − α = λ(x
(k)
− α),
(2.25)
où on a volontairement évité d’identifier φ(x
(k) ) avec x
(k+1) . L’idée de
la méthode d’Aitken consiste en effet à définir une nouvelle valeur de
x
(k+1) (et donc une nouvelle suite) qui soit une meilleure approximation
de α que celle donnée par φ(x
(k) ). On déduit de (2.25) que
α =
φ(x
(k) ) − λx
(k)
1 − λ
=
φ(x
(k) ) − λx
(k) + x
(k)
− x
(k)
1 − λ
ou encore
α = x
(k) + (φ(x
(k) ) − x
(k) )/(1 − λ)
(2.26)
On doit à présent calculer λ. Pour ce faire, on introduit la suite
λ
(k) =
φ(φ(x
(k) )) − φ(x
(k) )
φ(x (k) ) − x (k)
(2.27)
et on vérifie qu’on a la propriété suivante
Lemme 2.1 Si la suite définie par x
(k+1) = φ(x
(k) ) converge vers
α, alors lim
k→∞
λ
(k) = φ
(α).