5.10 Méthode de Richardson et du gradient
167
Proposition 5.6 Si A ∈ R
n×n et P ∈ R
n×n sont des matrices
symétriques définies positives, la méthode de Richardson dynamique
converge si, par exemple, α k est choisi de la manière suivante
α k =
(z
(k) )
T
r
(k)
(z (k) ) T Az (k)
∀k ≥ 0
(5.56)
où z
(k) = P
−1
r
(k) est le résidu préconditionné défini en (5.50).
La méthode (5.49) avec ce choix de α k est appelée méthode du gradient préconditionné à pas optimal, ou simplement méthode du gradient à pas optimal quand le préconditionneur P est l’identité. Enfin,
on a l’estimation suivante
e
(k)
A ≤
K(P
−1 A) − 1
K(P −1 A) + 1
k
e
(0)
A , k ≥ 0
(5.57)
Le paramètre α k dans (5.56) est celui qui minimise la nouvelle erreur
e
(k+1)
A (voir Exercice 5.17).
En général, on préférera donc la version dynamique qui, contrairement à la version stationnaire, ne nécessite pas la connaissance des valeurs propres extrêmes de P
−1 A. Noter que le paramètre α k est déterminé
à l’aide de quantités obtenues à l’itération précédente.
On peut récrire plus efficacement la méthode du gradient préconditionné de la manière suivante (le faire en exercice) : soit x
(0) , poser
r
(0) = b − Ax
(0) , puis
pour k = 0, 1, . . .
Pz
(k) = r
(k) ,
α k =
(z
(k) )
T
r
(k)
(z (k) ) T Az (k) ,
x
(k+1) = x
(k) + α k z
(k) ,
r
(k+1) = r
(k)
− α k Az
(k)
(5.58)
Le même algorithme peut être utilisé pour implémenter la méthode
de Richardson en remplaçant simplement α k par une valeur constante α.
D’après (5.55), on voit que si P
−1 A est mal conditionnée la vitesse
de convergence sera très faible, même pour α = α opt (puisque dans ce
cas ρ(B αopt ) 1). Un choix convenable de P permettra d’éviter cette