Méthode de Jacobi

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant l’algèbre
Cet article est une ébauche concernant l’algèbre.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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 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 donné, la suite avec .

A=M-NM est une matrice inversible.


où F est une fonction affine. 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 (si la matrice M est diagonale, sinon se référer à la section convergence)

Algorithme[modifier | modifier le code]


Si x est solution de Ax=b alors .

Vecteur erreur[modifier | modifier le code]

Soit le vecteur erreur

On pose , ce qui donne .

Convergence[modifier | modifier le code]

L'algorithme converge si (c-à-d. Bk tend vers la matrice nulle).

Théorème — Une condition nécessaire et suffisante pour que 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 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).

avec
pour la ligne i de  :


Vecteur résidu[modifier | modifier le code]

Soit le vecteur résidu. On peut écrire avec que l'on calcule de la manière suivante :

.

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  :

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]