88
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
ce qui permet de conclure que ˜
R est effectivement la matrice de Cholesky de
A
T A. Les ´ el´ ements diagonaux de ˜
R sont donc non nuls si et seulement si A
est de rang maximum.
Le proc´ ed´ e de Gram-Schmidt n’est pas tr` es utilis´ e en pratique car les
erreurs d’arrondi font que les vecteurs calcul´ es ne sont en g´ en´ eral pas lin´ eairement ind´ ependants. L’algorithme produit en effet des valeurs tr` es petites de
q k+1 2 et ˜
r kk , ce qui entraˆ ıne des instabilit´ es num´ eriques en arithm´ etique
` a virgule flottante et la destruction de l’orthogonalit´ e de la matrice ˜
Q (voir
l’Exemple 3.2).
Ceci sugg` ere d’utiliser une version plus stable, appel´ ee proc´ ed´ e de GramSchmidt modifi´ e. Au d´ ebut de la k-i` eme ´ etape, on retranche du vecteur a k
ses projections le long des vecteurs ˜
q 1 , . . . , ˜
q k . L’´ etape d’orthogonalisation
est alors effectu´ ee sur le vecteur r´ esultant. En pratique, apr` es avoir calcul´ e
(˜ q 1 , a k+1 )˜ q 1 ` a la k + 1-i` eme ´ etape, ce vecteur est imm´ ediatement retranch´ e ` a
a k+1 . Ainsi, on pose
a
(1)
k+1 = a k+1 − (˜ q 1 , a k+1 )˜ q 1 .
Ce nouveau vecteur a
(1)
k+1 est projet´ e le long de la direction de ˜
q 2 , et le vecteur
obtenu est retranch´ e de a
(1)
k+1 , ce qui donne
a
(2)
k+1 = a
(1)
k+1 − (˜ q 2 , a
(1)
k+1 )˜ q 2 ,
et ainsi de suite, jusqu’` a ce que a
(k)
k+1 soit calcul´ e.
On peut v´ erifier que a
(k)
k+1 co¨ ıncide avec le vecteur correspondant q k+1
du proc´ ed´ e de Gram-Schmidt classique, puisque, grˆ ace ` a l’orthogonalit´ e des
vecteurs ˜
q 1 , ˜
q 2 , . . . , ˜
q k , on a
a
(k)
k+1 = a k+1 − (˜ q 1 , a k+1 )˜ q 1 − (˜ q 2 , a k+1 − (˜ q 1 , a k+1 )˜ q 1 ) ˜
q 2 + . . .
= a k+1 −
k
j=1
(˜ q j , a k+1 )˜ q j .
Le Programme 8 est une impl´ ementation du proc´ ed´ e de Gram-Schmidt
modifi´ e. Remarquer qu’il n’est pas possible de stocker la factorisation QR
dans la matrice A. En g´ en´ eral, la matrice
R est stock´ ee dans A, tandis que
Q
est stock´ ee s´ epar´ ement. Le coˆ ut de l’algorithme de Gram-Schmidt modifi´ e est
de l’ordre de 2mn
2 flops.
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
ce qui permet de conclure que ˜
R est effectivement la matrice de Cholesky de
A
T A. Les ´ el´ ements diagonaux de ˜
R sont donc non nuls si et seulement si A
est de rang maximum.
Le proc´ ed´ e de Gram-Schmidt n’est pas tr` es utilis´ e en pratique car les
erreurs d’arrondi font que les vecteurs calcul´ es ne sont en g´ en´ eral pas lin´ eairement ind´ ependants. L’algorithme produit en effet des valeurs tr` es petites de
q k+1 2 et ˜
r kk , ce qui entraˆ ıne des instabilit´ es num´ eriques en arithm´ etique
` a virgule flottante et la destruction de l’orthogonalit´ e de la matrice ˜
Q (voir
l’Exemple 3.2).
Ceci sugg` ere d’utiliser une version plus stable, appel´ ee proc´ ed´ e de GramSchmidt modifi´ e. Au d´ ebut de la k-i` eme ´ etape, on retranche du vecteur a k
ses projections le long des vecteurs ˜
q 1 , . . . , ˜
q k . L’´ etape d’orthogonalisation
est alors effectu´ ee sur le vecteur r´ esultant. En pratique, apr` es avoir calcul´ e
(˜ q 1 , a k+1 )˜ q 1 ` a la k + 1-i` eme ´ etape, ce vecteur est imm´ ediatement retranch´ e ` a
a k+1 . Ainsi, on pose
a
(1)
k+1 = a k+1 − (˜ q 1 , a k+1 )˜ q 1 .
Ce nouveau vecteur a
(1)
k+1 est projet´ e le long de la direction de ˜
q 2 , et le vecteur
obtenu est retranch´ e de a
(1)
k+1 , ce qui donne
a
(2)
k+1 = a
(1)
k+1 − (˜ q 2 , a
(1)
k+1 )˜ q 2 ,
et ainsi de suite, jusqu’` a ce que a
(k)
k+1 soit calcul´ e.
On peut v´ erifier que a
(k)
k+1 co¨ ıncide avec le vecteur correspondant q k+1
du proc´ ed´ e de Gram-Schmidt classique, puisque, grˆ ace ` a l’orthogonalit´ e des
vecteurs ˜
q 1 , ˜
q 2 , . . . , ˜
q k , on a
a
(k)
k+1 = a k+1 − (˜ q 1 , a k+1 )˜ q 1 − (˜ q 2 , a k+1 − (˜ q 1 , a k+1 )˜ q 1 ) ˜
q 2 + . . .
= a k+1 −
k
j=1
(˜ q j , a k+1 )˜ q j .
Le Programme 8 est une impl´ ementation du proc´ ed´ e de Gram-Schmidt
modifi´ e. Remarquer qu’il n’est pas possible de stocker la factorisation QR
dans la matrice A. En g´ en´ eral, la matrice
R est stock´ ee dans A, tandis que
Q
est stock´ ee s´ epar´ ement. Le coˆ ut de l’algorithme de Gram-Schmidt modifi´ e est
de l’ordre de 2mn
2 flops.