104
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
Exemple 3.5 Consid´ erons le syst` eme lin´ eaire (3.2) avec
A =
ε 1
1 0
, b =
1 + ε
1
,
(3.60)
qui admet comme solution exacte x=1, quelle que soit la valeur de ε. Le conditionnement de la matrice est petit puisque K∞(A) = (1 + ε)
2 . En r´ esolvant le syst` eme avec
ε = 10
−15 par une factorisation LU avec 16 chiffres significatifs, et en utilisant les
Programmes 5, 2 et 3, on obtient
x = [0.8881784197001253, 1.000000000000000]
T ,
ce qui repr´ esente une erreur de plus de 11% sur la premi` ere composante. On peut
se faire une id´ ee des raisons de ce manque de pr´ ecision en examinant (3.56). Cette
derni` ere in´ egalit´ e ne donne en effet pas une majoration uniform´ ement petite de tous
les termes de la matrice δA. Plus pr´ ecis´ ement :
|δA| ≤
3.55 · 10
−30
1.33 · 10
−15
1.33 · 10
−15
2.22
.
Remarquer que les ´ el´ ements des matrices correspondantes
L et
U sont grands en
module. En revanche, la m´ ethode de Gauss avec changement de pivot total ou partiel
conduit `
a la solution exacte du syst` eme (voir Exercice 6).
•
Consid´ erons ` a pr´ esent le rˆ ole du conditionnement dans l’analyse d’erreur de
la m´ ethode de Gauss. La solution
x obtenue par cet algorithme a typiquement
un petit r´ esidu r = b − A x (voir [GL89]). N´ eanmoins, cette propri´ et´ e ne garantit pas que l’erreur x −
x soit petite quand K(A) 1 (voir l’Exemple 3.6).
En fait, en interpr´ etant δb comme le r´ esidu dans (3.11), on a
−
x
x
≤ K(A) r
1
≤ K(A)
r
b
.
Ce r´ esultat sera utilis´ e pour construire des m´ ethodes, fond´ ees sur l’analyse
a posteriori, qui permettent d’am´ eliorer la pr´ ecision de la m´ ethode de Gauss
(voir Section 3.11).
Exemple 3.6 Consid´ erons le syst` eme lin´ eaire Ax = b avec
A =
1
1.0001
1.0001
1
, b =
1
1
,
dont la solution est x = [0.499975 . . . , 0.499975 . . .]
T . Supposons qu’on ait calcul´ e
une solution approch´ ee
x = [−4.499775, 5.5002249]
T . Le r´ esidu correspondant, r
[−0.001, 0]
T , est petit alors que
x est tr` es diff´ erent de la solution exacte. Ceci est li´ e
au grand conditionnement de la matrice A. Dans ce cas en effet K∞(A) = 20001. •
Une estimation du nombre de chiffres significatifs exacts de la solution
num´ erique peut ˆ etre obtenue comme suit. D’apr` es (3.13), en posant γ = u
(l’unit´ e d’arrondi) et en supposant uK ∞ (A) ≤ 1/2, on a
∞
x ∞
≤
2uK ∞ (A)
1 − uK ∞ (A)
≤ 4uK ∞ (A).
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
Exemple 3.5 Consid´ erons le syst` eme lin´ eaire (3.2) avec
A =
ε 1
1 0
, b =
1 + ε
1
,
(3.60)
qui admet comme solution exacte x=1, quelle que soit la valeur de ε. Le conditionnement de la matrice est petit puisque K∞(A) = (1 + ε)
2 . En r´ esolvant le syst` eme avec
ε = 10
−15 par une factorisation LU avec 16 chiffres significatifs, et en utilisant les
Programmes 5, 2 et 3, on obtient
x = [0.8881784197001253, 1.000000000000000]
T ,
ce qui repr´ esente une erreur de plus de 11% sur la premi` ere composante. On peut
se faire une id´ ee des raisons de ce manque de pr´ ecision en examinant (3.56). Cette
derni` ere in´ egalit´ e ne donne en effet pas une majoration uniform´ ement petite de tous
les termes de la matrice δA. Plus pr´ ecis´ ement :
|δA| ≤
3.55 · 10
−30
1.33 · 10
−15
1.33 · 10
−15
2.22
.
Remarquer que les ´ el´ ements des matrices correspondantes
L et
U sont grands en
module. En revanche, la m´ ethode de Gauss avec changement de pivot total ou partiel
conduit `
a la solution exacte du syst` eme (voir Exercice 6).
•
Consid´ erons ` a pr´ esent le rˆ ole du conditionnement dans l’analyse d’erreur de
la m´ ethode de Gauss. La solution
x obtenue par cet algorithme a typiquement
un petit r´ esidu r = b − A x (voir [GL89]). N´ eanmoins, cette propri´ et´ e ne garantit pas que l’erreur x −
x soit petite quand K(A) 1 (voir l’Exemple 3.6).
En fait, en interpr´ etant δb comme le r´ esidu dans (3.11), on a
−
x
x
≤ K(A) r
1
≤ K(A)
r
b
.
Ce r´ esultat sera utilis´ e pour construire des m´ ethodes, fond´ ees sur l’analyse
a posteriori, qui permettent d’am´ eliorer la pr´ ecision de la m´ ethode de Gauss
(voir Section 3.11).
Exemple 3.6 Consid´ erons le syst` eme lin´ eaire Ax = b avec
A =
1
1.0001
1.0001
1
, b =
1
1
,
dont la solution est x = [0.499975 . . . , 0.499975 . . .]
T . Supposons qu’on ait calcul´ e
une solution approch´ ee
x = [−4.499775, 5.5002249]
T . Le r´ esidu correspondant, r
[−0.001, 0]
T , est petit alors que
x est tr` es diff´ erent de la solution exacte. Ceci est li´ e
au grand conditionnement de la matrice A. Dans ce cas en effet K∞(A) = 20001. •
Une estimation du nombre de chiffres significatifs exacts de la solution
num´ erique peut ˆ etre obtenue comme suit. D’apr` es (3.13), en posant γ = u
(l’unit´ e d’arrondi) et en supposant uK ∞ (A) ≤ 1/2, on a
∞
x ∞
≤
2uK ∞ (A)
1 − uK ∞ (A)
≤ 4uK ∞ (A).