4.4 M´ ethodes de Krylov
153
sans aucun contrˆ ole de l’erreur. N´ eanmoins le r´ esidu est disponible sans avoir
` a calculer explicitement la solution ; en effet, `
a la k-i` eme ´ etape, on a
b − Ax
(k)
2 = h k+1,k |e
T
k z k |,
et on peut d´ ecider par cons´ equent d’interrompre l’algorithme si
h k+1,k |e
T
k z k |/r
(0)
2 ≤ ε,
(4.61)
o` u ε > 0 est une tol´ erance fix´ ee.
La cons´ equence la plus importante du Th´ eor` eme 4.13 est que la m´ ethode
d’Arnoldi peut ˆ etre vue comme une m´ ethode directe, puisqu’elle fournit la
solution exacte apr` es un nombre fini d’it´ erations. Ceci n’est cependant plus
vrai en arithm´ etique `
a virgule flottante `
a cause de l’accumulation des erreurs
d’arrondi. De plus, si on prend en compte le coˆ ut ´ elev´ e du calcul (qui est de
l’ordre de 2(n z +mn) flops pour m ´ etapes et une matrice creuse d’ordre n ayant
n z coefficients non nuls) et la m´ emoire importante n´ ecessaire au stockage de
la matrice V m , on comprend que la m´ ethode d’Arnoldi ne peut ˆ etre utilis´ ee
telle quelle en pratique, sauf pour de petites valeurs de m.
De nombreux rem` edes existent contre ce probl` eme. Un d’entre eux consiste
` a pr´ econditionner le syst` eme (en utilisant, par exemple, un des pr´ econditionneurs de la Section 4.3.2). On peut aussi introduire des versions modifi´ ees de
la m´ ethode d’Arnoldi en suivant deux approches :
1. on effectue au plus m ´ etapes cons´ ecutives, m ´ etant un nombre petit fix´ e
(habituellement m 10). Si la m´ ethode ne converge pas, on pose x
(0) =
x
(m) et on recommence l’algorithme d’Arnoldi pour m nouvelles ´ etapes.
La proc´ edure est r´ ep´ et´ ee jusqu’` a convergence. Cette m´ ethode, appel´ ee
FOM(m) ou m´ ethode d’Arnoldi avec red´ emarrage (ou restart), permet de
r´ eduire l’occupation m´ emoire puisqu’elle ne n´ ecessite de stocker que des
matrices d’au plus m colonnes ;
2. on impose une limitation dans le nombre de directions qui entrent en
jeu dans le proc´ ed´ e d’orthogonalisation d’Arnoldi. On obtient alors la
m´ ethode d’orthogonalisation incompl` ete ou IOM. En pratique, la k-i` eme
´ etape de l’algorithme d’Arnoldi g´ en` ere un vecteur v k+1 qui est orthonormal aux q vecteurs pr´ ec´ edents, o` u q est fix´ e en fonction de la m´ emoire
disponible.
Il est important de noter que ces deux strat´ egies n’ont plus la propri´ et´ e de
donner la solution exacte apr` es un nombre fini d’it´ erations.
Le Programme 22 donne une impl´ ementation de l’algorithme d’Arnoldi
(FOM) avec un crit` ere d’arrˆ et bas´ e sur le r´ esidu (4.61). Le param` etre d’entr´ ee m est la taille maximale admissible des sous-espaces de Krylov. C’est par
cons´ equent le nombre maximum d’it´ erations.
153
sans aucun contrˆ ole de l’erreur. N´ eanmoins le r´ esidu est disponible sans avoir
` a calculer explicitement la solution ; en effet, `
a la k-i` eme ´ etape, on a
b − Ax
(k)
2 = h k+1,k |e
T
k z k |,
et on peut d´ ecider par cons´ equent d’interrompre l’algorithme si
h k+1,k |e
T
k z k |/r
(0)
2 ≤ ε,
(4.61)
o` u ε > 0 est une tol´ erance fix´ ee.
La cons´ equence la plus importante du Th´ eor` eme 4.13 est que la m´ ethode
d’Arnoldi peut ˆ etre vue comme une m´ ethode directe, puisqu’elle fournit la
solution exacte apr` es un nombre fini d’it´ erations. Ceci n’est cependant plus
vrai en arithm´ etique `
a virgule flottante `
a cause de l’accumulation des erreurs
d’arrondi. De plus, si on prend en compte le coˆ ut ´ elev´ e du calcul (qui est de
l’ordre de 2(n z +mn) flops pour m ´ etapes et une matrice creuse d’ordre n ayant
n z coefficients non nuls) et la m´ emoire importante n´ ecessaire au stockage de
la matrice V m , on comprend que la m´ ethode d’Arnoldi ne peut ˆ etre utilis´ ee
telle quelle en pratique, sauf pour de petites valeurs de m.
De nombreux rem` edes existent contre ce probl` eme. Un d’entre eux consiste
` a pr´ econditionner le syst` eme (en utilisant, par exemple, un des pr´ econditionneurs de la Section 4.3.2). On peut aussi introduire des versions modifi´ ees de
la m´ ethode d’Arnoldi en suivant deux approches :
1. on effectue au plus m ´ etapes cons´ ecutives, m ´ etant un nombre petit fix´ e
(habituellement m 10). Si la m´ ethode ne converge pas, on pose x
(0) =
x
(m) et on recommence l’algorithme d’Arnoldi pour m nouvelles ´ etapes.
La proc´ edure est r´ ep´ et´ ee jusqu’` a convergence. Cette m´ ethode, appel´ ee
FOM(m) ou m´ ethode d’Arnoldi avec red´ emarrage (ou restart), permet de
r´ eduire l’occupation m´ emoire puisqu’elle ne n´ ecessite de stocker que des
matrices d’au plus m colonnes ;
2. on impose une limitation dans le nombre de directions qui entrent en
jeu dans le proc´ ed´ e d’orthogonalisation d’Arnoldi. On obtient alors la
m´ ethode d’orthogonalisation incompl` ete ou IOM. En pratique, la k-i` eme
´ etape de l’algorithme d’Arnoldi g´ en` ere un vecteur v k+1 qui est orthonormal aux q vecteurs pr´ ec´ edents, o` u q est fix´ e en fonction de la m´ emoire
disponible.
Il est important de noter que ces deux strat´ egies n’ont plus la propri´ et´ e de
donner la solution exacte apr` es un nombre fini d’it´ erations.
Le Programme 22 donne une impl´ ementation de l’algorithme d’Arnoldi
(FOM) avec un crit` ere d’arrˆ et bas´ e sur le r´ esidu (4.61). Le param` etre d’entr´ ee m est la taille maximale admissible des sous-espaces de Krylov. C’est par
cons´ equent le nombre maximum d’it´ erations.