5.12 Quand doit-on arrêter une méthode itérative ?
173
0
50
100
150
200
250
300
350
400
450
500
10 −6
10 −5
10 −4
10 −3
10 −2
10 −1
10 0
10 1
Figure 5.11. Comportement, en fonction des itérations k, du résidu normalisé
r
(k) /r
(0) (trait discontinu) et de l’erreur x − x
(k) (trait plein) pour les
itérations de Gauss-Seidel appliquées au système de l’Exemple 5.17
Comme ρ(B) doit être strictement plus petit que 1 pour que la méthode
converge, on en déduit
e
(k)
≤
1
1 − ρ(B)
δ
(k)
(5.66)
On voit avec cette dernière inégalité que le contrôle par l’incrément
n’est pertinent que quand ρ(B) est beaucoup plus petit que 1. Dans ce
cas, l’erreur sera en effet du même ordre de grandeur que l’incrément.
On peut tirer la même conclusion quand B n’est pas symétrique définie positive (comme pour les méthodes de Jacobi et Gauss-Seidel) ; mais
dans ce cas (5.66) n’est plus vrai.
Si on s’intéresse aux erreurs relatives, on doit remplacer (5.65) par
δ
(kmin)
b
≤ ε
et par conséquent, (5.66) par
e
(k)
b
≤
1
1 − ρ(B)
ε.
Exemple 5.18 Considérons un système dont la matrice A∈ R
50×50 est tridiagonale, symétrique, dont les coefficients valent 2.001 sur la diagonale principale
et 1 sur la sous- et la sur-diagonale. On choisit comme d’habitude b de manière
à ce que (1, . . . , 1)
T soit la solution exacte. Comme A est tridiagonale et à diagonale dominante stricte, la méthode de Gauss-Seidel converge environ deux
fois plus vite que celle de Jacobi (Proposition 5.4). On utilise le Programme 5.2
173
0
50
100
150
200
250
300
350
400
450
500
10 −6
10 −5
10 −4
10 −3
10 −2
10 −1
10 0
10 1
Figure 5.11. Comportement, en fonction des itérations k, du résidu normalisé
r
(k) /r
(0) (trait discontinu) et de l’erreur x − x
(k) (trait plein) pour les
itérations de Gauss-Seidel appliquées au système de l’Exemple 5.17
Comme ρ(B) doit être strictement plus petit que 1 pour que la méthode
converge, on en déduit
e
(k)
≤
1
1 − ρ(B)
δ
(k)
(5.66)
On voit avec cette dernière inégalité que le contrôle par l’incrément
n’est pertinent que quand ρ(B) est beaucoup plus petit que 1. Dans ce
cas, l’erreur sera en effet du même ordre de grandeur que l’incrément.
On peut tirer la même conclusion quand B n’est pas symétrique définie positive (comme pour les méthodes de Jacobi et Gauss-Seidel) ; mais
dans ce cas (5.66) n’est plus vrai.
Si on s’intéresse aux erreurs relatives, on doit remplacer (5.65) par
δ
(kmin)
b
≤ ε
et par conséquent, (5.66) par
e
(k)
b
≤
1
1 − ρ(B)
ε.
Exemple 5.18 Considérons un système dont la matrice A∈ R
50×50 est tridiagonale, symétrique, dont les coefficients valent 2.001 sur la diagonale principale
et 1 sur la sous- et la sur-diagonale. On choisit comme d’habitude b de manière
à ce que (1, . . . , 1)
T soit la solution exacte. Comme A est tridiagonale et à diagonale dominante stricte, la méthode de Gauss-Seidel converge environ deux
fois plus vite que celle de Jacobi (Proposition 5.4). On utilise le Programme 5.2