150
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
I4 −3A+A
2 , et puisqu’il n’y a pas de polynˆ ome p1 de degr´ e 1 tel que p1(A)v = 0. Par
cons´ equent, tous les sous-espaces de Krylov ` a partir de K2(A; v) sont de dimension
2. Le vecteur w = [1, 1, −1, 1]
T est de degr´ e 4 par rapport `
a A.
•
Pour un m fix´ e, il est possible de calculer une base orthonormale de
K m (A; v) en utilisant l’algorithme d’Arnoldi.
En posant v 1 = v/v 2 , cette m´ ethode g´ en` ere une base orthonormale {v i }
de K m (A; v 1 ) en utilisant le proc´ ed´ e de Gram-Schmidt (voir Section 3.4.3).
Pour k = 1, . . . , m, l’algorithme d’Arnoldi consiste `
a calculer :
h ik = v
T
i Av k ,
i= 1, 2, . . ., k,
w k = Av k −
k
i=1
h ik v i , h k+1,k = w k 2 .
(4.53)
Si w k = 0, le processus s’interrompt (on parle de breakdown) ; autrement, on
pose v k+1 = w k /w k 2 et on reprend l’algorithme en augmentant k de 1.
On peut montrer que si la m´ ethode s’ach` eve ` a l’´ etape m, alors les vecteurs
v 1 , . . . , v m forment une base de K m (A; v). Dans ce cas, en notant V m ∈ R
n×m
la matrice dont les colonnes sont les vecteurs v i , on a
V
T
m AV m = H m , V
T
m+1 AV m =
H m ,
(4.54)
o` u
H m ∈ R
(m+1)×m est la matrice de Hessenberg sup´ erieure dont les coefficients h ij sont donn´ es par (4.53) et H m ∈ R
m×m est la restriction de
H m aux
m premi` eres lignes et m premi` eres colonnes.
L’algorithme s’interrompt `
a une ´ etape k < m si et seulement si deg A (v 1 ) =
k. Pour ce qui de la stabilit´ e, tout ce qui a ´ et´ e dit pour le proc´ ed´ e de GramSchmidt peut ˆ etre repris ici. Pour des variantes plus efficaces et plus stables
de (4.53), nous renvoyons `
a [Saa96].
Les fonctions arnoldi_alg et GSarnoldi du Programme 21, fournissent
une impl´ ementation MATLAB de l’algorithme d’Arnoldi. En sortie, les colonnes de V contiennent les vecteurs de la base construite, et la matrice H
stocke les coefficients h ik calcul´ es par l’algorithme. Si m ´ etapes sont effectu´ ees, V = V m et H(1 : m, 1 : m) = H m .
Programme 21 - arnoldialg : M´ ethode d’Arnoldi avec orthonormalisation de
Gram-Schmidt
function [V,H]=arnoldialg(A,v,m)
% ARNOLDIALG Algorithme d’Arnoldi
% [B,H]=ARNOLDIALG(A,V,M) construit pour un M fix´ e une base orthonormale
% B de K M(A,V) telle que VˆT*A*V=H.
v=v/norm(v,2); V=v; H=[]; k=0;
while k <= m-1
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
I4 −3A+A
2 , et puisqu’il n’y a pas de polynˆ ome p1 de degr´ e 1 tel que p1(A)v = 0. Par
cons´ equent, tous les sous-espaces de Krylov ` a partir de K2(A; v) sont de dimension
2. Le vecteur w = [1, 1, −1, 1]
T est de degr´ e 4 par rapport `
a A.
•
Pour un m fix´ e, il est possible de calculer une base orthonormale de
K m (A; v) en utilisant l’algorithme d’Arnoldi.
En posant v 1 = v/v 2 , cette m´ ethode g´ en` ere une base orthonormale {v i }
de K m (A; v 1 ) en utilisant le proc´ ed´ e de Gram-Schmidt (voir Section 3.4.3).
Pour k = 1, . . . , m, l’algorithme d’Arnoldi consiste `
a calculer :
h ik = v
T
i Av k ,
i= 1, 2, . . ., k,
w k = Av k −
k
i=1
h ik v i , h k+1,k = w k 2 .
(4.53)
Si w k = 0, le processus s’interrompt (on parle de breakdown) ; autrement, on
pose v k+1 = w k /w k 2 et on reprend l’algorithme en augmentant k de 1.
On peut montrer que si la m´ ethode s’ach` eve ` a l’´ etape m, alors les vecteurs
v 1 , . . . , v m forment une base de K m (A; v). Dans ce cas, en notant V m ∈ R
n×m
la matrice dont les colonnes sont les vecteurs v i , on a
V
T
m AV m = H m , V
T
m+1 AV m =
H m ,
(4.54)
o` u
H m ∈ R
(m+1)×m est la matrice de Hessenberg sup´ erieure dont les coefficients h ij sont donn´ es par (4.53) et H m ∈ R
m×m est la restriction de
H m aux
m premi` eres lignes et m premi` eres colonnes.
L’algorithme s’interrompt `
a une ´ etape k < m si et seulement si deg A (v 1 ) =
k. Pour ce qui de la stabilit´ e, tout ce qui a ´ et´ e dit pour le proc´ ed´ e de GramSchmidt peut ˆ etre repris ici. Pour des variantes plus efficaces et plus stables
de (4.53), nous renvoyons `
a [Saa96].
Les fonctions arnoldi_alg et GSarnoldi du Programme 21, fournissent
une impl´ ementation MATLAB de l’algorithme d’Arnoldi. En sortie, les colonnes de V contiennent les vecteurs de la base construite, et la matrice H
stocke les coefficients h ik calcul´ es par l’algorithme. Si m ´ etapes sont effectu´ ees, V = V m et H(1 : m, 1 : m) = H m .
Programme 21 - arnoldialg : M´ ethode d’Arnoldi avec orthonormalisation de
Gram-Schmidt
function [V,H]=arnoldialg(A,v,m)
% ARNOLDIALG Algorithme d’Arnoldi
% [B,H]=ARNOLDIALG(A,V,M) construit pour un M fix´ e une base orthonormale
% B de K M(A,V) telle que VˆT*A*V=H.
v=v/norm(v,2); V=v; H=[]; k=0;
while k <= m-1