4.5 Tests d’arrˆ et
159
Exemple 4.10 Consid´ erons le syst` eme lin´ eaire Ax=b avec
A =
⎡
⎣
4
1
1
2 −9
0
0 −8 −6
⎤
⎦ , b =
⎡
⎣
6
−7
−14
⎤
⎦ ,
qui admet le vecteur unit´ e comme solution. Appliquons la m´ ethode de Jacobi et
´ evaluons l’erreur ` a chaque it´ eration en utilisant (4.70). La Figure 4.10 montre une
assez bonne ad´ equation entre le comportement de l’erreur e
(k+1) ∞ et celui de son
estimation
(k+1) .
•
0
5
10
15
20
25
10
−8
10
−7
10
−6
10
−5
10
−4
10
−3
10
−2
10
−1
10
0
10
1
Fig. 4.10. Erreur absolue (trait plein) et erreur estim´ ee ` a l’aide de (4.70) (pointill´ es).
Le nombre d’it´ erations est indiqu´ e sur l’axe des x
4.5.2 Un test d’arrˆ et bas´ e sur le r´ esidu
Un autre crit` ere d’arrˆ et consiste ` a tester si r
(k)
≤ ε, ε ´ etant une tol´ erance
fix´ ee. Comme
− x
(k)
= A
−1 b − x
(k)
= A
−1 r
(k)
≤ ≤A
−1
ε,
on doit prendre ε ≤ δ/A
−1
pour que l’erreur soit inf´ erieure ` a δ.
Il est en g´ en´ eral plus judicieux de consid´ erer un r´ esidu normalis´ e : on interrompt alors les it´ erations quand r
(k)
/r
(0)
≤ ε ou bien quand r
(k)
/b ≤
ε (ce qui correspond au choix x
(0) = 0). Dans ce dernier cas, le test d’arrˆ et
fournit le contrˆ ole suivant de l’erreur relative
− x
(k)
x
≤
−1
(k)
x
≤ K(A)
(k)
b
≤ εK(A).
Dans le cas des m´ ethodes pr´ econditionn´ ees, le r´ esidu est remplac´ e par le r´ esidu
pr´ econditionn´ e. Le crit` ere pr´ ec´ edent devient alors
−1 r
(k)
P −1 r (0)
≤ ε,
o` u P est la matrice de pr´ econditionnement.