Méthode de Gauss-Seidel

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

A x = 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 N$ .

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

\begin{array}{cccc} A x = b \Leftrightarrow M x = N x + b \Leftrightarrow & x & = & M^{- 1} N x + M^{- 1} b \\ = & F (x) \end{array}

où $F$ est une fonction affine.

Algorithme

{\begin{array}{cc} x^{(0)} donne & , \\ x^{(k + 1)} = M^{- 1} N x^{(k)} + M^{- 1} b & sinon . \end{array}

Si $x$ est solution de $A x = b$ alors $x = M^{- 1} N x + 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} N e^{(k)}

On pose $B = M^{- 1} N$ , ce qui donne $e^{(k + 1)} = B e^{(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 $ρ (B) < 1,$ on rappelle que $ρ (B) = max_{i = 1, \dots, n} | λ_{i} |$ où $λ_{1}, \dots, λ_{n}$ sont les valeurs propres de $B$ .

Théorème: si $A$ est à diagonale strictement dominante $| a_{i i} | > \sum_{i \neq j} | a_{i j} |, \forall i = 1, \dots, n$ alors pour tout $x_{0}$ la méthode de Gauss-Seidel converge vers la solution $x$ du système $A x = b .$