Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

Accueil > Mathématiques > Résolution de systèmes linéaires > Méthode de Gauss-Seidel

Méthode de Gauss-Seidel

Toutes les versions de cet article : [English] [français]

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 :

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

Un message, un commentaire ?

comments powered by Disqus