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) 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}$$