4.4 M´ ethodes de Krylov
149
Autrement dit r
(k) = p k (A)r
(0) , o` u p k (A) est un polynˆ ome en A de degr´ e k.
Si on d´ efinit l’espace
K m (A; v) = vect
v, Av, . . ., A
m−1 v
,
(4.50)
il est imm´ ediat d’apr` es (4.49) que r
(k)
∈ K k+1 (A; r
(0) ). L’espace (4.50) est
appel´ e sous-espace de Krylov d’ordre m. C’est un sous-espace de l’espace engendr´ e par tous les vecteurs u ∈ R
n de la forme u = p m−1 (A)v, o` u p m−1 est
un polynˆ ome en A de degr´ e ≤ m − 1.
De mani` ere analogue ` a (4.49), on montre que l’it´ er´ ee x
(k) de la m´ ethode
de Richardson est donn´ ee par
x
(k) = x
(0) +
k−1
j=0
α j r
(j) .
L’it´ er´ ee x
(k) appartient donc `
a l’espace
W k =
v = x
(0) + y, y ∈ K k (A; r
(0) )
.
(4.51)
Remarquer aussi que
k−1
j=0 α j r
(j) est un polynˆ ome en A de degr´ e inf´ erieur
` a k − 1. Dans la m´ ethode de Richardson non pr´ econditionn´ ee, on cherche
donc une valeur approch´ ee de x dans l’espace W k . Plus g´ en´ eralement, on peut
imaginer des m´ ethodes dans lesquelles on recherche des solutions approch´ ees
de la forme
x
(k) = x
(0) + q k−1 (A)r
(0) ,
(4.52)
o` u q k−1 est un polynˆ ome choisi de mani` ere ` a ce que x
(k) soit, dans un sens `
a
pr´ eciser, la meilleure approximation de x dans W k . Une m´ ethode dans laquelle
on recherche une solution de la forme (4.52) avec W k d´ efini par (4.51) est
appel´ ee m´ ethode de Krylov.
On a le r´ esultat suivant :
Propri´ et´ e 4.6 Soit A ∈ R
n×n et v ∈ R
n . On d´ efinit le degr´ e de v par rapport
` a A , not´ e deg A (v), comme ´ etant le degr´ e minimum des polynˆ omes non nuls
p tels que p(A)v = 0. Le sous-espace de Krylov K m (A; v) a une dimension
´ egale `
a m si et seulement si le degr´ e de v par rapport `
a A est strictement
sup´ erieur `
a m.
La dimension de K m (A; v) est donc ´ egale au minimum entre m et le degr´ e de
v par rapport `
a A. Par cons´ equent, la dimension des sous-espaces de Krylov
est une fonction croissante de m. Remarquer que le degr´ e de v ne peut pas ˆ etre
plus grand que n d’apr` es le th´ eor` eme de Cayley-Hamilton (voir Section 1.7).
Exemple 4.7 Consid´ erons la matrice A = tridiag 4 (−1, 2, −1). Le vecteur v =
[1, 1, 1, 1]
T est de degr´ e 2 par rapport `
a A puisque p2(A)v = 0 avec p2(A) =
149
Autrement dit r
(k) = p k (A)r
(0) , o` u p k (A) est un polynˆ ome en A de degr´ e k.
Si on d´ efinit l’espace
K m (A; v) = vect
v, Av, . . ., A
m−1 v
,
(4.50)
il est imm´ ediat d’apr` es (4.49) que r
(k)
∈ K k+1 (A; r
(0) ). L’espace (4.50) est
appel´ e sous-espace de Krylov d’ordre m. C’est un sous-espace de l’espace engendr´ e par tous les vecteurs u ∈ R
n de la forme u = p m−1 (A)v, o` u p m−1 est
un polynˆ ome en A de degr´ e ≤ m − 1.
De mani` ere analogue ` a (4.49), on montre que l’it´ er´ ee x
(k) de la m´ ethode
de Richardson est donn´ ee par
x
(k) = x
(0) +
k−1
j=0
α j r
(j) .
L’it´ er´ ee x
(k) appartient donc `
a l’espace
W k =
v = x
(0) + y, y ∈ K k (A; r
(0) )
.
(4.51)
Remarquer aussi que
k−1
j=0 α j r
(j) est un polynˆ ome en A de degr´ e inf´ erieur
` a k − 1. Dans la m´ ethode de Richardson non pr´ econditionn´ ee, on cherche
donc une valeur approch´ ee de x dans l’espace W k . Plus g´ en´ eralement, on peut
imaginer des m´ ethodes dans lesquelles on recherche des solutions approch´ ees
de la forme
x
(k) = x
(0) + q k−1 (A)r
(0) ,
(4.52)
o` u q k−1 est un polynˆ ome choisi de mani` ere ` a ce que x
(k) soit, dans un sens `
a
pr´ eciser, la meilleure approximation de x dans W k . Une m´ ethode dans laquelle
on recherche une solution de la forme (4.52) avec W k d´ efini par (4.51) est
appel´ ee m´ ethode de Krylov.
On a le r´ esultat suivant :
Propri´ et´ e 4.6 Soit A ∈ R
n×n et v ∈ R
n . On d´ efinit le degr´ e de v par rapport
` a A , not´ e deg A (v), comme ´ etant le degr´ e minimum des polynˆ omes non nuls
p tels que p(A)v = 0. Le sous-espace de Krylov K m (A; v) a une dimension
´ egale `
a m si et seulement si le degr´ e de v par rapport `
a A est strictement
sup´ erieur `
a m.
La dimension de K m (A; v) est donc ´ egale au minimum entre m et le degr´ e de
v par rapport `
a A. Par cons´ equent, la dimension des sous-espaces de Krylov
est une fonction croissante de m. Remarquer que le degr´ e de v ne peut pas ˆ etre
plus grand que n d’apr` es le th´ eor` eme de Cayley-Hamilton (voir Section 1.7).
Exemple 4.7 Consid´ erons la matrice A = tridiag 4 (−1, 2, −1). Le vecteur v =
[1, 1, 1, 1]
T est de degr´ e 2 par rapport `
a A puisque p2(A)v = 0 avec p2(A) =