3.12 Syst` emes ind´ etermin´ es
109
Le probl` eme consiste donc ` a minimiser la norme euclidienne du r´ esidu. La
solution de (3.62) peut ˆ etre d´ etermin´ ee en imposant au gradient de la fonction
Φ de s’annuler en x
∗ . Puisque
Φ(x) = (Ax − b)
T (Ax − b) = x
T A
T Ax − 2x
T A
T b + b
T b,
on a
∇Φ(x
∗ ) = 2A
T Ax
∗
− 2A
T b = 0.
Il en d´ ecoule que x
∗ doit ˆ etre solution du syst` eme carr´ e
A
T Ax
∗ = A
T b,
(3.63)
appel´ e syst` eme des ´ equations normales. Le syst` eme est non singulier si A est
de rang maximum. Dans ce cas, la solution au sens des moindres carr´ es existe
et est unique.
Remarquons que B = A
T A est une matrice sym´ etrique d´ efinie positive.
Ainsi, pour r´ esoudre les ´ equations normales, on pourrait d’abord effectuer
la factorisation de Cholesky B = H
T H, puis r´ esoudre les deux syst` emes
H
T y = A
T b et Hx
∗ = y. Cependant, cette m´ ethode pr´ esentent deux inconv´ enients majeur. D’une part le syst` eme (3.63) est mal conditionn´ e. D’autre
part, les erreurs d’arrondi peuvent entraˆ ıner une perte du nombre de chiffres
significatifs lors du calcul de A
T A, ce qui peut alt´ erer les propri´ et´ es d’inversibilit´ e et/ou de positivit´ e de cette matrice. Ainsi, dans l’exemple suivant (o` u
les calculs sont effectu´ es dans MATLAB), A est de rang maximal et la matrice
fl(A
T A) est singuli` ere
A =
⎡
⎣
1
1
2
−27 0
0
2
−27
⎤
⎦ , fl(A
T A) =
1 1
1 1
.
Il est en g´ en´ eral plus efficace d’utiliser la factorisation QR introduite `
a la
Section 3.4.3. On a alors le r´ esultat suivant :
Th´ eor` eme 3.7 Soit A ∈ R
m×n , avec m ≥ n, une matrice de rang maximal.
Alors, l’unique solution de (3.62) est donn´ ee par
x
∗ = ˜
R
−1 ˜
Q
T b,
(3.64)
o` u ˜
R ∈ R
n×n et ˜
Q ∈ R
m×n sont les matrices d´ efinies dans (3.45) ` a partir de
la factorisation QR de A. De plus, le minimum de Φ est donn´ e par
Φ(x
∗ ) =
m
i=n+1
[(Q
T b) i ]
2 .
109
Le probl` eme consiste donc ` a minimiser la norme euclidienne du r´ esidu. La
solution de (3.62) peut ˆ etre d´ etermin´ ee en imposant au gradient de la fonction
Φ de s’annuler en x
∗ . Puisque
Φ(x) = (Ax − b)
T (Ax − b) = x
T A
T Ax − 2x
T A
T b + b
T b,
on a
∇Φ(x
∗ ) = 2A
T Ax
∗
− 2A
T b = 0.
Il en d´ ecoule que x
∗ doit ˆ etre solution du syst` eme carr´ e
A
T Ax
∗ = A
T b,
(3.63)
appel´ e syst` eme des ´ equations normales. Le syst` eme est non singulier si A est
de rang maximum. Dans ce cas, la solution au sens des moindres carr´ es existe
et est unique.
Remarquons que B = A
T A est une matrice sym´ etrique d´ efinie positive.
Ainsi, pour r´ esoudre les ´ equations normales, on pourrait d’abord effectuer
la factorisation de Cholesky B = H
T H, puis r´ esoudre les deux syst` emes
H
T y = A
T b et Hx
∗ = y. Cependant, cette m´ ethode pr´ esentent deux inconv´ enients majeur. D’une part le syst` eme (3.63) est mal conditionn´ e. D’autre
part, les erreurs d’arrondi peuvent entraˆ ıner une perte du nombre de chiffres
significatifs lors du calcul de A
T A, ce qui peut alt´ erer les propri´ et´ es d’inversibilit´ e et/ou de positivit´ e de cette matrice. Ainsi, dans l’exemple suivant (o` u
les calculs sont effectu´ es dans MATLAB), A est de rang maximal et la matrice
fl(A
T A) est singuli` ere
A =
⎡
⎣
1
1
2
−27 0
0
2
−27
⎤
⎦ , fl(A
T A) =
1 1
1 1
.
Il est en g´ en´ eral plus efficace d’utiliser la factorisation QR introduite `
a la
Section 3.4.3. On a alors le r´ esultat suivant :
Th´ eor` eme 3.7 Soit A ∈ R
m×n , avec m ≥ n, une matrice de rang maximal.
Alors, l’unique solution de (3.62) est donn´ ee par
x
∗ = ˜
R
−1 ˜
Q
T b,
(3.64)
o` u ˜
R ∈ R
n×n et ˜
Q ∈ R
m×n sont les matrices d´ efinies dans (3.45) ` a partir de
la factorisation QR de A. De plus, le minimum de Φ est donn´ e par
Φ(x
∗ ) =
m
i=n+1
[(Q
T b) i ]
2 .