01NM:Kapitola7

Z WikiSkripta FJFI ČVUT v Praze
Verze z 1. 8. 2010, 10:25, kterou vytvořil Admin (diskuse | příspěvky)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání
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 01NM

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01NMAdmin 1. 8. 201010:22
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201513:47
Header editovatHlavičkový souborKlinkjak 1. 9. 201522:49 header.tex
Kapitola1 editovatFinitní metodyAdmin 1. 8. 201010:24 kapitola1.tex
Kapitola2 editovatIterační metody řešení soustav lineárních algebraických rovnicKlinkjak 3. 9. 201519:49 kapitola2.tex
Kapitola3 editovatČástečný problém vlastních číselAdmin 1. 8. 201010:25 kapitola3.tex
Kapitola4 editovatÚplný problém vlastních číselAdmin 1. 8. 201010:25 kapitola4.tex
Kapitola5 editovatIterační metody řešení rovnice tvaru f(x)=0Admin 1. 8. 201010:25 kapitola5.tex
Kapitola6 editovatIterační metody pro řešení systémů nelineárních algebraických a transcendentních rovnicAdmin 1. 8. 201010:25 kapitola6.tex
Kapitola7 editovatLagrangeova interpolaceAdmin 1. 8. 201010:25 kapitola7.tex
Kapitola8 editovatNumerický výpočet derivaceAdmin 1. 8. 201010:25 kapitola8.tex
Kapitola9 editovatNumerický výpočet integrálu Admin 1. 8. 201010:25 kapitola9.tex

Zdrojový kód

%\wikiskriptum{01NM}
 
\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$$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'$$n+1$ vzájemně různých kořenů ležících mezi kořeny funkce $Q$. To opět znamená, že funkce $Q''$$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}