3.4 Autres types de factorisation
87
n
A
m
=
m − n
˜
Q
˜
R
0
n
n
n
m − n
Fig. 3.1. Factorisation r´ eduite. Les matrices de la factorisation QR sont en pointill´ es
o` u Q est orthogonale, P est une matrice de permutation et R 11 est une matrice
triangulaire sup´ erieure inversible d’ordre r.
Dans la suite, quand nous utiliserons la factorisation QR, nous nous r´ ef´ ererons toujours `
a sa forme r´ eduite (3.44). Nous verrons une application int´ eressante de cette factorisation dans la r´ esolution des syst` emes surd´ etermin´ es
(voir Section 3.12).
Les matrices ˜
Q et ˜
R dans (3.44) peuvent ˆ etre calcul´ ees en utilisant le proc´ ed´ e d’orthogonalisation de Gram-Schmidt. Partant d’une famille de vecteurs
lin´ eairement ind´ ependants x 1 , . . ., x n , cet algorithme permet de construire
une famille de vecteurs orthogonaux q 1 , . . . , q n , donn´ es par
q 1 = x 1 ,
q k+1 = x k+1 −
k
i=1
(q i , x k+1 )
(q i , q i )
q i ,
k = 1, . . . , n − 1.
(3.46)
Notons a 1 , . . . , a n les vecteurs colonnes de A, posons ˜
q 1 = a 1 /a 1 2 et, pour
k = 1, . . . , n − 1, calculons les vecteurs colonnes de ˜
Q par
˜
q k+1 = q k+1 /q k+1 2 ,
o` u
q k+1 = a k+1 −
k
j=1
(˜ q j , a k+1 )˜ q j .
Ensuite, en ´ ecrivant A= ˜
Q ˜
R et en exploitant le fait que ˜
Q est orthogonale
(c’est-` a-dire ˜
Q
−1 = ˜
Q
T ), on peut facilement calculer les ´ el´ ements de ˜
R.
On peut ´ egalement noter que, si A est de rang maximum, la matrice A
T A
est sym´ etrique d´ efinie positive (voir Section 1.9) et qu’elle admet donc une
unique d´ ecomposition de Cholesky de la forme H
T H. D’autre part, l’orthogonalit´ e de ˜
Q implique
H
T H = A
T A = ˜
R
T ˜
Q
T ˜
Q ˜
R = ˜
R
T ˜
R,
87
n
A
m
=
m − n
˜
Q
˜
R
0
n
n
n
m − n
Fig. 3.1. Factorisation r´ eduite. Les matrices de la factorisation QR sont en pointill´ es
o` u Q est orthogonale, P est une matrice de permutation et R 11 est une matrice
triangulaire sup´ erieure inversible d’ordre r.
Dans la suite, quand nous utiliserons la factorisation QR, nous nous r´ ef´ ererons toujours `
a sa forme r´ eduite (3.44). Nous verrons une application int´ eressante de cette factorisation dans la r´ esolution des syst` emes surd´ etermin´ es
(voir Section 3.12).
Les matrices ˜
Q et ˜
R dans (3.44) peuvent ˆ etre calcul´ ees en utilisant le proc´ ed´ e d’orthogonalisation de Gram-Schmidt. Partant d’une famille de vecteurs
lin´ eairement ind´ ependants x 1 , . . ., x n , cet algorithme permet de construire
une famille de vecteurs orthogonaux q 1 , . . . , q n , donn´ es par
q 1 = x 1 ,
q k+1 = x k+1 −
k
i=1
(q i , x k+1 )
(q i , q i )
q i ,
k = 1, . . . , n − 1.
(3.46)
Notons a 1 , . . . , a n les vecteurs colonnes de A, posons ˜
q 1 = a 1 /a 1 2 et, pour
k = 1, . . . , n − 1, calculons les vecteurs colonnes de ˜
Q par
˜
q k+1 = q k+1 /q k+1 2 ,
o` u
q k+1 = a k+1 −
k
j=1
(˜ q j , a k+1 )˜ q j .
Ensuite, en ´ ecrivant A= ˜
Q ˜
R et en exploitant le fait que ˜
Q est orthogonale
(c’est-` a-dire ˜
Q
−1 = ˜
Q
T ), on peut facilement calculer les ´ el´ ements de ˜
R.
On peut ´ egalement noter que, si A est de rang maximum, la matrice A
T A
est sym´ etrique d´ efinie positive (voir Section 1.9) et qu’elle admet donc une
unique d´ ecomposition de Cholesky de la forme H
T H. D’autre part, l’orthogonalit´ e de ˜
Q implique
H
T H = A
T A = ˜
R
T ˜
Q
T ˜
Q ˜
R = ˜
R
T ˜
R,