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 $k \in \mathbf{N}$.

$A=M-N$ où M est une matrice inversible.

\[\begin{array}{cccc} Ax=b \Leftrightarrow Mx=Nx+b \Leftrightarrow & x &=& M^{-1}Nx+M^{-1}b \\ & &=& F(x) \end{array}\]

où $F$ est une fonction affine.

Algorithme

\[\left\{ \begin{array}{cc} x^{(0)} \textrm{ donne}& ,\\ x^{(k+1)} = M^{-1}Nx^{(k)}+M^{-1}b& \textrm{sinon}. \end{array} \right.\]

Si $x$ est solution de $Ax=b$ alors $x = M^{-1}Nx+M^{-1}b$

Erreur

Soit $e^{(k)}$ le vecteur erreur

\[e^{(k+1)}=x^{(k+1)}-x^{(k)}=M^{-1}N(x^{(k)}-x^{(k-1)})=M^{-1}Ne^{(k)}\]

On pose $B = M^{-1}N$, ce qui donne \(e^{(k+1)}=Be^{(k)}=B^{(k+1)}e^{(0)}.\)

Convergence

L’algorithme converge si $\lim_{k \to \infty} | e^{(k)} | = 0 \Leftrightarrow \lim_{k \to \infty} | B^k | = 0$ (matrice nulle).

Théorème: Une condition nécessaire et suffisante pour que $\lim_{k \to \infty} | B^k | = 0$ est que le rayon spectral de $B$ vérifie \(\rho(B)<1,\) on rappelle que $\rho(B) = \max_{i = 1,\ldots,n} |\lambda_i|$ où $ \lambda_1,\ldots,\lambda_n$ sont les valeurs propres de $B$.

Théorème: si $A$ est à  diagonale strictement dominante \(\left | a_{ii} \right | > \sum_{i \ne j} {\left | a_{ij} \right |},\forall i=1,\ldots,n\) alors pour tout $x_0$ 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=D-E-F\) 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 = D-E$ et $N = F$ (dans la méthode de Jacobi, $M = D$ et $N = E+F$).

\[x^{(k+1)}=(D-E)^{-1}Fx^{(k)}+(D-E)^{-1}b\]

on a alors:

\[x^{(k+1)}_i = \displaystyle\frac{b_i - \displaystyle\sum_{j=1}^{i-1} a_{ij} x^{(k+1)}_j - \displaystyle\sum_{j=i+1}^{n} a_{ij} x^{(k)}_j }{a_{ii}}\]

Test d’arrêt

Pour le test d’arrêt, on utilise le vecteur résidu $r^{(k)}=b-Ax^{(k)}$, ce qui donne, pour une précision donnée $\epsilon$ :

\[\dfrac{\|r^{(k)} \|}{\|b\|}=\frac{\|b-Ax^{(k)} \|}{\|b\|} < \epsilon\]