01NUM1:Kapitola5

Z WikiSkripta FJFI ČVUT v Praze
Verze z 26. 12. 2015, 22:57, kterou vytvořil Dedicma2 (diskuse | příspěvky) (Zrušena verze 5760 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. 201617:56
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůDedicma2 23. 5. 201722:31
Header editovatHlavičkový souborDedicma2 17. 1. 201617:20 header.tex
Kapitola0 editovatZnačeníDedicma2 23. 5. 201722:32 preamble.tex
Kapitola2 editovatOpakování a doplnění znalostí z lineární algebryKubuondr 30. 1. 201718:14 prezentace2.tex
Kapitola3 editovatÚvod do numerické matematikyKubuondr 10. 12. 201615:17 prezentace3.tex
Kapitola4 editovatPřímé metody pro lineární soustavyKubuondr 30. 1. 201712:27 prezentace4.tex
Kapitola5 editovatIterativní metodyKubuondr 31. 1. 201711:41 prezentace5.tex
Kapitola6 editovatVlastní čísla a vektory maticKubuondr 31. 1. 201714:13 prezentace6.tex
Kapitola7 editovatNelineární rovniceKubuondr 31. 1. 201715:27 prezentace7.tex
Kapitola8 editovatInterpolaceKubuondr 31. 1. 201716:43 prezentace8.tex
Kapitola9 editovatDerivace a integraceKubuondr 31. 1. 201718: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 \]
\[ \vec c = ( \matice I - \matice B) \vec x^* \Rightarrow \vec x^* =\todo{Důkaz 5.8 - regularita} ( \matice I - \matice B )^{-1} \vec c =\todo{Důkaz 5.8 - vysvětlit proč} \sum_{i = 0}^\infty \matice B^i \vec c \]
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}
\todo{Důkaz 5.9 - použij \ref{GeomKSpektrum} }
\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}
\todo{Důkaz 5.10 - použij \ref{JordanovaVeta} }
\end{proof}
\end{theorem}
 
\begin{example*}
Vezmeme polynom \( p (t) = at^2 + bt + c \). Potom \( p( \matice A ) = a \matice A^2 + b \matice A + c \matice I \).
\todo{Příklad k 5.10 z přednášky}
\end{example*}
 
\begin{theorem}
\label{KHermPDPostupneAproximace}
Nechť matice \( \matice A \) je hermitovská a pozitivně definitní. Pak metoda postupných aproximací konverguje 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{KPredpodmineneMetody}
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}
\todo{Důkaz 5.13}
\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*}

Citováno z „https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01NUM1:Kapitola5&oldid=5761“