01NUM1:Kapitola5: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
m |
m |
||
Řádka 469: | Řádka 469: | ||
Kde poslední rovnost plyne z Jordanovy věty a rozpisu nahoře. V absolutních hodnotách tedy máme: \[\lvert 1-\omega\rvert^n = \prod_{i=1}^n \lvert \lambda_i \rvert\] | Kde poslední rovnost plyne z Jordanovy věty a rozpisu nahoře. V absolutních hodnotách tedy máme: \[\lvert 1-\omega\rvert^n = \prod_{i=1}^n \lvert \lambda_i \rvert\] | ||
Pak je splněno buď I) všechna \( \lambda_i \) jsou stejná, tj, \(\lvert 1-\omega\rvert^n = \lvert \lambda_i \rvert^n \) a tedy nastává rovnost \(\rho (\matice B_{\omega}) = \lvert \lambda_i \rvert \) | Pak je splněno buď I) všechna \( \lambda_i \) jsou stejná, tj, \(\lvert 1-\omega\rvert^n = \lvert \lambda_i \rvert^n \) a tedy nastává rovnost \(\rho (\matice B_{\omega}) = \lvert \lambda_i \rvert \) | ||
− | anebo II) existuje takové \(\lambda_{i_1} \), že \(\lvert \lambda_{i_1} \rvert < \lvert 1-\omega \rvert\), pak ale musí zároveň existovat takové \(\lambda_{i_2}\), že \(\lvert \lambda_{i_2} \rvert > \lvert 1-\omega \rvert\) a nastává tudíž \(\rho (\matice B_{\omega}) | + | anebo II) existuje takové \(\lambda_{i_1} \), že \(\lvert \lambda_{i_1} \rvert < \lvert 1-\omega \rvert\), pak ale musí zároveň existovat takové \(\lambda_{i_2}\), že \(\lvert \lambda_{i_2} \rvert > \lvert 1-\omega \rvert\) a nastává tudíž \(\rho (\matice B_{\omega}) \geq \lvert \lambda_{i_2} \rvert>\lvert \lambda_i \rvert \). Z věty \ref{KSOR} pak plyne divergence metody pro \( \omega \in \mathbbm R \setminus \langle 0 , 2 \rangle \). |
\end{proof} | \end{proof} | ||
\end{theorem} | \end{theorem} |
Verze z 31. 1. 2017, 10:41
[ znovu generovat, | výstup z překladu ] | Kompletní WikiSkriptum včetně všech podkapitol. | |
PDF Této kapitoly | [ znovu generovat, | výstup z překladu ] | Přeložení pouze této kaptioly. |
ZIP | Kompletní zdrojový kód včetně obrázků. |
Součásti dokumentu 01NUM1
součást | akce | popis | poslední editace | soubor | |||
---|---|---|---|---|---|---|---|
Hlavní dokument | editovat | Hlavní stránka dokumentu 01NUM1 | Dedicma2 | 3. 6. 2024 | 19:49 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Dedicma2 | 3. 6. 2024 | 19:48 | ||
Header | editovat | Hlavičkový soubor | Dedicma2 | 17. 1. 2016 | 16:20 | header.tex | |
Kapitola0 | editovat | Značení | Dedicma2 | 23. 5. 2017 | 21:32 | znaceni.tex | |
Kapitola2 | editovat | Opakování a doplnění znalostí z lineární algebry | Dedicma2 | 3. 6. 2024 | 15:41 | prezentace2.tex | |
Kapitola3 | editovat | Úvod do numerické matematiky | Dedicma2 | 3. 6. 2024 | 15:51 | prezentace3.tex | |
Kapitola4 | editovat | Přímé metody pro lineární soustavy | Dedicma2 | 3. 6. 2024 | 16:47 | prezentace4.tex | |
Kapitola5 | editovat | Iterativní metody | Dedicma2 | 3. 6. 2024 | 16:59 | prezentace5.tex | |
Kapitola6 | editovat | Vlastní čísla a vektory matic | Dedicma2 | 3. 6. 2024 | 17:07 | prezentace6.tex | |
Kapitola7 | editovat | Nelineární rovnice | Kubuondr | 31. 1. 2017 | 14:27 | prezentace7.tex | |
Kapitola8 | editovat | Interpolace | Kubuondr | 31. 1. 2017 | 15:43 | prezentace8.tex | |
Kapitola9 | editovat | Derivace a integrace | Kubuondr | 31. 1. 2017 | 17:33 | prezentace9.tex |
Zdrojový kód
%\wikiskriptum{01NUM1} \section{Iterativní metody – úvod a soustavy lineárních rovnic} \subsection{Iterativní metody obecně} \begin{theorem} \label{KIterativniMetody} Iterativní metoda tvaru \[ \vec x^{( k + 1 )} = \matice B^{( k )} \vec x^{( k )} + \vec c^{( k )} \] splňující \[ \vec x = \matice B^{( k )} \vec x + \vec c^{( k )} \] konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když \[ \lim_{k \rightarrow \infty} \prod_{i = 0}^k \matice B^{( k - i )} = \Theta \] \begin{proof} \[ \lim_{k \rightarrow \infty} \vec x^{( k )} - \vec x = \lim_{k \rightarrow \infty} \matice B^{( k - 1)} \vec x^{( k -1 )} + \vec c^{( k - 1 )} - \matice B^{( k - 1 )} \vec x - \vec c^{( k - 1 )} = \] \[ = \lim_{k \rightarrow \infty} \matice B^{( k - 1 )} ( \vec x^{( k -1 )} - \vec x ) = \dots = \lim_{k \rightarrow \infty} \prod_{i = 0}^{k - 1} \matice B^{( k - i - 1 )} ( \vec x^{( 0 )} - \vec x ) \] což je rovno nule pro libovolné \( \vec x^{( 0 )} \) právě tehdy, je-li splněna podmínka z věty. \end{proof} \end{theorem} \begin{remark*} Vzhledem k tomu, že je výběr \( \vec x^{( 0 )} \) libovolný, bude tato metoda konvergovat i přes numerické chyby. Iterativní metody pro řešení soustav lineárních algebraických rovnic mají \textbf{samoopravující} vlastnost a jsou tudíž stabilní vzhledem k numerickým chybám. \end{remark*} \subsection{Stacionární iterativní metody} \begin{theorem} \label{KStacionarniIterativniMetody} Stacionární iterativní metoda, tj. metoda tvaru \[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \] splňující \[ \vec x = \matice B \vec x + \vec c \] konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když \[ \lim_{k \rightarrow \infty } \matice B^k = \Theta \] \begin{proof} \( \matice B^k = \prod_{i = 0}^k \matice B \) a tedy platnost této věty plyne přímo z \ref{KIterativniMetody}. \end{proof} \end{theorem} \begin{theorem} \label{KStacionarniIterativniMetodySpektrum} Stacionární iterativní metoda, tj. metoda tvaru \[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \] splňující \[ \vec x = \matice B \vec x + \vec c \] konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když \[ \rho ( \matice B ) < 1 \] \begin{proof} Plyne z \ref{GeomKSpektrum} a \ref{KStacionarniIterativniMetody}. \end{proof} \end{theorem} \begin{theorem} \label{KStacionarniIterativniMetodyNorma} Postačující podmínkou pro to, aby stacionární iterativní metoda, tj. metoda tvaru \[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \] splňující \[ \vec x = \matice B \vec x + \vec c \] konvergovala pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) je \[ \exists \; \text{maticová norma} \; \lVert \, \cdot \, \rVert, \lVert \matice B \rVert < 1 \] \begin{proof} Plyne z \ref{GeomKNorma} a \ref{KStacionarniIterativniMetody}. \end{proof} \end{theorem} \begin{theorem}[Aposteriorní odhad chyby pro stacionární iterativní metody] \label{AposteriorniOdhad} Pro stacionární iterativní metodu, tj. metodu tvaru \[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \] splňující \[ \vec x = \matice B \vec x + \vec c \] kde \( \vec x \) je řešením soustavy lineárních rovnic \( \matice A \vec x = \vec b \), platí při použití \textbf{souhlasné normy} tyto odhady chyby aproximace řešení: \begin{enumerate}[(1)] \item \( \displaystyle \left\lVert \vec x^{( k )} - \vec x \right\rVert \leq \left\lVert \matice A^{-1} \right\rVert \left\rVert \matice A \vec x^{( k )} - \vec b \right\rVert \) \\ \item \( \displaystyle \left\lVert \vec x^{( k )} - \vec x \right\rVert \leq \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \lVert \matice B \rVert \left\lVert \vec x^{( k - 1)} - \vec x^{( k )} \right\rVert \) \end{enumerate} \begin{proof} \begin{enumerate}[(1)] \item Nahrazujeme vektor \( \vec x\) pomocí \( \vec x =\matice A^{-1} \vec b \). \[ \left\lVert \vec x^{( k )} - \vec x \right\rVert = \left\lVert \matice A^{-1} ( \matice A \vec x^{( k )} - \vec b ) \right\rVert \leq \left\lVert \matice A^{-1} \right\rVert \left\rVert \matice A \vec x^{( k )} - \vec b \right\rVert \] kde poslední nerovnost plyne z trojúhelníkové nerovnosti. \item Nahrazujeme vektor \( \vec x\) pomocí \( \vec x =( \matice I - \matice B )^{-1} \vec c \), což je inverze podmínky pro řešení. \[ \left\lVert \vec x^{( k )} - \vec x \right\rVert = \left\lVert ( \matice I - \matice B )^{-1} ( ( \matice I - \matice B ) \vec x^{( k )} - \vec c ) \right\rVert \leq \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert ( \matice I - \matice B ) \vec x^{( k )} - \vec c \right\rVert \] kde poslední nerovnost je opět aplikací trojúhleníkové nerovnosti. \[ \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert ( \matice I - \matice B ) \vec x^{( k )} - \vec c \right\rVert = \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert \vec x^{(k)} - \matice B \vec x^{( k )} - \vec c \right\rVert = \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert \matice B \vec x^{(k - 1)} + \vec c - \matice B \vec x^{( k )} - \vec c \right\rVert = \] \[ = \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert \matice B ( \vec x^{(k - 1)} - \vec x^{( k )} ) \right\rVert \leq \left\lVert ( \matice I - \matice B )^{-1} \right\rVert \left\lVert \matice B \right\rVert \left\lVert \vec x^{(k - 1)} - \vec x^{( k )} \right\rVert \] kde poslední nerovnost je znovu pouze aplikací trojúhelníkové nerovnosti. \qedhere \end{enumerate} \end{proof} \end{theorem} \begin{define}[V prezentaci poznámka] Nechť \( \vec x^{( k )} \) je \( k \)-tá aproximace řešení soustavy lineárních rovnic \( \matice A \vec x = \vec b \). Potom definujeme reziduum v \( k \)-té iteraci \[ \vec r^{( k )} = \matice A \vec x^{( k )} - \vec b \] \end{define} \setcounter{define}{7} \begin{theorem}[Apriorní odhad chyby pro stacionární iterativní metody] \label{ApriorniOdhad} Pro stacionární iterativní metodu, tj. metodu tvaru \[ \vec x^{( k + 1 )} = \matice B \vec x^{( k )} + \vec c \] splňující \[ \vec x = \matice B \vec x + \vec c \] a dále splňující pro nějakou maticovou normu \[ \lVert \matice B \rVert < 1 \] platí \[ \left\lVert \vec x^{(k)} - \vec x \right\rVert \leq \lVert \matice B \rVert^k \left( \left\lVert \vec x^{(0)} \right\rVert + \frac{\lVert \vec c \rVert}{1 - \lVert \matice B \rVert} \right) \] kde používaná vektorová norma je \textbf{souhlasná} s normou maticovou. \begin{proof} \[ \vec x^{(k)} = \matice B \vec x^{(k - 1)} + \vec c = \dots = \matice B^k \vec x^{(0)} + \sum_{i = 0}^{k - 1} \matice B^i \vec c \] Protože \( \lVert \matice B \rVert < 1 \), tak díky \ref{AbsEigenvalueVSNorma} \( \rho ( \matice B ) < 1 \), a tedy \( 0 \notin \sigma ( \matice I - \matice B ) \), tedy \( ( \matice I - \matice B ) \) je regulární a můžeme upravovat \[ \vec c = ( \matice I - \matice B) \vec x \Rightarrow \vec x = ( \matice I - \matice B )^{-1} \vec c = \sum_{i = 0}^\infty \matice B^i \vec c \] kde poslední rovnost platí, protože \( \lVert \matice B \rVert < 1 \), a tedy díky \ref{GeomKNorma} řada konverguje. S pomocí těchto dvou rozvojů můžeme za použití trojúhelníkové nerovnosti a vzorce pro součet geometrické řady odhadovat \[ \left\lVert \vec x^{(k)} - \vec x \right\rVert = \left\lVert \matice B^k \vec x^{(0)} + \sum_{i = 0}^{k - 1} \matice B^i \vec c - \sum_{i = 0}^\infty \matice B^i \vec c \right\rVert = \left\lVert \matice B^k \vec x^{(0)} - \sum_{i = k}^\infty \matice B^i \vec c \right\rVert = \left\lVert \matice B^k \left( \vec x^{(0)} - \sum_{i = 0}^\infty \matice B^i \vec c \right) \right\rVert \leq \] \[ \leq \lVert \matice B \rVert^k \left\lVert \vec x^{(0)} - \sum_{i = 0}^\infty \matice B^i \vec c \right\rVert \leq \lVert \matice B \rVert^k \left( \left\lVert \vec x^{(0)} \right\rVert + \sum_{i = 0}^\infty \lVert \matice B \rVert^i \lVert \vec c \rVert \right) = \lVert \matice B \rVert^k \left( \left\lVert \vec x^{(0)} \right\rVert + \frac{\lVert \vec c \rVert}{1 - \lVert \matice B \rVert} \right) \] \end{proof} \end{theorem} \subsection{Metoda postupných aproximací} Využijeme znalosti rezidua v \( k \)-té iteraci a definujeme \[ \vec x^{( k + 1 )} = \vec x^{( k )} - \vec r^{( k )} = \vec x^{( k )} - \matice A \vec x^{( k )} + \vec b = ( \matice I - \matice A ) \vec x^{( k )} + \vec b \] Vidíme, že tato metoda obecně splňuje podmínku \[ \vec x = ( \matice I - \matice A ) \vec x + \vec b \] \begin{theorem} \label{KPostupneAproximace} Metoda postupných aproximací pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \), kde matice \( \matice A \) je regulární, tj. metoda tvaru \[ \vec x^{(k + 1)} = ( \matice I - \matice A ) \vec x^{(k)} + \vec b \] konverguje pro libovolné \( \vec x^{(0)} \) k \( \vec x \) právě tehdy, když \[ \rho ( \matice I - \matice A ) < 1 \] \begin{proof} Plyne z \ref{KStacionarniIterativniMetodySpektrum}. \end{proof} \end{theorem} \begin{remark*} Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence metody postupných aproximací existence nějaké normy, pro kterou \[ \lVert \matice I - \matice A \rVert < 1 \] \end{remark*} \begin{theorem} \label{PolynomEigenvalues} Nechť \( p(t) \) je polynom, \( \matice A \in \mathbbm C^{n, n} \) a \( \lambda \in \sigma ( \matice A ) \). Potom \( p( \lambda ) \in \sigma ( p( \matice A ) ) \). \begin{proof} Využijeme vztahu \( \lambda \in \sigma ( \matice A ) \Leftrightarrow ( \matice A - \lambda \matice I ) \) je singulární. Rozepíšeme \( p ( t ) \) do tvaru \[ p ( t ) = \sum_{i = 0}^n a_i t^i, \; a_n \neq 0 \] Potom můžeme upravit \[ p ( \matice A ) - p ( \lambda ) \matice I = \sum_{i = 0}^n a_i \matice A^i - \sum_{i = 0}^n a_i \lambda^i = \sum_{i = 1}^n a_i ( \matice A - \lambda \matice I )^i = ( \matice A - \lambda \matice I ) \sum_{i = 1}^n a_i ( \matice A - \lambda \matice I )^{i - 1} \] Z čehož plyne, že \( p ( \matice A ) - p ( \lambda ) \matice I \) je sigulární a tedy \( p ( \lambda ) \in \sigma ( p ( \matice A ) ) \). \end{proof} \end{theorem} \begin{remark*}\textit{(Důkaz z přednášky)} Z \ref{MocninaJordan} víme, že se při mocnění umocňuje spektrum. S pomocí Jordanovy věty dále zjistíme, že pro násobení platí: \[a^k\matice A^k=a^k \matice X^-1\matice J^k \matice X=\matice X^-1 (a\matice J)^k \matice X\] Obdobně pro sčítání. Z toho je vidět, spektrum součtu matice obsahuje součet vlastních čísel. Složením těchto operací definuje polynom. Platí tedy \(p(\matice A)=matice X^-1 p(\matice J) \matice X\), což dokazuje větu. \end{remark*} \begin{theorem} \label{KHermPDPostupneAproximace} Nechť matice \( \matice A \) je hermitovská a pozitivně definitní. Pak metoda postupných aproximací pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když \[ \Theta < \matice A < 2 \matice I \] \begin{proof} Díky \ref{KPostupneAproximace} metoda postupných aproximací konverguje právě tehdy, když \( \sigma ( \matice I - \matice A ) \subset \left( -1, 1 \right) \). Hermitovskost matice \( \matice A \) nám zaručuje reálnost vlastních čísel. Vezmeme polynom \( p ( t ) = 1 - t \), tedy \( p ( \matice I - \matice A ) = \matice A \) a užitím \ref{PolynomEigenvalues} dostáváme \( \sigma ( \matice A ) \subset p ( \left( -1 , 1 \right) ) = \left( 0, 2 \right) \), tedy \( \matice A \) je pozitivně definitní. \\ Vezmeme polynom \( q ( t ) = 1 + t \), tedy \( q ( \matice I - \matice A ) = 2 \matice I - \matice A \) a užitím \ref{PolynomEigenvalues} dostáváme \( \sigma ( 2 \matice I - \matice A ) \subset q ( \left( -1 , 1 \right) ) = \left( 0, 2 \right) \), tedy \( 2 \matice I - \matice A \) je pozitivně definitní. To je jinak zapsáno \( \matice A < 2 \matice I \). \end{proof} \end{theorem} \begin{remark*} Nejspíše platí i pro nehermitovské matice. Všechny věty, které jsou v důkazu použité, platí bez ohledu na to, zda jsou vlastní čísla reálná či komplexní, pokud se nahradí interval kruhem v \(\matice C\) obsahujícím daný interval. \end{remark*} \subsection{Předpodmíněná metoda postupných aproximací} Abychom zlepšili konvergenci metody postupných aproximací, vynásobíme soustavu regulární maticí \( \matice H \) a dostáváme \[ \matice{H A} \vec x = \matice H \vec b \] Použitím metody postupných aproximací pro tuto soustavu dostáváme \[ \vec x^{( k + 1 )} = ( \matice I - \matice{H A} ) \vec x^{( k )} + \matice H \vec b \] Podmínka \[ \vec x = ( \matice I - \matice{H A} ) \vec x + \matice H \vec b \] je splněna díky tomu, že je obecně splněná pro metodu postupných aproximací. \setcounter{define}{12} \begin{theorem} \label{KPredpodmineneAproximace} Předpodmíněná metoda postupných aproximací s předpodmíněním \( \matice H \) pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \), kde matice \( \matice A \) je regulární, tj. metoda tvaru \[ \vec x^{( k + 1 )} = ( \matice I - \matice{H A} ) \vec x^{( k )} + \matice H \vec b \] konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když \[ \rho ( \matice I - \matice{H A} ) < 1 \] \begin{proof} Plyne z \ref{KStacionarniIterativniMetodySpektrum}. \end{proof} \end{theorem} \begin{remark*} Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence předpodmíněné metody postupných aproximací existence nějaké normy, pro kterou \[ \lVert \matice I - \matice{H A} \rVert < 1 \] \end{remark*} \begin{theorem} \label{KHermPDPredpodmineneAproximace} Nechť matice \( \matice A \) je hermitovská a pozitivně definitní. Pak předpodmíněná metoda postupných aproximací pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) když platí \textbf{postačující podmínka} \[ \Theta < \matice A <\matice H^{-1} + \left( \matice H^{-1} \right)^* \] Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice A} \) \begin{proof} Chceme dokázat \( \lVert \matice I - \matice{H A} \rVert_{\matice A} < 1 \) a tím splnit předpoklady \ref{KPredpodmineneAproximace} (Energetická norma existuje, protože je \( \matice A \) hermitovská a pozitivně definitní). \[ \lVert \matice I - \matice{H A} \rVert_{\matice A} = \left\lVert \matice A^{\frac{1}{2}} ( \matice I - \matice{H A} ) \matice A^{-\frac{1}{2}} \right\rVert_2 = \left\lVert \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} \right\rVert_2 = \lVert \matice B \rVert_2 \] když označíme \( \matice B = \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} \). Dále \[ \lVert \matice B \rVert_2 < 1 \Leftrightarrow \lVert \matice B \rVert_2^2 < 1 \] Využijeme \ref{NormaMatice} a \ref{AbsEigenvalueVSNorma} \[ \lVert \matice B \rVert_2^2 = \rho ( \matice B^* \matice B ) \leq \left\lVert \matice B^* \matice B \right\rVert \] pro nějakou normu. Budeme tedy odhadovat ze shora matici \( \matice B^* \matice B \). \[ \matice B^* \matice B = ( \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} )^* ( \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} ) = ( \matice I - \matice A^{\frac{1}{2}} \matice H^* \matice A^{\frac{1}{2}} ) ( \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} ) \] kde poslední rovnost plyne z hermitovskosti matice \( \matice A \). \[ ( \matice I - \matice A^{\frac{1}{2}} \matice H^* \matice A^{\frac{1}{2}} ) ( \matice I - \matice A^{\frac{1}{2}} \matice H \matice A^{\frac{1}{2}} ) = \matice I - \matice A^{\frac{1}{2}} ( \matice H^* + \matice H ) \matice A^{\frac{1}{2}} + \matice A^{\frac{1}{2}} \matice H^* \matice A \matice H \matice A^{\frac{1}{2}} \] Využijeme snadno ověřitelné rovnosti \( \matice H^* ( \matice H^{-1} + \left( \matice H^{-1} \right)^* ) \matice H = \matice H^* + \matice H \) a dostáváme \[ \matice I - \matice A^{\frac{1}{2}} ( \matice H^* + \matice H ) \matice A^{\frac{1}{2}} + \matice A^{\frac{1}{2}} \matice H^* \matice A \matice H \matice A^{\frac{1}{2}} = \matice I - \matice A^{\frac{1}{2}} \matice H^* ( \matice H^{-1} + \left( \matice H^{-1} \right)^* ) \matice H \matice A^{\frac{1}{2}} + \matice A^{\frac{1}{2}} \matice H^* \matice A \matice H \matice A^{\frac{1}{2}} = \] \[ = \matice I - \matice A^{\frac{1}{2}} \matice H^* ( \underbrace{\matice H^{-1} + \left( \matice H^{-1} \right)^* - \matice A}_{> \Theta} ) \matice H \matice A^{\frac{1}{2}} \] kde jsme k odhadu využili předpokladů věty. Dále víme, že \( \matice H^* \matice H \) je pozitivně definitní (Ověření: \( \braket{\matice H^* \matice H \vec x | \vec x} = \braket{\matice H \vec x | \matice H \vec x} = \lVert \matice H \vec x \rVert > 0 \)). Protože i \( \matice A \) je pozitivně definitní, můžeme odhadnout \[ \matice A^{\frac{1}{2}} \matice H^* ( \matice H^{-1} + \left( \matice H^{-1} \right)^* - \matice A ) \matice H \matice A^{\frac{1}{2}} > \Theta \] A protože i \( \matice B^* \matice B \) je pozitivně definitní, konečně můžeme odhadnout \[ \matice I - \matice A^{\frac{1}{2}} \matice H^* ( \matice H^{-1} + \left( \matice H^{-1} \right)^* - \matice A ) \matice H \matice A^{\frac{1}{2}} < \matice I \] Tím jsme naplnili předpoklady \ref{KPredpodmineneAproximace}, a tedy dokázali platnost věty. \end{proof} \end{theorem} Jak tedy volit matici \( \matice H \)? Pokud bychom volili \( \matice H = \matice A^{-1} \) dostáváme \[ \vec x^{( k + 1 )} = \left( \matice I - \matice A^{-1} \matice A \right) \vec x^{( k )} + \matice A^{-1} \vec b = \vec x \] Tedy předpodmíněná metoda postupných aproximací by konvergovala v první iteraci. Avšak výpočet \( \matice A^{-1} \) provádíme Gaussovou eliminační metodou, čemuž jsme se chtěli vyhnout. \\ Oblíbenou metodou je tzv. \textbf{neúplný LU rozklad}, kde malé prvky zanedbáváme, čímž můžeme zlepšit časovou náročnost. \subsection{Richardsonovy iterace} Zavedeme tzv. \textbf{relaxační parametr} \( \theta \in \mathbbm C \). Metoda Richardsonových iterací je předpodmíněnou metodou postupných iterací, kde volíme \[ \matice H = \theta \matice I \] a dostáváme \[ \vec x^{( k + 1 )} = ( \matice I - \theta \matice A ) + \theta \vec b \] \setcounter{define}{15} \begin{theorem} \label{KHermPDRichardson} Nechť matice \( \matice A \) je hermitovská a pozitivně definitní. Nechť \( \theta \in \mathbbm R \). Pak metoda Richardsonových iterací konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když \[ \Theta < \matice A < \frac{2}{\theta} \matice I \] Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice A} \) \begin{proof} Pomocí \ref{KHermPDPredpodmineneAproximace} dokážeme, že se jedná o \textbf{postačující podmínku}: \todo{Důkaz nutnosti podmínky od doc. Humhala} \[ \matice H^{-1} + \left( \matice H^{-1} \right)^* = \frac{1}{\theta} \matice I + \left( \frac{1}{\theta} \matice I \right)^* = \frac{2}{\theta} \matice I \] \end{proof} \end{theorem} \subsection{Jacobiho metoda} Vyjdeme ze vzorce pro výpočet složek násobku matice a vektoru, tj. \[ \left( \matice A \vec y \right)_i = \sum_{j = 1}^n \matice A_{ij} \vec y_j \] Budeme chtít, aby když z vektoru \( \vec x^{( k )} \) nahradíme \( i \)-tou složku \( i \)-tou složkou vektoru \( \vec x^{( k + 1 )} \), byla splněna \( i \)-tá rovnice soustavy, tj. \[ \sum_{\substack{j = 1 \\ j \neq i}}^n \matice A_{ij} \vec x_j^{( k )} + \matice A_{ii} \vec x_i^{( k + 1 )} = \vec b_i \] Tedy dostáváme \[ \vec x_i^{( k + 1 )} = \frac{\vec b_i - \sum_{j = 1, j \neq i}^n \matice A_{ij} \vec x_j^{( k )}}{\matice A_{ii}} \] Z posledního předpisu je vidět, že musíme předpokládat nenulovou diagonálu. Toho však lze u regulární matice dosáhnout přerovnáním. \subsection{Jacobiho metoda - numerická analýza} Rozepíšeme matici \( \matice A \) do tvaru \[ \matice A = \matice D - \matice L - \matice R \] kde \begin{itemize} \item \( \matice D \) je diagonální matice s diagonálou matice \( \matice A \) \item \( \matice L \) je dolní trojúhelníková matice s prvky pod diagonálou \( \matice A \), vynásobenými \( ( - 1 ) \) \item \( \matice R \) je horní trojúhelníková matice s prvky nad diagonálou \( \matice A \), vynásobenými \( ( - 1 ) \) \end{itemize} Můžeme tedy shrnout předpis pro prvky \( \vec x^{( k + 1 )} \) do jednoho vztahu \[ \vec x^{( k + 1 )} = \matice D^{-1} \left( \vec b + ( \matice L + \matice R ) \vec x^{( k )} \right) = \matice D^{-1} \vec b + \matice D^{-1} ( \matice D - \matice A ) \vec x^{( k )} = \left( \matice I - \matice D^{-1} \matice A \right) \vec x^{( k )} + \matice D^{-1} \vec b \] Zjišťujeme, že Jacobiho metoda je vlastně předpodmíněnou metodou postupných aproximací, kde volíme \[ \matice H = \matice D^{-1}\] \[\vec c = \matice D^{-1} \vec b \] \setcounter{define}{17} \begin{theorem} \label{KJacobi} Jacobiho metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když \[ \rho \left( \matice D^{-1} ( \matice L + \matice R ) \right) < 1 \] \begin{proof} Díky vztahu \( \matice A = \matice D - \matice L - \matice R \) můžeme upravit \[ \rho \left( \matice D^{-1} ( \matice L + \matice R ) \right) = \rho \left( \matice D^{-1} ( \matice D - \matice A ) \right) = \rho \left( \matice I - \matice D^{-1} \matice A \right) < 1 \] čímž jsou splněny předpoklady \ref{KPredpodmineneAproximace}. \end{proof} \end{theorem} \begin{remark*} Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence Jacobiho metody existence nějaké normy, pro kterou \[ \left\lVert \matice D^{-1} ( \matice L + \matice R ) \right\rVert < 1 \] \end{remark*} \begin{define} \label{PrevladajiciDiagonala} Pokud pro matici \( \matice A \in \mathbbm C^{n, n} \) platí \[ \sum_{\substack{j = 1 \\ j \neq i}}^n \lvert \matice A_{ij} \rvert < \lvert \matice A_{ii} \rvert \] Nazýváme ji maticí s převládající diagonálou. \end{define} \begin{theorem} \label{KDiagJacobi} Nechť má matice \( \matice A \) převládající diagonálu. Pak Jacobiho metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \). \begin{proof} Chceme ukázat \( \lVert \matice D^{-1} ( \matice L + \matice R ) \rVert_\infty = \lVert \matice D^{-1} ( \matice D - \matice A ) \rVert_\infty = \lVert \matice I - \matice D^{-1} \matice A \rVert_\infty < 1 \) a využít \ref{KJacobi}. Matice \( \matice D \) je diagonální a na její diagonále jsou prvky diagonály matice \( \matice A \). Proto pro prvky matice \( \matice D^{-1} \matice A \) platí \[ \left( \matice D^{-1} \matice A \right)_{ij} = \frac{\matice A_{ij}}{\matice A_{ii}} \] A tedy na diagonále \( \matice D^{-1} \matice A \) jsou jedničky. Proto \[ \left( \matice I - \matice D^{-1} \matice A \right)_{ij} = \begin{cases} 0, & i =j \\ \frac{\matice A_{ij}}{\matice A_{ii}}, & i \neq j \end{cases} \] Díky \ref{NormaMatice} platí \[ \lVert \matice I - \matice D^{-1} \matice A \rVert_\infty = \max_{i \in \hat n} \sum_{j = 1}^n \left\lvert \left( \matice I - \matice D^{-1} \matice A \right)_{ij} \right\rvert = \max_{i \in \hat n} \frac{1}{\matice A_{ii}} \sum_{\substack{j = 1 \\ j \neq i}}^n \lvert \matice A_{ij} \rvert < 1 \] kde poslední nerovnost je důsledkem toho, že matice \( \matice A \) má převládající diagonálu. \end{proof} \end{theorem} \begin{theorem} \label{KHermPDJacobi} Nechť je matice \( \matice A \) hermitovská a pozivně definitní. Pak Jacobiho metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když \[ \Theta < \matice A < 2 \matice D \] Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice A} \) \begin{proof} Protože je matice \( \matice A \) hermitovská, jsou diagonální prvky \( \matice A_{ii} \in \mathbbm R \) (musí platit \( \matice A_{ii} = \overline{\matice A_{ii}} \)), tudíž \( \matice D = \matice D^* \). Protože je navíc pozitivné definitní, platí \( \vec x^* \matice A \vec x > 0 \). Zvolíme–li \(\vec x = \vec e_{(i)} \), kde \( \vec e_{(i)} \) jsou vektory ze standardní báze, dostaneme \( \matice A_{ii} = \matice D_{ii} = \vec e_{(i)}^* \matice A \vec e_{(i)} > 0 \), tj. \(\matice D \) je pozitivně definitní. \begin{enumerate} \item[( \( \Leftarrow \) )] Upravíme předpis Jacobiho metody do tvaru \[ \vec x^{( k + 1 )} = ( \matice I - \matice D^{-1} \matice A ) \vec x^{( k + 1 )} + \matice D^{-1} \vec b \] což je předpis předpodmíněné metody postupných aproximací s předpodmíněním \( \matice H = \matice D^{-1} \). Dále tedy platí \[ \matice H^{-1} + \left( \matice H^{-1} \right)^* = \matice D + \matice D^* = 2 \matice D \] čímž jsou splněny předpoklady \ref{KHermPDPredpodmineneAproximace}. \item[( \( \Rightarrow \) )] Díky \ref{KStacionarniIterativniMetodySpektrum} víme, že \( \sigma ( \matice I - \matice D^{-1} \matice A ) \subset \left( -1, 1 \right) \). Užitím \ref{PolynomEigenvalues} s \( p ( t ) = 1 + t \) dostáváme \( \sigma ( 2 \matice I - \matice D^{-1} \matice A ) \subset \left( 0, 2 \right) \). Můžeme upravit \[ 2 \matice I - \matice D^{-1} \matice A = \matice D^{-\frac{1}{2}} ( 2 \matice I - \matice D^{-\frac{1}{2}} \matice A \matice D^{-\frac{1}{2}} ) \matice D^{\frac{1}{2}} \] Z čehož plyne, že je matice \( 2 \matice I - \matice D^{-\frac{1}{2}} \matice A \matice D^{-\frac{1}{2}} \) pozitivně definitní. Toho využijeme při odhadu \[ \braket{( 2 \matice D - \matice A ) \vec x | \vec x} = \vec x ( 2 \matice D - \matice A ) \vec x = \vec x \matice D^{\frac{1}{2}} \matice D^{-\frac{1}{2}} ( 2 \matice D - \matice A ) \matice D^{-\frac{1}{2}} \matice D^{\frac{1}{2}} \vec x = \left( \matice D^{\frac{1}{2}} \vec x \right)^* \left( 2 \matice I - \matice D^{-\frac{1}{2}} \matice A \matice D^{-\frac{1}{2}} \right) \left( \matice D^{\frac{1}{2}} \vec x \right) = \] \[ = \braket{\left( 2 \matice I - \matice D^{-\frac{1}{2}} \matice A \matice D^{-\frac{1}{2}} \right) \matice D^{\frac{1}{2}} \vec x | \matice D^{\frac{1}{2}} \vec x} > 0 \] Tedy \( 2 \matice D - \matice A > \Theta \), což je jinak zapsáno \( 2 \matice D > \matice A \). \end{enumerate} \end{proof} \end{theorem} \subsection{Gaussova-Seidelova metoda} Vyjdeme ze stejného vztahu jako v případě Jacobiho metody, avšak použijeme již napočítané složky vektoru \( \vec x^{( k + 1 )} \), tedy \[ \sum_{j = 1}^i \matice A_{ij} \vec x_j^{( k + 1 )} + \sum_{j = i + 1}^n \matice A_{ij} \vec x_j^{( k )} = \vec b_i \] Tedy dostáváme \[ \vec x_i^{( k + 1 )} = \frac{\vec b_i - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec x_j^{( k + 1 )} - \sum_{j = i + 1}^n \matice A_{ij} \vec x_j^{( k )}}{\matice A_{ii}} \] Znovu musíme předpokládat nenulovou diagonálu. \subsection{Gaussova-Seidelova metoda - numerická analýza} Použijeme stejného přepisu matice \( \matice A \) jako v případě Jacobiho metody a shrneme předpis pro prvky \( \vec x^{( k + 1 )} \) do jednoho vztahu \[ \vec x^{( k + 1 )} = \matice D^{-1} \left( \vec b + \matice L \vec x^{( k + 1 )} + \matice R \vec x^{( k )} \right) \] který upravujeme \[ \matice D \vec x^{( k + 1 )} - \matice L \vec x^{( k + 1 )} = \vec b + \matice R \vec x^{( k )} \] \[ \vec x^{( k + 1 )} = ( \matice D - \matice L )^{-1} ( \matice D - \matice L - \matice A ) \vec x^{( k )} + ( \matice D - \matice L )^{-1} \vec b \] \[ \vec x^{( k + 1 )} = \left( \matice I - ( \matice D - \matice L )^{-1} \matice A \right) \vec x^{( k )} + ( \matice D - \matice L )^{-1} \vec b \] Zjišťujeme, že Gaussova-Seidelova metoda je vlastně předpodmíněnou metodou postupných aproximací, kde volíme \[ \matice H = ( \matice D - \matice L )^{-1} \] \setcounter{define}{22} \begin{theorem} \label{KGaussSeidel} Gaussova-Seidelova metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když \[ \rho \left( ( \matice D - \matice L )^{-1} \matice R \right) < 1 \] \begin{proof} Upravíme předpis Gaussovy-Seidelovy metody do tvaru \[ \vec x^{( k + 1 )} = ( \matice I - \left( \matice D - \matice L \right)^{-1} \matice A ) \vec x^{( k )} + \left( \matice D - \matice L \right)^{-1} \vec b \] což je předpis předpodmíněné metody postupných aproximací s předpodmíněním \( \matice H = \left( \matice D - \matice L \right)^{-1} \). Díky vztahu \( \matice A = \matice D - \matice L - \matice R \) můžeme upravit \[ \rho \left( \left( \matice D - \matice L \right)^{-1} \matice R \right) = \rho \left( \left( \matice D - \matice L \right)^{-1} ( \matice D - \matice L - \matice A ) \right) = \rho \left( \matice I - \left( \matice D - \matice L \right)^{-1} \matice A \right) < 1 \] čímž jsou splněny předpoklady \ref{KPredpodmineneAproximace}. \end{proof} \end{theorem} \begin{remark*} Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence Gaussovy-Seidelovy metody existence nějaké normy, pro kterou \[ \left\lVert ( \matice D - \matice L )^{-1} \matice R \right\rVert < 1 \] \end{remark*} \begin{theorem} \label{KDiagGaussSeidel} Nechť má matice \( \matice A \) převládající diagonálu. Pak Gaussova-Seidelova metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \). \begin{proof} Označíme \( \matice B = \left( \matice D - \matice L \right)^{-1} \matice R \). Chceme ukázat \( \lVert \matice B \rVert_\infty < 1 \) a využít \ref{KGaussSeidel}. Díky \ref{NormaMatice} platí \[ \lVert \matice B \rVert_\infty = \max_{\lVert \vec x \rVert_\infty = 1} \lVert \matice B \vec x \rVert_\infty \] Označíme tento maximální vektor \( \vec u \) ( \( \lVert \vec u \rVert_\infty = 1 \) ) a dále označíme \( \vec v = \matice B \vec u \). Potom platí \[ \lVert \matice B \rVert_\infty = \lVert \matice B \vec u \rVert_\infty = \lVert \vec v \rVert_\infty = \max_{k \in \hat n} \lvert \vec v_k \rvert \] Označíme takovouto maximální složku indexem \( i \). Upravíme rovnici \( \matice B \vec u = \vec v \) do tvaru \[ \left( \matice D - \matice L \right)^{-1} \matice R \vec u = \vec v \] \[ \matice R \vec u = ( \matice D - \matice L ) \vec v \] a budeme upravovat její \( i \)-tou (maximální) složku: \[ \sum_{j = i + 1}^n -\matice A_{ij} \vec u_j = \sum_{j = 1}^i \matice A_{ij} \vec v_j \] Upravíme a díky trojúhelníkové nerovnosti odhadujeme \[ \lvert \vec v_i \rvert = \left\lvert \frac{1}{\matice A_{ii}} \left( \sum_{j = i + 1}^n - \matice A_{ij} \vec u_j - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec v_j \right) \right\rvert \leq \frac{1}{\lvert \matice A_{ii} \rvert} \left( \sum_{j = i + 1}^n \lvert \matice A_{ij} \rvert \lvert \vec u_j \rvert + \sum_{j = 1}^{i - 1} \lvert \matice A_{ij} \rvert \lvert \vec v_j \rvert \right) \] Využijeme vlastností \( \lvert \vec u_j \rvert \leq 1 \) a \( \lvert \vec v_j \rvert \leq \lvert \vec v_i \rvert \): \[ \frac{1}{\lvert \matice A_{ii} \rvert} \left( \sum_{j = i + 1}^n \lvert \matice A_{ij} \rvert \lvert \vec u_j \rvert + \sum_{j = 1}^{i - 1} \lvert \matice A_{ij} \rvert \lvert \vec v_j \rvert \right) \leq \frac{1}{\lvert \matice A_{ii} \rvert} \left( \sum_{j = i + 1}^n \lvert \matice A_{ij} \rvert + \lvert \vec v_i \rvert \sum_{j = 1}^{i - 1} \lvert \matice A_{ij} \rvert \right) = \sum_{j = i + 1}^n \frac{\lvert \matice A_{ij} \rvert}{\lvert \matice A_{ii} \rvert} + \lvert \vec v_i \rvert \sum_{j = 1}^{i - 1} \frac{\lvert \matice A_{ij} \rvert}{\lvert \matice A_{ii} \rvert} \] Označíme \( a = \sum_{j = i + 1}^n \frac{\lvert \matice A_{ij} \rvert}{\lvert \matice A_{ii} \rvert} \) a \( b = \sum_{j = 1}^{i - 1} \frac{\lvert \matice A_{ij} \rvert}{\lvert \matice A_{ii} \rvert} \) a máme nerovnost \[ \lvert \vec v_i \rvert \leq a + b \lvert \vec v_i \rvert \] Zároveň ale díky tomu, že matice \( \matice A \) má převládající diagonálu, platí \( a + b < 1 \) a konečně můžeme odhadovat \[ \lvert \vec v_i \rvert \leq \frac{a}{1 - b} < \frac{a}{a + b - b} = 1 \] \end{proof} \end{theorem} \begin{theorem} \label{KHermPDGaussSeidel} Nechť je matice \( \matice A \) hermitovská a pozivně definitní. Pak Gaussova-Seidelova metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \). Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice A} \) \begin{proof} Upravíme předpis Gaussovy-Seidelovy metody do tvaru \[ \vec x^{( k + 1 )} = ( \matice I - \left( \matice D - \matice L \right)^{-1} \matice A ) \vec x^{( k )} + \left( \matice D - \matice L \right)^{-1} \vec b \] což je předpis předpodmíněné metody postupných aproximací s předpodmíněním \( \matice H = \left( \matice D - \matice L \right)^{-1} \). Díky hermitovskosti matice \( \matice A \) platí \( \matice L^* = \matice R \) a \( \matice D^* = \matice D \). Potom můžeme využít \ref{KHermPDPredpodmineneAproximace} protože platí \[ \matice H^{-1} + \left( \matice H^{-1} \right)^* = \matice D - \matice L + ( \matice D - \matice L )^* = \matice D - \matice L + \matice D - \matice R = \matice D + \matice A > \matice A \] \end{proof} \end{theorem} \subsection{Super-relaxační metoda (SOR – Succesive Over Relaxation)} Upravíme předpis pro Gaussovu-Seidelovu metodu do tvaru \[ \vec x_i^{( k + 1 )} = \vec x_i^{( k )} + \Delta \vec x_i^{( k )} \] Zavedeme tzv. \textbf{relaxační parametr} \( \omega \) a pozměníme předpis pro Gaussovu-Seidelovu metodu na \[ \vec x_i^{( k + 1 )} = \vec x_i^{( k )} + \omega \Delta \vec x_i^{( k )} \] Vidíme, že pro \( \omega = 1 \) super-relaxační metoda přechází v metodu Gaussovu-Seidelovu. \begin{remark*} Obdobnou modifikaci můžeme provést i pro Jacobiho metodu i pro Richardsonovy iterace. \end{remark*} \subsection{Super-relaxační metoda - numerická analýza} Vyjádříme po složky vektoru \( \Delta \vec x^{( k )} \) z Gaussovy-Seidelovy metody jako \[ \Delta \vec x_i^{( k )} = \vec x_i^{( k + 1 )} - \vec x_i^{( k )} = \frac{\vec b_i - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec x_j^{( k + 1 )} - \sum_{j = i + 1}^n \matice A_{ij} \vec x_j^{( k )}}{\matice A_{ii}} - \vec x_i^{( k )} = \frac{\vec b_i - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec x_j^{( k + 1 )} - \sum_{j = i}^n \matice A_{ij} \vec x_j^{( k )}}{\matice A_{ii}} \] Nyní tento vztah použijeme pro super-relaxační metodu \[ \vec x_i^{( k + 1 )} = \vec x_i^{( k )} + \frac{\omega}{\matice A_{ii}} \left( \vec b_i - \sum_{j = 1}^{i - 1} \matice A_{ij} \vec x_j^{( k + 1 )} - \sum_{j = i}^n \matice A_{ij} \vec x_j^{( k )} \right) \] Použijeme stejného přepisu matice \( \matice A \) jako v případě Jacobiho metody a shrneme předpis pro prvky \( \vec x^{( k + 1 )} \) do jednoho vztahu \[ \vec x^{( k + 1 )} = \vec x^{( k )} + \omega \matice D^{-1} \left( \vec b + \matice L \vec x^{( k + 1 )} + ( \matice R - \matice D ) \vec x^{( k )} \right) \] který upravujeme \[ \matice D \vec x^{( k + 1 )} - \omega \matice L \vec x^{( k + 1 )} = ( \matice D - \omega ( \matice D - \matice R ) ) \vec x^{( k )} + \omega \vec b \] \[ \vec x^{( k+1 )} = ( \matice D - \omega \matice L )^{-1} ( \matice D - \omega ( \matice A + \matice L ) ) \vec x^{( k )} + \omega ( \matice D - \omega \matice L )^{-1} \vec b \] \[ \vec x^{( k+1 )} = \left( \matice I - \omega ( \matice D - \omega \matice L )^{-1} \matice A \right) \vec x^{( k )} + \omega ( \matice D - \omega \matice L )^{-1} \vec b \] Zjišťujeme, že super-relaxační metoda je vlastně předpodmíněnou metodou postupných aproximací, kde volíme \[ \matice H = \omega ( \matice D - \omega \matice L )^{-1} \] \setcounter{define}{27} \begin{theorem} \label{KSOR} Super-relaxační metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když \[ \rho \left( \matice B_\omega \right) < 1 \] kde jsem označili \[B_\omega = \matice I - \omega ( \matice D - \omega \matice L )^{-1} \matice A \] \begin{proof} Plyne z \ref{KStacionarniIterativniMetodySpektrum}. \end{proof} \end{theorem} \begin{remark*} Díky \ref{AbsEigenvalueVSNorma} je postačující podmínkou konvergence super-relaxační metody existence nějaké normy, pro kterou \[ \left\lVert \matice B_\omega \right\rVert < 1 \] \end{remark*} \begin{theorem} \label{NKSOR} Pro každé \( \omega \in \mathbbm R \) platí \[ \lvert \omega - 1 \rvert \leq \rho \left( \matice B_\omega \right) \] a tedy super-relaxační metoda nemůže konvergovat pro \( \omega \in \mathbbm R \setminus \langle 0 , 2 \rangle \) \begin{proof} Pro důkaz využijeme toho, že determinant nezávisí na volbě báze. Podle označení je \[\matice B_\omega = (\matice D - \omega \matice L)^{-1}\big[(1-\omega)\matice D + \omega \matice R\big] \] Z Jordanovy věty zároveň víme: \[\matice A = (\matice T)^{-1} \matice {JT} \Rightarrow \det(\matice A) = \det(\matice J) = \prod_{i=1}^n \lambda_i\] Aplikujeme tuto znalost na naši matici (členy determinantu za \(\matice L\) a \(\matice R\) vypadnou, neboť jsou to singulární matice: \[\det(\matice B_{\omega}) = \frac{1}{\prod_{i=1}^n \matice A_{ii}} \prod_{i=1}^n (1-\omega) \matice A_{ii}} = (1-\omega)^n = \prod_{i=1}^n \lambda_i\] Kde poslední rovnost plyne z Jordanovy věty a rozpisu nahoře. V absolutních hodnotách tedy máme: \[\lvert 1-\omega\rvert^n = \prod_{i=1}^n \lvert \lambda_i \rvert\] Pak je splněno buď I) všechna \( \lambda_i \) jsou stejná, tj, \(\lvert 1-\omega\rvert^n = \lvert \lambda_i \rvert^n \) a tedy nastává rovnost \(\rho (\matice B_{\omega}) = \lvert \lambda_i \rvert \) anebo II) existuje takové \(\lambda_{i_1} \), že \(\lvert \lambda_{i_1} \rvert < \lvert 1-\omega \rvert\), pak ale musí zároveň existovat takové \(\lambda_{i_2}\), že \(\lvert \lambda_{i_2} \rvert > \lvert 1-\omega \rvert\) a nastává tudíž \(\rho (\matice B_{\omega}) \geq \lvert \lambda_{i_2} \rvert>\lvert \lambda_i \rvert \). Z věty \ref{KSOR} pak plyne divergence metody pro \( \omega \in \mathbbm R \setminus \langle 0 , 2 \rangle \). \end{proof} \end{theorem} \begin{theorem} \label{KDiagSOR} Nechť má matice \( \matice A \) převládající diagonálu a platí \( 0 < \omega \leq 1 \). Pak super-relaxační metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \). \begin{proof} Oberhuber nezná. \end{proof} \end{theorem} \begin{theorem}[Ostrowski] \label{Ostrowski} Nechť je matice \( \matice A \) hermitovská a pozivně definitní. Pak super-relaxační metoda pro soustavu lineárních rovnic \( \matice A \vec x = \vec b \) konverguje pro libovolné \( \vec x^{( 0 )} \) k \( \vec x \) právě tehdy, když \[ 0 < \omega < 2 \] Konvergence je navíc monotónní vzhledem k normě \( \lVert \, \cdot \, \rVert_{\matice A} \) \begin{proof} Upravíme předpis super-relaxační metody do tvaru \[ \vec x^{( k + 1 )} = ( \matice I - \omega \left( \matice D - \omega \matice L \right)^{-1} \matice A ) \vec x^{( k )} + \omega \left( \matice D - \omega \matice L \right)^{-1} \vec b \] což je předpis předpodmíněné metody postupných aproximací s předpodmíněním \( \matice H = \omega \left( \matice D - \omega \matice L \right)^{-1} \). Díky podmínce věty platí \[ \frac{2}{\omega} - 1 > 0 \] Díky hermitovskosti matice \( \matice A \) platí \( \matice L^* = \matice R \) a \( \matice D^* = \matice D \). Potom můžeme s využitím \ref{KHermPDPredpodmineneAproximace} dokázat \textbf{postačující podmínku}, protože platí \[ \matice H^{-1} + \left( \matice H^{-1} \right)^* = \frac{1}{\omega} ( \matice D - \omega \matice L) + \frac{1}{\omega} ( \matice D - \omega \matice L )^* = \frac{1}{\omega} \matice D - \matice L + \frac{1}{\omega} \matice D - \matice R = \left( \frac{2}{\omega} - 1 \right) \matice D + \matice A > \matice A \] \end{proof} \end{theorem} \setcounter{define}{37} \begin{theorem} \label{SORJacobiEigenvalue} Nechť je matice \( \matice A \) dvoucyklická a shodně uspořádaná. Nechť dále \( \omega \neq 0 \) a \( \lambda \neq 0 \) a \( \matice B_\omega \in \mathbbm C^{n, n} \) je maticí super-relaxační metody a \( \matice B_J \in \mathbbm C^{n, n} \) je maticí Jacobiho metody. Nechť čísla \( \lambda \) a \( \mu \) splňují \[ ( \lambda + \omega - 1 )^2 = \omega^2 \mu^2 \lambda \] Pak \( \lambda \in \sigma ( \matice B_\omega ) \Leftrightarrow \mu \in \sigma ( \matice B_J ) \). Navíc platí, že pro \[ \omega_{opt} = \frac{2}{1 + \sqrt{1 - \rho^2 ( \matice B_J ) }} \] nabývá \( \rho( \matice B_\omega ) \) svého minima a super-relaxační metoda tedy konverguje nejrychleji. \begin{proof}\renewcommand{\qedsymbol}{} Bez důkazu. \end{proof} \end{theorem} \subsection{Shrnutí podmínek konvergence} ~\\ ~\\ \begin{tabular}{c | c | c} \textbf{Podmínka na matici} \( \matice A \) & Převládající diagonála & Hermitovská a pozitivně definitní \\ \hline \textbf{Jacobiho metoda} & vždy & \( \matice A < 2 \matice D \) \\ \hline \textbf{Gaussova-Seidelova metoda} & vždy & vždy \\ \hline \textbf{Super-relaxační metoda} & \( 0 < \omega \leq 1 \) & \( 0 < \omega < 2 \) \\ \end{tabular}