LG

Outils pour utilisateurs

Outils du site

Piste :
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 16:17] – Ajout de "Méthode du point fixe" 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 131: Ligne 131:
  
 Valeur optimale de $\varrho =\frac{2}{\lambda_1 + \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.1550416663.txt.gz · Dernière modification : 2019/02/17 16:17 de root