01NUM1:Kapitola8: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
(Všechny věty)
(Důkaz 11)
Řádka 57: Řádka 57:
 
\[ f \left[ x_i, \dots, x_{i + k} \right] = \frac{f^{( k )} ( \xi )}{k!} \]
 
\[ f \left[ x_i, \dots, x_{i + k} \right] = \frac{f^{( k )} ( \xi )}{k!} \]
 
\begin{proof}
 
\begin{proof}
\todo{Důkaz 8.11}
+
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 ) \]
 +
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{proof}
 
\end{theorem}
 
\end{theorem}
 +
 +
\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*}
  
 
\subsection{Hermitova-Birkhoffova interpolace}
 
\subsection{Hermitova-Birkhoffova interpolace}

Verze z 30. 12. 2015, 17:00

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{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}
\todo{Důkaz 8.3}
\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}
\todo{Důkaz 8.8}
\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 \) \todo{Proč ne víc?} právě \( n + 2 \) kořenů. 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 \) právě \( n + 2 \) kořenů. 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 \) právě jeden kořen, ten 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^{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 ) \)\todo{Opravdu \( 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 ) \]
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{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*}
 
\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 \cup \{ 0 \}, \; \forall k \in \hat m_i \cup \{ 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 \cup \{ 0 \}, \; \forall k \in \hat m_i \cup \{ 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 \cup \{ 0 \}, \; \forall j \in \hat n_2 \cup \{ 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}