5.6 La m´ ethode QR pour les matrices de Hessenberg
187
[Dat95], Th´ eor` eme 8.5.4, p. 418) :
A 1 = HAH =
λ 1 b
T
0
A 2
,
o` u b ∈ R
n−1 , H est la matrice de Householder telle que Hx 1 = αx 1 pour
α ∈ R, et o` u les valeurs propres de A 2 ∈ R
(n−1)×(n−1) sont les mˆ emes que
celles de A, except´ ee λ 1 . La matrice H peut ˆ etre calcul´ ee en utilisant (5.38)
avec v = x 1 ± ±x 1 2 e 1 .
La m´ ethode de d´ eflation consiste ` a calculer la seconde valeur propre dominante (ou “sous-dominante”) de A en appliquant la m´ ethode de la puissance `
a
A 2 , `
a condition que λ 2 et λ 3 aient des modules distincts. Une fois calcul´ ee λ 2 ,
le vecteur propre correspondant x 2 peut ˆ etre calcul´ e en appliquant la m´ ethode
de la puissance inverse ` a la matrice A avec µ = λ 2 (voir Section 5.3.2). On
proc` ede de mˆ eme pour les autres valeurs propres et vecteurs propres de A.
5.6.2 R´ eduction d’une matrice sous la forme de Hessenberg
Une matrice A∈ R
n×n peut ˆ etre transform´ ee en une matrice semblable de la
forme de Hessenberg sup´ erieure avec un coˆ ut de l’ordre de n
3 flops. L’algorithme n´ ecessite n − 2 ´ etapes et la transformation Q peut ˆ etre calcul´ ee comme
produit de matrices de Householder P (1) · · · P (n−2) . C’est pourquoi ce proc´ ed´ e
de r´ eduction est connu sous le nom de m´ ethode de Householder.
La k-i` eme ´ etape consiste ` a transformer A ` a l’aide d’une matrice de Householder P (k) afin d’annuler les ´ el´ ements situ´ es sur les lignes k + 2, . . . , n de la
k-i` eme colonne de A, pour k = 1, . . ., (n−2) (voir Section 5.6.1). Par exemple,
dans le cas n = 4, le processus de r´ eduction donne :
⎡
⎢
⎢
⎢
⎢
⎢
⎣
• • • •
• • • •
• • • •
• • • •
⎤
⎥
⎥
⎥
⎥
⎥
⎦
−→
P (1)
⎡
⎢
⎢
⎢
⎢
⎢
⎣
• • • •
• • • •
0 • • •
0 • • •
⎤
⎥
⎥
⎥
⎥
⎥
⎦
−→
P (2)
⎡
⎢
⎢
⎢
⎢
⎢
⎣
• • • •
• • • •
0 • • •
0 0 • •
⎤
⎥
⎥
⎥
⎥
⎥
⎦
,
o` u les • d´ esignent les coefficients de la matrice a priori non nuls. Etant donn´ e
A
(0) = A, la m´ ethode g´ en` ere une suite de matrices A
(k) qui sont orthogonalement semblables ` a A
A
(k) = P
T
(k) A
(k−1) P (k) = (P (k) · · · P (1) )
T A(P (k) · · · P (1) )
= Q
T
(k) AQ (k) ,
k ≥ 1.
(5.45)
Pour tout k ≥ 1 la matrice P (k) est donn´ ee par (5.41), o` u x est remplac´ e par le
k-i` eme vecteur colonne de A
(k−1) . D’apr` es la d´ efinition (5.41), il est facile de
v´ erifier que l’op´ eration P
T
(k) A
(k−1) laisse inchang´ ees les k premi` eres lignes de
A
(k−1) , tandis que P
T
(k) A
(k−1) P (k) = A
(k) fait de mˆ eme pour les k premi` eres
187
[Dat95], Th´ eor` eme 8.5.4, p. 418) :
A 1 = HAH =
λ 1 b
T
0
A 2
,
o` u b ∈ R
n−1 , H est la matrice de Householder telle que Hx 1 = αx 1 pour
α ∈ R, et o` u les valeurs propres de A 2 ∈ R
(n−1)×(n−1) sont les mˆ emes que
celles de A, except´ ee λ 1 . La matrice H peut ˆ etre calcul´ ee en utilisant (5.38)
avec v = x 1 ± ±x 1 2 e 1 .
La m´ ethode de d´ eflation consiste ` a calculer la seconde valeur propre dominante (ou “sous-dominante”) de A en appliquant la m´ ethode de la puissance `
a
A 2 , `
a condition que λ 2 et λ 3 aient des modules distincts. Une fois calcul´ ee λ 2 ,
le vecteur propre correspondant x 2 peut ˆ etre calcul´ e en appliquant la m´ ethode
de la puissance inverse ` a la matrice A avec µ = λ 2 (voir Section 5.3.2). On
proc` ede de mˆ eme pour les autres valeurs propres et vecteurs propres de A.
5.6.2 R´ eduction d’une matrice sous la forme de Hessenberg
Une matrice A∈ R
n×n peut ˆ etre transform´ ee en une matrice semblable de la
forme de Hessenberg sup´ erieure avec un coˆ ut de l’ordre de n
3 flops. L’algorithme n´ ecessite n − 2 ´ etapes et la transformation Q peut ˆ etre calcul´ ee comme
produit de matrices de Householder P (1) · · · P (n−2) . C’est pourquoi ce proc´ ed´ e
de r´ eduction est connu sous le nom de m´ ethode de Householder.
La k-i` eme ´ etape consiste ` a transformer A ` a l’aide d’une matrice de Householder P (k) afin d’annuler les ´ el´ ements situ´ es sur les lignes k + 2, . . . , n de la
k-i` eme colonne de A, pour k = 1, . . ., (n−2) (voir Section 5.6.1). Par exemple,
dans le cas n = 4, le processus de r´ eduction donne :
⎡
⎢
⎢
⎢
⎢
⎢
⎣
• • • •
• • • •
• • • •
• • • •
⎤
⎥
⎥
⎥
⎥
⎥
⎦
−→
P (1)
⎡
⎢
⎢
⎢
⎢
⎢
⎣
• • • •
• • • •
0 • • •
0 • • •
⎤
⎥
⎥
⎥
⎥
⎥
⎦
−→
P (2)
⎡
⎢
⎢
⎢
⎢
⎢
⎣
• • • •
• • • •
0 • • •
0 0 • •
⎤
⎥
⎥
⎥
⎥
⎥
⎦
,
o` u les • d´ esignent les coefficients de la matrice a priori non nuls. Etant donn´ e
A
(0) = A, la m´ ethode g´ en` ere une suite de matrices A
(k) qui sont orthogonalement semblables ` a A
A
(k) = P
T
(k) A
(k−1) P (k) = (P (k) · · · P (1) )
T A(P (k) · · · P (1) )
= Q
T
(k) AQ (k) ,
k ≥ 1.
(5.45)
Pour tout k ≥ 1 la matrice P (k) est donn´ ee par (5.41), o` u x est remplac´ e par le
k-i` eme vecteur colonne de A
(k−1) . D’apr` es la d´ efinition (5.41), il est facile de
v´ erifier que l’op´ eration P
T
(k) A
(k−1) laisse inchang´ ees les k premi` eres lignes de
A
(k−1) , tandis que P
T
(k) A
(k−1) P (k) = A
(k) fait de mˆ eme pour les k premi` eres