4.4 M´ ethodes de Krylov
151
[k,V,H] = GSarnoldi(A,m,k,V,H);
end
return
function [k,V,H]=GSarnoldi(A,m,k,V,H)
% GSARNOLDI M´ ethode de Gram-Schmidt pour l’algorithme d’Arnoldi
k=k+1; H=[H,V(:,1:k)’*A*V(:,k)];
s=0;
for i=1:k
s=s+H(i,k)*V(:,i);
end
w=A*V(:,k)-s; H(k+1,k)=norm(w,2);
if H(k+1,k)>=eps & k V=[V,w/H(k+1,k)];
else
k=m+1;
end
return
Ayant d´ ecrit un algorithme pour construire la base d’un sous-espace de Krylov
d’ordre quelconque, nous pouvons maintenant r´ esoudre le syst` eme lin´ eaire
(3.2) par une m´ ethode de Krylov. Pour toutes ces m´ ethodes, le vecteur x
(k)
est toujours de la forme (4.52) et, pour un r
(0) donn´ e, x
(k) est choisi comme
´ etant l’unique ´ el´ ement de W k qui satisfait un crit` ere de distance minimale ` a
x. C’est la mani` ere de choisir x
(k) qui permet de distinguer deux m´ ethodes
de Krylov.
L’id´ ee la plus naturelle est de chercher x
(k)
∈ W k comme le vecteur qui
minimise la norme euclidienne de l’erreur. Mais cette approche n’est pas utilisable en pratique car x
(k) d´ ependrait alors de l’inconnue x.
Voici deux strat´ egies alternatives :
1. calculer x
(k)
∈ W k en imposant au r´ esidu r
(k) d’ˆ etre orthogonal `
a tout
vecteur de K k (A; r
(0) ), autrement dit on cherche x
(k)
∈ W k tel que
v
T (b − Ax
(k) ) = 0
∀v ∈ K k (A; r
(0) );
(4.55)
2. calculer x
(k)
∈ W k qui minimise la norme euclidienne du r´ esidu r
(k)
2 ,
c’est-` a-dire
b − Ax
(k)
2 = min
v∈Wk
b − Av 2 .
(4.56)
La relation (4.55) conduit `
a la m´ ethode d’Arnoldi pour les syst` emes lin´ eaires
(´ egalement connue sous le nom de FOM, pour full orthogonalization method),
tandis que (4.56) conduit `
a la m´ ethode GMRES.
Dans les deux prochaines sections, nous supposerons que k ´ etapes de l’algorithme d’Arnoldi auront ´ et´ e effectu´ ees. Une base orthonormale de K k (A; r
(0) )