01NUM1:Kapitola5: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
(Věty 1-5) |
m (stylistika) |
||
Řádka 68: | Řádka 68: | ||
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í: | 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)] | \begin{enumerate}[(1)] | ||
− | \item \ | + | \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 \ | + | \\ |
+ | \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} | \end{enumerate} | ||
\begin{proof} | \begin{proof} |
Verze z 17. 12. 2015, 01:53
[ 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 | 20:49 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Dedicma2 | 3. 6. 2024 | 20:48 | ||
Header | editovat | Hlavičkový soubor | Dedicma2 | 17. 1. 2016 | 17:20 | header.tex | |
Kapitola0 | editovat | Značení | Dedicma2 | 23. 5. 2017 | 22:32 | znaceni.tex | |
Kapitola2 | editovat | Opakování a doplnění znalostí z lineární algebry | Dedicma2 | 3. 6. 2024 | 16:41 | prezentace2.tex | |
Kapitola3 | editovat | Úvod do numerické matematiky | Dedicma2 | 3. 6. 2024 | 16:51 | prezentace3.tex | |
Kapitola4 | editovat | Přímé metody pro lineární soustavy | Dedicma2 | 3. 6. 2024 | 17:47 | prezentace4.tex | |
Kapitola5 | editovat | Iterativní metody | Dedicma2 | 3. 6. 2024 | 17:59 | prezentace5.tex | |
Kapitola6 | editovat | Vlastní čísla a vektory matic | Dedicma2 | 3. 6. 2024 | 18:07 | prezentace6.tex | |
Kapitola7 | editovat | Nelineární rovnice | Kubuondr | 31. 1. 2017 | 15:27 | prezentace7.tex | |
Kapitola8 | editovat | Interpolace | Kubuondr | 31. 1. 2017 | 16:43 | prezentace8.tex | |
Kapitola9 | editovat | Derivace a integrace | Kubuondr | 31. 1. 2017 | 18: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} \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}