Différences

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

--- math:matrices:systeme_lineaire:suite [2019/02/17 18:09] – Ajout de "Méthode de relaxation de Gauss-Seidel" root
+++ math: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.
-  * 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.
@@ Ligne 224: / Ligne 224: @@
 $$x^{p+1} = (D-E)^{-1}Fx^p+(D-E)^{-1}b$$
-Critère de convergence : A est symétrique et définie positive.
+Critère de convergence :
+  * A est symétrique et définie positive.
+  * A est à diagonale strictement dominante.
+Exemple :
+$$
+A =
+\begin{pmatrix}
+& 1 & 1 \\
+& 4 & 2 \\
+& 2 & 4
+\end{pmatrix}
+$$
+et b l'objectif :
+$$b =
+\begin{pmatrix}
+\\
+\\
+\\
+\end{pmatrix}$$
+Le résultat attendu est
+$$x =
+\begin{pmatrix}
+.0625 \\
+.15625 \\
+.65625 \\
+\end{pmatrix}$$
+Les valeurs propres A sont : 2, 2.43845 et 6.56155. Elles sont toutes supérieures à 0.
+$$
+D =
+\begin{pmatrix}
+& 0 & 0 \\
+& 4 & 0 \\
+& 0 & 4
+\end{pmatrix}
+$$
+$$
+E =
+\begin{pmatrix}
+  &  0 & 0 \\
+-1 &  0 & 0 \\
+-1 & -2 & 0
+\end{pmatrix}
+$$
+$$
+F =
+\begin{pmatrix}
+& -1 & -1 \\
+&  0 & -2 \\
+&  0 &  0
+\end{pmatrix}
+$$
+$$
+D-E =
+\begin{pmatrix}
+& 0 & 0 \\
+& 4 & 0 \\
+& 2 & 4
+\end{pmatrix}
+$$
+$$
+(D-E)^{-1} =
+\begin{pmatrix}
+.333333  &  0     & 0 \\
+-0.083333 &  0.25  & 0 \\
+-0.041666 & -0.125 & 0.25
+\end{pmatrix}
+$$
+$$
+(D-E)^{-1}F =
+\begin{pmatrix}
+& -0.333333 & -0.333333 \\
+&  0.083333 & -0.416666 \\
+&  0.041666 &  0.291666
+\end{pmatrix}
+$$
+$$
+(D-E)^{-1}b =
+\begin{pmatrix}
+.333333 \\
+.416666 \\
+.458333
+\end{pmatrix}
+$$
+$$x^0 =
+\begin{pmatrix}
+\\
+\\
+\\
+\end{pmatrix}$$
+$$x^1 = (D-E)^{-1}Fx^0+(D-E)^{-1}b$$
+$$x^1 =
+\begin{pmatrix}
+.333333 \\
+.416666 \\
+.458333 \\
+\end{pmatrix}$$
+$$x^5 =
+\begin{pmatrix}
+.060936 \\
+.157414 \\
+.656059 \\
+\end{pmatrix}$$
+$$x^{10} =
+\begin{pmatrix}
+.0625 \\
+.15625 \\
+.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}
+& 1 & 0 \\
+& 4 & 2 \\
+& 2 & 4
+\end{pmatrix}
+$$
+et b l'objectif :
+$$b =
+\begin{pmatrix}
+\\
+\\
+\\
+\end{pmatrix}$$
+Le résultat attendu est
+$$x =
+\begin{pmatrix}
+.3125 \\
+.0625 \\
+.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.333333 &  0 \\
+-0.25 &  0        & -0.5 \\
+& -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 \\
+.027806 & 0 & -0.55051 \\
+ -0.015308 &  0 &  0.202041 \\
+\end{pmatrix}
+$$
+$$\left(\frac{D}{\omega}-E \right)^{-1} b =
+\begin{pmatrix}
+.367007 \\
+.44949 \\
+.578317 \\
+\end{pmatrix}$$
+$$x^0 =
+\begin{pmatrix}
+\\
+\\
+\\
+\end{pmatrix}$$
+$$x^1 =
+\begin{pmatrix}
+.367007 \\
+.44949 \\
+.578317 \\
+\end{pmatrix}$$
+$$x^5 =
+\begin{pmatrix}
+.312208 \\
+.062704 \\
+.71869 \\
+\end{pmatrix}$$
+$$x^{10} =
+\begin{pmatrix}
+.3125 \\
+.0625 \\
+.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$$