5. Systèmes linéaires
119
se réduit à M
0 ({)=D{e lorsque D est symétrique. Par conséquent, lorsque
D est symétrique, définie positive, M({) a pour minimum D{ = e= Àc haque
pas, on détermine une valeur n qui minimise la quantité M({ n + n u n ).Le
succès de la méthode du gradient conjugué a incité de nombreux auteurs à
proposer des méthodes plus générales dans le cas où D n’est pas une matrice
symétrique, définie positive. La méthode la plus simple, lorsque D n’est pas
symétrique, consiste à remplacer l’équation D{ = e par D
w D{ = D
w e dans
laquelle D
w D est symétrique, mais cette méthode a l’inconvénient d’eectuer des produits supplémentaires et d’amplifier le mauvais conditionnement éventuel de A puisque frqg(D
w D)=frqg(D)
2
. D’autres méthodes
plus e!caces ont été proposées pour D non symétrique comme la méthode
CGS (Conjugate Gradient Square), la méthode BiCGStab (Bi-Conjugate
Gradient Stabilized ) ou la méthode GMRES (Generalized Minimum Residual Method ).
5.4.1 Méthode de la plus profonde descente
La méthode de la plus profonde descente cherche à minimiser le résidu
u n = Elle se fonde sur l’algorithme suivant : On se donne un vecteur { 0 > puis
on calcule successivement les quantités
;
A A ?
A A =
u n = e D{ n
n =
(u n >u n )
(u n >Du n )
{ n+1 = { n + n u n
où (u n >u n ) e s tl ep r o d u i ts c a l a i r ed eu n par lui-même. L’e!cacité de la
méthode dépend du conditionnement de la matrice D. Notons
E({ n )=?D({ n {)> ({ n {) A
1@2
la norme “énergétique”. Soit D une matrice symétrique définie positive, et
= max @ min le conditionnement de la matrice D, est le rapport de
la plus grande valeur propre de D sur la plus petite. La convergence de la
méthode de la plus profonde descente est donnée par
E({ n )
µ 1
+1
¶ n
E({ 0 )
La méthode n’est pas toujours e!cace : si la matrice D a un grand conditionnement, on voit dans l’expression précédente que si est élevé, la norme
énergétique n’évolue presque pas. Par conséquent, le vecteur résiduel u n ne
change pas beaucoup d’une itération à l’autre : la convergence est très lente.
Pour éviter ce problème, Fox, Husky et Wilkinson ont proposé en 1949 de
remplacer la minimisation le long du vecteur résiduel par une minimisation
le long de la direction orthogonale : c’est la méthode des directions conjuguées. Hestenes et Stiefel ont montré qu’on pouvait choisir ces directions à
chaque pas : c’est la méthode du gradient conjugué.
119
se réduit à M
0 ({)=D{e lorsque D est symétrique. Par conséquent, lorsque
D est symétrique, définie positive, M({) a pour minimum D{ = e= Àc haque
pas, on détermine une valeur n qui minimise la quantité M({ n + n u n ).Le
succès de la méthode du gradient conjugué a incité de nombreux auteurs à
proposer des méthodes plus générales dans le cas où D n’est pas une matrice
symétrique, définie positive. La méthode la plus simple, lorsque D n’est pas
symétrique, consiste à remplacer l’équation D{ = e par D
w D{ = D
w e dans
laquelle D
w D est symétrique, mais cette méthode a l’inconvénient d’eectuer des produits supplémentaires et d’amplifier le mauvais conditionnement éventuel de A puisque frqg(D
w D)=frqg(D)
2
. D’autres méthodes
plus e!caces ont été proposées pour D non symétrique comme la méthode
CGS (Conjugate Gradient Square), la méthode BiCGStab (Bi-Conjugate
Gradient Stabilized ) ou la méthode GMRES (Generalized Minimum Residual Method ).
5.4.1 Méthode de la plus profonde descente
La méthode de la plus profonde descente cherche à minimiser le résidu
u n = Elle se fonde sur l’algorithme suivant : On se donne un vecteur { 0 > puis
on calcule successivement les quantités
;
A A ?
A A =
u n = e D{ n
n =
(u n >u n )
(u n >Du n )
{ n+1 = { n + n u n
où (u n >u n ) e s tl ep r o d u i ts c a l a i r ed eu n par lui-même. L’e!cacité de la
méthode dépend du conditionnement de la matrice D. Notons
E({ n )=?D({ n {)> ({ n {) A
1@2
la norme “énergétique”. Soit D une matrice symétrique définie positive, et
= max @ min le conditionnement de la matrice D, est le rapport de
la plus grande valeur propre de D sur la plus petite. La convergence de la
méthode de la plus profonde descente est donnée par
E({ n )
µ 1
+1
¶ n
E({ 0 )
La méthode n’est pas toujours e!cace : si la matrice D a un grand conditionnement, on voit dans l’expression précédente que si est élevé, la norme
énergétique n’évolue presque pas. Par conséquent, le vecteur résiduel u n ne
change pas beaucoup d’une itération à l’autre : la convergence est très lente.
Pour éviter ce problème, Fox, Husky et Wilkinson ont proposé en 1949 de
remplacer la minimisation le long du vecteur résiduel par une minimisation
le long de la direction orthogonale : c’est la méthode des directions conjuguées. Hestenes et Stiefel ont montré qu’on pouvait choisir ces directions à
chaque pas : c’est la méthode du gradient conjugué.