- Méthode de jacobi
-
Méthode de Jacobi
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.
Sommaire
Principe de construction
On cherche à construire l'algorithme pour x(0) donné, la suite x(k + 1) = F(x(k)) avec .
A = M − N où M est une matrice inversible.
où F est une fonction affine. M − 1N 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
Si x est solution de Ax = b alors x = M − 1Nx + M − 1b .Vecteur erreur
Soit e(k) le vecteur erreur
e(k + 1) = x(k + 1) − x(k) = M − 1N(x(k) − x(k − 1)) = M − 1Ne(k)
On pose B = M − 1N, ce qui donne e(k + 1) = Be(k) = B(k + 1)e(0).Convergence
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 x(0) pour les systèmes linéaires dont la matrice est à diagonale strictement dominante.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 et -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 − 1b
avec
pour la ligne i de D − 1(E + F) :
Vecteur résidu
Soit r(k) = De(k) le vecteur résidu. On peut écrire avec que l'on calcule de la manière suivante :.
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 ε :
Conclusion
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
Articles connexes
Liens externes
- (fr) Méthode de Jacobi
- Portail des mathématiques
Catégorie : Analyse numérique matricielle
Wikimedia Foundation. 2010.