====Propriétés==== * 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. ====Méthode de Jacobi==== 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}$$ ====Méthode du point fixe==== $$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}$$ ====Méthode de relaxation de Gauss-Seidel==== 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}$$ ====Méthode de sur-relaxation de Southwell==== 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}$$ ====Méthode de Jacobi, préconditionnementn par la diagonale==== 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. Todo critère chapitre 6. ====Méthode de Jacobi, préconditionnement par la sous matrice triangulaire inférieure==== 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$$