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

Principe de construction

La méthode de Jacobi 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} \lvert\lambda_i\rvert$ 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 Jacobi converge vers la solution $x$ du système $Ax=b.$

Méthode de Jacobi

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 Jacobi, on choisit $M = D$ et $N = E+F$ (dans la méthode de Gauss-Seidel, $M = D-E$ et $N = F$).

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

avec pour la ligne $i$ de $D^{-1}(E+F)$ : $-(\dfrac{a_{i,1}}{a_{i,i}},\cdots, \dfrac{a_{i,i-1}}{a_{i,i}},0,\dfrac{a_{i,i+1}}{a_{i,i}},\cdots, \dfrac{a_{i,n}}{a_{i,i}})$

on a alors:

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

Résidu

Soit $r^{(k)}=b-Ax^{(k)}$ le vecteur résidu. On peut écrire $x_i^{(k+1)}=\frac{r_i^{(k)}}{a_{ii}} + x_i^{(k)}$ avec $r_i^{(k)}$ que l’on calcule de la manière suivante :

\[r_i^{(k+1)}=-\sum_{j=1,j \ne i}^n a_{ij} \frac{r_i^{(k)}}{a_{jj}}\]

Test d’arrêt

Pour le test d’arrêt, on utilise le vecteur résidu, ce qui donne, pour une précision donnée $\epsilon$ :

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