Agrégation 2018/2019
Méthode QR
Leçons : 157 ; 162 ; 233
Références : CIARLET, Introduction à l’analyse numérique matricielle et à
l’optimisation (p.124)
Prérequis :
- La décomposition QR est un produit d’une matrice unitaire (i.e Q∗ Q = In ) et d’une matrice
triangulaire supérieure dont les coefficients diagonaux sont réels et strictement positifs
- La décomposition LU est un produit d’une matrice inférieure avec des 1 sur la diagonale et
d’une matrice triangulaire supérieure.
- L’application (
Un (C) × Tn+ (C) → GLn (C)
(Q, R) 7→ QR
est un homéomorphisme. 1
Introduction :
La méthode QR que nous présenterons ci-dessous est l’outil le plus utilisé pour calculer
les valeurs propres d’une matrice quelconque (pas forcément symétrique). Pour les matrices
symétriques, cette méthode est aussi efficace que la méthode de Jacobi. Pour tout A ∈ GLn (C),
on va faire converger une suite de matrices vers une matrice triangulaire ayant sur sa diagonale
les valeurs propres de A.
Théorème 1. Soient A ∈ GLn (C) et λ1 , . . . , λn ∈ C vérifiant
|λ1 | > |λ2 | > · · · > |λn | > 0
tels qu’il existe une matrice inversible P d’inverse admettant une décomposition LU et que l’on
ait
λ1
−1
P AP = D =
..
.
λn
Alors la suite définie par
(
A1 = A
Ak+1 = Rk Qk où Qk Rk est la décomposition QR de Ak
converge vers une matrice triangulaire supérieure dont la diagonale est diag(λ1 , . . . , λn ). 2
1. Tn+ (C) est l’ensemble des matrices triangulaires supérieures de Mn (C) à coefficients diagonaux réels stricte-
ment positifs.
2. Attention, cet énoncé n’est pas complètement exacte, car les coefficients strictement au dessus de la diagonale
peuvent ne pas converger (osciller par exemple), il faut comprendre que la diagonale de la suite (An ) converge vers
les valeurs propres (λ1 , · · · , λn ) et les coefficients strictement sous la diagonale convergent vers 0.
ENS Rennes - Université de Rennes 1 1 Pierre Le Barbenchon
Agrégation 2018/2019
Démonstration. On notera Q(k) = Q1 . . . Qk et R(k) = Rk . . . R1 . On a alors
Ak = Q(k) R(k)
que l’on peut prouver par un calcul 3 . On a aussi
Ak+1 = Q(k)∗ AQ(k)
que l’on peut prouver par récurrence 4 .
L’idée est de trouver l’expression de Q(k) pour avoir le comportement de Ak et pour trouver
Q on va trouver la décomposition QR de Ak d’une autre manière.
(k)
Étape 1 : Trouver la décomposition QR de Ak d’une autre manière
On a Ak = P Dk P −1 , donc en notant QR la décomposition QR de P 5 , on a
Ak = QRDk LU = QR(Dk LD−k )Dk U
On veut étudier le comportement de Dk LD−k . Grâce à la décroissance des modules des λi et du
fait qu’il y a des coefficients 1 sur la diagonale de L, on a Dk LD−k converge vers In 6
Ainsi on a aussi RDk LD−k R−1 qui converge vers In quand k tend vers l’infini. On note
maintenant Ok Tk la décomposition QR de RDk LD−k R−1 . De ce fait, par l’homéomorphisme de
la décomposition QR et comme Ok Tk converge vers In alors on a aussi Ok et Tk qui convergent
vers In .
Pour l’instant, on a
Ak = (QOk )(Tk RDk U )
QOk est bien unitaire car Q et Ok le sont. De plus, Tk RDk U est triangulaire supérieure mais elle
n’est pas à diagonale réelle strictement positive à cause de Dk et U . On factorise D (resp. U ) par
une matrice diagonale ∆1 (resp. ∆2 ) qui contient les eiθ où θ est un argument de chaque coefficient
de la diagonale de D (resp. U ) 7 . Donc D = ∆1 |D| où |D| est la matrice diag(|λ1 |, . . . , |λn |) et
U = ∆2 U 0.
ρ1 eiθ1
iθ
(∗) e 1 0 ρ1 (∗)
Si U =
.. , alors on a ∆2 =
.. et U 0 =
..
. . .
0 ρn eiθn 0 eiθn 0 ρn
0
Ainsi |D| et U sont bien triangulaires supérieures de diagonale réelle strictement positive.
On a alors
Ak = (QOk ∆k1 ∆2 )(∆−1 −k k k
2 ∆1 Tk R∆1 |D| ∆2 U )
0
Maintenant on a bien ∆−1 −k k k 0 + k
2 ∆1 Tk R∆1 |D| ∆2 U ) ∈ Tn (C) et on a QOk ∆1 ∆2 unitaire. Donc on a
bien une décomposition QR de Ak .
Comme Ak = Q(k) R(k) est aussi une décomposition QR de Ak , on a, par unicité de la
décomposition QR,
Q(k) = QOk ∆k1 ∆2
3. Ak = (Q1 R1 )k = Q1 (R1 Q1 )k−1 R1 = Q1 Ak−1 2 R1 = Q1 (Q2 R2 )k−1 R1 = Q1 Q2 (R2 Q2 )k−2 R2 R1 = · · · =
Q1 . . . Qk−1 Rk−1 Qk−1 Rk−1 . . . R1 = Q1 . . . Qk−1 Ak Rk−1 . . . R1 = Q1 . . . Qk−1 Qk Rk Rk−1 . . . R1 = Q(k) R(k)
4. Ak+1 = Rk Qk = Q∗k Qk Rk Qk = Q∗k Ak Qk = Q∗k Q(k−1)∗ AQ(k−1) Qk = Q(k)∗ AQ(k)
5. puisque P est inversible (par l’homéomorphisme de la proposition 1)
6. Le calcul des coefficients de Dk LD−k donne
0 si i < j
(D LD )ij = 1
k −k si i = j
λ k
i
si i > j
λj
7. c’est possible car U est inversible puisque P −1 l’est donc aucun des coefficients diagonaux de U est nul et les
λi sont supposés de module strictement positifs
ENS Rennes - Université de Rennes 1 2 Pierre Le Barbenchon
Agrégation 2018/2019
Étape 2 : Convergence de Ak
On a alors
Ak+1 = (QOk ∆k1 ∆2 )∗ A(QOk ∆k1 ∆2 ) = (∆k1 ∆2 )∗ Ok∗ Q∗ AQOk (∆k1 ∆2 )
Or
Q∗ AQ = Q∗ QRDR−1 Q−1 Q = RDR−1
en se rappelant que P = QR et A = P DP −1 . De plus comme R est triangulaire supérieure on a
λ1 (∗)
RDR−1 =
..
.
0 λn
Nous avons vu que Ok tend vers In donc on a
(∗0 )
λ1
Ok∗ Q∗ AQOk qui converge vers
..
.
0 λn
De plus, la conjugaison par ∆k1 ∆2 ne changera ni les coefficients nuls sous la diagonale ni la
diagonale. Donc (Ak ) converge bien vers une matrice triangulaire supérieure dont la diagonale est
diag(λ1 , . . . , λn ).
Remarques :
— Si A est réelle et satisfait les hypothèses, alors les valeurs propres sont réelles et toutes les
matrices que l’on considère sont réelles.
— Attention, si l’on deux valeurs propres de même module, le théorème est faux, par exemple,
si A est orthogonale, alors Ak = A pour tout k et donc elle ne converge pas vers une
matrice triangulaire supérieure a priori. Cependant, si plusieurs valeurs propres ont même
module, on va avoir une convergence vers une matrice triangulaire par blocs et chaque
bloc concerne les valeurs propres d’un même module.
— En pratique, on met la matrice A sous forme de Hessenberg (extension au cas non
symétrique de Householder) car la suite des (Ak ) restera sous forme de Hessenberg, ce qui
simplifiera les calculs.
— Pour trouver les vecteurs propres de A, on met A sous forme de Hessenberg : A = P HP −1 ,
on aura alors
Ak+1 = (Q1 Q2 . . . Qk )−1 H(Q1 Q2 . . . Qk )
On aura alors Q1 Q2 . . . Qk qui convergera vers une matrice contenant les vecteurs propres
en colonne
ENS Rennes - Université de Rennes 1 3 Pierre Le Barbenchon