01NUM1:Kapitola7

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.
ZIP			Kompletní zdrojový kód včetně obrázků.
Součásti dokumentu 01NUM1

součást	akce		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{Nelineární rovnice}
 
\subsection{Separace kořenů}
 
\begin{theorem}[Bolzanova Věta]
\label{Bolzano}
Nechť je \( f \in \mathcal C ( \left< a, b \right> ) \). Nechť dále \( f ( a ) f ( b ) < 0 \). Potom funkce \( f \) má na \( \left( a, b \right) \) alespoň jeden kořen. Pokud \( f' \) na \( \left( a, b \right) \) nemění znaménko, pak je tento kořen jedinný. 
\begin{proof}
BÚNO \( f ( a ) < 0 \)
\begin{enumerate}[(1)]
\item Důkaz sporem
\\ Položíme \( c = \sup \left\{ x \in \left< a, b \right> | f ( x ) < 0 \right\} \). Předpokládáme \( f ( c ) \neq 0 \), tedy podle definice  \( f ( c ) < 0 \). Volíme \( d \in \left( f(c), 0 \right) \) a díky definici \( c \) neexistuje \( y \in \left< a, b \right> \) takové, aby \( f ( y ) = d \), což je spor se spojitostí funkce \( f \). \qedhere
\end{enumerate}
\end{proof}
\end{theorem}
 
\subsection{Výpočet kořene - metoda bisekcí}
Nechť je \( f \in \mathcal C ( \left< a, b \right> ) \). Nechť dále \( f ( a ) f ( b ) < 0 \). Interval půlíme a vždy pomocí \ref{Bolzano} určíme, v které polovině se nachází kořen. Postup opakujeme s novým intervalem. Označíme-li kořen \( \alpha \) a bod, který půlí interval \( x_k \), můžeme odhadovat
\[ \lvert \alpha - x_k \rvert \leq \frac{b - a}{2^k} \]
 
\subsection{Iterativní metody pro hledání kořenů}
 
\begin{lemma*}
Nechť \( \varphi ( \alpha ) = \alpha \) pro nějaké \( \alpha \). Nechť je dále \( \varphi \) diferencovatelná na nějakém \( H_\alpha^r \) a \( \lvert \varphi' ( x ) \rvert \leq K \) pro nějaké \( K < 1 \). Nechť je posloupnost \( \left\{ x_k  \right\}_{k = 0}^\infty \) definována rekurentním vztahem
\[ x_{k + 1} = \varphi ( x_k ) \]
Potom
\[ x_k \in H_\alpha^r, \; \forall k \in \mathbbm N \]
\begin{proof}
indukcí podle \( k \)
\begin{itemize}
\item \( k = 0 \)
\\Je předpokladem věty.
\item \( k \Rightarrow k + 1 \)
\[ \left\lvert x_{k + 1} - \alpha \right\rvert = \left\lvert \varphi ( x_k ) - \varphi ( \alpha ) \right\rvert \]
Použijeme Lagrangeovu věty o přírůstku (předpoklady splněny indukčním předpokladem):
\[ \left\lvert \varphi ( x_k ) - \varphi ( \alpha ) \right\rvert = \left\lvert \varphi' ( \xi ) \right\rvert \left\lvert x_k - \alpha \right\rvert \leq K \left\lvert x_k - \alpha \right\rvert < \left\lvert x_k - \alpha \right\rvert \]
\end{itemize}
\end{proof}
\end{lemma*}
 
\setcounter{define}{3}
\begin{theorem}
\label{KIterativniMetodyKorenu}
Nechť \( \varphi ( \alpha ) = \alpha \) pro nějaké \( \alpha \). Nechť je dále \( \varphi \) diferencovatelná na nějakém \( H_\alpha^r \) a \( \lvert \varphi' ( x ) \rvert \leq K \) pro nějaké \( K < 1 \). Nechť je posloupnost \( \left\{ x_k  \right\}_{k = 0}^\infty \) definována rekurentním vztahem
\[ x_{k + 1} = \varphi ( x_k ) \]
Potom
\[ \lim_{k \rightarrow \infty} x_k = \alpha, \; \forall x_0 \in H_\alpha^r \]
\begin{proof}
\[ \left\lvert x_k - \alpha \right\rvert = \left\lvert \varphi ( x_{k - 1} ) - \varphi ( \alpha ) \right\rvert \]
Díky lemmatu můžeme opakovaně použít Lagrangeovu větu o přírůstku
\[ \left\lvert \varphi ( x_{k - 1} ) - \varphi ( \alpha ) \right\rvert = \left\lvert \varphi ( \xi_{k - 1} ) \right\rvert \left\lvert x_{k - 1} - \alpha \right\rvert = \dots = \left\lvert x_0 - \alpha \right\rvert \prod_{i = 0}^{k - 1} \left\lvert \varphi ( \xi_i ) \right\rvert \leq K^k \left\lvert x_0 - \alpha \right\rvert \]
A tedy
\[ \lim_{k \rightarrow \infty} ( x_k - \alpha ) = \lim_{k \rightarrow \infty} K^k \left\lvert x_0 - \alpha \right\rvert = 0 \]
\end{proof}
\begin{remark*}
Předpoklad \( \lvert \varphi' ( x ) \rvert \leq K<1 \) splníme např. tak, že \(\lvert \varphi' ( \alpha ) \rvert<1\). Budeme tedy hledat okolí \(H_{\alpha}^r\) tak, aby to bylo splněné.
\end{remark*}
\end{theorem}
 
\subsection{Metoda regula falsi}
 
\setcounter{define}{9}
\begin{theorem}
\label{KRegulaFalsi}
Nechť je \( \alpha \) kořenem funkce \( f \). Nechť dále existuje \( H_\alpha^r \) takové, že \( f \in \mathcal C^2 ( H_\alpha^r ) \). Nechť \( f' ( \alpha ) \neq 0 \). Nechť \( x_0 \in H_\alpha^r \). Potom metoda regula falsi konverguje.
\begin{proof}
Využijeme vztahu
\[ \varphi ( x ) = x - \frac{x - x_k'}{f ( x ) - f ( x_k' )} f ( x ) \]
Tedy
\[ \varphi' ( x ) = 1 - \left( \frac{x - x_k'}{f ( x ) - f ( x_k' )} \right)' f ( x ) - \frac{x - x_k'}{f ( x ) - f ( x_k' )} f' ( x ) \]
\[ \varphi' ( \alpha ) = 1 + \frac{\alpha - x_k'}{f ( x_k' )} f' ( \alpha ) = \frac{f ( x_k' ) + ( \alpha - x_k' ) f' ( \alpha )}{f ( x_k' )} \]
Nyní pomocí Taylorových rozvojů odhadneme nejprve rozvojem do druhého řádu
\[ f ( x_k' ) = f ( \alpha ) + f' ( \alpha ) \left( x_k' - \alpha \right) + \frac{f'' ( \xi )}{2} \left( x_k' - \alpha \right)^2 \]
Tedy
\[ f ( x_k' ) + \left( \alpha - x_k' \right) f' ( \alpha ) = \frac{f'' ( \xi )}{2} \left( x_k' - \alpha \right)^2 \]
A následně rozvojem do prvního řádu
\[ f ( x_k' ) = f' ( \eta ) \left( x_k' - \alpha \right) \]
Tedy ve výsledku
\[ \frac{f ( x_k' ) + ( \alpha - x_k' ) f' ( \alpha )}{f ( x_k' )} = \frac{f'' ( \xi )}{2 f' ( \eta )} \left( x_k' - \alpha \right) = K \left( x_k' - \alpha \right) \]
kde \( K \) je definováno poslední rovností. Správnou volbou \( x_k' \) můžeme tedy libovolně zmenšit \( \lvert \varphi' ( \alpha ) \rvert \). Tím jsou splněny předpoklady \ref{KIterativniMetodyKorenu}.
\end{proof}
\end{theorem}
\begin{remark*}
Pro platnost věty je zásadní, že se jedná o \( H_\alpha^r \), tj. určitá podmnožina, kde je \( f \in \mathcal C^2 ( H_\alpha ) \). Rozhodně to neplatí pro všechna $x \in \matice R$,
pokud je \( f \in \mathcal C^2 (\matice R)\).
\end{remark*}
\begin{remark*}
Věta lze dokázat i přímo, dokonce se slabším předpokladem \( f \in \mathcal C^1 ( H_\alpha^r ) \): 
\[ x_{k + 1} - \alpha = x_k - \alpha - \frac{x_k - x_k'}{f ( x_k ) - f ( x_k' )} f(x_k) = x_k - \alpha - \frac{x_k - x_k'}{f'(\xi) ( x_k - x_k' )}f(x_k)=  x_k - \alpha - \frac{f(x_k)}{f'(\xi)}=\]
V třetím rovnítku jsme použili Lagrangeovu větu.
\[= x_k - \alpha - \frac{f(x_k)+f(\alpha)}{f'(\xi)}=x_k - \alpha - \frac{(x_k- \alpha)f'(\eta)}{f'(\xi)}= \left( \frac{f'(\xi)-f'(\eta)}{f'(\xi)} \right) (x_k - \alpha)\]
Dodali jsme \(f(\alpha)\), které je nulové, a znovu použili Lagrangeovu větu. Z ní plyne, že \(\xi \in [x_k,x_k']\) a \(\eta \in [x_k,\alpha]\). Při dostatečně malém okolí je první závorka posledního výrazu menší než jedna a \(f(\xi) \neq 0\). Dokázali jsme tedy, že posloupnost postupných aproximací konverguje.
\end{remark*}
 
\subsection{Newtonova metoda}
 
\setcounter{define}{12}
\begin{theorem}
\label{KNewton}
Nechť je \( \alpha \) kořenem funkce \( f \). Nechť dále existuje \( H_\alpha^r \) takové, že \( f \in \mathcal C^2 ( H_\alpha^r ) \). Nechť \( f' ( \alpha ) \neq 0 \). Nechť \( x_0 \in H_\alpha^r \). Potom Newtonova metoda konverguje.
\begin{proof}
Využijeme vztahu
\[ x_{k + 1} = x_k - \frac{f ( x_k )}{f' ( x_k )} \]
k úpravě
\[ x_{k + 1} - \alpha = x_k - \alpha - \frac{f ( x_k )}{f' ( x_k )} = x_k - \alpha - \frac{f ( x_k ) - f ( \alpha )}{f' ( x_k )} \]
Použijeme Lagrangeovu větu o přírůstku:
\[ x_k - \alpha - \frac{f ( x_k ) - f ( \alpha )}{f' ( x_k )} = x_k - \alpha - \frac{f' ( \xi ) ( x_k - \alpha )}{f' ( x_k )} = \frac{f' ( x_k ) - f' ( \xi )}{f' ( x_k )} \left( x_k - \alpha \right) \]
Znovu použijeme Lagrangeovu větu o přírůstku:
\[ \frac{f' ( x_k ) - f' ( \xi )}{f' ( x_k )} \left( x_k - \alpha \right) = \frac{f'' ( \xi' )}{f' ( x_k )} \left( x_k - \xi \right) \left( x_k - \alpha \right) = K \left( x_k - \xi \right) \left( x_k - \alpha \right) \]
kde \( K \) je definováno poslední rovností a díky spojitosti \( f' \) platí \( K < 1 \). Tím jsou splněny předpoklady \ref{KIterativniMetodyKorenu}.
\end{proof}
\end{theorem}
 
\setcounter{define}{14}
\begin{theorem}
\label{NewtonRad}
Nechť je \( \alpha \) kořenem funkce \( f \). Nechť dále existuje \( H_\alpha^r \) takové, že \( f \in \mathcal C^2 ( H_\alpha^r ) \). Nechť \( f' ( \alpha ) \neq 0 \). Nechť \( x_0 \in H_\alpha^r \). Potom Newtonova metoda je metodou druhého řádu přesnosti. Pokud je  \( f \in \mathcal C^1 ( H_\alpha^r ) \), potom Newtonova metoda je metodou prvního řádu přesnosti.
\begin{proof}
\begin{enumerate}
\item (\textit{druhý řád}) Viz důkaz \ref{KNewton}. 
\item (\textit{první řád}) Zde můžeme použít Lagrangeovu větu pouze jednou. Pokud je však \(\xi \) dostatečně blízko \(x_k\) (což zajišťujeme volbou okolí), pak je \(K=\frac{f' ( x_k ) - f' ( \xi )}{f' ( x_k )}<1\), tj. \(\varphi \) je kontrahující, Newtonova metoda konverguje a je metodou prvního řádu.
\end{enumerate}
\end{proof}
\end{theorem}
 
\subsection{Metody pro řešení soustav nelineárních rovnic}
 
\setcounter{define}{23}
\begin{theorem}[Lagrangeova věta o přírůstku funkce více proměnných]
\label{VoPF}
Nechť \( G \) je konvexní oblast. Nechť funkce \( f \in \mathcal C^1 ( G ) \). Potom pro každé \( \vec u, \vec v \in G \) existuje \( \vec \xi \in \left( \vec u, \vec v \right) \) (úsečka mezi \( \vec u \) a \( \vec v) \) takový, že
\[ f ( \vec u ) - f ( \vec v ) = \nabla f ( \vec \xi ) ( \vec u - \vec v ) \]
\begin{proof}
Definujeme funkci
\[ \varphi ( t ) = f ( \vec u + t ( \vec v - \vec u ) ), \; \forall t \in \left< 0, 1 \right> \]
Potom
\[ \varphi' ( t ) = \nabla f ( \vec u + t ( \vec v - \vec u ) ) ( \vec v - \vec u ) \]
Protože \( \varphi \) je funkce jedné proměnné, můžeme použít klasickou Lagrangeovu větu o přírůstku:
\[ \varphi ( 1 ) - \varphi ( 0 ) = \varphi' ( \eta ) \]
Označíme \( \vec \xi = \vec u + \eta ( \vec v - \vec u ) \) a budeme tedy upravovat
\[ f ( \vec u ) - f ( \vec v ) = - ( \varphi ( 1 ) - \varphi ( 0 ) ) = - \varphi' ( \eta ) = - \nabla f ( \vec u + \eta ( \vec v - \vec u ) ) ( \vec v - \vec u ) = \nabla f ( \vec \xi ) ( \vec u - \vec v ) \]
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{KNewtonLinearne}
Nechť platí:
\begin{itemize}
\item Existuje konvexní oblast \( G \), obsahující řešení \( \vec a \) systému rovnic \( \vec f ( \vec x ) = \vec 0 \)
\item \( \matice J_{\vec f} ( \vec a ) \) je regulární
\item složky \( \vec f \) jsou funkce spojité na \( G \), jejich první parciální derivace také
\end{itemize}
Potom existuje \( H_{\vec a}^\delta \) takové, že pro každé \( \vec x^{( 0 )} \in H_{\vec a}^\delta \) posloupnost generovaná Newtonovou metodou konverguje k \( \vec a \).
\begin{proof}
Nejprve díky \ref{VoPF} ukážeme pomocné tvrzení
\[ \vec f ( \vec x^{( k )} ) - \vec f ( \vec a ) =
\begin{pmatrix}
f_1 ( \vec x^{( k )} ) - f_1 ( \vec a ) \\
\vdots \\
f_n ( \vec x^{( k )} ) - f_n ( \vec a ) \\
\end{pmatrix} =
\begin{pmatrix}
\nabla f_1 ( \vec \xi_1 ) \\
\vdots \\
\nabla f_n ( \vec \xi_n ) \\
\end{pmatrix}
\left( \vec x^{( k )} - \vec a \right) = \matice J_{\vec f} ( \vec \xi ) \left( \vec x^{( k )} - \vec a \right) \]
kde \( \matice J_{\vec f} ( \vec \xi ) \) je definovaná poslední rovností. Dále využijeme vztahu
\[ \vec x^{( k + 1 )} = \vec x^{( k )} - \matice J_{\vec f}^{-1} ( \vec x^{( k )} ) \vec f ( \vec x^{( k )} ) \]
Potom můžeme odhadovat
\[ \left\lVert \vec x^{( k + 1 )} - \vec a \right\rVert = \left\lVert \vec x^{( k )} - \vec a - \matice J_{\vec f}^{-1} ( \vec x^{( k )} ) \vec f ( \vec x^{( k )} ) \right\rVert = \left\lVert \vec x^{( k )} - \vec a - \matice J_{\vec f}^{-1} ( \vec x^{( k )} ) \left( \vec f ( \vec x^{( k )} ) - \vec f ( \vec a ) \right) \right\rVert = \]
\[ = \left\lVert \vec x^{( k )} - \vec a - \matice J_{\vec f}^{-1} ( \vec x^{( k )} ) \matice J_{\vec f} ( \vec \xi ) \left( \vec x^{( k )} - \vec a \right) \right\rVert = \left\lVert \left( \matice I - \matice J_{\vec f}^{-1} ( \vec x^{( k )} ) \matice J_{\vec f} ( \vec \xi ) \right) \left( \vec x^{( k )} - \vec a \right) \right\rVert \leq \]
\[ \leq \left\lVert \matice I - \matice J_{\vec f}^{-1} ( \vec x^{( k )} ) \matice J_{\vec f} ( \vec \xi ) \right\rVert \left\lVert \vec x^{( k )} - \vec a \right\rVert = K \left\lVert \vec x^{( k )} - \vec a \right\rVert \]
kde \( K \) je definováno poslední rovností. Budeme chtít ukázat \( K < 1 \), tedy
\[ \matice I - \matice J_{\vec f}^{-1} ( \vec x^{( k )} ) \matice J_{\vec f} ( \vec \xi ) = \matice J_{\vec f}^{-1} ( \vec a ) \matice J_{\vec f} ( \vec a ) - \matice J_{\vec f}^{-1} ( \vec x^{( k )} ) \matice J_{\vec f} ( \vec \xi ) + \matice J_{\vec f}^{-1} ( \vec a ) \matice J_{\vec f} ( \vec \xi ) - \matice J_{\vec f}^{-1} ( \vec a ) \matice J_{\vec f} ( \vec \xi ) = \]
\[ = \matice J_{\vec f}^{-1} (\vec a) \left( \matice J_{\vec f} ( \vec a ) - \matice J_{\vec f} ( \vec \xi ) \right) + \left( \matice J_{\vec f}^{-1} ( \vec a ) - \matice J_{\vec f}^{-1} ( \vec x^{( k )} ) \right) \matice J_{\vec f} ( \vec \xi ) < 1 \]
Kde poslední rovnost plyne z faktu, že \( \matice J_{\vec f} ( \vec a ) - \matice J_{\vec f} ( \vec \xi ) \) můžeme udělat libovolně malou a \( \matice J_{\vec f} ( \vec \xi ) \) je omezená.
\end{proof}
\end{theorem}
 
\begin{theorem}
\label{KNewtonQuadraticky}
Nechť platí:
\begin{itemize}
\item Existuje konvexní oblast \( G \), obsahující řešení \( \vec a \) systému rovnic \( \vec f ( \vec x ) = \vec 0 \)
\item \( \matice J_{\vec f} ( \vec a ) \) je regulární
\item složky \( \vec f \) jsou funkce spojité na \( G \), jejich první a druhé parciální derivace také
\end{itemize}
Potom existuje \( H_{\vec a}^\delta \) takové, že pro každé \( \vec x^{( 0 )} \in H_{\vec a}^\delta \) posloupnost generovaná Newtonovou metodou konverguje k \( \vec a \) kvadraticky, tj. s přesností druhého řádu.
\begin{proof}
\todo{Důkaz 7.26}
\end{proof}
\end{theorem}