158
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
Cette derni` ere estimation est en g´ en´ eral plutˆ ot optimiste, comme le confirme
l’Exemple 4.9.
Exemple 4.9 Pour la matrice A3 de l’Exemple 4.2, dans le cas de la m´ ethode de
Jacobi, en posant ε = 10
−5 , la condition (4.66) est satisfaite pour kmin = 16, et
(4.67) donne kmin = 15. Sur la matrice A4 de l’Exemple 4.2, on trouve que (4.66)
est satisfaite avec kmin = 30, tandis que (4.67) donne kmin = 26.
•
4.5.1 Un test d’arrˆ et bas´ e sur l’incr´ ement
D’apr` es la relation de r´ ecurrence sur l’erreur e
(k+1) = Be
(k) , on a
(k+1)
≤ ≤B
(k)
.
(4.68)
En utilisant l’in´ egalit´ e triangulaire, on a
(k+1)
≤ ≤B(e
(k+1)
+ x
(k+1)
− x
(k)
),
et donc
− x
(k+1)
≤
1 − −B
(k+1)
− x
(k)
.
(4.69)
En particulier, en prenant k = 0 dans (4.69) et en appliquant la formule de
r´ ecurrence (4.68) on obtient aussi l’in´ egalit´ e
− x
(k+1)
≤
k+1
1 − −B
(1)
− x
(0)
qu’on peut utiliser pour estimer le nombre d’it´ erations n´ ecessaire ` a satisfaire
la condition e
(k+1)
≤ ε, pour une tol´ erance ε donn´ ee.
En pratique, on peut estimer B comme suit : puisque
x
(k+1)
− x
(k) = −(x − x
(k+1) ) + (x − x
(k) ) = B(x
(k)
− x
(k−1) ),
la quantit´ e B est minor´ ee par c = δ k+1 /δ k , o` u δ k+1 = x
(k+1)
− x
(k)
.
En rempla¸ cant B par c, le membre de droite de (4.69) sugg` ere d’utiliser
l’indicateur suivant pour e
(k+1)
(k+1) =
δ
2
k+1
δ k − δ k+1
.
(4.70)
Il faut prendre garde au fait qu’avec l’approximation utilis´ ee pour B, on ne
peut pas voir
(k+1) comme un majorant de e
(k+1)
. N´ eanmoins,
(k+1) fournit souvent une indication raisonnable du comportement de l’erreur, comme
le montre l’exemple suivant.