Méthode de Jacobi

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La méthode de Jacobi, due au mathématicien allemand Karl Jacobi, est une méthode itérative de résolution d'un système matriciel 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.

Principe de construction[modifier | modifier le code]

On cherche à construire, pour x^{(0)} donné, la suite x^{(k+1)}=F(x^{(k)}) avec k \in \N.

A=M-NM est une matrice inversible.

\begin{matrix}
Ax=b \Leftrightarrow 
Mx=Nx+b \Leftrightarrow & x &=& M^{-1}Nx+M^{-1}b \\  & &=& F(x)\end{matrix}
où F est une fonction affine. M^{-1}N est alors appelée matrice de Jacobi.

Attention, l'algorithme qui suit n'est valable que si la matrice A est à diagonale strictement dominante sur les lignes.

Algorithme[modifier | modifier le code]


\left\{
\begin{array}{l} 
x^{(0)} \; \mbox{connu}\\ 
x^{(k+1)} = M^{-1}Nx^{(k)}+M^{-1}b 
\end{array} 
\right.


Si x est solution de Ax=b alors x = M^{-1}Nx+M^{-1}b .

Vecteur erreur[modifier | modifier le code]

Soit e^{(k)} le vecteur erreur

e^{(k+1)}=x^{(k+2)}-x^{(k+1)}=M^{-1}N(x^{(k+1)}-x^{(k)})=M^{-1}Ne^{(k)}

On pose B = M^{-1}N, ce qui donne e^{(k+1)}=Be^{(k)}=B^{k+1}e^{(0)}.

Convergence[modifier | modifier le code]

L'algorithme converge si \lim_{k \to \infty} \| e^{(k)} \| = 0 \Longleftrightarrow \lim_{k \to \infty} \| B^k \| = 0 (c-à-d. Bk tend vers la 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 (plus grande valeur propre en module) de B soit strictement inférieur à 1.

Théorème — La méthode converge quel que soit x^{(0)} pour les systèmes linéaires dont la matrice est à diagonale strictement dominante.

Méthode de Jacobi[modifier | modifier le code]

On décompose la matrice A de la façon suivante : A=D-E-F avec D la matrice diagonale de A, -E la matrice triangulaire inférieure de A de diagonale nulle et -F la matrice triangulaire supérieure de diagonale nulle. 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 x^{(k+1)}_i=\cdots x^{(k)}_i+\frac{b_i}{a_{ii}} avec
pour la ligne i de D^{-1}(E+F) : -\left(\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}}\right)


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

Vecteur résidu[modifier | modifier le code]

Soit r^{(k)}=D e^{(k)} le vecteur résidu. On peut écrire x_i^{(k+1)}=\frac{r_i^{(k)}}{a_{i,i}} + x_i^{(k)} avec r_i^{(k)} que l'on calcule de la manière suivante :

r_l^{(k+1)}=-\sum_{j=1 \atop j \ne l}^n a_{l,j} \frac{r_l^{(k)}}{a_{j,j}}.

Test d'arrêt[modifier | modifier le code]

Pour le test d'arrêt, on utilise l'erreur relative sur le vecteur résidu, ce qui donne, pour une précision donnée \varepsilon : \frac{\|r^{(k)} \|}{\|b\|} < \varepsilon

Conclusion[modifier | modifier le code]

Cette méthode a un coût de l'ordre de 3n2+2n par itération. Elle converge moins vite que la méthode de Gauss-Seidel, mais est très facilement parallélisable.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]