Accueil > Mathématiques > Résolution de systèmes linéaires > Méthode de Jacobi

Méthode de Jacobi

samedi 20 mai 2006, par Nadir SOUALEM

Mots-clés: .

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 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-NM 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}

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| \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) : -(\frac{a_{i,1}}{a_{i,i}},\cdots, \frac{a_{i,i-1}}{a_{i,i}},0,\frac{a_{i,i+1}}{a_{i,i}},\cdots, \frac{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 :

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

Messages

Un message, un commentaire ?

modération a priori

Ce forum est modéré a priori : votre contribution n'apparaîtra qu'après avoir été validée par un administrateur du site.

Qui êtes-vous ?
Votre message
  • Pour créer des paragraphes, laissez simplement des lignes vides.

Si vous souhaitez aider financièrement le projet Math-Linux.com, vous pouvez aider notre équipe. Merci !!!

Links