LG

Outils pour utilisateurs

Outils du site

Piste : • lieur
math:matrices:systeme_lineaire:suite

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentesRévision précédente
Prochaine révision		Révision précédente
math:matrices:systeme_lineaire:suite [2019/02/17 15:26] – Ajout de "Méthode de Jacobi" rootmath:matrices:systeme_lineaire:suite [2020/04/27 08:04] (Version actuelle) – Conversion de <note> vers <WRAP> root
Ligne 2: Ligne 2:
   * Si une suite converge dans un espace vectoriel (ex. $\|x\|_2$ ou $|||A|||_2$), elle converge dans tous les autres espaces vectoriels.   * 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.+  * 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 = M - N$, la suite $x^{p+1} = M^{-1} N x^p + M^{-1} b$ converge si $M + {}^t\!N$ est définie positive.
Ligne 14: Ligne 14:
 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. 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.
  
-====Divers==== +Exemple : 
-$X^{n+1} = X^n-\varrho(AX^n-b)$ avec $A$ symétrique. On obtient le minimum de $\frac{1}{2} (AX,X)_N-(b,X)_N$.+ 
 +$$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. 
 + 
 +<WRAP center round info 60%> 
 +Todo critère chapitre 6. 
 +</WRAP> 
 + 
 +====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$$
  
math/matrices/systeme_lineaire/suite.1550413619.txt.gz · Dernière modification : 2019/02/17 15:26 de root