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 k \in \N.

A = M − N où M 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 − 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

\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 − 1Nx + M − 1b .

Vecteur erreur

Soit e(k) le vecteur erreur

e(k + 1) = x(k + 2) − x(k + 1) = M − 1N(x(k + 1) − x(k)) = 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 \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

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 − 1b

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

Soit r(k) = De(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

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\|} < \varepsilon

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Méthode de Jacobi de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Methode 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • Methode iterative — Méthode itérative En analyse numérique, une méthode itérative résout un problème (comme une équation ou un système d équations) en utilisant une valeur initiale, puis en la raffinant par une succession d approximations se rapprochant… …   Wikipédia en Français

  • Méthode Itérative — En analyse numérique, une méthode itérative résout un problème (comme une équation ou un système d équations) en utilisant une valeur initiale, puis en la raffinant par une succession d approximations se rapprochant graduellement de la solution.… …   Wikipédia en Français

  • Methode de Gauss-Seidel — Méthode de Gauss Seidel La méthode de Gauss Seidel 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… …   Wikipédia en Français

  • Méthode De Gauss-Seidel — La méthode de Gauss Seidel 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. En notant A = [aij]ij …   Wikipédia en Français

  • Méthode de gauss-seidel — La méthode de Gauss Seidel 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. En notant A = [aij]ij …   Wikipédia en Français

  • Jacobi — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Patronyme Jacobi est un nom de famille notamment porté par : Johann Georg Jacobi (1740 1814), poète allemand ; Friedrich Heinrich Jacobi (1743… …   Wikipédia en Français

  • Méthode de surrelaxation successive — En analyse numérique, la méthode de surrelaxation successive est une variante de la méthode de Gauss Seidel pour résoudre un système d équations linéaires. La convergence de cet algorithme est généralement plus rapide. Une approche similaire peut …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”