Nous allons étudier une méthode itérative de résolution de système linéaire : la méthode de Gauss-Seidel. L’objectif est de construire une suite vectorielle convergente vers la solution du système linéaire.

Principe de construction

La méthode de Gauss-Seidel est une méthode itérative de résolution de système linéaire de la forme

Ax=b

Pour cela, on utilise une suite x(k) qui converge vers un point fixe x, solution du système d’équations linéaires. On cherche à  construire l’algorithme pour x(0) donné, la suite x(k+1)=F(x(k)) avec kN.

A=MN où M est une matrice inversible.

Ax=bMx=Nx+bx=M1Nx+M1b=F(x)

F est une fonction affine.

Algorithme

{x(0) donne,x(k+1)=M1Nx(k)+M1bsinon.

Si x est solution de Ax=b alors x=M1Nx+M1b

Erreur

Soit e(k) le vecteur erreur

e(k+1)=x(k+1)x(k)=M1N(x(k)x(k1))=M1Ne(k)

On pose B=M1N, ce qui donne e(k+1)=Be(k)=B(k+1)e(0).

Convergence

L’algorithme converge si limk|e(k)|=0limk|Bk|=0 (matrice nulle).

Théorème: Une condition nécessaire et suffisante pour que limk|Bk|=0 est que le rayon spectral de B vérifie ρ(B)<1, on rappelle que ρ(B)=maxi=1,,n|λi|λ1,,λn sont les valeurs propres de B.

Théorème: si A est à  diagonale strictement dominante |aii|>ij|aij|,i=1,,n alors pour tout x0 la méthode de Gauss-Seidel converge vers la solution x du système Ax=b.

Méthode de Gauss-Seidel

On décompose la matrice A de la façon suivante :A=DEF avec

  • D la diagonale
  • E la partie en dessous de la diagonale
  • F la partie au dessus.

Dans la méthode de Gauss-Seidel, on choisit M=DE et N=F (dans la méthode de Jacobi, M=D et N=E+F).

x(k+1)=(DE)1Fx(k)+(DE)1b

on a alors:

xi(k+1)=bij=1i1aijxj(k+1)j=i+1naijxj(k)aii

Test d’arrêt

Pour le test d’arrêt, on utilise le vecteur résidu r(k)=bAx(k), ce qui donne, pour une précision donnée ϵ :

r(k)b=bAx(k)b<ϵ