Součásti dokumentu 01NUM1
Zdrojový kód
%\wikiskriptum{01NUM1}
\section{Interpolace}
\subsection{Lagrangeův polynom}
\setcounter{define}{2}
\begin{theorem}
\label{LagrangeuvPolynom}
Buď \( f: \mathbbm R \rightarrow \mathbbm R \) a body \( x_0, x_1, \dots, x_n \in D_f \). Pak existuje právě jeden Lagrangeův interpolační polynom \( L_n \) příslušící funkci \( f \) a uzlům \( x_0, x_1, \dots, x_n \).
\begin{proof}
\begin{enumerate}[(1)]
\item existence
\\ Plyne přímo z definice Lagrangeova polynomu.
\item jedinečnost - důkaz sporem
\\ Předpokládáme existenci dvou různých Lagrangeových polynomů \( L_n^1 \) a \( L_n^2 \). Využijeme vlastnosti Lagrangeova polynomu
\[ L_n^1 ( x_i ) = L_n^2 ( x_i ) = f ( x_i ), \; \forall i \in \hat n^0 \]
Polynom \( ( L_n^1 - L_n^2 ) \) je polynomem stupně nejvýše \( n \) a platí
\[ ( L_n^1 - L_n^2 ) ( x_i ) = 0, \; \forall i \in \hat n^0 \]
Tedy \( ( L_n^1 - L_n^2 ) \) je roven nule v \( n + 1 \) bodech, což vzhledem k jeho stupni (nejvýše \(n\)) znamená, že \( ( L_n^1 - L_n^2 ) \) je nulovým polynomem a tedy \( L_n^1 = L_n^2 \). \qedhere
\end{enumerate}
\end{proof}
\end{theorem}
\subsection{Lagrangeův polynom - Newtonova formule}
\setcounter{define}{7}
\begin{theorem}
\label{NewtonovaFormule}
Pro poměrné diference \( k \)-tého řádu platí
\[ f \left[ x_i, \dots, x_{i + k} \right] = \sum_{j = i}^{i + k} \frac{f ( x_j )}{\prod_{m = i, m \neq j}^{i + k} ( x_j - x_m ) } \]
\begin{proof}
indukcí podle \( k \)
\begin{itemize}
\item \( k = 1 \)
\[ f \left[ x_i, x_{i + 1} \right] = \frac{f ( x_{i + 1} ) - f ( x_i )}{x_{i+1} - x_i} = \frac{f ( x_i )}{x_i - x_{i + 1}} + \frac{f ( x_{i + 1} )}{x_{i + 1} - x_i} \]
\item \( k \rightarrow k + 1 \)
\[ f \left[ x_i, \dots, x_{i + k + 1} \right] = \frac{f \left[ x_{i + 1}, \dots, x_{i + k + 1} \right] - f \left[ x_i, \dots, x_{i + k} \right]}{x_{i + k + 1} - x_i} \]
Použijeme indukční předpoklad na poměrné diference menšího řádu
\[\frac{f \left[ x_{i + 1}, \dots, x_{i + k + 1} \right] - f \left[ x_i, \dots, x_{i + k} \right]}{x_{i + k + 1} - x_i} = \frac{1}{x_{i + k + 1} - x_i} \left( \sum_{j = i + 1}^{i + k + 1} \frac{f ( x_j )}{\prod_{m = i + 1, m \neq j}^{i + k + 1} ( x_j - x_m )} - \sum_{j = i}^{i + k} \frac{f ( x_j )}{\prod_{m = i, m \neq j}^{i + k} ( x_j - x_m )} \right) = \]
Vyndáme přebývající členy a sloučíme sumy.
\begin{multline*}
= \frac{1}{x_{i + k + 1} - x_i} \left( \frac{f ( x_{i + k + 1} )}{\prod_{m = i + 1}^{i + k} ( x_{i + k + 1} - x_m ) } - \frac{f ( x_i )}{\prod_{m = i + 1}^{i + k} ( x_i - x_m ) } + \right. \\
\left. + \sum_{j = i + 1}^{i + k} f ( x_j ) \left( \frac{1}{\prod_{m = i + 1, m \neq j}^{i + k + 1} ( x_j - x_m )} - \frac{1}{\prod_{m = i, m \neq j}^{i + k} ( x_j - x_m )} \right) \right) =
\end{multline*}
Roznásobíme závorku, ze samostatných členů dostaneme první a poslední člen sumy z tvrzení věty (mínus využito na otočení závorky), v sumě vytkneme společné členy produktu.
\[ = \frac{f ( x_{i + k + 1} )}{\prod_{m = i}^{i + k} ( x_{i + k + 1} - x_m ) } + \frac{f ( x_i )}{\prod_{m = i + 1}^{i + k + 1} ( x_i - x_m ) } + \sum_{j = i + 1}^{i + k} \frac{f ( x_j )}{\left( x_{i + k + 1} - x_i \right) \prod_{m = i + 1, m \neq j}^{i + k} ( x_j - x_m )} \left( \frac{1}{\underbrace{x_j - x_{i + k + 1}}_{\text{pokud} \; j \neq i + k + 1}} - \frac{1}{\underbrace{x_j - x_i}_{\text{pokud} \; j \neq i}} \right) =\]
Převedeme na společný jmenovatel a následně zkrátíme.
\[ = \frac{f ( x_{i + k + 1} )}{\prod_{m = i}^{i + k} ( x_{i + k + 1} - x_m ) } + \frac{f ( x_i )}{\prod_{m = i + 1}^{i + k + 1} ( x_i - x_m ) } + \sum_{j = i + 1}^{i + k} \frac{f ( x_j )}{\left( x_{i + k + 1} - x_i \right) \prod_{m = i + 1, m \neq j}^{i + k} ( x_j - x_m )} \left( \frac{x_{i + k + 1} - x_i}{\underbrace{\left( x_j - x_{i + k + 1} \right)}_{\text{pokud} \; j \neq i + k + 1} \underbrace{\left( x_j - x_i \right)}_{\text{pokud} \; j \neq i}} \right) = \]
\[ = \frac{f ( x_{i + k + 1} )}{\prod_{m = i}^{i + k} ( x_{i + k + 1} - x_m ) } + \frac{f ( x_i )}{\prod_{m = i + 1}^{i + k + 1} ( x_i - x_m ) } + \sum_{j = i + 1}^{i + k} \frac{f ( x_j )}{\prod_{m = i, m \neq j}^{i + k + 1} ( x_j - x_m )} = \sum_{j = i}^{i + k + 1} \frac{f ( x_j )}{\prod_{m = i, m \neq j}^{i + k + 1} ( x_j - x_m )}\]
\end{itemize}
\end{proof}
\end{theorem}
\subsection{Lagrangeův polynom - chyba aproximace}
\setcounter{define}{9}
\begin{theorem}
\label{LagrangeZbytek}
Nechť \( I_x \subset D_f \) nejmenší interval takový, že \( x, x_0, x_1, \dots, x_n \in I_x \) a \( f \in \mathcal C^{n + 1} ( I_x) \). Buď \( L_n \) Lagrangeův interpolační polynom příslušící funkci \( f \) a uzlům \( x_0, x_1, \dots, x_n \). Potom existuje \( \xi \in I_x \) takové, že
\[ R_n ( x ) = f ( x ) - L_n ( x ) = \frac{f^{( n + 1 )} ( \xi )}{( n + 1 )!} \omega_n ( x ) \]
kde definujeme
\[ \omega_n ( x ) = \prod_{i = 0}^n ( x - x_i ) \]
\begin{proof}
Pokud \( x = x_i \) pro nějaké \( i \), tak je \( R_n ( x ) = 0 \) z definice Lagrangeova polynomu a \( \omega_n ( x ) = 0 \) přímo z definice a věta platí triviálně.
V ostatních případech volíme pevné \( x \in I_x \). Definujeme
\[ Q_n ( t ) = \omega_n ( x ) R_n ( t ) - \omega_n ( t ) R_n ( x ) \]
Triviálně \( Q_n ( x ) = 0 \). Přímo z definice \( \omega_n ( x_i ) = 0, \; \forall i \in \hat n \cup \{ 0 \} \). Z definice Lagrangeova polynomu plyne \( R_n ( x_i ) = 0, \; \forall i \in \hat n \cup \{ 0 \} \). Tedy dohromady platí i \( Q_n ( x_i ) = 0, \; \forall i \in \hat n \cup \{ 0 \} \), tudíž \( Q_n ( t ) \) má na \( I_x \) nejméně \( n + 2 \) kořenů (jeden v \( x \) a \( n + 1 \) v \( x_i \)). V těchto bodech je hodnota \( Q_n' ( t ) \) nenulová se střídajícím se znaménkem. Můžeme tedy na těchto \( n + 1 \) intervalech aplikovat Rolleovu větu a \( Q_n' ( t ) \) má na \( I_x \) nejméně \( n + 1 \) kořenů (v každém pod-intervalu jeden). Tento proces opakujeme, existence příslušné derivace \( Q_n ( t ) \) je zajištěna podmínkou diferencovatelnosti funkce \( f \). \( Q_n^{( n + 1 )} \) má na \( I_x \) nejméně jeden kořen, libovolný z nich označíme \( \xi \). Platí
\[ Q_n^{( n + 1 )} ( t ) = \omega_n ( x ) R_n^{( n + 1 )} ( t ) - \omega_n^{( n + 1 )} ( t ) R_n ( x ) \]
Protože \( L_n ( x ) \) je polynom stupně \( n \), můžeme zjednodušit
\[ R_n^{( n + 1 )} ( t ) = f^{( n + 1 )} ( t ) - \underbrace{L_n^{( n + 1 )} ( x )}_{= 0} = f^{( n + 1 )} ( t ) \]
Polynom \( \omega_n ( t ) \) můžeme rozdělit na \( \omega_n ( t ) = t^{n+1} + p_n ( t ) \), kde \( p_n ( t ) \) je nějaký polynom stupně \( n \), a tedy
\[ \omega_n^{( n + 1 )}(x) = ( x^{n + 1} )^{( n + 1 )} + \underbrace{p_n^{( n + 1 )} ( t )}_{= 0} = (n + 1)! \]
a tedy dohromady
\[ Q_n^{( n + 1 )} ( t ) = \omega_n ( x ) f^{( n + 1 )} ( t ) - ( n + 1 )! \, R_n ( x ) \]
po dosazení kořenu \( \xi \) dostáváme
\[ Q_n^{( n + 1 )} ( \xi ) = 0 = \omega_n ( x ) f^{( n + 1 )} ( \xi ) - ( n + 1 )! \, R_n ( x ) \]
z čehož jednoduchou algebraickou úpravou dostaneme tvrzení věty.
\end{proof}
\end{theorem}
\begin{theorem}
\label{LagrangePomerneDiference}
Nechť \( f \in \mathcal C^k ( D_f ) \). Potom pro libovolné \( i \) existuje \( \xi \) ležící mezi uzly \( x_i, \dots, x_{i + k} \) takové, že
\[ f \left[ x_i, \dots, x_{i + k} \right] = \frac{f^{( k )} ( \xi )}{k!} \]
\begin{proof}
Použijeme \ref{NewtonovaFormule} a oddělíme ze sumy první člen:
\[ f \left[ x_i, \dots, x_{i + k} \right] = \sum_{j = i}^{i + k} \frac{f ( x_j )}{\prod_{m = i, m \neq j}^{i + k} ( x_j - x_m )} = \frac{f ( x_i )}{\prod_{m = i + 1}^{i + k} ( x_i - x_m )} + \sum_{j = i + 1}^{i + k} \frac{f ( x_j )}{\prod_{m = i, m \neq j}^{i + k} ( x_j - x_m )} \]
Celou rovnici přenásobíme prvním jmenovatelem:
\[ f \left[ x_i, \dots, x_{i + k} \right] \prod_{m = i + 1}^{i + k} ( x_i - x_m ) = f ( x_i ) + \sum_{j = i + 1}^{i + k} f ( x_j ) \frac{\prod_{m = i + 1}^{i + k} ( x_i - x_m )}{\prod_{m = i, m \neq j}^{i + k} ( x_j - x_m )} \]
Vytkneme z produktů tak, aby měly stejné meze:
\[ f ( x_i ) + \sum_{j = i + 1}^{i + k} f ( x_j ) \frac{\prod_{m = i + 1}^{i + k} ( x_i - x_m )}{\prod_{m = i, m \neq j}^{i + k} ( x_j - x_m )} = f ( x_i ) + \sum_{j = i + 1}^{i + k} f ( x_j ) \frac{( x_i - x_j ) \prod_{m = i + 1, m \neq j}^{i + k} ( x_i - x_m )}{( x_j - x_i ) \prod_{m = i + 1, m \neq j}^{i + k} ( x_j - x_m )} = \]
\[ = f ( x_i ) - \sum_{j = i + 1}^{i + k} f ( x_j ) \prod_{\substack{m = i + 1 \\ m \neq j}}^{i + k} \frac{( x_i - x_m )}{( x_j - x_m )} \]
Nyní použijeme definici báze Lagrangeova polynomu a definici Lagrangeova polynomu (máme posunuté číslování, ale to nevadí, protože to je jen jiné značení, odpovídající tvaru věty):
\[ f ( x_i ) - \sum_{j = i + 1}^{i + k} f ( x_j ) \prod_{\substack{m = i + 1 \\ m \neq j}}^{i + k} \frac{( x_i - x_m )}{( x_j - x_m )} = f ( x_i ) - \sum_{j = i + 1}^{i + k} f ( x_j ) l_j ( x_i ) = f ( x_i ) - L_{k - 1} ( x_i ) = R_{k - 1} ( x_i ) \]
Použijeme \ref{LagrangeZbytek}:
\[ f \left[ x_i, \dots, x_{i + k} \right] \prod_{m = i + 1}^{i + k} ( x_i - x_m ) = R_{k - 1} ( x_i ) = \frac{f^{( k )} ( \xi )}{k!} \prod_{m = i}^{i + k} ( x_i - x_m ) \] \todo{Poslední produkt je 0, něco je špatně.(nejspíš by mělo být m od i+1, to však neodpovídá definici $R_n$)}
Vydělíme rovnici produktem a dostaneme tvrzení věty:
\[ f \left[ x_i, \dots, x_{i + k} \right] = \frac{f^{( k )} ( \xi )}{k!} \]
\end{proof}
\end{theorem}
\begin{proof}
\textit{(z Wikipedie: Mean value theorem (divided differences))} Postupujeme podobně, jako v důkazu \ref{LagrangeZbytek}: Vezmeme si zbytek po Lagrangeovu polynomu \(R_k\) a \(k\)–krát zderivujeme. S využitím Newtonovy formule dostaneme:
\[ R_k^{( k )} ( x ) = f^{( k )} ( x ) - L_k^{( k )} ( x ) = f^{( k )} ( x ) - f \left[ x_0, \dots, x_k \right] k! \]
Opakovaným aplikováním Rolleovy věty dostaneme existenci \(\xi\), které je kořenem \(R_k^{(k)}\). Z toho plyne:
\[0=R_k^{( k )} ( \xi )=f^{( k )} ( \xi ) - f \left[ x_0, \dots, x_k \right] k!\]
Z čehož úpravou dostaneme tvrzení věty pro nejvyšší stupeň. Pro nižší derivace bychom použili polynom nižšího stupně.
\end{proof}
\begin{remark*}
Pro \( k = 1 \) předchozí věta přechází v Lagrangeovu větu o přírůstku:
\[ f \left[ x_i, x_{i + 1} \right] = \frac{f ( x_i ) - f ( x_{i + 1} )}{x_i - x_{i - 1}} = f' ( \xi ) \]
\end{remark*}
\begin{remark*}
Tato věta se v ZS 2016/17 neobjevila.
\end{remark*}
\subsection{Hermitova-Birkhoffova interpolace}
\setcounter{define}{20}
\begin{theorem}[V prezentaci definice]
\label{HermitPolynom}
Nechť funkce \( f : \mathbbm R \rightarrow \mathbbm R \), interval \( I \subset D_f \) takový, že \( f \in \mathcal C^M ( I ) \). Buďte \( x_0, x_1, \dots, x_n \in I \) různé uzly, ve kterých známe
\[ f^{( k )} ( x_i ), \; \forall i \in \hat n^0, \; \forall k \in \hat m_i^0, \text{kde} \; m_i \in \hat M \]
Definujeme číslo
\[ N = \sum_{i = 1}^n ( m_i + 1 ) \]
Potom existuje právě jeden polynom \( H_{N - 1} ( t ) \) stupně \( N - 1 \), který splňuje
\[ H_{N - 1}^{( k )} ( x_i ) = f^{( k )} ( x_i ), \; \forall i \in \hat n^0, \; \forall k \in \hat m_i^0 \]
Tento polynom se nazývá Hermitovský interpolační polynom.
\begin{proof}\renewcommand{\qedsymbol}{}
Bez důkazu.
\end{proof}
\end{theorem}
\setcounter{define}{22}
\begin{theorem}
\label{HermitZbytek}
Nechť a \( I_x \subset D_f \) nejmenší interval takový, že \( x, x_0, x_1, \dots, x_n \in I_x \) a \( f \in \mathcal C^N ( I_x ) \). Buď \( H_{N - 1} \) Hermitovský interpolační polynom příslušící funkci \( f \) a uzlům \( x_0, x_1, \dots, x_n \). Potom existuje \( \xi \in I_x \) takové, že
\[ f ( x ) - H_{N - 1} ( x ) = \frac{f^{( N )} ( \xi )}{N!} \Omega_N ( x ) \]
kde definujeme
\[ \Omega_N ( x ) = \prod_{i = 0}^n ( x - x_i )^{m_i + 1} \]
\begin{proof}\renewcommand{\qedsymbol}{}
Bez důkazu.
\end{proof}
\end{theorem}
\subsection{Interpolace v \texorpdfstring{\( \mathbbm R^n \)}{R na n}}
\setcounter{define}{24}
\begin{remark}[Oprava chyby v prezentaci]
Mějme různé body \( \left( x_i, y_j \right), \; \forall i \in \hat n_1^0, \; \forall j \in \hat n_2^0 \) a funkci \( f ( x_i, y_j ) \). Potom můžeme definovat bazické polynomy
\[ l_i^x ( x ) = \prod_{k = 1, k \neq i}^{n_1} \frac{x - x_k}{x_i - x_k} \]
\[ l_j^y ( y ) = \prod_{k = 1, k \neq j}^{n_2} \frac{y - y_k}{y_j - y_k} \]
Lagrangeův interpolační polynom má potom tvar
\[ L_n ( x, y ) = \sum_{i = 0}^{n_1} \sum_{j = 0}^{n_2} f ( x_i, y_j ) l_i^x ( x ) l_j^y ( y ) \]
\end{remark}
