LG

• Si une suite converge dans un espace vectoriel (ex. $\|x\|_2$ ou $|||A|||_2$), elle converge dans tous les autres espaces vectoriels.

• La suite $x^{p+1} = S x^p + d$ converge si le rayon spectral de S (plus grande valeur propre en valeur absolue) est inférieur à 1.

• Soit $A = M - N$, la suite $x^{p+1} = M^{-1} N x^p + M^{-1} b$ converge si $M + {}^t\!N$ est définie positive.

Soit $A = D - E - F$ avec D matrice diagonale, $-E$ matrice diagonale triangulaire inférieure de $A$, $-F$ matrice diagonale triangulaire supérieure de $A$.

$$x^{p+1} = D^{-1}(E+F)x^p+D^{-1}b$$

Critère de convergence : $A$ est à diagonale strictement dominante pour que la matrice d'itération $D^{-1} (E+F)$ ait un rayon spectral inférieur à 1.

Exemple :

$$A = \begin{pmatrix} 3 & 1 & 1 \\ 1 & -4 & 2 \\ -1 & 2 & 4 \\ \end{pmatrix}$$

et b l'objectif : $$b = \begin{pmatrix} 2 \\ 1 \\ 4 \\ \end{pmatrix}$$

Le résultat attendu est $$x = \begin{pmatrix} 0.264706 \\ 0.279412 \\ 0.926471 \\ \end{pmatrix}$$

On y va : $$D = \begin{pmatrix} 3 & 0 & 0 \\ 0 & -4 & 0 \\ 0 & 0 & 4 \\ \end{pmatrix}$$ $$D^{-1} = \begin{pmatrix} 1/3 & 0 & 0 \\ 0 & -1/4 & 0 \\ 0 & 0 & 1/4 \\ \end{pmatrix}$$ $$E = \begin{pmatrix} 0 & 0 & 0 \\ -1 & 0 & 0 \\ 1 & -2 & 0 \\ \end{pmatrix}$$ $$F = \begin{pmatrix} 0 & -1 & -1 \\ 0 & 0 & -2 \\ 0 & 0 & 0 \\ \end{pmatrix}$$ $$E+F = \begin{pmatrix} 0 & -1 & -1 \\ -1 & 0 & -2 \\ 1 & -2 & 0 \\ \end{pmatrix}$$ $$D^{-1}(E+F) = \begin{pmatrix} 0 & -1/3 & -1/3 \\ 1/4 & 0 & 1/2 \\ 1/4 & -1/2 & 0 \\ \end{pmatrix}$$

On pause : $$x^0 = \begin{pmatrix} 0 \\ 0 \\ 0 \\ \end{pmatrix}$$ $$x^{1} = D^{-1}(E+F)x^0+D^{-1}b$$ $$x^1 = \begin{pmatrix} 0.66666 \\ -0.25 \\ 1 \\ \end{pmatrix}$$ $$x^2 = \begin{pmatrix} 0.4166 \\ 0.4166 \\ 1.2916 \\ \end{pmatrix}$$ $$x^5 = \begin{pmatrix} 0.334491 \\ 0.1875 \\ 0.939236 \\ \end{pmatrix}$$ $$x^{10} = \begin{pmatrix} 0.269286 \\ 0.283549 \\ 0.937478 \\ \end{pmatrix}$$ $$x^{20} = \begin{pmatrix} 0.264648 \\ 0.27936 \\ 0.926332 \\ \end{pmatrix}$$ $$x^{30} = \begin{pmatrix} 0.264707 \\ 0.279412 \\ 0.926472 \\ \end{pmatrix}$$

$$x^{p+1} = (I-\varrho A) x^p + \varrho b$$

Critère de convergence :

• rayon spectral de $I-\varrho A$ soit inférieur à 1
• $0 < \varrho < 2 / \lambda_N$.

Valeur optimale de $\varrho =\frac{2}{\lambda_1 + \lambda_N}$

Exemple :

$$A \begin{pmatrix} 5 & 2 & 1 \\ 5 & 6 & 2 \\ -4 & 2 & 1 \\ \end{pmatrix} $$

et b l'objectif : $$b = \begin{pmatrix} 1 \\ 2 \\ 3 \\ \end{pmatrix}$$

Le résultat attendu est $$x = \begin{pmatrix} -0.22222 \\ -0.55555 \\ 3.22222 \\ \end{pmatrix}$$

Les valeurs propres de A sont : 0.827344, 2.51213 et 8.66053.

$\varrho =\frac{2}{0.827344 + 8.66053} = 0.210795$

$$I-\varrho A = \begin{pmatrix} -0.053977 & -0.421591 & -0.210795 \\ -1.05398 & -0.264772 & -0.421591 \\ 0.843182 & -0.421591 & 0.789205 \\ \end{pmatrix}$$

Rayon spectrale (plus grande valeur propre en valeur absolue) de $I-\varrho A$ : $0.8256$

$$\varrho b = \begin{pmatrix} 0.210795 \\ 0.421591 \\ 0.632386 \\ \end{pmatrix}$$

Soit $x^{p+1}=(I-\varrho A)x^p + \varrho b$.

$$x^0 = \begin{pmatrix} 0 \\ 0 \\ 0 \\ \end{pmatrix}$$ $$x^1 = \begin{pmatrix} 0.210795 \\ 0.421591 \\ 0.632386 \\ \end{pmatrix}$$ $$x^5 = \begin{pmatrix} -0.038406 \\ -0.102398 \\ 2.06383 \\ \end{pmatrix}$$ $$x^{10} = \begin{pmatrix} -0.202545 \\ -0.474434 \\ 2.78176 \\ \end{pmatrix}$$ $$x^{20} = \begin{pmatrix} -0.219334 \\ -0.543621 \\ 3.15744 \\ \end{pmatrix}$$ $$x^{50} = \begin{pmatrix} -0.222213 \\ -0.555518 \\ 3.22202 \\ \end{pmatrix}$$

Soit $A = D - E - F$ avec D matrice diagonale, $-E$ matrice diagonale triangulaire inférieure de $A$, $-F$ matrice diagonale triangulaire supérieure de $A$.

$$x^{p+1} = (D-E)^{-1}Fx^p+(D-E)^{-1}b$$

Critère de convergence :

• A est symétrique et définie positive.
• A est à diagonale strictement dominante.

Exemple :

$$ A = \begin{pmatrix} 3 & 1 & 1 \\ 1 & 4 & 2 \\ 1 & 2 & 4 \end{pmatrix} $$

et b l'objectif : $$b = \begin{pmatrix} 1 \\ 2 \\ 3 \\ \end{pmatrix}$$

Le résultat attendu est $$x = \begin{pmatrix} 0.0625 \\ 0.15625 \\ 0.65625 \\ \end{pmatrix}$$

Les valeurs propres A sont : 2, 2.43845 et 6.56155. Elles sont toutes supérieures à 0.

$$ D = \begin{pmatrix} 3 & 0 & 0 \\ 0 & 4 & 0 \\ 0 & 0 & 4 \end{pmatrix} $$

$$ E = \begin{pmatrix} 0 & 0 & 0 \\ -1 & 0 & 0 \\ -1 & -2 & 0 \end{pmatrix} $$

$$ F = \begin{pmatrix} 0 & -1 & -1 \\ 0 & 0 & -2 \\ 0 & 0 & 0 \end{pmatrix} $$

$$ D-E = \begin{pmatrix} 3 & 0 & 0 \\ 1 & 4 & 0 \\ 1 & 2 & 4 \end{pmatrix} $$

$$ (D-E)^{-1} = \begin{pmatrix} 0.333333 & 0 & 0 \\ -0.083333 & 0.25 & 0 \\ -0.041666 & -0.125 & 0.25 \end{pmatrix} $$

$$ (D-E)^{-1}F = \begin{pmatrix} 0 & -0.333333 & -0.333333 \\ 0 & 0.083333 & -0.416666 \\ 0 & 0.041666 & 0.291666 \end{pmatrix} $$

$$ (D-E)^{-1}b = \begin{pmatrix} 0.333333 \\ 0.416666 \\ 0.458333 \end{pmatrix} $$

$$x^0 = \begin{pmatrix} 0 \\ 0 \\ 0 \\ \end{pmatrix}$$ $$x^1 = (D-E)^{-1}Fx^0+(D-E)^{-1}b$$ $$x^1 = \begin{pmatrix} 0.333333 \\ 0.416666 \\ 0.458333 \\ \end{pmatrix}$$ $$x^5 = \begin{pmatrix} 0.060936 \\ 0.157414 \\ 0.656059 \\ \end{pmatrix}$$ $$x^{10} = \begin{pmatrix} 0.0625 \\ 0.15625 \\ 0.65625 \\ \end{pmatrix}$$

On garde les mêmes hypothèses que la relaxation de Gauss-Seidel.

$$x^{p+1} = \left(\frac{D}{\omega}-E \right)^{-1} \left(F + \frac{1-\omega}{\omega} D \right) x^p + \left(\frac{D}{\omega}-E \right)^{-1} b$$

$\omega = \frac{2}{1+\sqrt{1-\varrho(J)^2}}$ avec $J = D^{-1}(E+F)$. Cette formule n'est valable que si $A$ est tridiagonale.

Critère de convergence :

• A est symétrique et définie positive.
• A est à diagonale strictement dominante.
• $0 < \omega < 2$
• $\varrho(J) < 1$

Exemple :

$$ A = \begin{pmatrix} 3 & 1 & 0 \\ 1 & 4 & 2 \\ 0 & 2 & 4 \end{pmatrix} $$

et b l'objectif : $$b = \begin{pmatrix} 1 \\ 2 \\ 3 \\ \end{pmatrix}$$

Le résultat attendu est $$x = \begin{pmatrix} 0.3125 \\ 0.0625 \\ 0.71875 \\ \end{pmatrix}$$

Les valeurs propres A sont : 1.60862, 3.22713 et 6.16425. Elles sont toutes supérieures à 0.

$$J = \begin{pmatrix} 0 & -0.333333 & 0 \\ -0.25 & 0 & -0.5 \\ 0 & -0.5 & 0 \\ \end{pmatrix}$$

Les valeurs propres J sont : -0.57735, 0 et 0.57735. Le rayon spectral vaut 0.57735.

$$\omega = \frac{2}{1+\sqrt{1-0.57735^2}} = 1.10102$$

$$\left(\frac{D}{\omega}-E \right)^{-1} \left(F + \frac{1-\omega}{\omega} D \right) = \begin{pmatrix} -0.10102 & -0.367007 & 0 \\ 0.027806 & 0 & -0.55051 \\ -0.015308 & 0 & 0.202041 \\ \end{pmatrix} $$

$$\left(\frac{D}{\omega}-E \right)^{-1} b = \begin{pmatrix} 0.367007 \\ 0.44949 \\ 0.578317 \\ \end{pmatrix}$$

$$x^0 = \begin{pmatrix} 0 \\ 0 \\ 0 \\ \end{pmatrix}$$ $$x^1 = \begin{pmatrix} 0.367007 \\ 0.44949 \\ 0.578317 \\ \end{pmatrix}$$ $$x^5 = \begin{pmatrix} 0.312208 \\ 0.062704 \\ 0.71869 \\ \end{pmatrix}$$ $$x^{10} = \begin{pmatrix} 0.3125 \\ 0.0625 \\ 0.71875 \\ \end{pmatrix}$$

Soit $A = D - E - F$ avec D matrice diagonale, $-E$ matrice diagonale triangulaire inférieure de $A$, $-F$ matrice diagonale triangulaire supérieure de $A$.

$$x^{p+1} = ((1-\varrho)I_n + \varrho D^{-1}(E+F))x^p+\varrho D^{-1}b$$

Critère de convergence : pas besoin que $A$ dit à diagonale strictement dominante.

Soit

• $x=\sqrt{D^{-1}}y$
• $\widetilde{A}=\sqrt{D^{-1}} A \sqrt{D^{-1}}$
• $\widetilde{b}=\sqrt{D^{-1}}b$
• $\widetilde{D} = I_n$
• $E$ est à la fois la matrice diagonale et la matrice triangulaire inférieure.

$$y^{n+1}=[I_n - \varrho (\widetilde{D} - {}^t\!\widetilde{E})^{-1}(\widetilde{D} - \widetilde{E})^{-1}\widetilde{A}]y^n + \varrho (\widetilde{D} - {}^t\!\widetilde{E})^{-1}(\widetilde{D} - \widetilde{E})^{-1}b$$