Součásti dokumentu 01NUM1
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 \[ \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 \[ \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}
\todo{Důkaz 5.5}
\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}
