5.6 La m´ ethode QR pour les matrices de Hessenberg
185
Si, pour k ≥ 1, on veut laisser les k premi` eres composantes de x inchang´ ees
et annuler toutes les composantes ` a partir de la k + 2-i` eme, la matrice de
Householder P = P (k) prend la forme suivante
P (k) =
⎡
⎣
I k
0
0 R n−k
⎤
⎦ , R n−k = I n−k − 2
w
(k) (w
(k) )
T
w (k) 2
2
.
(5.41)
Comme d’habitude, I k est la matrice identit´ e d’ordre k, et R n−k est la matrice
de Householder ´ el´ ementaire d’ordre n − k associ´ ee ` a la sym´ etrie par rapport
` a l’hyperplan orthogonal au vecteur w
(k)
∈ R
n−k . D’apr` es (5.39), le vecteur
de Householder est donn´ e par
w
(k) = x
(n−k)
± ±x
(n−k)
2 e
(n−k)
1
,
(5.42)
o` u x
(n−k)
∈ R
n−k est le vecteur constitu´ e par les n − k derni` eres composantes
de x et e
(n−k)
1
est le premier vecteur de la base canonique de R
n−k . Nous discuterons ` a la Section 5.6.5 d’un crit` ere pour choisir le signe dans la d´ efinition
de w
(k) .
Les composantes du vecteur y = P (k) x sont
⎧
⎪ ⎪ ⎨
⎪ ⎪ ⎩
y j = x j
j = 1, . . ., k,
y j = 0
j = k + 2, . . . , n,
y k+1 = ±±x
(n−k)
2 .
Nous utiliserons les matrices de Householder ` a la Section 5.6.2 pour transformer une matrice A en une matrice de Hessenberg sup´ erieure H
(0) . Ceci constitue la premi` ere ´ etape d’une impl´ ementation efficace de la m´ ethode QR (5.32)
avec T
(0) = H
(0) .
Exemple 5.6 Soient x=[1, 2, 3, 4, 5]
T et k = 1 (ce qui signifie qu’on veut annuler
les composantes xj pour j = 3, 4, 5). La matrice P (1) et le vecteur y=P (1) x sont
donn´ es par
P (1) =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1 0
0
0
0
0 0.2722
0.4082
0.5443
0.6804
0 0.4082
0.7710 −0.3053 −0.3816
0 0.5443 −0.3053
0.5929 −0.5089
0 0.6804 −0.3816 −0.5089
0.3639
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
, y =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1
7.3485
0
0
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
•
Les matrices ´ el´ ementaires de Givens sont des matrices orthogonales de rotation qui permettent d’annuler certains coefficients d’un vecteur ou d’une
185
Si, pour k ≥ 1, on veut laisser les k premi` eres composantes de x inchang´ ees
et annuler toutes les composantes ` a partir de la k + 2-i` eme, la matrice de
Householder P = P (k) prend la forme suivante
P (k) =
⎡
⎣
I k
0
0 R n−k
⎤
⎦ , R n−k = I n−k − 2
w
(k) (w
(k) )
T
w (k) 2
2
.
(5.41)
Comme d’habitude, I k est la matrice identit´ e d’ordre k, et R n−k est la matrice
de Householder ´ el´ ementaire d’ordre n − k associ´ ee ` a la sym´ etrie par rapport
` a l’hyperplan orthogonal au vecteur w
(k)
∈ R
n−k . D’apr` es (5.39), le vecteur
de Householder est donn´ e par
w
(k) = x
(n−k)
± ±x
(n−k)
2 e
(n−k)
1
,
(5.42)
o` u x
(n−k)
∈ R
n−k est le vecteur constitu´ e par les n − k derni` eres composantes
de x et e
(n−k)
1
est le premier vecteur de la base canonique de R
n−k . Nous discuterons ` a la Section 5.6.5 d’un crit` ere pour choisir le signe dans la d´ efinition
de w
(k) .
Les composantes du vecteur y = P (k) x sont
⎧
⎪ ⎪ ⎨
⎪ ⎪ ⎩
y j = x j
j = 1, . . ., k,
y j = 0
j = k + 2, . . . , n,
y k+1 = ±±x
(n−k)
2 .
Nous utiliserons les matrices de Householder ` a la Section 5.6.2 pour transformer une matrice A en une matrice de Hessenberg sup´ erieure H
(0) . Ceci constitue la premi` ere ´ etape d’une impl´ ementation efficace de la m´ ethode QR (5.32)
avec T
(0) = H
(0) .
Exemple 5.6 Soient x=[1, 2, 3, 4, 5]
T et k = 1 (ce qui signifie qu’on veut annuler
les composantes xj pour j = 3, 4, 5). La matrice P (1) et le vecteur y=P (1) x sont
donn´ es par
P (1) =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1 0
0
0
0
0 0.2722
0.4082
0.5443
0.6804
0 0.4082
0.7710 −0.3053 −0.3816
0 0.5443 −0.3053
0.5929 −0.5089
0 0.6804 −0.3816 −0.5089
0.3639
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
, y =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1
7.3485
0
0
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
•
Les matrices ´ el´ ementaires de Givens sont des matrices orthogonales de rotation qui permettent d’annuler certains coefficients d’un vecteur ou d’une