144
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
On remarque aussi que, pour tout j = 0, . . ., k, la relation (4.44) implique
(Ap
(j) )
T p
(k+1) = (Ap
(j) )
T r
(k+1)
− β k (Ap
(j) )
T p
(k) .
Par hypoth` ese de r´ ecurrence pour j ≤ k − 1, le dernier produit scalaire est
nul. Montrons que c’est aussi le cas du premier produit scalaire du second
membre. Soit V k = vect(p
(0) , . . ., p
(k) ). Si on choisit p
(0) = r
(0) , on voit avec
(4.44) que V k peut aussi s’exprimer comme V k = vect(r
(0) , . . . , r
(k) ). Donc,
Ap
(k)
∈ V k+1 pour tout k ≥ 0 d’apr` es (4.39). Comme r
(k+1) est orthogonal `
a
tout vecteur de V k (voir (4.43)),
(Ap
(j) )
T r
(k+1) = 0,
j = 0, 1, . . ., k − 1.
On a donc prouv´ e (4.40) par r´ ecurrence sur k, d` es lors que les directions
A-orthogonales sont choisies comme en (4.44) et (4.45).
La m´ ethode du gradient conjugu´ e (not´ ee GC) est la m´ ethode obtenue en
choisissant comme directions de descente les vecteurs p
(k) donn´ es par (4.44)
et comme param` etres d’acc´ el´ eration les α k d´ efinis en (4.38). Par cons´ equent,
´ etant donn´ e x
(0)
∈ R
n , en posant r
(0) = b − Ax
(0) et p
(0) = r
(0) , la k-i` eme
it´ eration de la m´ ethode du gradient conjugu´ e s’´ ecrit
α 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) ,
β k =
(Ap
(k) )
T r
(k+1)
(Ap (k) ) T p (k) ,
p
(k+1) = r
(k+1)
− β k p
(k) .
On peut montrer que les deux param` etres α k et β k peuvent aussi s’exprimer
ainsi (voir Exercice 10) :
α k =
(k)
2
2
p (k) T Ap (k)
, β k = −
(k+1)
2
2
(k)
2
2
.
(4.46)
Remarquons enfin qu’en ´ eliminant la direction de descente de r
(k+1) = r
(k)
−
α k Ap
(k) , on obtient la relation de r´ ecurrence ` a trois termes sur les r´ esidus
(voir Exercice 11)
Ar
(k) = −
1
α k
r
(k+1) +
1
α k
−
β k−1
α k−1
r
(k) +
β k
α k−1
r
(k−1) .
(4.47)
Concernant la convergence de la m´ ethode du gradient conjugu´ e, on a les r´ esultats suivants.
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
On remarque aussi que, pour tout j = 0, . . ., k, la relation (4.44) implique
(Ap
(j) )
T p
(k+1) = (Ap
(j) )
T r
(k+1)
− β k (Ap
(j) )
T p
(k) .
Par hypoth` ese de r´ ecurrence pour j ≤ k − 1, le dernier produit scalaire est
nul. Montrons que c’est aussi le cas du premier produit scalaire du second
membre. Soit V k = vect(p
(0) , . . ., p
(k) ). Si on choisit p
(0) = r
(0) , on voit avec
(4.44) que V k peut aussi s’exprimer comme V k = vect(r
(0) , . . . , r
(k) ). Donc,
Ap
(k)
∈ V k+1 pour tout k ≥ 0 d’apr` es (4.39). Comme r
(k+1) est orthogonal `
a
tout vecteur de V k (voir (4.43)),
(Ap
(j) )
T r
(k+1) = 0,
j = 0, 1, . . ., k − 1.
On a donc prouv´ e (4.40) par r´ ecurrence sur k, d` es lors que les directions
A-orthogonales sont choisies comme en (4.44) et (4.45).
La m´ ethode du gradient conjugu´ e (not´ ee GC) est la m´ ethode obtenue en
choisissant comme directions de descente les vecteurs p
(k) donn´ es par (4.44)
et comme param` etres d’acc´ el´ eration les α k d´ efinis en (4.38). Par cons´ equent,
´ etant donn´ e x
(0)
∈ R
n , en posant r
(0) = b − Ax
(0) et p
(0) = r
(0) , la k-i` eme
it´ eration de la m´ ethode du gradient conjugu´ e s’´ ecrit
α 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) ,
β k =
(Ap
(k) )
T r
(k+1)
(Ap (k) ) T p (k) ,
p
(k+1) = r
(k+1)
− β k p
(k) .
On peut montrer que les deux param` etres α k et β k peuvent aussi s’exprimer
ainsi (voir Exercice 10) :
α k =
(k)
2
2
p (k) T Ap (k)
, β k = −
(k+1)
2
2
(k)
2
2
.
(4.46)
Remarquons enfin qu’en ´ eliminant la direction de descente de r
(k+1) = r
(k)
−
α k Ap
(k) , on obtient la relation de r´ ecurrence ` a trois termes sur les r´ esidus
(voir Exercice 11)
Ar
(k) = −
1
α k
r
(k+1) +
1
α k
−
β k−1
α k−1
r
(k) +
β k
α k−1
r
(k−1) .
(4.47)
Concernant la convergence de la m´ ethode du gradient conjugu´ e, on a les r´ esultats suivants.