01NM:Kapitola7

Z WikiSkripta FJFI ČVUT v Praze
Verze z 17. 2. 2010, 16:11, kterou vytvořil Tomas (diskuse | příspěvky) (odkaz na hlavičkovou stránku dokumentu,)

Přejít na: navigace, hledání

\section{Lagrangeova interpolace} Buď $f$ reálná funkce reálné proměnné a nechť jsou dány její hodnoty ve vzájemně různých bodech $x_0\, x_1\, \hdots\, x_n$ --- nazýváme je interpolační uzly. Našim úkolem je najít polynom $L_n$ co nejnižšího stupně tak, aby platilo $(\forall i\in\hat n_0)(L_n(x_i)=f(x_i))$. Tento polynom se nazývá Lagrangeův interpolační polynom příslušný k funkci $f$ a uzlům $x_0\, x_1\, \hdots\, x_n$. \begin{remark} Očekáváme, že je-li funkce $f$ dostatečně hladká, bude ji možno aproximovat polynomem $T_n$ i mezi interpolačními uzly. Proto také mluvíme o interpolačním polynomu. Kdybychom chtěli naopak usuzovat na hodnoty funkce $f$ vně nejmenšího intervalu obsahujícího interpolační uzly, mluvili bychom o extrapolaci. \end{remark} \begin{tvrz} \label{eajLip} Buďte $f$ reálná funkce reálné proměnné a $x_0\, x_1\, \hdots\, x_n\in D(f)$. Potom existuje právě jeden Lagrangeův interpolační polynom příslušný k funkci $f$ a uzlům $x_0\, x_1\, \hdots\, x_n$. \begin{proof} Existence: Definujme funkci \[ \Phi_i(x)=\frac{(x-x_0)(x-x_1)\hdots(x-x_{i-1})(x-x_{i+1})\hdots(x-x_n)}{(x_i-x_0)(x_i-x_1)\hdots(x_i-x_{i-1})(x_i-x_{i+1})\hdots(x_i-x_n)}. \] Zřejmě $\Phi_i$ je polynom stupně $n$ a platí $\Phi_i(x_j)=\delta_{ij}$ pro $i\, j\in\hat n_0$. Dále je zřejmé, že funkce \begin{equation} \label{Lip} L_n(x)=\sum_{i=0}^n f(x_i) \Phi_i(x) \end{equation} je polynom stupně nejvýše $n$-tého a že platí $(\forall i\in\hat n_0)(L_n(x_i)=f(x_i))$.

Jednoznačnost: Předpokládejme existenci polynomu $P_n\ne L_n$ stupně nejvýše $n$-tého takového, že $(\forall i\in\hat n_0)(P_n(x_i)=f(x_i))$. Potom funkce $P_n-L_n$ musí být také polynom stupně nejvýše $n$-tého. Přitom ale $P_n-L_n$ má $n+1$ kořenů, takže to musí být nulový polynom. \end{proof} \end{tvrz} \begin{theorem} \label{chybaomega} \begin{enumerate} \item Buď $I$ interval a nechť $x_0\, x_1\, \hdots\, x_n\in I$. \item Nechť má funkce $f$ v intervalu $I$ derivaci řádu $n+1$. \item Buď $L_n$ Lagrangeův interpolační polynom příslušný k funkci $f$ a uzlům $x_0\, x_1\, \hdots\, x_n$. \end{enumerate} Potom $\forall x\in I$ existuje bod $\xi$ ležící v nejmenším intervalu obsahujícím body $x\, x_0\, x_1\, \hdots\, x_n$ tak, že platí \[ f(x)-L_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\;\omega_n(x), \] kde $\omega_n(x)=(x-x_0)(x-x_1)\hdots(x-x_n)$. \begin{proof} Pro $x\in\{x_0\, x_1\, \hdots\, x_n\}$ je $f(x)-L_n(x)=0$, takže tvrzení zřejmě platí. Zvolme tedy pevně $x\in I$ tak, aby $(\forall i\in\hat n_0)(x\ne x_i)$. Označíme-li \[ R_n(x)=f(x)-L_n(x)\, Q(t)=\omega_n(x) R_n(t)-\omega_n(t) R_n(x), \] potom zřejmě $Q(x)=0$, a protože $(\forall i\in\hat n_0)(\omega_n(x_i)=0\, R_n(x_i)=0)$, je i $(\forall i\in\hat n_0)(Q(x_i)=0)$. Funkce $Q$ má tedy $n+2$ kořenů a to podle Rolleovy věty\footnote{Rolleova věta: Buď $f$ reálná funkce spojitá na omezeném a uzavřeném itervalu $\langle a\, b\rangle$ a nechť má $f$ v každém bodě intervalu $(a\, b)$ derivaci. Je-li $f(a)=f(b)$, potom existuje $\xi\in(a\, b)$ tak, že $f'(\xi)=0$.} znamená, že funkce $Q'$ má $n+1$ vzájemně různých kořenů ležících mezi kořeny funkce $Q$. To opět znamená, že funkce $Q$ má $n$ vzájemně různých kořenů ležících mezi kořeny funkce $Q'$ atd. Nakonec se dozvídáme, že funkce $Q^{(n+1)}$ má jeden kořen ležící mezi kořeny funkce $Q^{(n)}$. Označíme-li tento kořen $\xi$, platí tedy $Q^{(n+1)}(\xi)=0$. Podle definice funkce $R_n$ zřejmě platí \[ R_n^{(n+1)}(x)=f^{(n+1)}(x)-L_n^{(n+1)}(x)=f^{(n+1)}(x)-0=f^{(n+1)}(x), \] neboť $L_n$ je polynom stupně nejvýše $n$-tého. Podle definice funkce $\omega$ zase platí $\omega^{(n+1)}(x)=(n+1)!$, a tak \[ Q^{(n+1)}(\xi)=\omega_n(x) f_n^{(n+1)} (\xi) - R_n(x) (n+1)! = 0 \Rightarrow R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!} \;\omega_n(x). \] \end{proof} \end{theorem} Konstrukce polynomu $L_n$ podle důkazu tvrzení \ref{eajLip} není ekonomická. Ukážeme si proto dvě lepší řešení. \subsection{Newtonova interpolační formule pro neekvidistantní intervaly} \begin{define} Buďte $f$ reálná funkce reálné proměnné, $x_0\, x_1\, \hdots\, x_n\in D(f)$ (tyto body přitom nemusejí být seřazeny podle velikosti). Poměrnými diferencemi 1. řádu nazýváme podíly typu \[ f(x_0\, x_1)=\frac{f(x_1)-f(x_0)}{x_1-x_0}\, \hdots\, f(x_{n-1}\, x_n)=\frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}. \] Poměrnými diferencemi 2. řádu nazýváme výrazy \[ f(x_0\, x_1\, x_2)=\frac{f(x_1\, x_2)-f(x_0\, x_1)}{x_2-x_0}\, \hdots\, \] \[ f(x_{n-2}\, x_{n-1}\, x_n)=\frac{f(x_{n-1}\, x_n)-f(x_{n-2}\, x_{n-1})}{x_n-x_{n-2}}. \] Poměrnými diferencemi $k$-tého řádu nazýváme výrazy \[ f(x_i, \hdots\, x_{i+k})=\frac{f(x_{i+1}\, \hdots\, x_{i+k})-f(x_i\, \hdots\, x_{i+k-1})}{x_{i+k}-x_i}. \] \end{define} Poměrné diference je zvykem zapisovat do tzv. diferenčního schématu: \[ \begin{matrix} x_0 & f(x_0)\\ & & f(x_0\, x_1)\\ x_1 & f(x_1) & & f(x_0\, x_1\, x_2)\\ & & f(x_1\, x_2) & & f(x_0\, x_1\, x_2\, x_3)\\ x_2 & f(x_2) & & f(x_1\, x_2\, x_3)\\ & & f(x_2\, x_3)\\ x_3 & f(x_3) & &\\ \vdots & \vdots & \vdots & \vdots & \vdots\\ x_{n-3} & f(x_{n-3}) & & \\ & & f(x_{n-3}\, x_{n-2})\\ x_{n-2} & f(x_{n-2}) & & f(x_{n-3}\, x_{n-2}\, x_{n-1})\\ & & f(x_{n-2}\, x_{n-1}) & & f(x_{n-3}\, x_{n-2}\, x_{n-1}\, x_n)\\ x_{n-1} & f(x_{n-1}) & & f(x_{n-2}\, x_{n-1}\, x_n)\\ & & f(x_{n-1}\, x_n)\\ x_n & f(x_n) \end{matrix} \] \begin{tvrz} \label{pomdif} Pro poměrnou diferenci $k$-tého řádu platí \[ f(x_i\, x_{i+1}\, \hdots\, x_{i+k})=\frac{f(x_i)}{(x_i-x_{i+1})\hdots(x_i-x_{i+k})}+ \] \[ +\frac{f(x_{i+1})}{(x_{i+1}-x_i)(x_{i+1}-x_{i+2})\hdots(x_{i+1}-x_{i+k})}+\hdots+\frac{f(x_{i+k})}{(x_{i+k}-x_i)\hdots(x_{i+k}-x_{i+k-1})}. \] \begin{proof} Indukcí podle $k$: Pro $k=1$ je \[ f(x_i\, x_{i+1})=\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}. \] Předpokládejme, že tvrzení platí pro $k-1$. Dokážeme, že platí pro $k$: \[ f(x_i, x_{i+1}\, \hdots\, x_{i+k})=\frac{f(x_{i+1}\, \hdots\, x_{i+k})-f(x_i\, \hdots\, x_{i+k-1})}{x_{i+k}-x_i}\stackrel{\text{IP}}{=} \] \[ \stackrel{\text{IP}}{=}\frac{1}{x_{i+k}-x_i} \left [\frac{f(x_{i+1})}{(x_{i+1}-x_{i+2})\hdots(x_{i+1}-x_{i+k})}+\hdots+\right. \] \[ +\frac{f(x_{i+k-1})}{(x_{i+k-1}-x_{i+1})\hdots(x_{i+k-1}-x_{i+k-2})(x_{i+k-1}-x_{i+k})}+\frac{f(x_{i+k})}{(x_{i+k}-x_{i+1})\hdots(x_{i+k}-x_{i+k-1})}- \] \[ -\frac{f(x_i)}{(x_i-x_{i+1})\hdots(x_i-x_{i+k-1})}-\frac{f(x_{i+1})}{(x_{i+1}-x_i)(x_{i+1}-x_{i+2})\hdots(x_{i+1}-x_{i+k-1})}- \] \[ \left. -\hdots-\frac{f(x_{i+k-1})}{(x_{i+k-1}-x_i)\hdots(x_{i+k-1}-x_{i+k-2})}\right ]. \] V lomených závorkách se vyskytují rozdíly typu\footnote{Dále pro stručnost nebudeme zdůrazňovat, že nulové členy ve jmenovatelích jsou vynechány, takže např. místo $(x_j-x_i)\hdots(x_j-x_{j-1})(x_j-x_{j+1})\hdots(x_j-x_{j+k})$ budeme psát jen \linebreak[4]$(x_j-x_i)\hdots(x_j-x_{i+k})$.} \[ \frac{f(x_j)}{(x_j-x_{i+1})\hdots(x_j-x_{i+k})}-\frac{f(x_j)}{(x_j-x_i)\hdots(x_j-x_{i+k-1})}. \] Pro tyto dvojice platí \[ \frac{1}{x_{i+k}-x_i} \left [ \frac{f(x_j)}{(x_j-x_{i+1})\hdots(x_j-x_{i+k})}-\frac{f(x_j)}{(x_j-x_i)\hdots(x_j-x_{i+k-1})}\right ]= \] \[

\frac{f(x_j)}{(x_j-x_{i+1})\hdots(x_j-x_{i+k-1})}\cdot\frac{1}{x_{i+k}-x_i}\cdot\left [ \frac{1}{x_j-x_{i+k}}-\frac{1}{x_j-x_i}\right ]

\] \[

\frac{f(x_j)}{(x_j-x_{i+1})\hdots(x_j-x_{i+k-1})}\cdot\frac{1}{x_{i+k}-x_i}\cdot\frac{(x_j-x_i)-(x_j-x_{i+k})}{(x_j-x_{i+k})(x_j-x_i)}

\] \[ =\frac{f(x_j)}{(x_j-x_i)\hdots(x_j-x_{i+k})}\cdot\frac{x_{i+k}-x_i}{x_{i+k}-x_i}=\frac{f(x_j)}{(x_j-x_i)\hdots(x_j-x_{i+k})}. \] \end{proof} \end{tvrz} \begin{dusl} \begin{enumerate} \item Poměrná diference součtu/rozdílu je součet/rozdíl odpovídajících poměrných diferencí. \item Poměrná diference funkce $\alpha f$, kde $\alpha$ je konstanta, je rovna $\alpha$-násobku poměrné diference funkce $f$. \item Poměrná diference je symetrická vůči všem svým proměnným, tj. skutečně nezáleží na pořadí uzlů. \item Poměrná diference $k$-tého řádu funkce $f(x)=x^n$ je homogenní forma (viz dále) stupně $n-k$ ve svých proměnných. \end{enumerate} \begin{proof} Dokážeme bod 4. Ještě předtím si ale vysvětlíme, co je to forma.

Polynom je součet sčítanců tvaru $ax_1^{k_1}x_2^{k_2}\hdots x_n^{k_n}$. Číslo $k_1+k_2+\hdots+k_n$ se nazývá stupeň sčítance. Polynom, jehož všechny sčítance mají stejný stupeň, se nazývá forma.

Máme tedy dokázat, že $f(x_i\, \hdots\, x_{i+k})=\sum x_i^{\alpha_0} x_{i+1}^{\alpha_1} \hdots x_{i+k}^{\alpha_k}$, kde suma je přes všechny $(k+1)$-tice $(\alpha_0\, \alpha_1\, \hdots\, \alpha_k)$, pro které platí $\alpha_0+\alpha_1+\hdots+\alpha_k=n-k$. Důkaz provedeme indukcí podle $k$. Pro $k=1$ je \[ f(x_i, x_{i+1})=\frac{x_{i+1}^n-x_i^n}{x_{i+1}-x_i}=x_{i+1}^{n-1}+x_{i+1}^{n-2}x_i+\hdots+x_i^{n-1}. \] Předpokládejme nyní, že tvrzení platí pro $k$. Dokážeme, že platí i pro $k+1$: \[ f(x_i, x_{i+1}\, \hdots\, x_{i+k}\, x_{i+k+1})=\frac{f(x_{i+1}\, \hdots\, x_{i+k}\, x_{i+k+1})-f(x_i\, x_{i+1}\, \hdots\, x_{i+k})}{x_{i+k+1}-x_i}= \] \[

\frac{f(x_{i+k+1}\, x_{i+1}\, \hdots\, x_{i+k})-f(x_i\, x_{i+1}\, \hdots\, x_{i+k})}{x_{i+k+1}-x_i}

\] \[ =\sum x_{i+1}^{\alpha_1} \hdots x_{i+k}^{\alpha_k}\cdot\frac{x_{i+k+1}^{\alpha_0}-x_i^{\alpha_0}}{x_{i+k+1}-x_i}=\sum x_{i+1}^{\alpha_1} \hdots x_{i+k}^{\alpha_k} (x_{i+k+1}^{\alpha_0-1} + x_{i+k+1}^{\alpha_0-2} x_i + \hdots + x_i^{\alpha_0-1}). \] Sumy jsou opět přes všechna $\alpha_j\, j\in\hat k_0$, taková, že $\alpha_0+\alpha_1+\hdots+\alpha_k=n-k$. \end{proof} \end{dusl} \begin{remark} Z bodu 4 v předchozím tvrzení vyplývá, že $n$-tá poměrná diference funkce $x\mapsto x^n$ je konstanta a vyšší poměrné diference této funkce jsou rovny nule. Totéž zřejmě platí pro polynom stupně $n$. \end{remark} Nyní můžeme přikročit ke konstrukci Lagrangeova interpolačního polynomu. Nechť je dána funkce $f$ a uzly $x_0\, x_1\, \hdots\, x_n$. Pro $n\ge 1$ můžeme psát \[ L_n=L_0+(L_1-L_0)+(L_2-L_1)+\hdots+(L_n-L_{n-1}). \] Protože $L_k-L_{k-1}$ je polynom stupně nejvýše $k$-tého a uzly $x_0\, x_1\, x_{k-1}$ musejí být jeho kořeny, znamená to, že \[ L_k(x)-L_{k-1}(x)=A(x-x_0)(x-x_1)\hdots(x-x_{k-1}), \] kde $A$ je konstanta. Uvážíme-li, že $L_k(x_k)=f(x_k)$, plyne z předchozího vztahu \begin{equation} \label{konstA} f(x_k)-L_{k-1}(x_k)=A(x_k-x_0)(x_k-x_1)\hdots(x_k-x_{k-1}), \end{equation} takže pro konstantu $A$ s použitím důkazu tvrzení \ref{eajLip} dostáváme \[ A=\frac{f(x_k)}{(x_k-x_0)\hdots(x_k-x_{k-1})}-\frac{\sum_{j=0}^{k-1} f(x_j)\frac{(x_k-x_0)\hdots(x_k-x_{j-1})(x_k-x_{j+1})\hdots(x_k-x_{k-1})}{(x_j-x_0)\hdots(x_j-x_{j-1})(x_j-x_{j+1})\hdots(x_j-x_{k-1})}}{(x_k-x_0)\hdots(x_k-x_{k-1})}= \] \[

\frac{f(x_k)}{(x_k-x_0)\hdots(x_k-x_{k-1})}-\sum_{j=0}^{k-1} \frac{f(x_j)}{(x_j-x_0)\hdots(x_j-x_{j-1})(x_j-x_{j+1})\hdots(x_j-x_{k-1})(x_k-x_j)}

\] \[ =\sum_{j=0}^k \frac{f(x_j)}{(x_j-x_0)\hdots(x_j-x_{j-1})(x_j-x_{j+1})\hdots(x_j-x_k)}=f(x_0\, x_1\, \hdots\, x_k). \] Protože zřejmě $L_0(x)\equiv f(x_0)$, plyne z předchozích vztahů ihned \begin{equation} \label{Lagpol} \begin{array}{c} L_n(x)=f(x_0)+(x-x_0) f(x_0\, x_1)+(x-x_0)(x-x_1) f(x_0\, x_1\, x_2)+\hdots+\\ +(x-x_0)(x-x_1)\hdots(x-x_{n-1}) f(x_0\, x_1\, \hdots\, x_n). \end{array} \end{equation} \begin{remark} V praxi vycházíme z diferenčního schématu. Stačí z něj ovšem spočítat jen $f(x_0)\, f(x_0\, x_1)\, \hdots\, f(x_0\, \hdots, x_n)$. \end{remark} Na závěr se vraťme k větě \ref{chybaomega}. Buď $(\forall j\in\hat n_0)(x\ne x_j)$. Potom podle tvrzení \ref{pomdif} platí \[ f(x\, x_0\, \hdots\, x_n)=\frac{f(x)}{(x-x_0)\hdots(x-x_n)}+ \] \[ +\sum_{j=0}^n \frac{f(x_j)}{(x_j-x)(x_j-x_0)\hdots(x_j-x_{j-1})(x_j-x_{j+1})\hdots(x_j-x_n)}, \] odkud s použitím důkazu tvrzení \ref{eajLip} plyne \[ f(x)=(x-x_0)\hdots(x-x_n)\; f(x\, x_0\, \hdots\, x_n)- \] \[ -\sum_{j=0}^n f(x_j)\;\frac{(x-x_0)\hdots(x-x_n)}{(x_j-x)(x_j-x_0)\hdots(x_j-x_{j-1})(x_j-x_{j+1})\hdots(x_j-x_n)}= \] \[

\omega_n(x)f(x\, x_0\, \hdots\, x_n)+\sum_{j=0}^n f(x_j)\;\frac{(x-x_0)\hdots(x-x_{j-1})(x-x_{j+1})\hdots(x-x_n)}{(x_j-x_0)\hdots(x_j-x_{j-1})(x_j-x_{j+1})\hdots(x_j-x_n)}

\] \[ =\omega_n(x)f(x\, x_0\, \hdots\, x_n)+\sum_{j=0}^n f(x_j)\Phi_j(x)=\omega_n(x)f(x\, x_0\, \hdots\, x_n)+L_n(x). \] Je tedy $f(x)-L_n(x)=\omega_n(x) f(x\, x_0\, \hdots\, x_n)$. Porovnáním tohoto výrazu s výrazem ve zmiňované větě \ref{chybaomega} zjistíme, že platí \[ f(x\, x_0\, \hdots\, x_n)=\frac{f^{(n+1)} (\xi)}{(n+1)!}, \] odkud po přeindexování $x\rightarrow x_i\, x_0\rightarrow x_{i+1}\, \hdots\, x_{n-1}\rightarrow x_{i+k}$ dostaneme \begin{equation} \label{katanaksi} f(x_i\, x_{i+1}\, \hdots\, x_{i+k})=\frac{f^{(k)} (\xi)}{k!}. \end{equation} \subsection{Newtonova interpolační formule pro ekvidistantní intervaly} $ $

Buďte $x_0\in\mathbbm R$, $h\in\mathbbm{R}^{+}$. Potom $\forall i\in\mathbbm Z$ definujeme \begin{equation} \label{uzly} x_i=x_0+ih\, f_i=f(x_i). \end{equation} \begin{define} Konečnými diferencemi 1. řádu nazýváme výrazy \[ \hdots\, \kdz{3}{1}=f_{-1}-f_{-2}\, \kdz{1}{1}=f_0-f_{-1}\, \kd{1}{1}=f_1-f_0\, \kd{3}{1}=f_2-f_1\, \hdots \] Konečnými diferencemi 2. řádu nazýváme výrazy \[ \hdots\, f_{-2}^2=\kdz{3}{1}-\kdz{5}{1}\, f_{-1}^2=\kdz{1}{1}-\kdz{3}{1}\, f_0^2=\kd{1}{1}-\kdz{1}{1}\, f_1^2=\kd{3}{1}-\kd{1}{1}, f_2^2=\kd{5}{1}-\kd{3}{1}\, \hdots \] Konečnými diferencemi $k$-tého řádu nazýváme výrazy \[ f_i^k=f_{i+\frac{1}{2}}^{k-1}-f_{i-\frac{1}{2}}^{k-1}. \] \end{define} \begin{remark} Zjednodušené značení: \[ \begin{array}{lcll} \text{diference vpřed v $i$-tém uzlu} & \Delta f_i &=& f_{i+1}-f_i,\\ \text{diference vzad v $(i+1)$-ním uzlu} & \nabla f_{i+1} &=& f_{i+1}-f_i,\\ \text{symetrická diference} & \delta f_{i+\frac{1}{2}} &=& f_{i+1}-f_i.\\ \end{array} \] \end{remark} \begin{remark} Diferenční schéma: \[ \begin{matrix} \hdots\\ f_{-3}\\ & \kdz{5}{1}\\ f_{-2} & & f_{-2}^2\\ & \kdz{3}{1} & & \kdz{3}{3}\\ f_{-1} & & f_{-1}^2 & & f_{-1}^4\\ & \kdz{1}{1} & & \kdz{1}{3} & & \kdz{1}{5}\\ f_{0} & & f_0^2 & & f_0^4 & & f_0^6\\ & \kd{1}{1} & & \kd{1}{3} & & \kd{1}{5}\\ f_{1} & & f_1^2 & & f_1^4\\ & \kd{3}{1} & & \kd{3}{3}\\ f_{2} & & f_2^2\\ & \kd{5}{1}\\ f_{3}\\ \hdots \end{matrix} \] \end{remark} \begin{tvrz}[nerekurzivní vyjádření $f_i^k$] Platí \[ f_i^k=\kcislo{k}{0}f_{i+\frac{k}{2}}-\kcislo{k}{1}f_{i-1+\frac{k}{2}}+\kcislo{k}{2} f_{i-2+\frac{k}{2}}-\hdots+ \] \[ +(-1)^{k-1}\kcislo{k}{k-1}f_{i+1-\frac{k}{2}}+(-1)^k\kcislo{k}{k}f_{i-\frac{k}{2}}. \] \begin{proof}[Náznak důkazu] \[ \begin{array}{cll} f_{i+\frac{1}{2}}^1 &=& f_{i+1}-f_i,\\ f_i^2 &=& f_{i+\frac{1}{2}}^1-f_{i-\frac{1}{2}}^1=(f_{i+1}-f_i)-(f_i-f_{i-1})=f_{i+1}-2f_i+f_{i-1},\\ f_{i+\frac{1}{2}}^3 &=& f_{i+1}^2-f_i^2=(f_{i+2}-2f_{i+1}+f_i)-(f_{i+1}-2f_i+f_{i-1})=\\ &=& f_{i+2}-3f_{i+1}+3f_i-f_{i-1}. \end{array} \] \end{proof} \end{tvrz} \begin{dusl} \begin{enumerate} \item $f=\phi\pm\psi \Rightarrow f_i^k=\phi_i^k\pm\psi_i^k$, \item $(\alpha f)_i^k=\alpha f_i^k$. \end{enumerate} \end{dusl} \begin{tvrz}[,,to neni přímo důsledek"] \label{pomakon} \[ f(x_i\, x_{i+1}\, \hdots\, x_{i+k})=\frac{f_{i+\frac{k}{2}}^k}{k!\;h^k} \] \begin{proof} \[ f(x_i\, x_{i+1})=\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}=\frac{f_{i+1}-f_i}{h}=\frac{f_{i+\frac{1}{2}}^1}{h}, \] \[ f(x_i\, x_{i+1}\, x_{i+2})=\frac{f(x_{i+1}\, x_{i+2})-f(x_i\, x_{i+1})}{x_{i+2}-x_i}=\frac{1}{2h}\left(\frac{f_{i+\frac{3}{2}}^1}{h}-\frac{f_{i+\frac{1}{2}}^1}{h}\right)=\frac{f_{i+1}^2}{2h^2}. \] \end{proof} \end{tvrz} \begin{dusl} Pro polynom $n$-tého řádu je $n$-tá konečná diference konstanta a konečné diference vyšších řádů jsou nulové. \end{dusl} \subsubsection{Newtonova interpolační formule pro ekvidistantní intervaly pro interpolaci vpřed} Sloučíme vzorce (\ref{Lagpol}) a (\ref{uzly}). \begin{enumerate} \item Zavedeme substituci $t=\frac{x-x_0}{h}$: \[ \left. \begin{matrix} x=x_0+th\\ x_i=x_0+ih \end{matrix} \right \} x-x_i=h(t-i). \] \item Poměrné diference nahradíme podle tvrzení \ref{pomakon} konečnými: \[ L_n(x_0+th)=f_0+t\kd{1}{1}+\frac{t(t-1)}{2!}f_1^2+\frac{t(t-1)(t-2)}{3!}\kd{3}{3}+\hdots+\frac{t(t-1)\hdots(t-n+1)}{n!}\kd{n}{n}. \] ,,Dá se to přepsat elegantně --- já to nevyžaduju": \[ L_n(x_0+th)=f_0+\kcislo{t}{1} \Delta f_0+\kcislo{t}{2} \Delta^2 f_0+\hdots+\kcislo{t}{n} \Delta^n f_0. \] \end{enumerate} \subsubsection{Newtonova interpolační formule pro ekvidistantní intervaly pro interpolaci vzad} Proměnné ve vzorci (\ref{Lagpol}) přeindexujeme takto: $x_i\rightarrow x_{-i}\; (i\in\hat n)$. \begin{enumerate} \item Zavedeme substituci $t=\frac{x-x_0}{h}$: \[ \left. \begin{matrix} x=x_0+th\\ x_{-i}=x_0-ih \end{matrix} \right \} x-x_{-i}=h(t+i). \] \item Poměrné diference nahradíme konečnými: \[ L_n(x_0+th)=f_0+t\kdz{1}{1}+\frac{t(t+1)}{2!}f_{-1}^2+\frac{t(t+1)(t+2)}{3!}\kdz{3}{3}+\hdots+\frac{t(t+1)\hdots(t+n-1)}{n!}\kdz{n}{n}. \] ,,Trošku elegantnější je to s tim nabla": \[ L_n(x_0+th)=f_0+\kcislo{t}{1} \nabla f_0+\kcislo{t+1}{2} \nabla^2 f_0+\hdots+\kcislo{t+n-1}{n} \nabla^n f_0. \] \end{enumerate}


% následující řádky upravují pouze zobrazení stránky na wiki na obsah dokumentu nemají vliv - prosím neměnit ! %\parentlatexfile{01NMskriptum} %\usewikiobsah{01NM:Obsah} %\parentlatexpreamble{01NM:Preamble} .................................. odkaz na hlavičkovou stránku dokumentu, jehož vložení umožní překlad částečného pdf, tj. pdf, které vznikne pouze z této stránky