164
5 Systèmes linéaires
Méthode de Gauss-Seidel
Quand on applique la méthode de Jacobi, chaque composante x
(k+1)
i
du nouveau vecteur x
(k+1) est calculée indépendamment des autres. On
peut espérer accélérer la convergence si, pour calculer x
(k+1)
i
, on exploite
les nouvelles composantes x
(k+1)
j
, j = 1, . . ., i − 1, en plus des anciennes
x
(k)
j , j ≥ i . Ceci revient à modifier (5.51) comme suit : pour k ≥ 0 (en
supposant encore que a ii = 0 pour i = 1, . . . , n)
x
(k+1)
i
=
1
a ii
⎛
⎝ b i −
i−1
j=1
a ij x
(k+1)
j
−
n
j=i+1
a ij x
(k)
j
⎞
⎠ , i = 1, .., n (5.53)
La mise à jour des composantes est donc à présent séquentielle, alors
que dans la méthode originale de Jacobi, elle se faisait simultanément
(ou en parallèle). La nouvelle méthode, appelée méthode de Gauss-Seidel,
correspond au choix P = D − E et α k = 1, k ≥ 0, dans (5.49), où E est
la matrice triangulaire inférieure dont les coefficients non nuls sont e ij =
−a ij , i = 2, . . ., n, j = 1, . . ., i−1. La matrice d’itération correspondante
est alors
B = (D − E)
−1 (D − E − A).
Une généralisation de cette idée conduit à la méthode de relaxation
dans laquelle P =
1
ω D − E, où ω = 0 est le paramètre de relaxation, et
α k = 1, k ≥ 0 (voir Exercice 5.13).
Pour la méthode de Gauss-Seidel, il existe, comme pour celle de Jacobi, certaines classes de matrices qui donnent des matrices d’itération
satisfaisant les hypothèses de la Proposition 5.2 (celles garantissant la
convergence). Indiquons par exemple :
1. les matrices à diagonale strictement dominante par ligne ;
2. les matrices réelles symétriques définies positives.
La méthode de Gauss-Seidel est implémentée dans le Programme 5.2
(en choisissant P = ’G’).
Il n’y a pas de résultat général établissant que la méthode de GaussSeidel converge toujours plus vite que celle de Jacobi. On peut cependant
l’affirmer dans certains cas, comme le montre la proposition suivante
5 Systèmes linéaires
Méthode de Gauss-Seidel
Quand on applique la méthode de Jacobi, chaque composante x
(k+1)
i
du nouveau vecteur x
(k+1) est calculée indépendamment des autres. On
peut espérer accélérer la convergence si, pour calculer x
(k+1)
i
, on exploite
les nouvelles composantes x
(k+1)
j
, j = 1, . . ., i − 1, en plus des anciennes
x
(k)
j , j ≥ i . Ceci revient à modifier (5.51) comme suit : pour k ≥ 0 (en
supposant encore que a ii = 0 pour i = 1, . . . , n)
x
(k+1)
i
=
1
a ii
⎛
⎝ b i −
i−1
j=1
a ij x
(k+1)
j
−
n
j=i+1
a ij x
(k)
j
⎞
⎠ , i = 1, .., n (5.53)
La mise à jour des composantes est donc à présent séquentielle, alors
que dans la méthode originale de Jacobi, elle se faisait simultanément
(ou en parallèle). La nouvelle méthode, appelée méthode de Gauss-Seidel,
correspond au choix P = D − E et α k = 1, k ≥ 0, dans (5.49), où E est
la matrice triangulaire inférieure dont les coefficients non nuls sont e ij =
−a ij , i = 2, . . ., n, j = 1, . . ., i−1. La matrice d’itération correspondante
est alors
B = (D − E)
−1 (D − E − A).
Une généralisation de cette idée conduit à la méthode de relaxation
dans laquelle P =
1
ω D − E, où ω = 0 est le paramètre de relaxation, et
α k = 1, k ≥ 0 (voir Exercice 5.13).
Pour la méthode de Gauss-Seidel, il existe, comme pour celle de Jacobi, certaines classes de matrices qui donnent des matrices d’itération
satisfaisant les hypothèses de la Proposition 5.2 (celles garantissant la
convergence). Indiquons par exemple :
1. les matrices à diagonale strictement dominante par ligne ;
2. les matrices réelles symétriques définies positives.
La méthode de Gauss-Seidel est implémentée dans le Programme 5.2
(en choisissant P = ’G’).
Il n’y a pas de résultat général établissant que la méthode de GaussSeidel converge toujours plus vite que celle de Jacobi. On peut cependant
l’affirmer dans certains cas, comme le montre la proposition suivante