Méthode de Jacobi
Les méthodes itératives
Les méthodes itératives pour la résolution d'un système de Cramer $$AX=b$$ de $$n$$ équations à
$$n$$ inconnus consistent à construire une suite $$(X^{(k)})_{k\geq 0}$$ qui converge vers la
solution du système. Plus précisément, on prouve que $$A$$ peut être écrite sous la forme $$A=M-
N$$, avec $$M\in \mathcal{M}_n(R)$$ inversible et $$N\in \mathcal{M}_n(R)$$. Les suites générant
les deux méthodes sont définies par
(0)
𝑋 ∈ 𝑀𝑛, 1 ( \𝑅 ) ,
(𝑘+1) (𝑘)
𝑀 𝑋 =𝑁 𝑋 +𝑏
Les suites ainsi considérées, si elles sont covergentes, convergent nécessairement vers la solution du
système.
La Méthode de Jacobi
La méthode itérative de Jacobi pour résoudre $$(S): AX=b$$, consiste en premier lieu à décomposer
$$A$$ sous la forme: $$A=D-E-F,$$ o\`u $$D$$ est une matrice diagonale, $$E$$ est une matrice
triangulaire inférieure et $$F$$ est une matrice triangulaire supérieure.
$$A= \underbrace{\begin{pmatrix}a_{1,1}& 0 &\cdots &0\\0&\ddots&\ddots&0
\\\vdots&\ddots&\ddots &0 \\0&\cdots& 0& a_{n,n}\end{pmatrix}}_{D}-
\underbrace{\begin{pmatrix}0&\cdots&\cdots&0\\-a_{2,1}&\ddots&& 0 \\\vdots&\ddots&\ddots &0
\\-a_{n,1}&\cdots&-a_{n,n-1}&0\end{pmatrix}}_{E} - \underbrace{\begin{pmatrix}0&-a_{1,2}&\cdots& -
a_{1,n}\\\vdots &\ddots&\ddots& \vdots \\\vdots &&\ddots&-a_{n-1,n}
\\0&\cdots&\cdots&0\end{pmatrix}}_{F}$$
Considérons, par exemple, le cas où $$n=3$$. On a
$$A=\begin{pmatrix}a_{1,1}& a_{1,2} &a_{1,3}\\a_{2,1}&a_{2,2}&a_{2,3}\\a_{3,1}& a_{3,2}&
a_{3,3}\end{pmatrix}\\= \underbrace{\begin{pmatrix}a_{1,1}& 0 &0\\0&a_{2,2}&0 \\0& 0&
a_{3,3}\end{pmatrix}}_{D}- \underbrace{\begin{pmatrix}0&0&0\\-a_{2,1}&0& 0 \\-a_{3,1}&-
a_{3,2}&0\end{pmatrix}}_{E} - \underbrace{\begin{pmatrix}0&-a_{1,2}& -a_{1,3}\\0 &0&-a_{2,3}
\\0&0&0\end{pmatrix}}_{F}$$
Le système $$(S): AX=b$$ est équivalent alors à
$$ DX-(E+F)X=b\Longleftrightarrow DX=(E+F)X+b $$
⎛⎜ X k ⎞⎟
⎜⎜ 1 ⎟⎟
⎜⎜ ⎟
(k )
⎜⎜ k ⎟⎟⎟
Soit $$(X^{(k)})_{k\geq 0}$$ la suite de vecteurs dans $$R^3$$ définie par X = ⎜⎜⎜ X ⎟⎟⎟ , vérifiant
⎜⎜ 2 ⎟⎟
⎜⎜ ⎟
⎜⎜ k ⎟⎟⎟
⎜ X3 ⎟
⎝ ⎠
$$\underbrace{D}_M X^{(k+1)}=\underbrace{(E+F)}_NX^{(k)}+b$$
Si $$A$$ est à diagonale strictement dominante, alors les coefficients diagonaux de $$A$$ sont non
nuls. Par conséquent, $$M$$ est inversible.
Dans ce cas, $$ X^{(k+1)}=M^{-1}NX^{(k)}+M^{-1}b.$$
Remarque:
Si la suite $$(X_k)_{k\geq 0}$$ est convergente, alors
$$\displaystyle\lim_{k\rightarrow +\infty}X^{(k)}=X,$$
avec $$X$$ l'unique solution du système $$(S)$$.
Les composantes du vecteur $$X^{(k+1)}$$ s'écrivent en fonction des composantes du vecteur
$$X^{(k)}$$ comme suit:
$$\begin{pmatrix}a_{1,1}&0&0\\0&a_{2,2}&0 \\0&0&a_{3,3}\end{pmatrix} \begin{pmatrix}x_1^{(k+1)}
\\ x_2^{(k+1)} \\x_3^{(k+1)}\end{pmatrix}= \begin{pmatrix}0&-a_{1,2}&-a_{1,3}\\-a_{2,1}&0&-a_{2,3} \\-
a_{3,1}& -a_{3,2}&0\end{pmatrix} \begin{pmatrix}x_1^{(k)} \\ x_2^{(k)} \\x_3^{(k)}\end{pmatrix}+
\begin{pmatrix}b_1 \\ b_2 \\ b_3\end{pmatrix} $$
Ainsi, on en déduit que
⎧⎪ ⎧⎪
⎪⎪ ⎪⎪ b − a x (k ) − a x (k )
⎪⎪ x (k + 1) = 1 1, 2 2 1, 3 3
⎪⎪ ⎪⎪
⎪⎪
a
⎪⎪ ⎪⎪ 1
⎪⎪ ⎪⎪
⎪⎪ a x (k + 1) + a x (k ) + a x (k ) = b ⎪⎪ 1, 1
⎪⎪ 1, 1 1 1, 2 2 1, 3 3 1
⎪⎪
b − a x (k ) − a x (k )
⎪⎪ ⎪⎪
⎪⎪ ⎪⎪
(k ) (k + 1) (k ) (k + 1) 2 2, 1 1 2, 3 3
⎨⎪ a x +a x + a x = b ⇔ ⎨⎪ x =
⎪ ⎪
⎪⎪ 2, 1 1 2, 2 2 2, 3 3 2 ⎪⎪ 2 a
2, 2
⎪⎪ ⎪⎪
(k ) (k ) (k + 1)
⎪⎪ a x + a x + a x =b
⎪⎪ ⎪⎪
⎪⎪
⎪⎪ 3, 1 1 3, 2 2 3, 3 3 3 (k ) (k )
⎪⎪ (k + 1) b 3 − a 3, 1x 1 − a 3, 2x 2
⎪⎪
⎪⎪
⎪⎪ ⎪⎪ x =
a
⎪⎪ ⎪⎪ 3
⎪⎪ ⎪⎪
⎪⎩ ⎪⎩ 3, 3
Dans $$R^n$$, les composantes $$x_i^{(k+1)}$$ ($$i\in\{0,1,\cdots,n\}$$) du vecteur $$X^{(k+1)}$$
s'écrivent en fonction des composantes $$x_i^{(k)}$$ du vecteur $$X^{(k)}$$ comme suit:
$$x_i^{(k+1)}=\frac{1}{a_{ii}} \left( b_i-\sum \limits_{j=1, j\neq i}^{n} a_{ij} x_j^{(k)} \right),~~\forall i\in\
{1,\cdots ,n\}$$
Convergence de la méthode de Jacobi
Question: Existe-il une condition sur la matrice $$A$$ assurant la convergence de la suite
$$(X^{(k)})_{k\geq 0}$$ est convergente?
Théorème:
Soit $$A$$ une matrice à diagonale strictement dominante alors la méthode de Jacobi appliquée au
système $$(S): AX=b$$ est convergente vers la solution de $$(S)$$ pour tout
$$X^{(0)}\in\mathcal{M}_{n,1}(R)$$.
Remarque:
On peut considérer le critère d’arrêt suivant pour la méthode de Jacobi:
$$||AX^{(k)}-b|| \leq \varepsilon$$ avec $$\varepsilon$$ très petit.
On dit que $$\varepsilon$$ est une tolérance.
Étude d'un exemple
On considère un système d'équations linéaires $$(S)$$, telle que $$(S) \Leftrightarrow AX=b$$ avec
⎛⎜ X ⎞⎟
⎛⎜ 5 2 − 1 ⎞⎟ ⎜⎜ 1 ⎟⎟ ⎛⎜ 6 ⎞⎟
⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟
A = ⎜⎜⎜ 1 6 − 3 ⎟⎟⎟ , X = ⎜⎜⎜ X 2 ⎟⎟⎟ et b = ⎜⎜⎜⎜ 4 ⎟⎟⎟⎟
⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ ⎜ ⎟
⎜⎜ ⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟
⎜ 2 1 4 ⎟⎟ ⎜2⎟
X
⎜⎜ ⎟⎟
⎝ ⎠ ⎜ ⎟ ⎝ ⎠
⎝ 3⎠
1- Montrer qu’il existe une unique solution de $$(S)$$ dans $$R^3$$.
2- Etudier la convergence de la méthode de Jacobi pour la résolution de $$(S)$$.
3- Donner le schéma itératif de la méthode de Jacobi associé à $$(S)$$.
4- Calculer les quatres premiers itérés par la méthode de Jacobi.
1- Existence d'une unique solution de $$(S)$$ dans $$R^3$$ :
On a $$\det(A)=126\neq 0$$ $$\Rightarrow$$ $$\exists!\,X\in R^3$$ / $$AX=b$$.
2- Etude de la convergence de la méthode de Jacobi pour la résolution de $$(S)$$:
On a:
|𝑎1, 1 | > | 𝑎1, 2 | + | 𝑎1, 3 | ( 𝑐𝑎𝑟 |5| > |2| + | -1| )
|𝑎2, 2 | > | 𝑎2, 1 | + | 𝑎2, 3 | ( 𝑐𝑎𝑟 |6| > |1| + | -3| )
|𝑎3, 3 | > | 𝑎3, 1 | + | 𝑎3, 2 | 𝑐𝑎𝑟 |4| > |2| + |1| )
$$\Rightarrow A$$ est une matrice à diagonale strictement dominante.
$$\Rightarrow$$ La méthode de Jacobi est convergente.
3- Schéma itératif associé à
(S)
avec la méthode de Jacobi:
4- Application de la méthode de Jacobi avec $$4$$ itérations:
Considérons par exemple un vecteur initial $$X^{(0)}=\begin{pmatrix}0 \\ 0\\0\end{pmatrix}$$.
• Itération 1 : $$X^{(1)}=\begin{pmatrix}6/5 \\ 2/3\\7/4\end{pmatrix}$$
• Itération 2 : $$X^{(2)}=\begin{pmatrix}1,2833\\1,3417\\0,9833\end{pmatrix}$$
• Itération 3 : $$X^{(3)}= \begin{pmatrix}0,86\\0,9444\\0.7729\end{pmatrix}$$
• Itération 4 : $$X^{(4)}= \begin{pmatrix} 0,9768 \\0,9098\\1,0839\end{pmatrix}$$