01NUM1:Kapitola5

Z WikiSkripta FJFI ČVUT v Praze
Verze z 8. 1. 2016, 14:27, kterou vytvořil Dedicma2 (diskuse | příspěvky) (Zrušena verze 5807 od uživatele Dedicma2 (diskuse))

Přejít na: navigace, hledání
PDF [ 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.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01NUM1

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01NUM1Kubuondr 26. 11. 201616:56
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůDedicma2 23. 5. 201721:31
Header editovatHlavičkový souborDedicma2 17. 1. 201616:20 header.tex
Kapitola0 editovatZnačeníDedicma2 23. 5. 201721:32 preamble.tex
Kapitola2 editovatOpakování a doplnění znalostí z lineární algebryKubuondr 30. 1. 201717:14 prezentace2.tex
Kapitola3 editovatÚvod do numerické matematikyKubuondr 10. 12. 201614:17 prezentace3.tex
Kapitola4 editovatPřímé metody pro lineární soustavyKubuondr 30. 1. 201711:27 prezentace4.tex
Kapitola5 editovatIterativní metodyKubuondr 31. 1. 201710:41 prezentace5.tex
Kapitola6 editovatVlastní čísla a vektory maticKubuondr 31. 1. 201713:13 prezentace6.tex
Kapitola7 editovatNelineární rovniceKubuondr 31. 1. 201714:27 prezentace7.tex
Kapitola8 editovatInterpolaceKubuondr 31. 1. 201715:43 prezentace8.tex
Kapitola9 editovatDerivace a integraceKubuondr 31. 1. 201717:33 prezentace9.tex

Zdrojový kód

%\wikiskriptum{01NUM1}
\section{Iterativní metody}
 
\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^{( 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^{( i )} ( \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}
 
\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í 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
\[ \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
\[ \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 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í}
 
\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}
\[ ( \matice I - \matice A ) \vec x + \vec b = \matice I \vec x - \matice A \vec x + \vec b = \vec x \]
Tím jsou splněny předpoklady \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{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 hermitovskosti matice a \ref{KPostupneAproximace} metoda postupných aproximací konverguje právě tehdy, když \( \sigma ( \matice I - \matice A ) \subset \left( -1 , 1 \right) \), tedy právě tehdy, když \( \sigma ( \matice A ) \subset \left( 0 , 2 \right) \). Použitím \ref{PolynomEigenvalues} ( kde \( \matice A = \matice I \) a \( p(t) = 2t \) ) dostaneme díky faktu, že matice \( \matice I \) má jedinné vlastní číslo 1 tvrzení věty.
\end{proof}
\end{theorem}
 
\subsection{Předpodmíněná metoda 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}
\[ ( \matice I - \matice{H A} ) \vec x + \matice H \vec b = \matice I \vec x - \matice H \vec b + \matice H \vec b = \vec x \]
Tím jsou splněny předpoklady \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í 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}
 
\subsection{Richardsonovy iterace}
 
\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}
Upravíme předpis pro Richardsonovy iterace do tvaru
\[ \vec x^{( k + 1 )} = ( \matice I - \theta \matice I \matice A ) \vec x^{( k )} + \theta \matice I \vec b \]
což je předpis předpodmíněné metody postupných aproximací s předpodmíněním \( \matice H = \theta \matice I \). Potom můžeme využít \ref{KHermPDPredpodmineneAproximace} protože platí
\[ \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 - numerická analýza}
 
\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}
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í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*}
 
\setcounter{define}{19}
\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}
\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} \). Protože je matice \( \matice A \) pozitivně definitní, platí pro libovolný vektor \( \vec x^* \matice A \vec x \in \mathbbm R \). Tedy \( \vec e_i^* \matice A \vec e_i = \matice A_{ii} \in \mathbbm R \) a díky tomu \( \matice D = \matice D^* \). 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 \) )] \todo{Důkaz 5.21 - zpětná implikace}
\end{enumerate}
\end{proof}
\end{theorem}
 
\subsection{Gaussova-Seidelova metoda - numerická analýza}
 
\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 - numerická analýza}
 
\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 \]
\begin{proof}
\[ \left( \matice I - \omega ( \matice D - \omega \matice L )^{-1} \matice A \right) \vec x + \omega ( \matice D - \omega \matice L )^{-1} \vec b = \vec x -  \omega ( \matice D - \omega \matice L )^{-1} \vec b +  \omega ( \matice D - \omega \matice L )^{-1} \vec b = \vec x \]
Tím jsou splněny předpoklady \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 \left( 0 , 2 \right)  \)
\begin{proof}
\todo{Důkaz 5.29}
\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 využít \ref{KHermPDPredpodmineneAproximace} 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}
\todo{Důkaz 5.38}
\end{proof}
\end{theorem}