01NUM1:Kapitola5: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
(Všechny věty) |
|||
Řádka 146: | Řádka 146: | ||
\begin{theorem} | \begin{theorem} | ||
\label{KHermPDPostupneAproximace} | \label{KHermPDPostupneAproximace} | ||
− | Nechť matice \( \matice A \) je hermitovská a pozitivně definitní. Pak metoda postupných aproximací konverguje právě tehdy, když | + | 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 \] | \[ \Theta < \matice A < 2 \matice I \] | ||
\begin{proof} | \begin{proof} | ||
Řádka 157: | Řádka 157: | ||
\setcounter{define}{12} | \setcounter{define}{12} | ||
\begin{theorem} | \begin{theorem} | ||
− | \label{ | + | \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 | 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 \] | \[ \vec x^{( k + 1 )} = ( \matice I - \matice{H A} ) \vec x^{( k )} + \matice H \vec b \] | ||
Řádka 165: | Řádka 165: | ||
\todo{Důkaz 5.13} | \todo{Důkaz 5.13} | ||
\end{proof} | \end{proof} | ||
+ | |||
\end{theorem} | \end{theorem} | ||
Řádka 171: | Řádka 172: | ||
\[ \lVert \matice I - \matice{H A} \rVert < 1 \] | \[ \lVert \matice I - \matice{H A} \rVert < 1 \] | ||
\end{remark*} | \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 \) právě tehdy, když | ||
+ | \[ \Theta < \matice A <\matice H^{-1} + ( \matice H^{-1} )^* \] | ||
+ | Konvergence je navíc monotónní vzhledem k \todo{Spíš maticové, ne?} vektorové normě \( \lVert \, \cdot \, \rVert_{\matice A} \) | ||
+ | \begin{proof} | ||
+ | \todo{Důkaz 5.14} | ||
+ | \end{proof} | ||
+ | \end{theorem} | ||
+ | |||
+ | \subsection{Richardsonovy iterace} | ||
+ | |||
+ | \setcounter{define}{15} | ||
+ | \begin{theorem} | ||
+ | \label{KHermPDRichardson} | ||
+ | Nechť matice \( \matice A \) je hermitovská a pozitivně definitní. 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 \todo{Spíš maticové, ne?} vektorové normě \( \lVert \, \cdot \, \rVert_{\matice A} \) | ||
+ | \begin{proof} | ||
+ | \todo{Důkaz 5.16} | ||
+ | \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} | ||
+ | \todo{Důkaz 5.18} | ||
+ | \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} | ||
+ | \todo{Důkaz 5.20} | ||
+ | \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 \todo{Spíš maticové, ne?} vektorové normě \( \lVert \, \cdot \, \rVert_{\matice A} \) | ||
+ | \begin{proof} | ||
+ | \todo{Důkaz 5.21} | ||
+ | \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} | ||
+ | \todo{Důkaz 5.23} | ||
+ | \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} | ||
+ | \todo{Důkaz 5.24} | ||
+ | \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 \todo{Spíš maticové, ne?} vektorové normě \( \lVert \, \cdot \, \rVert_{\matice A} \) | ||
+ | \begin{proof} | ||
+ | \todo{Důkaz 5.25} | ||
+ | \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} | ||
+ | \todo{Důkaz 5.28} | ||
+ | \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á.\todo{Důkaz 5.30} | ||
+ | \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 \todo{Spíš maticové, ne?} vektorové normě \( \lVert \, \cdot \, \rVert_{\matice A} \) | ||
+ | \begin{proof} | ||
+ | \todo{Důkaz 5.31 - to v prezentaci je divný} | ||
+ | \end{proof} | ||
+ | \end{theorem} | ||
+ | |||
+ | \setcounter{define}{37} | ||
+ | \begin{theorem} | ||
+ | \label{SOREigenvalue} | ||
+ | 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í a \( \matice B_J \in \mathbbm C^{n, n} \) je Jacobiho maticí. 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} |
Verze z 26. 12. 2015, 21:58
[ 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} \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í 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} \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*} \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 \) právě tehdy, když \[ \Theta < \matice A <\matice H^{-1} + ( \matice H^{-1} )^* \] Konvergence je navíc monotónní vzhledem k \todo{Spíš maticové, ne?} vektorové normě \( \lVert \, \cdot \, \rVert_{\matice A} \) \begin{proof} \todo{Důkaz 5.14} \end{proof} \end{theorem} \subsection{Richardsonovy iterace} \setcounter{define}{15} \begin{theorem} \label{KHermPDRichardson} Nechť matice \( \matice A \) je hermitovská a pozitivně definitní. 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 \todo{Spíš maticové, ne?} vektorové normě \( \lVert \, \cdot \, \rVert_{\matice A} \) \begin{proof} \todo{Důkaz 5.16} \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} \todo{Důkaz 5.18} \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} \todo{Důkaz 5.20} \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 \todo{Spíš maticové, ne?} vektorové normě \( \lVert \, \cdot \, \rVert_{\matice A} \) \begin{proof} \todo{Důkaz 5.21} \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} \todo{Důkaz 5.23} \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} \todo{Důkaz 5.24} \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 \todo{Spíš maticové, ne?} vektorové normě \( \lVert \, \cdot \, \rVert_{\matice A} \) \begin{proof} \todo{Důkaz 5.25} \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} \todo{Důkaz 5.28} \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á.\todo{Důkaz 5.30} \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 \todo{Spíš maticové, ne?} vektorové normě \( \lVert \, \cdot \, \rVert_{\matice A} \) \begin{proof} \todo{Důkaz 5.31 - to v prezentaci je divný} \end{proof} \end{theorem} \setcounter{define}{37} \begin{theorem} \label{SOREigenvalue} 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í a \( \matice B_J \in \mathbbm C^{n, n} \) je Jacobiho maticí. 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}