172
5 Systèmes linéaires
5.12 Quand doit-on arrêter une méthode itérative ?
En théorie, il faudrait effectuer un nombre infini d’itérations pour obtenir
la solution exacte d’un système linéaire avec une méthode itérative. En
pratique, ce n’est ni nécessaire, ni raisonnable (même si effectivement le
nombre d’itérations pour obtenir la solution avec la précision machine
peut être très élevé pour de grands systèmes). En effet, ce n’est en général
pas d’une solution exacte dont on a besoin, mais plutôt d’une valeur x
(k)
qui approche la solution exacte avec une erreur inférieure à une tolérance
fixée. Mais comme l’erreur est elle-même inconnue (puisqu’elle dépend
de la solution exacte), on a besoin d’un estimateur d’erreur a posteriori
qui donne une estimation de l’erreur à partir de quantités calculées au
cours de la résolution.
Un premier estimateur est donné par le résidu, défini en (5.48). Ainsi,
on peut décider de stopper les itérations à la première étape k min pour
laquelle
r
(kmin)
≤ εb.
En posant
x = x
(kmin) et r = r
(kmin) dans (5.32) on obtient
e
(kmin)
x
≤ εK(A),
qui est une estimation de l’erreur relative. On voit donc que le contrôle
par le résidu n’est pertinent que pour les matrices dont le conditionnement n’est pas trop grand.
Exemple 5.17 Considérons le système linéaire (5.1) où A=A20 est la matrice
de Hilbert de dimension 20 définie dans l’Exemple 5.9. On choisit b pour que
la solution exacte soit x = (1, 1, . . . , 1)
T . Comme A est symétrique définie
positive, on est assuré de la convergence de la méthode de Gauss-Seidel. On
utilise le Programme 5.2 pour résoudre ce système, avec x0 égal au vecteur nul
et une tolérance de 10
−5 sur le résidu. La méthode converge en 472 itérations ;
l’erreur relative est cependant très grande (égale à 0.26). Ceci est dû au fait
que A est extrêmement mal conditionnée (K(A) 10
17 ). Sur la Figure 5.11,
on trace le résidu (normalisé par le résidu initial) et l’erreur en fonction du
nombre d’itérations.
Un autre estimateur est donné par l’incrément δ
(k) = x
(k+1)
− x
(k) .
Autrement dit, on peut choisir de stopper la méthode à la première
itération k min pour laquelle
δ
(kmin)
≤ ε.
(5.65)
Dans le cas particulier où B est symétrique définie positive, on a
e
(k)
= e
(k+1)
− δ
(k)
≤ ρ(B)e
(k)
+ δ
(k)
.
5 Systèmes linéaires
5.12 Quand doit-on arrêter une méthode itérative ?
En théorie, il faudrait effectuer un nombre infini d’itérations pour obtenir
la solution exacte d’un système linéaire avec une méthode itérative. En
pratique, ce n’est ni nécessaire, ni raisonnable (même si effectivement le
nombre d’itérations pour obtenir la solution avec la précision machine
peut être très élevé pour de grands systèmes). En effet, ce n’est en général
pas d’une solution exacte dont on a besoin, mais plutôt d’une valeur x
(k)
qui approche la solution exacte avec une erreur inférieure à une tolérance
fixée. Mais comme l’erreur est elle-même inconnue (puisqu’elle dépend
de la solution exacte), on a besoin d’un estimateur d’erreur a posteriori
qui donne une estimation de l’erreur à partir de quantités calculées au
cours de la résolution.
Un premier estimateur est donné par le résidu, défini en (5.48). Ainsi,
on peut décider de stopper les itérations à la première étape k min pour
laquelle
r
(kmin)
≤ εb.
En posant
x = x
(kmin) et r = r
(kmin) dans (5.32) on obtient
e
(kmin)
x
≤ εK(A),
qui est une estimation de l’erreur relative. On voit donc que le contrôle
par le résidu n’est pertinent que pour les matrices dont le conditionnement n’est pas trop grand.
Exemple 5.17 Considérons le système linéaire (5.1) où A=A20 est la matrice
de Hilbert de dimension 20 définie dans l’Exemple 5.9. On choisit b pour que
la solution exacte soit x = (1, 1, . . . , 1)
T . Comme A est symétrique définie
positive, on est assuré de la convergence de la méthode de Gauss-Seidel. On
utilise le Programme 5.2 pour résoudre ce système, avec x0 égal au vecteur nul
et une tolérance de 10
−5 sur le résidu. La méthode converge en 472 itérations ;
l’erreur relative est cependant très grande (égale à 0.26). Ceci est dû au fait
que A est extrêmement mal conditionnée (K(A) 10
17 ). Sur la Figure 5.11,
on trace le résidu (normalisé par le résidu initial) et l’erreur en fonction du
nombre d’itérations.
Un autre estimateur est donné par l’incrément δ
(k) = x
(k+1)
− x
(k) .
Autrement dit, on peut choisir de stopper la méthode à la première
itération k min pour laquelle
δ
(kmin)
≤ ε.
(5.65)
Dans le cas particulier où B est symétrique définie positive, on a
e
(k)
= e
(k+1)
− δ
(k)
≤ ρ(B)e
(k)
+ δ
(k)
.