174
5 Systèmes linéaires
pour résoudre ce système, mais on remplace le test d’arrêt basé sur le résidu
par un test basé sur l’incrément, i.e. δ
(k) ≤ ε. Avec une donnée initiale dont
les composantes sont (x0)i = 10 sin(100i) (pour i = 1, . . . , n) et une tolérance
tol= 10
−5 , le programme donne, après 859 itérations, une solution telle que
e
(859) 0.0021. La convergence est très lente et l’erreur assez grande car le
rayon spectral de la matrice (environ 0.9952) est très proche de 1. Si les coefficients diagonaux valent 3, on obtient après seulement 17 itérations une erreur
e
(17) 8.96 · 10
−6 . Dans ce cas, le rayon spectral de la matrice d’itération
est égal à 0.443.
Résumons-nous
1. Résoudre un système linéaire avec une méthode itérative consiste à
construire, en partant d’une donnée initiale x
(0) , une suite de vecteurs x
(k) convergeant vers la solution exacte quand k → ∞ ;
2. une méthode itérative converge pour toute donnée initiale x
(0) ssi
le rayon spectral de la matrice d’itération est strictement plus petit
que 1 ;
3. les méthodes itératives traditionnelles sont celles de Jacobi et de
Gauss-Seidel. Une condition suffisante de convergence est que la matrice soit à diagonale strictement dominante par ligne (ou symétrique
définie positive dans le cas de Gauss-Seidel) ;
4. dans la méthode de Richardson, la convergence est accélérée à
l’aide d’un paramètre et (éventuellement) d’un préconditionneur bien
choisi ;
5. avec la méthode du gradient conjugué, la solution d’un système symétrique défini positif est calculée en un nombre fini d’itérations (en
arithmétique exacte). Cette méthode peut se généraliser au cas non
symétrique ;
6. on a deux critères d’arrêt possible pour les méthodes itératives : l’un
basé sur le résidu, l’autre sur l’incrément. Le premier est pertinent
quand le système est bien conditionné, le second quand le rayon
spectral de la matrice d’itération n’est pas trop proche de 1.
5.13 Pour finir : méthode directe ou itérative ?
Dans cette section, on compare méthodes directes et itératives pour divers cas tests simples. Pour les systèmes linéaires de petite taille, le choix
n’a pas beaucoup d’importance car toutes les méthodes feront l’affaire.
En revanche, pour les grands systèmes linéaires, le choix dépendra principalement des propriétés de la matrice (telles que la symétrie, la définie positivité, la structure creuse, le conditionnement), mais également
5 Systèmes linéaires
pour résoudre ce système, mais on remplace le test d’arrêt basé sur le résidu
par un test basé sur l’incrément, i.e. δ
(k) ≤ ε. Avec une donnée initiale dont
les composantes sont (x0)i = 10 sin(100i) (pour i = 1, . . . , n) et une tolérance
tol= 10
−5 , le programme donne, après 859 itérations, une solution telle que
e
(859) 0.0021. La convergence est très lente et l’erreur assez grande car le
rayon spectral de la matrice (environ 0.9952) est très proche de 1. Si les coefficients diagonaux valent 3, on obtient après seulement 17 itérations une erreur
e
(17) 8.96 · 10
−6 . Dans ce cas, le rayon spectral de la matrice d’itération
est égal à 0.443.
Résumons-nous
1. Résoudre un système linéaire avec une méthode itérative consiste à
construire, en partant d’une donnée initiale x
(0) , une suite de vecteurs x
(k) convergeant vers la solution exacte quand k → ∞ ;
2. une méthode itérative converge pour toute donnée initiale x
(0) ssi
le rayon spectral de la matrice d’itération est strictement plus petit
que 1 ;
3. les méthodes itératives traditionnelles sont celles de Jacobi et de
Gauss-Seidel. Une condition suffisante de convergence est que la matrice soit à diagonale strictement dominante par ligne (ou symétrique
définie positive dans le cas de Gauss-Seidel) ;
4. dans la méthode de Richardson, la convergence est accélérée à
l’aide d’un paramètre et (éventuellement) d’un préconditionneur bien
choisi ;
5. avec la méthode du gradient conjugué, la solution d’un système symétrique défini positif est calculée en un nombre fini d’itérations (en
arithmétique exacte). Cette méthode peut se généraliser au cas non
symétrique ;
6. on a deux critères d’arrêt possible pour les méthodes itératives : l’un
basé sur le résidu, l’autre sur l’incrément. Le premier est pertinent
quand le système est bien conditionné, le second quand le rayon
spectral de la matrice d’itération n’est pas trop proche de 1.
5.13 Pour finir : méthode directe ou itérative ?
Dans cette section, on compare méthodes directes et itératives pour divers cas tests simples. Pour les systèmes linéaires de petite taille, le choix
n’a pas beaucoup d’importance car toutes les méthodes feront l’affaire.
En revanche, pour les grands systèmes linéaires, le choix dépendra principalement des propriétés de la matrice (telles que la symétrie, la définie positivité, la structure creuse, le conditionnement), mais également