120
Méthodes projectives
5.4.2 Méthode du gradient conjugué
La méthode du gradient conjugué est une amélioration de la méthode de la
plus profonde descente, dans laquelle le calcul de { n+1 = { n + n+1 s n se fait
le long de nouvelles directions (s 0 > ===> s n ).OnsupposequeD est une matrice
symétrique, définie positive. Les trois premières équations de l’algorithme
correspondent à la minimisation de M sur l’espace { 0 + Yhfw(s 0 > ===> s n ),o ù
{ 0 est un point arbitraire choisi comme point initial de l’algorithme. Les
deux dernières équations correspondent au calcul de la nouvelle direction.
Elle se fonde sur l’algorithme suivant. On se donne un point { 0 de R
q
,
u 0 = e D{ 0 et s 0 = u 0 et on calcule les quantités suivantes
;
A A A A A A A A ?
A A A A A A A A =
n+1 =
(u n >u n )
(s n >Ds n )
{ n+1 = { n + n+1 s n
u n+1 = u n n+1 Ds n
n+1 =
(u n+1 >u n+1 )
(u n >u n )
s n+1 = u n+1 + n+1 s n
On démontre qu’il existe un polynôme de degré n noté S n vérifiant { n
= S n (D){ 0 et S n (0) = 1. Le polynôme qui minimise l’expression
E
2 ({ n ) min
S n
max
S n ()
2
X
m
d
2
m m
est donné par
S n ()=
W n
µ max + min 2
max min
¶
W n
µ max + min
max min
¶
où W n est le polynôme de Tchebychev. Si = max @ min est le conditionnement de la matrice D,o na
E({ n ) 2
µ s
1
s
+1
¶ n
E({ 0 )
La méthode du gradient conjugué nécessite q
3 +5q
2 3q additions, q
3 +6q
2
multiplications et 2q divisions. Si la matrice D est mal conditionnée, la
convergence de l’algorithme du gradient conjugué est lente. Dans ce cas,
on cherchera à améliorer la vitesse de convergence : c’est la méthode du
gradient conjugué préconditionné.
5.4.3 Méthode du gradient conjugué préconditionné
Si les valeurs propres de la matrice D sont dispersées, il faut procéder à un
préconditionnement et remplacer le système D{ = e par PD{ = Pe où P