5. Systèmes linéaires
123
base canonique de R
n
.L am a t r i c e e
K n est de la forme
e
K n =
3
E
E
E
E
E
E
E
E
E
C
k 1>1 k 1>2 === k 1>n1
k 1>n
k 2>1 k 2>2 === k 2>n1
k 2>n
0
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
00
. . . k n>n1
k n>n
00
===
0
k n+1>n
4
F
F
F
F
F
F
F
F
F
D
L’algorithme d’Arnoldi conduit à la relation
DY n = Y n+1 e
K n1
= Y n K n + k n+1>n y n h
w
n
D’où on déduit la relation
Y
w
n DY n = K n
Partant du vecteur y 1 = y@ kyk, l’algorithme d’Arnoldi calcule pour n
=1> ===> p 1> les quantités
;
A A ?
A A =
z = Dy n
Pour l =1à n> Faire k l>n = y
w
l z, z = z k l>n y l
k n+1>n = kzk
Si k n+1>n =0alors Stop Sinon y n+1 = z@k n+1>n
La solution de l’équation D{ = e est obtenue en déterminant le vecteur | p
solution du système
K p | p = h 1
où est la norme du résidu initial = ku 0 k = ke D{ 0 k et h 1 =(1> 0> ===> 0).
La solution approchée { p est alors
{ p = { 0 + Y p | p
L’espace mémoire utilisé est de l’ordre de pq, ce qui correspond au stockage de m vecteurs de taille n. Pour réduire la taille de l’espace de Krylov
K p (D> y), on procède à des redémarrages. Ceci correspond à appliquer la
méthode d’Arnoldi pour un nombre p de pas, puis à utiliser la solution
obtenue comme vecteur initial d’un nouvel ensemble de p pas.