5.6 La m´ ethode QR pour les matrices de Hessenberg
189
doit ˆ etre triadiagonale sym´ etrique. Le Programme 27 donne le r´ esultat suivant
Q =
⎡
⎢
⎢
⎢
⎢
⎢
⎣
1.00 0
0
0
0
0.77 −0.61
0.20
0
0.51
0.40 −0.76
0
0.38
0.69
0.61
⎤
⎥
⎥
⎥
⎥
⎥
⎦
, H =
⎡
⎢
⎢
⎢
⎢
⎢
⎣
1.00 0.65 0
0
0.65 0.65 0.06
0
0
0.06 0.02
0.001
0
0 0 .001 0.0003
⎤
⎥
⎥
⎥
⎥
⎥
⎦
.
La pr´ ecision de la transformation (5.45) peut ˆ etre mesur´ ee en calculant la norme
· ·F de la diff´ erence entre H et Q
T H4Q. On trouve H − Q
T H4QF = 3.38 · 10
−17 ,
ce qui confirme l’in´ egalit´ e de stabilit´ e (5.46).
•
5.6.3 Factorisation QR d’une matrice de Hessenberg
Nous expliquons dans cette section comment impl´ ementer efficacement une
´ etape de la m´ ethode QR quand on part d’une matrice T
(0) = H
(0) sous la
forme de Hessenberg sup´ erieure.
Pour tout k ≥ 1, la premi` ere phase consiste ` a calculer la factorisation QR
de H
(k−1) au moyen de n − 1 rotations de Givens
Q
(k)
T
H
(k−1) =
G
(k)
n−1
T · · ·
G
(k)
1
T
H
(k−1) = R
(k) ,
(5.47)
o` u, pour j = 1, . . ., n − 1, G
(k)
j
= G(j, j + 1, θ j )
(k) est, pour k ≥ 1, la ji` eme matrice de rotation de Givens (5.43) dans laquelle θ j est choisi d’apr` es
(5.44) de mani` ere ` a ce que les coefficients d’indices (j + 1, j) de la matrice
G
(k)
j
T · · ·
G
(k)
1
T
H
(k−1) soient nuls. Le coˆ ut du produit (5.47) est
de l’ordre de 3n
2 flops.
L’´ etape suivante consiste ` a compl´ eter la transformation orthogonale
H
(k) = R
(k) Q
(k) = R
(k)
G
(k)
1 · · · G
(k)
n−1
.
(5.48)
La matrice orthogonale Q
(k) =
G
(k)
1 · · · G
(k)
n−1
est de la forme de Hessenberg
sup´ erieure. En effet, en prenant par exemple n = 3, on obtient (d’apr` es la
Section 5.6.1)
Q
(k) = G
(k)
1 G
(k)
2 =
⎡
⎢
⎢
⎣
• • 0
• • 0
0 0 1
⎤
⎥
⎥
⎦
⎡
⎢
⎢
⎣
1 0 0
0 • •
0 • •
⎤
⎥
⎥
⎦ =
⎡
⎢
⎢
⎣
• • •
• • •
0 • •
⎤
⎥
⎥
⎦ .
Le coˆ ut de (5.48) est ´ egalement de l’ordre de 3n
2 op´ erations, le coˆ ut total
est donc de l’ordre de 6n
2 flops. En conclusion, effectuer la factorisation QR
en utilisant les rotations de Givens sur une matrice de d´ epart de Hessenberg
sup´ erieure entraine une r´ eduction du coˆ ut de calcul d’un ordre de grandeur
par rapport `
a la factorisation utilisant le proc´ ed´ e de Gram-Schmidt modifi´ e
de la Section 5.5.
189
doit ˆ etre triadiagonale sym´ etrique. Le Programme 27 donne le r´ esultat suivant
Q =
⎡
⎢
⎢
⎢
⎢
⎢
⎣
1.00 0
0
0
0
0.77 −0.61
0.20
0
0.51
0.40 −0.76
0
0.38
0.69
0.61
⎤
⎥
⎥
⎥
⎥
⎥
⎦
, H =
⎡
⎢
⎢
⎢
⎢
⎢
⎣
1.00 0.65 0
0
0.65 0.65 0.06
0
0
0.06 0.02
0.001
0
0 0 .001 0.0003
⎤
⎥
⎥
⎥
⎥
⎥
⎦
.
La pr´ ecision de la transformation (5.45) peut ˆ etre mesur´ ee en calculant la norme
· ·F de la diff´ erence entre H et Q
T H4Q. On trouve H − Q
T H4QF = 3.38 · 10
−17 ,
ce qui confirme l’in´ egalit´ e de stabilit´ e (5.46).
•
5.6.3 Factorisation QR d’une matrice de Hessenberg
Nous expliquons dans cette section comment impl´ ementer efficacement une
´ etape de la m´ ethode QR quand on part d’une matrice T
(0) = H
(0) sous la
forme de Hessenberg sup´ erieure.
Pour tout k ≥ 1, la premi` ere phase consiste ` a calculer la factorisation QR
de H
(k−1) au moyen de n − 1 rotations de Givens
Q
(k)
T
H
(k−1) =
G
(k)
n−1
T · · ·
G
(k)
1
T
H
(k−1) = R
(k) ,
(5.47)
o` u, pour j = 1, . . ., n − 1, G
(k)
j
= G(j, j + 1, θ j )
(k) est, pour k ≥ 1, la ji` eme matrice de rotation de Givens (5.43) dans laquelle θ j est choisi d’apr` es
(5.44) de mani` ere ` a ce que les coefficients d’indices (j + 1, j) de la matrice
G
(k)
j
T · · ·
G
(k)
1
T
H
(k−1) soient nuls. Le coˆ ut du produit (5.47) est
de l’ordre de 3n
2 flops.
L’´ etape suivante consiste ` a compl´ eter la transformation orthogonale
H
(k) = R
(k) Q
(k) = R
(k)
G
(k)
1 · · · G
(k)
n−1
.
(5.48)
La matrice orthogonale Q
(k) =
G
(k)
1 · · · G
(k)
n−1
est de la forme de Hessenberg
sup´ erieure. En effet, en prenant par exemple n = 3, on obtient (d’apr` es la
Section 5.6.1)
Q
(k) = G
(k)
1 G
(k)
2 =
⎡
⎢
⎢
⎣
• • 0
• • 0
0 0 1
⎤
⎥
⎥
⎦
⎡
⎢
⎢
⎣
1 0 0
0 • •
0 • •
⎤
⎥
⎥
⎦ =
⎡
⎢
⎢
⎣
• • •
• • •
0 • •
⎤
⎥
⎥
⎦ .
Le coˆ ut de (5.48) est ´ egalement de l’ordre de 3n
2 op´ erations, le coˆ ut total
est donc de l’ordre de 6n
2 flops. En conclusion, effectuer la factorisation QR
en utilisant les rotations de Givens sur une matrice de d´ epart de Hessenberg
sup´ erieure entraine une r´ eduction du coˆ ut de calcul d’un ordre de grandeur
par rapport `
a la factorisation utilisant le proc´ ed´ e de Gram-Schmidt modifi´ e
de la Section 5.5.