Zdrojový kód
% \wikiskriptum{NME01}
\subsection{Interpolace}
\subsubsection{Lagrangeův interpolační polynom:}
\begin{itemize}
\item [=] polynom \underline{stupně} nejvýše \underline{\(n\)} tak, že \(L_n(x_0)= y_0,\ldots,L_{n}(x_{n})=y_{n},\), kde \(x_0,\ldots,x_{n}\)\ldots jsou \underline{uzly interpolace}
\item nelze do něj přidávat další uzly \(\leftarrow\) nový výpočet
\item hodí se pro odvozování numerických vzorců a výpočty integrálů (Simpson)
\item pro mnoho uzlů nemá smysl \(\rightarrow\) nehodí se příliš k interpolaci \(\rightarrow\) vznikají funkce, které příliš oscilují protože se přizpůsobí odchylkám v bodech od správného modelu (\underline{overfitting})
\item \underline{definice:}
\begin{itemize}
\item určíme si \underline{pomocné funkce \(F_i(x), i \in \hat{n}\)} tak, že \(F_i(x_{j}) =
\begin{cases}[\langle]
1\quad & j=i \\
0\quad & j\neq i
\end{cases}
\)
\item[\(\rightarrow\)] ty spočteme ze vztahu \[
F_{i}(x)=\left.\frac{(x-x_0)\cdot\ldots\cdot(x-x_{i-1})\cdot (x-x_{i+1})\cdot\ldots\cdot (x-x_{n})}{(x_i - x_0)\cdot \ldots \cdot (x_i -x_{i-1})\cdot(x_i -x_{i+1})\cdot \ldots\cdot (x_i-x_{n})}\right\}\text{\scriptsize fundamentální polynomy}
\]
\item Lagrangeův polynom pak získáme jako LK koeficientů \(F_{i}(x)\) s koeficienty \(y_{i}\) \\
\(\implies\boxed{L_{n}(x)=\sum_{i=0}^{n} y_{i}F_i(x) = \sum_{i=0}^{n} y_i \frac{w_{n}(x)}{(x-x_{i})w_n'(x_{i})}}\), kde \underline{\(w_{n}(x)=\prod_{i=0}^{n} (x-x_{i}) \)}\\
\(\hookrightarrow \) tento process je náročný \(\sim n^2\)
\end{itemize}
\item koeficienty \(L_{n}(x)\) lze počítat řešením soustavy LAR s tzv. \underline{Vandermondovou maticí}, ale ta bývá špatně podmíněná pro ekvidistantní uzly
\item hodnotu \(L_n(x)\) lépe určíme \underline{Nevillovým algoritmem:}
\begin{itemize}
\item tzv. iterovaná interpolace \(\leftarrow\) v každém kroku vytváříme interpolace vyšších řádů
\item používáme tehdy, pokud nás \underline{nezajímají koeficienty polynomu!}
\item \(L_{i,j}\) určíme z rekurentního vztahu jako
\[
\begin{aligned}
& L_{i,i}(x)=y_{i} & i \in\underline{\hat{n}} \\
& L_{i,j}(x)=\frac{(x-x_j)L_{i,j-1}(x) - (x-x_{i})L_{i+1,j}(x)}{x_{i}-x_{j}} & 0 \le i\le j \le n
\end{aligned}
\]
\(\hookrightarrow\) nejlepší aproximace je \(L_{0,n}(x)\)\\
\(\hookrightarrow\) \underline{schéma:}
\[
\boxed{
\begin{aligned}
& L_{0,0}(x) = & y_0 \\\\\\
& L_{1,1}(x) = & y_1 \\\\\\
& L_{2,2}(x) = & y_2
\end{aligned}
\begin{aligned}
\searrow \\\\ \nearrow \\ \searrow \\\\ \nearrow
\end{aligned}
\begin{aligned}
& L_{0,1}(x) \\\\\\
& L_{1,2}(x)
\end{aligned}
\begin{aligned}
\searrow \\
\nearrow
\end{aligned}
\underline{L_{0,2}(x)\text{\scriptsize\ldots best}}
}
\]
\item Nevillův algoritmus je náročný \(\sim n^2\), ale dá se upravit, aby byl náročný pouze \(\sim n\)
\end{itemize}
\item [\underline{pozn.:}] konvergence \(L_{n}(x) \to f(x)\) je pro \(n \to \infty\) zaručena pro analytické funkce
\end{itemize}
\subsubsection{Newtonův interpolační polynom:}
\begin{itemize}
\item vychytává některé nedostatky \(L_{n}(x)\), zvláště \underline{přidávání uzlů}
\item \underline{definice:} \(\boxed{N_{n}(x) = a_0 + a_1(x-x_1)+a_2(x-x_0)(x-x_1)+\ldots+a_n(x-x_0)(x-x_1)\cdot\ldots\cdot (x-x_{n-1})}\)
\item \underline{hledání koeficientů \(a_k\):}
\begin{enumerate}[label=\roman*)]
\item nechť \(n+1\) bodů \((x_{i},y_{i}), i \in \underline{\hat{n}}\rightarrow\) aby \(N_n(x)\) procházel \(\forall\) body, musí splňovat podmínky:
\[
\begin{aligned}
& y_0 = a_0 \\
& y_1 = a_0 + a_1(x_1-x_0) \\
& y_2 = a_0 + a_1(x_2-x_0)+ a_2(x_2-x_0)(x_2-x_1) \\
& \vdots \\
& y_n = a_0 + a_1(x_n-x_0) + a_2(x_n-x_0)(x_n-x_1) + \ldots + a_n \prod_{i=0}^{n-1} (x_n-x_i)
\end{aligned}
\]
\item přepsáno do matice máme:
\[
\begin{pmatrix}
1 \\
1 & (x_1-x_0) \\
1 & (x_2-x_0) & (x_2-x_0)(x_2-x_1) \\
1 & (x_3-x_0) & (x_3-x_0)(x_3-x_1) & (x_3-x_0)(x_3-x_1)(x_3-x_2) \\
\vdots \\
1 & (x_n-x_0) & (x_n-x_0)(x_n-x_1) & (x_n-x_0)(x_n-x_1)(x_n-x_2) & \ldots & \prod_{i=0}^{n-1} (x_n-x_i)
\end{pmatrix}\cdot
\begin{pmatrix}
a_0 \\
a_1 \\
a_2 \\
a_3 \\
\vdots \\
a_n
\end{pmatrix}=
\begin{pmatrix}
y_0 \\
y_1 \\
y_2 \\
y_3 \\
\vdots \\
y_n
\end{pmatrix}
\]
\item\stackunder{řešíme seshora dolů}{\scriptsize (vyjádříme koeficienty \(a_k\))} \(\rightarrow\)
\vspace{-3em}
\[
\left.
\begin{aligned}
& a_0 = y_0 = f(x_0) & \\
& a_1 = \frac{y_1-y_0}{x_1-x_0} = f(x_0,x_1) & \\
& \vdots & \\
f(x_0,x_1,\ldots,x_k) = & a_k = \sum_{j=0}^{k} \frac{f(x_j)}{\prod_{i=0, i\neq j}^{k} (x_j-x_i) } & k \in \underline{\hat{n}}
\end{aligned}
\right\}\text{\scriptsize z definice \underline{poměrné diference}}
\]
\item[\(\implies\)] Newtonův polynom se tak dá napsat ve tvaru
\[
\boxed{N_n(x)=f(x_0)+f(x_0,x_1)(x_1-x_0) + f(x_0,x_1,x_2)(x_2-x_0)(x_2-x_1)+\ldots+f(x_0,\ldots,x_n)\prod_{i=0}^{n-1} (x_n-x_i) }
\]
\end{enumerate}
\end{itemize}
\subsubsection{Hermiteova interpolace:}
\begin{itemize}
\item kromě funkčních hodnot má zadané i některé \underline{derivace}
\end{itemize}
\subsection{Interpolační spline}
\begin{itemize}
\item jedná se o lokální interpolaci, která kromě průchodu všemi uzly \((x_{i},y_{i})\) má i \underline{spojitou alespoň 1. derivaci} \(\implies\) v každém subintervalu klademe na interpolační spline \underline{4 podmínky}: \(\underline{y_{i}},\underline{y_{i+1}},\lim_{x \to x_i^+}f'(x)=\underline{y'_{i^+}=y'_{i^-}}=\lim_{x \to x_i^-}f'(x),\underline{y'_{{i+1}^+}=y'_{{i+1}^-}}\)
\item princip splinu je rozsekat interval \(\left<a,b \right>\) na řadu menších, kde jsme už schopni funkci dobře aproximovat polynomem
\item existuje i lineární spline, ale důležitější je \underline{kubický spline}
\subsubsection{Kubický spline:}
\begin{itemize}
\item odvození kubického splinu:
\begin{enumerate}[label=\roman*)]
\item[-] máme 4 parametry, budeme aproximovat kubickou funkci
\item výchozí funkce \(y(x)=a+bx+cx^2+dx ^3\) a funkční hodnoty v krajních bodech a \\ spojité 1. derivace \(\text{\stackengine{\stackgap}{\(\implies\)}{\scriptsize \(\hookrightarrow\) \underline{požadujeme}, implikace obecně neplatí!}{U}{l}{F}{T}{\stacktype}} \exists y''(x)\)
\item \underline{provedeme derivace:}\\
\[
\begin{aligned}
y'(x)=b + 2cx + 3dx^2\quad y''(x)=2c+6dx \quad
\Rightarrow \quad\underbrace{y''_1=2c+6dx_1\quad y''_2 = 2c + 6dx_2}_{\text{krajní body}} \\
\text{\scriptsize odečteme }\rightarrow\boxed{ d = \frac{1}{6}\frac{y''_2-y''_1}{x_2-x_1} }\qquad \text{\scriptsize dosadíme zpět} \rightarrow y''_1=2c+\frac{y''_2-y''_1}{x_2-x_1} x_1 \implies \boxed{c = \frac{1}{2}\frac{x_2y''_1-x_1y''_2}{x_2-x_1}}
\end{aligned}
\]
\item z rovností lze pak získat i hodnoty \(a,b\)
\[
y_1 = a + b x_1 + c x_1^2 + d x_1^3 \quad \land \quad y_2 = a + b x_2 + c x_2^2 + d x_2^3
\]
\(\hookrightarrow\) soustava \underline{LAR o 2 neznámých \(a,b\)}
\item jak určit \underline{druhé derivace?}
\begin{itemize}
\item [\(\hookrightarrow\) ] napíšeme hledaný spline ve tvaru \(y(x) = A(x)y_1 + B(x)y_2 + C(x)y''_1 + D(x)y''_2\), kde
\[
\begin{aligned}
& A(x)=\frac{x_2-x}{x_2-x_1} \quad & C(x)=\frac{1}{6}(A^3-A)(x_2-x_1)^2 \\
& B(x)=1-A(x)=\frac{x-x_1}{x_2-x_1}\quad & D(x)=\frac{1}{6}(B^3-B)(x_2-x_1)^2
\end{aligned}\]
\item[] a derivace:
\[
\begin{aligned}
& A'(x)=\frac{-1}{x_2-x_1}\quad & C'(x) = \frac{-1}{6}(3A^2-1)(x_2-x_1) \\
& B'(x) = \frac{1}{x_2-x_1}\quad & D'(x)=\frac{1}{6}(3B^2-1)(x_2-x_1)
\end{aligned}
\]
\end{itemize}
\item dosadíme:
\[y'(x)=A'(x)y_1+B'(x)y_2+C'(x)y''_1+D'(x)y''_2 = \frac{y_2-y_1}{x_2-x_1}-\frac{1}{6}(3A^2-1)(x_2-x_1)y''_1 + \frac{1}{6}(3B^2-1)(x_2-x_1)y''_2\]
\item požadujeme spojitost derivace v bodě \(x_1\) \(\Leftrightarrow\) \(\lim_{x \to x_1^-}y'(x)=\lim_{x \to x_1^+}y'(x)\)\\
\(\hookrightarrow\) tj. dostaneme rovnici jako v bodu v), akorát tentokrát na bodech \(x_0\) a \(x_1\) \(\implies y_0'', y_1''\)
\item ze spojitosti derivací dostáváme rovnost (a po dosazení bodů \(x_0,x_1,x_2\))
\[
% TODO: a přidat komentáře <08-07-20, kunzaatko> %
\begin{aligned}
y'(x_1) & = \frac{y_2-y_1}{x_2-x_1} - \frac{1}{6}(3\overbrace{\frac{(x_2-x_1)^2}{(x_2-x_1)^2}}^{=1} - 1)(x_2-x_1)y''_1 + \frac{1}{6}(3\cdot 0 -1 )(x_2-x_1)y_2'' \\ &= \frac{y_1-y_0}{x_1-x_0} + \frac{1}{6}(x_1-x_0)y_0'' + \frac{1}{3}(x_1-x_0)y_1''\\
& \Leftrightarrow \frac{y_2-y_1}{x_2-x_1}-\frac{y_1-y_0}{x_1-x_0} = \frac{1}{3} (x_2-x_0)y_1''+ \frac{1}{6}(x_1-x_0)y_0''+ \frac{1}{6}(x_2-x_1)y_2''
\end{aligned}
\]
\(\hookrightarrow\) volbou okrajových podmínek pro kubický spline (typicky \(y_0''= y_N'' = 0\), nebo \(y''_{0} = - y''_{N}\) ) získáme soustavu s tridiagonální maticí \(\implies\) snadno už určíme zbylé \underline{\(y_i''\)}
\end{enumerate}
\end{itemize}
\end{itemize}
