Verze z 10. 12. 2016, 14:14

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 \sm \{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}