01NUM1:Kapitola3

Z WikiSkripta FJFI ČVUT v Praze
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{Úvod do numerické matematiky}
 
\subsection{Reprezentace čísel s pohyblivou desetinnou čárkou}
 
\setcounter{define}{1}
\begin{theorem}
\label{ArbitraryPrecision}
Libovolné \( x \in \mathbbm R \) lze v libovolné soustavě o základu \( \beta \) s libovolnou přesností aproximovat reálným číslem \( x_\beta \), jehož zápis v této soustavě má konečný počet cifer.
\begin{proof}
\todo{Zrevidovat, zjednodušit důkaz 3.2 - Mlha si ho celý vycucal z prstu, snad by to šlo přepsat bez toho megavýroku.}
BÚNO \( x \geq 0 \). Označíme přesnost aproximace \( \varepsilon = \lvert x - x_\beta \rvert \) a zapíšeme \( x_\beta = \sum_{k = -m}^n x_k^{( \beta )} \beta^k \) Dokazujeme výrok
\[ (\forall \varepsilon > 0) (\forall \beta \in \mathbbm N \smallsetminus \{1\}) (\exists m,n \in \mathbbm N) (\forall l \in \mathbbm Z \cap \left< -m , n \right>) (\exists x_l^{( \beta )} \in \mathbbm Z, 0 \leq x_l^{( \beta )} < \beta}) (\left\lvert x - \sum_{k = -m}^n x_k^{( \beta )} \beta^k \right\rvert \leq \varepsilon) \]
Přepíšeme \( x_\beta \) do dvou sum (celá a desetinná část), tedy
\[ x_\beta = \sum_{k = -m}^n x_k^{( \beta )} \beta^k = \sum_{k = 0}^n x_k^{( \beta )} \beta^k + \sum_{k = 1}^m \frac{x_{-k}^{( \beta )}}{\beta^k} \]
a dále využijeme toho, že každé reálné číslo se dá pro nějaké konečné \( u \in \mathbbm N \) zapsat jako
\[ x = \sum_{k = 0}^u x_k \beta^k + \sum_{k = 1}^\infty \frac{x_{-k}}{\beta^k} \]
Položíme \( n = u \) a \( x_l^{( \beta )} = x_l, \; \forall l \in \mathbbm Z \cap \left< -m , n \right>\) a odhadujeme
\[ \left\lvert x - \sum_{k = -m}^n x_k^{( \beta )} \beta^k \right\rvert = \left\lvert \sum_{k = 0}^u x_k \beta^k + \sum_{k = 1}^\infty \frac{x_{-k}}{\beta^k} - \sum_{k = 0}^u x_k \beta^k - \sum_{k = 1}^m \frac{x_{-k}}{\beta^k} \right\rvert = \]
\[ \left\lvert \sum_{k = m + 1}^\infty \frac{x_{-k}}{\beta^k} \right\rvert \leq \left\lvert \sum_{k = m + 1}^\infty \frac{\beta}{\beta^k} \right\rvert = \left\lvert \sum_{k = m + 1}^\infty \frac{1}{\beta^{k - 1}} \right\rvert \leq \left\lvert \sum_{k = m + 1}^\infty \frac{1}{\beta} \right\rvert = \frac{m + 1}{\beta} \]
a protože chceme dosáhnout \( \frac{m + 1}{\beta} \leq \varepsilon \), stačí volit \( m = \lfloor \varepsilon \beta \rfloor - 1 \), aby platil dokazovaný výrok.
\end{proof}
\end{theorem}
 
\subsection{Podmíněnost matic}
 
\setcounter{define}{28}
\begin{theorem}
\label{PerturbacePodminenost}
Nechť matice \( \matice A \in \mathbbm C^{n, n} \) je regulární. Buď \( \vec x \) řešením soustavy \( \matice A \vec x = \vec b \neq \vec 0 \) a dále buďte \( \delta \vec x \), \( \delta \vec b \) perturbace takové, že platí \( \matice A ( \vec x + \delta \vec x ) = \vec b + \delta \vec b \). Pak platí
\[ \frac{\lVert \delta \vec x \rVert}{\lVert \vec x \rVert} \leq \kappa ( \matice A ) \frac{\lVert \delta \vec b \rVert}{\lVert \vec b \rVert} \]
a jde-li o indukovanou maticovou normu, pak existují \( \vec b \neq \vec 0 \) a \( \delta \vec b \neq \vec 0 \) takové, že nastává rovnost.
\begin{proof}
\begin{enumerate}[(1)]
\item Díky regularitě matice \( \matice A \) a požadavku nenulovosti soustavy platí \( \vec b \neq \vec 0 \) a \( \vec x \neq \vec 0 \). Úpravou soustavy s perturbacemi dostáváme
\[ \matice A \delta \vec x = \vec b + \delta \vec b - \matice A \vec x = \delta \vec b \]
a díky regularitě \( \matice A \) tedy \( \delta \vec x = \matice A^{-1} \delta \vec b \). Aplikací trojúhelníkové nerovnosti dále získáváme
\[ \lVert \vec b \rVert \leq \lVert \matice A \rVert \lVert \vec x \rVert \]
\[ \lVert \delta \vec x \rVert \leq \lVert \matice A^{-1} \rVert \lVert \delta \vec b \rVert \]
a tedy
\[ \lVert \vec b \rVert \rVert \delta \vec x \rVert \leq \lVert \matice A \rVert \lVert \matice A^{-1} \rVert \lVert \vec x \rVert \lVert \delta \vec b \rVert \]
Vydělíme (nenulovými) vektory a použíjeme definici \( \kappa ( \matice A ) = \lVert \matice A \rVert \lVert \matice A^{-1} \rVert \), čímž dostaneme tvrzení věty.
\item Pokud je maticová norma indukovaná, lze si definici normy přepsat jako
\[ \lVert \matice B \rVert = \max\limits_{\vec y} \frac{\lVert \matice B \vec y \rVert}{\lVert \vec y \rVert} \]
a tedy při volbě \( \vec z \) takového, aby nastalo toto maximum, platí
\[ \lVert \matice B \rVert \lVert \vec z \rVert = \frac{\lVert \matice B \vec z \rVert}{\lVert \vec z \rVert} \lVert \vec z \rVert = \lVert \matice B \vec z \rVert \]
a tedy se trojúhelníková nerovnost stává trojúhelníkovou rovností. Možnost volby takových vektorů máme, z čehož plyne tvrzení o rovnosti v dokazované větě \qedhere
\end{enumerate}
\end{proof}
\end{theorem}
 
\subsection{Předpodmínění}
 
\begin{remark}
\label{SingularniVzdalenost}
Nechť \( \matice A \in \mathbbm C^{n, n} \). Definujeme vzdálenost s normou \( p \) matice \( \matice A \) od množiny singulárních matic jako
\[ dist_p ( \matice A ) = \min_{\delta \in \mathbbm C} \left\{ \frac{\delta \lVert \matice A \rVert_p}{\lVert \matice A \rVert_p} \; \Bigg | \; ( 1 + \delta ) \matice A \; \text{je singulární} \right\} \]
Potom platí
\[ dist_p ( \matice A ) \leq \frac{1}{\kappa ( \matice A )} \]
\begin{proof}\renewcommand{\qedsymbol}{}
Bez důkazu.
\end{proof}
\end{remark}