170
5 Systèmes linéaires
On a le résultat important suivant
Proposition 5.7 Soit A une matrice symétrique définie positive.
En arithmétique exacte, la méthode du gradient conjugué pour résoudre (5.1) converge en au plus n étapes (en arithmétique exacte).
De plus, l’erreur e
(k) à la k-ème itération (avec k < n) est orthogonale à p
(j) , pour j = 0, . . . , k − 1 et
e
(k)
A ≤
2c
k
1 + c 2k e
(0)
A , avec c =
K(A) − 1
K(A) + 1
.
(5.63)
Ainsi, en l’absence d’erreur d’arrondi, on peut considérer CG comme
une méthode directe puisqu’elle fournit le résultat en un nombre fini
d’étapes. Cependant, pour les matrices de grande taille, CG est utilisé
comme une méthode itérative, c’est-à-dire dont les itérations sont interrompues quand un estimateur de l’erreur (p. ex. le résidu relatif (5.60))
devient inférieur à une tolérance donnée. En comparant (5.63) et (5.57),
on notera que la vitesse de convergence de l’erreur dépend du conditionnement de la matrice de manière plus favorable que pour la méthode du
gradient (grâce à la présence de la racine carrée de K(A)).
On peut aussi considérer une version préconditionnée de CG (PCG
en abrégé) avec un préconditionneur P symétrique et défini positif : étant
donné x
(0) , on pose r
(0) = b − Ax
(0) , z
(0) = P
−1
r
(0) et p
(0) = z
(0) , puis
pour k = 0, 1, . . .
α k =
p
(k) T r
(k)
p (k) T Ap (k)
,
x
(k+1) = x
(k) + α k p
(k) ,
r
(k+1) = r
(k)
− α k Ap
(k) ,
Pz
(k+1) = r
(k+1) ,
β k =
(Ap
(k) )
T
z
(k+1)
(Ap (k) ) T p (k) ,
p
(k+1) = z
(k+1)
− β k p
(k)
(5.64)
Dans ce cas, l’estimation d’erreur (5.60) est encore valable, mais en remplaçant K(A) par K(P
−1 A), qui est plus petit.
La méthode PCG est implémentée dans la fonction pcg de MATLAB.
pcg