152
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
aura donc ´ et´ e construite et on la supposera stock´ ee dans les vecteurs colonnes
de la matrice V k avec v 1 = r
(0) /r
(0)
2 . Dans ce cas, la nouvelle it´ er´ ee x
(k)
peut toujours s’´ ecrire comme
x
(k) = x
(0) + V k z
(k) ,
(4.57)
o` u z
(k) doit ˆ etre choisi selon un crit` ere donn´ e.
4.4.1 La m´ ethode d’Arnoldi pour les syst` emes lin´ eaires
Imposons ` a r
(k) d’ˆ etre orthogonal `
a K k (A; r
(0) ) en imposant (4.55) pour tous
les vecteurs de la base v i , i.e.
V
T
k r
(k) = 0.
(4.58)
Puisque r
(k) = b−Ax
(k) avec x
(k) de la forme (4.57), la relation (4.58) devient
V
T
k (b − Ax
(0) ) − V
T
k AV k z
(k) = V
T
k r
(0)
− V
T
k AV k z
(k) = 0.
(4.59)
Grˆ ace ` a l’orthonormalit´ e de la base et au choix de v 1 , on a V
T
k r
(0) = r
(0)
2 e 1 ,
e 1 ´ etant le premier vecteur unitaire de R
k . Avec (4.54), il d´ ecoule de (4.59)
que z
(k) est la solution du syst` eme lin´ eaire
H k z
(k) = r
(0)
2 e 1 .
(4.60)
Une fois z
(k) connu, on peut calculer x
(k) ` a partir de (4.57). Comme H k est
une matrice de Hessenberg sup´ erieure, on peut facilement r´ esoudre le syst` eme
lin´ eaire (4.60) en effectuant, par exemple, une factorisation LU de H k .
Remarquons qu’en arithm´ etique exacte la m´ ethode ne peut effectuer plus
de n ´ etapes et qu’elle s’ach` eve en m < n ´ etapes seulement si l’algorithme
d’Arnoldi s’interrompt. Pour la convergence de la m´ ethode, on a le r´ esultat
suivant.
Th´ eor` eme 4.13 En arithm´ etique exacte, la m´ ethode d’Arnoldi donne la solution de (3.2) apr` es au plus n it´ erations.
D´ emonstration. Si la m´ ethode s’arrˆ ete ` a la n-i` eme it´ eration, alors n´ ecessairement
x
(n) = x puisque Kn(A; r
(0) ) = R
n . Si la m´ ethode s’arrˆ ete ` a la m-i` eme it´ eration
(breakdown), pour un m < n, alors x
(m) = x. En effet, on inversant la premi` ere
relation de (4.54), on a
x
(m) = x
(0) + Vmz
(m) = x
(0) + VmH
−1
m V
T
m r
(0) = A
−1 b.
3
L’algorithme d’Arnoldi ne peut ˆ etre utilis´ e tel qu’on vient de le d´ ecrire, puisque
la solution ne serait calcul´ ee qu’apr` es avoir achev´ e l’ensemble du processus,
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
aura donc ´ et´ e construite et on la supposera stock´ ee dans les vecteurs colonnes
de la matrice V k avec v 1 = r
(0) /r
(0)
2 . Dans ce cas, la nouvelle it´ er´ ee x
(k)
peut toujours s’´ ecrire comme
x
(k) = x
(0) + V k z
(k) ,
(4.57)
o` u z
(k) doit ˆ etre choisi selon un crit` ere donn´ e.
4.4.1 La m´ ethode d’Arnoldi pour les syst` emes lin´ eaires
Imposons ` a r
(k) d’ˆ etre orthogonal `
a K k (A; r
(0) ) en imposant (4.55) pour tous
les vecteurs de la base v i , i.e.
V
T
k r
(k) = 0.
(4.58)
Puisque r
(k) = b−Ax
(k) avec x
(k) de la forme (4.57), la relation (4.58) devient
V
T
k (b − Ax
(0) ) − V
T
k AV k z
(k) = V
T
k r
(0)
− V
T
k AV k z
(k) = 0.
(4.59)
Grˆ ace ` a l’orthonormalit´ e de la base et au choix de v 1 , on a V
T
k r
(0) = r
(0)
2 e 1 ,
e 1 ´ etant le premier vecteur unitaire de R
k . Avec (4.54), il d´ ecoule de (4.59)
que z
(k) est la solution du syst` eme lin´ eaire
H k z
(k) = r
(0)
2 e 1 .
(4.60)
Une fois z
(k) connu, on peut calculer x
(k) ` a partir de (4.57). Comme H k est
une matrice de Hessenberg sup´ erieure, on peut facilement r´ esoudre le syst` eme
lin´ eaire (4.60) en effectuant, par exemple, une factorisation LU de H k .
Remarquons qu’en arithm´ etique exacte la m´ ethode ne peut effectuer plus
de n ´ etapes et qu’elle s’ach` eve en m < n ´ etapes seulement si l’algorithme
d’Arnoldi s’interrompt. Pour la convergence de la m´ ethode, on a le r´ esultat
suivant.
Th´ eor` eme 4.13 En arithm´ etique exacte, la m´ ethode d’Arnoldi donne la solution de (3.2) apr` es au plus n it´ erations.
D´ emonstration. Si la m´ ethode s’arrˆ ete ` a la n-i` eme it´ eration, alors n´ ecessairement
x
(n) = x puisque Kn(A; r
(0) ) = R
n . Si la m´ ethode s’arrˆ ete ` a la m-i` eme it´ eration
(breakdown), pour un m < n, alors x
(m) = x. En effet, on inversant la premi` ere
relation de (4.54), on a
x
(m) = x
(0) + Vmz
(m) = x
(0) + VmH
−1
m V
T
m r
(0) = A
−1 b.
3
L’algorithme d’Arnoldi ne peut ˆ etre utilis´ e tel qu’on vient de le d´ ecrire, puisque
la solution ne serait calcul´ ee qu’apr` es avoir achev´ e l’ensemble du processus,