Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

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

Méthode de Jacobi

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

Un message, un commentaire ?

comments powered by Disqus