5.5 La m´ ethode QR “de base”
181
ˆ etre triangulaire sup´ erieure. Si c’´ etait le cas, les valeurs propres de T seraient
n´ ecessairement r´ eelles et T semblable ` a A, ce qui est contradictoire.
Il peut aussi ne pas y avoir convergence vers une matrice triangulaire dans
des situations plus g´ en´ erales comme le montre l’Exemple 5.9.
Pour cette raison, il est n´ ecessaire d’introduire des variantes de la m´ ethode
QR (5.32) bas´ ees sur des techniques de translation et d´ eflation (voir Section
5.7 et, pour une discussion plus d´ etaill´ ee sur ce sujet, voir [GL89], Chapitre
7, [Dat95], Chapitre 8 et [Dem97], Chapitre 4).
Ces techniques permettent ` a T
(k) de converger vers une matrice quasitriangulaire sup´ erieure, connue sous le nom de d´ ecomposition de Schur r´ eelle
de A, pour laquelle on a le r´ esultat suivant (nous renvoyons `
a [GL89], p.
341-342 pour la preuve).
Propri´ et´ e 5.7 Etant donn´ e une matrice A ∈ R
n×n , il existe une matrice
orthogonale Q ∈ R
n×n telle que
Q
T AQ =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
R 11 R 12 . . . R 1m
0
R 22 . . . R 2m
. . .
. . .
. . .
. . .
0
0
. . . R mm
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
(5.34)
o` u chaque bloc diagonal R ii est soit un nombre r´ eel soit une matrice d’ordre
2 ayant des valeurs propres complexes conjugu´ ees. De plus
Q = lim
k→∞
Q
(0) Q
(1)
· · · Q
(k)
(5.35)
o` u Q
(k) est la matrice orthogonale construite `
a la k-i` eme ´ etape de la m´ ethode
QR (5.32).
5.5 La m´ ethode QR “de base”
Dans la forme “basique” de la m´ ethode QR, on pose Q
(0) = I n de sorte que
T
(0) = A. A chaque it´ eration k ≥ 1, la factorisation QR de la matrice T
(k−1)
peut ˆ etre effectu´ ee en utilisant le proc´ ed´ e de Gram-Schmidt modifi´ e d´ ecrit ` a
la Section 3.4.3, ce qui repr´ esente un coˆ ut de l’ordre de 2n
3 flops (pour une
matrice pleine). On a le r´ esultat de convergence suivant (pour la preuve, voir
[GL89], Th´ eor` eme 7.3.1, ou [Wil65], p. 517-519) :
Propri´ et´ e 5.8 (convergence de la m´ ethode QR) Soit A ∈ R
n×n une
matrice telle que
|λ 1 | > |λ 2 | > . . . > |λ n |.
181
ˆ etre triangulaire sup´ erieure. Si c’´ etait le cas, les valeurs propres de T seraient
n´ ecessairement r´ eelles et T semblable ` a A, ce qui est contradictoire.
Il peut aussi ne pas y avoir convergence vers une matrice triangulaire dans
des situations plus g´ en´ erales comme le montre l’Exemple 5.9.
Pour cette raison, il est n´ ecessaire d’introduire des variantes de la m´ ethode
QR (5.32) bas´ ees sur des techniques de translation et d´ eflation (voir Section
5.7 et, pour une discussion plus d´ etaill´ ee sur ce sujet, voir [GL89], Chapitre
7, [Dat95], Chapitre 8 et [Dem97], Chapitre 4).
Ces techniques permettent ` a T
(k) de converger vers une matrice quasitriangulaire sup´ erieure, connue sous le nom de d´ ecomposition de Schur r´ eelle
de A, pour laquelle on a le r´ esultat suivant (nous renvoyons `
a [GL89], p.
341-342 pour la preuve).
Propri´ et´ e 5.7 Etant donn´ e une matrice A ∈ R
n×n , il existe une matrice
orthogonale Q ∈ R
n×n telle que
Q
T AQ =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
R 11 R 12 . . . R 1m
0
R 22 . . . R 2m
. . .
. . .
. . .
. . .
0
0
. . . R mm
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
(5.34)
o` u chaque bloc diagonal R ii est soit un nombre r´ eel soit une matrice d’ordre
2 ayant des valeurs propres complexes conjugu´ ees. De plus
Q = lim
k→∞
Q
(0) Q
(1)
· · · Q
(k)
(5.35)
o` u Q
(k) est la matrice orthogonale construite `
a la k-i` eme ´ etape de la m´ ethode
QR (5.32).
5.5 La m´ ethode QR “de base”
Dans la forme “basique” de la m´ ethode QR, on pose Q
(0) = I n de sorte que
T
(0) = A. A chaque it´ eration k ≥ 1, la factorisation QR de la matrice T
(k−1)
peut ˆ etre effectu´ ee en utilisant le proc´ ed´ e de Gram-Schmidt modifi´ e d´ ecrit ` a
la Section 3.4.3, ce qui repr´ esente un coˆ ut de l’ordre de 2n
3 flops (pour une
matrice pleine). On a le r´ esultat de convergence suivant (pour la preuve, voir
[GL89], Th´ eor` eme 7.3.1, ou [Wil65], p. 517-519) :
Propri´ et´ e 5.8 (convergence de la m´ ethode QR) Soit A ∈ R
n×n une
matrice telle que
|λ 1 | > |λ 2 | > . . . > |λ n |.