4.4 M´ ethodes de Krylov
155
Exemple 4.8 R´ esolvons le syst` eme lin´ eaire Ax = b avec A = tridiag 100 (−1, 2, −1)
et b tel que la solution soit x = 1. Le vecteur initial est x
(0) = 0 et tol=10
−10 .
La m´ ethode converge en 50 it´ erations et la Figure 4.9 montre le comportement de
la norme euclidienne du r´ esidu normalis´ ee par celle du r´ esidu initial en fonction
du nombre d’it´ erations. Remarquer la r´ eduction brutale du r´ esidu : c’est le signal
typique du fait que le dernier sous-espace Wk construit est assez riche pour contenir
la solution exacte du syst` eme.
•
4.4.2 La m´ ethode GMRES
Dans cette m´ ethode, on choisit x
(k) de mani` ere ` a minimiser la norme euclidienne du r´ esidu `
a chaque it´ eration k. On a d’apr` es (4.57)
r
(k) = r
(0)
− AV k z
(k) .
(4.62)
Or, puisque r
(0) = v 1 r
(0)
2 , la relation (4.62) devient, d’apr` es (4.54),
r
(k) = V k+1 (r
(0)
2 e 1 −
H k z
(k) ),
(4.63)
o` u e 1 est le premier vecteur unitaire de R
k+1 . Ainsi, dans GMRES, la solution
` a l’´ etape k peut ˆ etre calcul´ ee avec (4.57) et
z
(k) choisi de mani` ere ` a minimiser r
(0)
2 e 1 −
H k z
(k)
2 .
(4.64)
Noter que la matrice V k+1 intervenant dans (4.63) ne modifie pas la valeur de
· · 2 car elle est orthogonale. Comme on doit r´ esoudre ` a chaque ´ etape un probl` eme de moindres carr´ es de taille k, GMRES est d’autant plus efficace que le
nombre d’it´ erations est petit. Exactement comme pour la m´ ethode d’Arnoldi,
GMRES s’ach` eve en donnant la solution exacte apr` es au plus n it´ erations. Un
arrˆ et pr´ ematur´ e est dˆ u `
a une interruption dans le proc´ ed´ e d’orthonormalisation d’Arnoldi. Plus pr´ ecis´ ement, on a le r´ esultat suivant :
Propri´ et´ e 4.7 La m´ ethode GMRES s’arrˆ ete ` a l’´ etape m (avec m < n) si
et seulement si la solution calcul´ ee x
(m) co¨ ıncide avec la solution exacte du
syst` eme.
Une impl´ ementation MATLAB ´ el´ ementaire de GMRES est propos´ ee dans le
Programme 23. Ce dernier demande en entr´ ee la taille maximale admissible
m des sous-espaces de Krylov et la tol´ erance tol sur la norme euclidienne du
r´ esidu normalis´ ee par celle du r´ esidu initial. Dans cette impl´ ementation, on
calcule la solution x
(k) ` a chaque pas pour calculer le r´ esidu, ce qui induit une
augmentation du coˆ ut de calcul.
155
Exemple 4.8 R´ esolvons le syst` eme lin´ eaire Ax = b avec A = tridiag 100 (−1, 2, −1)
et b tel que la solution soit x = 1. Le vecteur initial est x
(0) = 0 et tol=10
−10 .
La m´ ethode converge en 50 it´ erations et la Figure 4.9 montre le comportement de
la norme euclidienne du r´ esidu normalis´ ee par celle du r´ esidu initial en fonction
du nombre d’it´ erations. Remarquer la r´ eduction brutale du r´ esidu : c’est le signal
typique du fait que le dernier sous-espace Wk construit est assez riche pour contenir
la solution exacte du syst` eme.
•
4.4.2 La m´ ethode GMRES
Dans cette m´ ethode, on choisit x
(k) de mani` ere ` a minimiser la norme euclidienne du r´ esidu `
a chaque it´ eration k. On a d’apr` es (4.57)
r
(k) = r
(0)
− AV k z
(k) .
(4.62)
Or, puisque r
(0) = v 1 r
(0)
2 , la relation (4.62) devient, d’apr` es (4.54),
r
(k) = V k+1 (r
(0)
2 e 1 −
H k z
(k) ),
(4.63)
o` u e 1 est le premier vecteur unitaire de R
k+1 . Ainsi, dans GMRES, la solution
` a l’´ etape k peut ˆ etre calcul´ ee avec (4.57) et
z
(k) choisi de mani` ere ` a minimiser r
(0)
2 e 1 −
H k z
(k)
2 .
(4.64)
Noter que la matrice V k+1 intervenant dans (4.63) ne modifie pas la valeur de
· · 2 car elle est orthogonale. Comme on doit r´ esoudre ` a chaque ´ etape un probl` eme de moindres carr´ es de taille k, GMRES est d’autant plus efficace que le
nombre d’it´ erations est petit. Exactement comme pour la m´ ethode d’Arnoldi,
GMRES s’ach` eve en donnant la solution exacte apr` es au plus n it´ erations. Un
arrˆ et pr´ ematur´ e est dˆ u `
a une interruption dans le proc´ ed´ e d’orthonormalisation d’Arnoldi. Plus pr´ ecis´ ement, on a le r´ esultat suivant :
Propri´ et´ e 4.7 La m´ ethode GMRES s’arrˆ ete ` a l’´ etape m (avec m < n) si
et seulement si la solution calcul´ ee x
(m) co¨ ıncide avec la solution exacte du
syst` eme.
Une impl´ ementation MATLAB ´ el´ ementaire de GMRES est propos´ ee dans le
Programme 23. Ce dernier demande en entr´ ee la taille maximale admissible
m des sous-espaces de Krylov et la tol´ erance tol sur la norme euclidienne du
r´ esidu normalis´ ee par celle du r´ esidu initial. Dans cette impl´ ementation, on
calcule la solution x
(k) ` a chaque pas pour calculer le r´ esidu, ce qui induit une
augmentation du coˆ ut de calcul.