110
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
D´ emonstration. La factorisation QR de A existe et est unique puisque A est
de rang maximal. Ainsi, il existe deux matrices, Q∈ R
m×m et R∈ R
m×n telles que
A=QR, o` u Q est orthogonale. Le fait que les matrices orthogonales pr´ eservent le
produit scalaire euclidien entraˆ ıne
Ax − b
2
2 = Rx − Q
T b
2
2 .
En rappelant que R est trap´ ezo¨ ıdale, on a
Rx − Q
T b
2
2 = ˜
Rx − ˜
Q
T b
2
2 +
m
i=n+1
[(Q
T b)i]
2 .
Le minimum est donc atteint en x = x
∗ .
3
Pour plus de pr´ ecisions sur l’analyse du coˆ ut de cet algorithme (qui d´ epend
de l’impl´ ementation de la factorisation QR), ainsi que pour des r´ esultats sur sa
stabilit´ e, nous renvoyons le lecteur aux ouvrages cit´ es au d´ ebut de la section.
Si A n’est pas de rang maximal, les techniques de r´ esolution ci-dessus ne
s’appliquent plus. Dans ce cas en effet, si x
∗ est solution de (3.62), le vecteur
x
∗ + z, avec z ∈ Ker(A), est ´ egalement solution. On doit par cons´ equent
imposer une contrainte suppl´ ementaire pour forcer l’unicit´ e de la solution.
Typiquement, on peut chercher `
a minimiser la norme euclidienne de x
∗ . Le
probl` eme des moindres carr´ es peut alors ˆ etre formul´ e ainsi :
trouver x
∗
∈ R
n de norme euclidienne minimale tel que
Ax
∗
− b
2
2 ≤ min
x∈R n
Ax − b
2
2 .
(3.65)
Ce probl` eme est consistant avec (3.62) si A est de rang maximal puisque dans
ce cas (3.62) a une unique solution (qui est donc n´ ecessairement de norme
minimale).
L’outil pour r´ esoudre (3.65) est la d´ ecomposition en valeurs singuli` eres (ou
DVS, voir Section 1.9). On a en effet le th´ eor` eme suivant :
Th´ eor` eme 3.8 Soit A ∈ R
m×n dont la d´ ecomposition en valeurs singuli` eres
est donn´ ee par A = UΣV
T . Alors, l’unique solution de (3.65) est
x
∗ = A
† b ,
(3.66)
o` u A
† est la pseudo-inverse de A introduite dans la D´ efinition 1.16.
D´ emonstration. En utilisant la DVS de A, le probl` eme (3.65) est ´ equivalent ` a
trouver w = V
T x tel que w ait une norme euclidienne minimale et
Σw − U
T b
2
2 ≤ ≤Σy − U
T b
2
2 , ∀y ∈ R
n .
Si r est le nombre de valeurs singuli` eres σi non nulles de A, alors
Σw − U
T b
2
2 =
r
i=1
σiwi − (U
T b)i
2
+
m
i=r+1
(U
T b)i
2
,
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
D´ emonstration. La factorisation QR de A existe et est unique puisque A est
de rang maximal. Ainsi, il existe deux matrices, Q∈ R
m×m et R∈ R
m×n telles que
A=QR, o` u Q est orthogonale. Le fait que les matrices orthogonales pr´ eservent le
produit scalaire euclidien entraˆ ıne
Ax − b
2
2 = Rx − Q
T b
2
2 .
En rappelant que R est trap´ ezo¨ ıdale, on a
Rx − Q
T b
2
2 = ˜
Rx − ˜
Q
T b
2
2 +
m
i=n+1
[(Q
T b)i]
2 .
Le minimum est donc atteint en x = x
∗ .
3
Pour plus de pr´ ecisions sur l’analyse du coˆ ut de cet algorithme (qui d´ epend
de l’impl´ ementation de la factorisation QR), ainsi que pour des r´ esultats sur sa
stabilit´ e, nous renvoyons le lecteur aux ouvrages cit´ es au d´ ebut de la section.
Si A n’est pas de rang maximal, les techniques de r´ esolution ci-dessus ne
s’appliquent plus. Dans ce cas en effet, si x
∗ est solution de (3.62), le vecteur
x
∗ + z, avec z ∈ Ker(A), est ´ egalement solution. On doit par cons´ equent
imposer une contrainte suppl´ ementaire pour forcer l’unicit´ e de la solution.
Typiquement, on peut chercher `
a minimiser la norme euclidienne de x
∗ . Le
probl` eme des moindres carr´ es peut alors ˆ etre formul´ e ainsi :
trouver x
∗
∈ R
n de norme euclidienne minimale tel que
Ax
∗
− b
2
2 ≤ min
x∈R n
Ax − b
2
2 .
(3.65)
Ce probl` eme est consistant avec (3.62) si A est de rang maximal puisque dans
ce cas (3.62) a une unique solution (qui est donc n´ ecessairement de norme
minimale).
L’outil pour r´ esoudre (3.65) est la d´ ecomposition en valeurs singuli` eres (ou
DVS, voir Section 1.9). On a en effet le th´ eor` eme suivant :
Th´ eor` eme 3.8 Soit A ∈ R
m×n dont la d´ ecomposition en valeurs singuli` eres
est donn´ ee par A = UΣV
T . Alors, l’unique solution de (3.65) est
x
∗ = A
† b ,
(3.66)
o` u A
† est la pseudo-inverse de A introduite dans la D´ efinition 1.16.
D´ emonstration. En utilisant la DVS de A, le probl` eme (3.65) est ´ equivalent ` a
trouver w = V
T x tel que w ait une norme euclidienne minimale et
Σw − U
T b
2
2 ≤ ≤Σy − U
T b
2
2 , ∀y ∈ R
n .
Si r est le nombre de valeurs singuli` eres σi non nulles de A, alors
Σw − U
T b
2
2 =
r
i=1
σiwi − (U
T b)i
2
+
m
i=r+1
(U
T b)i
2
,