3.2 R´ esolution d’un syst` eme triangulaire
67
solution approch´ ee connue. Le but de l’analyse a posteriori est de relier l’erreur
(inconnue) e = y − x ` a des quantit´ es qu’on peut calculer en utilisant y et C.
Le point de d´ epart de l’analyse repose sur le fait que le r´ esidu r = b − Ay
est en g´ en´ eral non nul, puisque y n’est qu’une approximation de la solution
exacte inconnue. Le r´ esidu peut ˆ etre reli´ e ` a l’erreur grˆ ace ` a la Propri´ et´ e 3.1 :
si R < 1 alors
≤
1 − −R
.
(3.16)
Remarquer que l’estimation ne n´ ecessite pas que y co¨ ıncide avec la solution
x = Cb de l’analyse a priori r´ etrograde. On pourrait donc songer `
a calculer
C dans le seul but d’utiliser l’estimation (3.16) (par exemple, dans le cas
o` u (3.2) est r´ esolu par la m´ ethode d’´ elimination de Gauss, on peut calculer C
a posteriori en utilisant la factorisation LU de A, voir les Sections 3.3 et 3.3.1).
Concluons en remarquant que si δb est interpr´ et´ e dans (3.11) comme le
r´ esidu de la solution calcul´ ee y = x + δx, on a ´ egalement
x
≤ K(A)
b
.
(3.17)
L’estimation (3.17) n’est pas utilis´ ee en pratique car le r´ esidu calcul´ e est entach´ e d’erreur d’arrondi. En posant r = fl(b − Ay) et en supposant que
r = r+δr avec |δr| ≤ γ n+1 (|A| |y|+|b|), o` u γ n+1 = (n+1)u/(1−(n+1)u) > 0,
une estimation plus significative (en norme · · ∞ ) que (3.17) est donn´ ee par
∞
y ∞
≤
|A
−1
|(| r| + γ n+1 (|A||y| + |b|)) ∞
y ∞
,
(3.18)
o` u on a not´ e |A| la matrice n × n de coefficients |a ij |, i, j = 1, . . . , n. Cette
notation sera d´ esign´ ee dans la suite notation valeur absolue. Nous utiliserons
aussi la notation suivante
C ≤ D, o` u C, D ∈ R
m×n
pour indiquer que
c ij ≤ d ij pour i = 1, . . ., m, j = 1, . . . , n.
Des formules du type de (3.18) sont impl´ ement´ ees dans la biblioth` eque d’alg` ebre lin´ eaire LAPACK (voir [ABB
+ 92]).
3.2 R´ esolution d’un syst` eme triangulaire
Consid´ erons un syst` eme inversible 3×3 triangulaire inf´ erieur :
⎡
⎣
l 11 0
0
l 21 l 22 0
l 31 l 32 l 33
⎤
⎦
⎡
⎣
x 1
x 2
x 3
⎤
⎦ =
⎡
⎣
b 1
b 2
b 3
⎤
⎦ .
67
solution approch´ ee connue. Le but de l’analyse a posteriori est de relier l’erreur
(inconnue) e = y − x ` a des quantit´ es qu’on peut calculer en utilisant y et C.
Le point de d´ epart de l’analyse repose sur le fait que le r´ esidu r = b − Ay
est en g´ en´ eral non nul, puisque y n’est qu’une approximation de la solution
exacte inconnue. Le r´ esidu peut ˆ etre reli´ e ` a l’erreur grˆ ace ` a la Propri´ et´ e 3.1 :
si R < 1 alors
≤
1 − −R
.
(3.16)
Remarquer que l’estimation ne n´ ecessite pas que y co¨ ıncide avec la solution
x = Cb de l’analyse a priori r´ etrograde. On pourrait donc songer `
a calculer
C dans le seul but d’utiliser l’estimation (3.16) (par exemple, dans le cas
o` u (3.2) est r´ esolu par la m´ ethode d’´ elimination de Gauss, on peut calculer C
a posteriori en utilisant la factorisation LU de A, voir les Sections 3.3 et 3.3.1).
Concluons en remarquant que si δb est interpr´ et´ e dans (3.11) comme le
r´ esidu de la solution calcul´ ee y = x + δx, on a ´ egalement
x
≤ K(A)
b
.
(3.17)
L’estimation (3.17) n’est pas utilis´ ee en pratique car le r´ esidu calcul´ e est entach´ e d’erreur d’arrondi. En posant r = fl(b − Ay) et en supposant que
r = r+δr avec |δr| ≤ γ n+1 (|A| |y|+|b|), o` u γ n+1 = (n+1)u/(1−(n+1)u) > 0,
une estimation plus significative (en norme · · ∞ ) que (3.17) est donn´ ee par
∞
y ∞
≤
|A
−1
|(| r| + γ n+1 (|A||y| + |b|)) ∞
y ∞
,
(3.18)
o` u on a not´ e |A| la matrice n × n de coefficients |a ij |, i, j = 1, . . . , n. Cette
notation sera d´ esign´ ee dans la suite notation valeur absolue. Nous utiliserons
aussi la notation suivante
C ≤ D, o` u C, D ∈ R
m×n
pour indiquer que
c ij ≤ d ij pour i = 1, . . ., m, j = 1, . . . , n.
Des formules du type de (3.18) sont impl´ ement´ ees dans la biblioth` eque d’alg` ebre lin´ eaire LAPACK (voir [ABB
+ 92]).
3.2 R´ esolution d’un syst` eme triangulaire
Consid´ erons un syst` eme inversible 3×3 triangulaire inf´ erieur :
⎡
⎣
l 11 0
0
l 21 l 22 0
l 31 l 32 l 33
⎤
⎦
⎡
⎣
x 1
x 2
x 3
⎤
⎦ =
⎡
⎣
b 1
b 2
b 3
⎤
⎦ .