Méthode de Jacobi

Restez toujours informé : suivez-nous sur Google (☆)

Introduction

La méthode de Jacobi, due au mathématicien allemand Karl Jacobi, est une méthode iterative de résolution d'un système matriciel de la forme Ax=b. Pour cela, on utilise une suite x qui converge vers un point fixe x, solution du système d'équations linéaires.

Principe de construction

On cherche à construire l'algorithme pour x donné, la suite x = F(x) avec $k \in N$ .

A x = b \Leftrightarrow M x = N x + b \Leftrightarrow x = M^{- 1} N x + M^{- 1} b = F (x)

A = M − N où M est une matrice inversible.
où F est une fonction affine.

Algorithme

${x^{(0)} connu x^{(k + 1)} = M^{- 1} N x^{(k)} + M^{- 1} b$
Si x est solution de A**x = b alors x = M N**x + M b .

Vecteur erreur

Soit e le vecteur erreur

e = x − x = M N(x − x) = M N**e
On pose B = M N, ce qui donne e = B**e = B**e.

Convergence

k \to \infty lim ∣ e^{(k)} ∣ = 0 ⟺ k \to \infty lim ∣ B^{k} ∣ = 0

L'algorithme converge si (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 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 = D (E + F)x + D b $x_{i}^{(k + 1)} = \dots x^{(k)} i + \frac{b _{i}}{a ii}$ avec
pour la ligne i de D (E + F) : $- (\frac{a _{i, 1}}{a _{i, i}}, \dots, \frac{a _{i, i - 1}}{a _{i, i}}, 0, \frac{a _{i, i + 1}}{a _{i, i}}, \dots, \frac{a _{i, n}}{a _{i, i}})$

x^{(k + 1)} i = - \frac{1}{a ii} j \neq = i j = 1 \sum n a_{ij} x^{(k)} j + \frac{b _{i}}{a ii}

Vecteur résidu

Soit r = D**e 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 \neq = l j = 1}^{n} a_{l, j} \frac{r _{l}^{(k)}}{a _{j, j}}$ .

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 ε : $\frac{∣ r ^{(k)} ∣}{∣ b ∣} < ε$

Conclusion

Cette méthode a un coût de l'ordre de 3n²+2n par itération, elle est très facilement parallélisable contrairement à la méthode de Gauss-Seidel, mais qui converge plus vite.