3.12 Syst` emes ind´ etermin´ es
111
qui est minimal si wi = (U
T b)i/σi pour i = 1, . . . , r. De plus, il est clair que parmi
les vecteurs w de R
n dont les r premi` eres composantes sont fix´ ees, celui de norme
euclidienne minimale est celui dont les n − r composantes restantes sont nulles.
Ainsi, la solution est w
∗ = Σ
† U
T b, c’est-` a-dire, x
∗ = VΣ
† U
T b = A
† b, o` u Σ
† est la
matrice diagonale d´ efinie en (1.12).
3
En ce qui concerne la stabilit´ e du probl` eme (3.65), pr´ ecisons que si la
matrice A n’est pas de rang maximal, la solution x
∗ n’est pas n´ ecessairement
une fonction continue des donn´ ees, de sorte qu’une petite modification de ces
derni` eres peut induire de grandes variations dans x
∗ . En voici un exemple :
Exemple 3.9 Consid´ erons le syst` eme Ax = b avec
A =
⎡
⎣
1 0
0 0
0 0
⎤
⎦ , b =
⎡
⎣
1
2
3
⎤
⎦ , rg(A) = 1.
La fonction svd de MATLAB permet de calculer la d´ ecomposition en valeurs singuli` eres de A. En calculant la pseudo-inverse, on trouve alors la solution x
∗ = [1, 0]
T .
Si on modifie de 10
−12 l’´ el´ ement nul a22, la matrice perturb´ ee est de rang 2 (i.e.
de rang maximal) et la solution (unique au sens de (3.62)) est alors donn´ ee par
x
∗ = [1, 2 · 10
12 ]
T .
•
Dans le cas des syst` emes sousd´ etermin´ es, i.e. pour lesquels m < n, si A est
de rang maximal, la factorisation QR peut encore ˆ etre utilis´ ee. En particulier,
quand on l’applique `
a la matrice transpos´ ee A
T , la m´ ethode conduit `
a la
solution de norme euclidienne minimale. Si, au contraire, la matrice n’est pas
de rang maximal, on doit effectuer une d´ ecomposition en valeurs singuli` eres.
Remarque 3.7 Si m = n (syst` eme carr´ e), la DVS et la factorisation QR
peuvent ˆ etre utilis´ ees comme alternative ` a la m´ ethode de Gauss pour r´ esoudre
le syst` eme lin´ eaire Ax=b. Mˆ eme si ces algorithmes sont plus coˆ uteux que la
m´ ethode de Gauss (la DVS, par exemple, n´ ecessite 12n
3 flops), ils se r´ ev` elent
plus pr´ ecis quand le syst` eme est mal conditionn´ e et presque singulier.
Exemple 3.10 Calculons la solution du syst` eme lin´ eaire H15x=b, o` u H15 est la
matrice de Hilbert d’ordre 15 (voir (3.29)) et o` u le second membre est choisi de
fa¸ con `
a ce que la solution exacte soit le vecteur unit´ e x = 1. La m´ ethode de Gauss
avec changement de pivot partiel donne une solution dont l’erreur relative d´ epasse
100%. Une meilleure solution est obtenue en effectuant le calcul de la matrice pseudoinverse, dans lequel les ´ el´ ements de Σ inf´ erieurs ` a 10
−13 ont ´ et´ e remplac´ es par 0.
•
111
qui est minimal si wi = (U
T b)i/σi pour i = 1, . . . , r. De plus, il est clair que parmi
les vecteurs w de R
n dont les r premi` eres composantes sont fix´ ees, celui de norme
euclidienne minimale est celui dont les n − r composantes restantes sont nulles.
Ainsi, la solution est w
∗ = Σ
† U
T b, c’est-` a-dire, x
∗ = VΣ
† U
T b = A
† b, o` u Σ
† est la
matrice diagonale d´ efinie en (1.12).
3
En ce qui concerne la stabilit´ e du probl` eme (3.65), pr´ ecisons que si la
matrice A n’est pas de rang maximal, la solution x
∗ n’est pas n´ ecessairement
une fonction continue des donn´ ees, de sorte qu’une petite modification de ces
derni` eres peut induire de grandes variations dans x
∗ . En voici un exemple :
Exemple 3.9 Consid´ erons le syst` eme Ax = b avec
A =
⎡
⎣
1 0
0 0
0 0
⎤
⎦ , b =
⎡
⎣
1
2
3
⎤
⎦ , rg(A) = 1.
La fonction svd de MATLAB permet de calculer la d´ ecomposition en valeurs singuli` eres de A. En calculant la pseudo-inverse, on trouve alors la solution x
∗ = [1, 0]
T .
Si on modifie de 10
−12 l’´ el´ ement nul a22, la matrice perturb´ ee est de rang 2 (i.e.
de rang maximal) et la solution (unique au sens de (3.62)) est alors donn´ ee par
x
∗ = [1, 2 · 10
12 ]
T .
•
Dans le cas des syst` emes sousd´ etermin´ es, i.e. pour lesquels m < n, si A est
de rang maximal, la factorisation QR peut encore ˆ etre utilis´ ee. En particulier,
quand on l’applique `
a la matrice transpos´ ee A
T , la m´ ethode conduit `
a la
solution de norme euclidienne minimale. Si, au contraire, la matrice n’est pas
de rang maximal, on doit effectuer une d´ ecomposition en valeurs singuli` eres.
Remarque 3.7 Si m = n (syst` eme carr´ e), la DVS et la factorisation QR
peuvent ˆ etre utilis´ ees comme alternative ` a la m´ ethode de Gauss pour r´ esoudre
le syst` eme lin´ eaire Ax=b. Mˆ eme si ces algorithmes sont plus coˆ uteux que la
m´ ethode de Gauss (la DVS, par exemple, n´ ecessite 12n
3 flops), ils se r´ ev` elent
plus pr´ ecis quand le syst` eme est mal conditionn´ e et presque singulier.
Exemple 3.10 Calculons la solution du syst` eme lin´ eaire H15x=b, o` u H15 est la
matrice de Hilbert d’ordre 15 (voir (3.29)) et o` u le second membre est choisi de
fa¸ con `
a ce que la solution exacte soit le vecteur unit´ e x = 1. La m´ ethode de Gauss
avec changement de pivot partiel donne une solution dont l’erreur relative d´ epasse
100%. Une meilleure solution est obtenue en effectuant le calcul de la matrice pseudoinverse, dans lequel les ´ el´ ements de Σ inf´ erieurs ` a 10
−13 ont ´ et´ e remplac´ es par 0.
•