NME01:Kapitola8

Z WikiSkripta FJFI ČVUT v Praze
Verze z 5. 6. 2021, 15:57, kterou vytvořil Kunzmart (diskuse | příspěvky) (Založena nová stránka s textem „% \wikiskriptum{NME01} \subsection{Interpolace} \subsubsection{Lagrangeův interpolační polynom:} \begin{itemize} \item [=] polynom \underline{stupně}…“)

(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 NME01

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu NME01Kunzmart 5. 6. 202116:33
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůKunzmart 5. 6. 202116:59
Header editovatHlavičkový souborKunzmart 5. 6. 202115:54 header.tex
Kapitola1 editovatReprezentace čísel v počítačiKunzmart 5. 6. 202115:55 01_reprezentace_cisel_v_pocitaci.tex
Kapitola2 editovatChybyKunzmart 5. 6. 202115:55 02_chyby.tex
Kapitola3 editovatÚlohy lineární algebryKunzmart 5. 6. 202116:30 03_ulohy_lin_alg.tex
Kapitola4 editovatŘešení soustav Ax - bKunzmart 5. 6. 202115:56 03a_reseni_soustav_Ax-b.tex
Kapitola5 editovatVlastní číslaKunzmart 5. 6. 202115:56 03b_vlastni_cisla.tex
Kapitola6 editovatDeterminantKunzmart 5. 6. 202115:57 03c_determinant.tex
Kapitola7 editovatAproximace funkcíKunzmart 5. 6. 202116:31 04_aproximace_funkci.tex
Kapitola8 editovatInterpolaceKunzmart 5. 6. 202115:57 04a_interpolace.tex
Kapitola9 editovatČebyševova aproximaceKunzmart 5. 6. 202115:58 04b_cebysevovy_aproximace.tex
Kapitola10 editovatMetoda nejmenších čtvercůKunzmart 5. 6. 202115:58 04c_metoda_nejmensich_ctvercu.tex
Kapitola11 editovatŘešení nelineárních rovnicKunzmart 5. 6. 202116:32 05_reseni_nelinearnich_rovnic.tex
Kapitola12 editovatBisekceKunzmart 5. 6. 202115:59 05a_bisekce.tex
Kapitola13 editovatMetoda sečenKunzmart 5. 6. 202115:59 05b_metoda_secen.tex
Kapitola14 editovatRegula falsiKunzmart 5. 6. 202116:00 05c_regula_falsi.tex
Kapitola15 editovatMetoda Newton-RaphsonovaKunzmart 5. 6. 202116:00 05d_newton_raphsonova_metoda.tex
Kapitola16 editovatHledání kořenu polynomuKunzmart 5. 6. 202116:00 05e_hledani_korenu_polynomu.tex
Kapitola17 editovatMullerova metodaKunzmart 5. 6. 202116:01 05f_mullerova_metoda.tex
Kapitola18 editovatProstá iteraceKunzmart 5. 6. 202116:01 05g_prosta_iterace.tex
Kapitola19 editovatMetoda Newton-Raphson pro systémy rovnicKunzmart 5. 6. 202116:01 05h_newton_raphsonova_metoda_pro_systemy_rovnic.tex
Kapitola20 editovatHledání extrémů funkcíKunzmart 5. 6. 202116:32 06_hledani_extremu_funkci.tex
Kapitola21 editovatMetoda zlatého řezuKunzmart 5. 6. 202116:03 06a_metoda_zlateho_rezu.tex
Kapitola22 editovatParabolická iterpolaceKunzmart 5. 6. 202116:04 06b_parabolicka_iterpolace.tex
Kapitola23 editovatNelder Meadova metodaKunzmart 5. 6. 202116:09 06c_nelder_meadova_metoda.tex
Kapitola24 editovatGradientní metodyKunzmart 5. 6. 202116:09 06d_gradientni_metody.tex
Kapitola25 editovatNumerická integraceKunzmart 5. 6. 202116:32 07_numericka_integrace.tex
Kapitola26 editovatKvadraturní vzorceKunzmart 5. 6. 202116:09 07a_kvadraturni_vzorce.tex
Kapitola27 editovatIntegrály se singularitamiKunzmart 5. 6. 202116:10 07b_integraly_se_singularitami.tex
Kapitola28 editovatGaussovy kvadraturyKunzmart 5. 6. 202116:20 07c_gaussovy_kvadratury.tex
Kapitola29 editovatIntegrace Monte CarloKunzmart 5. 6. 202116:20 07d_integrace_monte_carlo.tex
Kapitola30 editovatObyčejné diferenciální rovniceKunzmart 5. 6. 202116:33 08_obycejne_diferencialni_rce.tex
Kapitola31 editovatEulerova metodaKunzmart 5. 6. 202116:21 08a_eulerova_metoda.tex
Kapitola32 editovatMetoda středního boduKunzmart 5. 6. 202116:21 08b_metoda_stredniho_bodu.tex
Kapitola33 editovatHeunova metodaKunzmart 5. 6. 202116:22 08c_heunova_metoda.tex
Kapitola34 editovatRunge Kuttovy metodyKunzmart 5. 6. 202116:22 08d_runge_kuttovy_metody.tex
Kapitola35 editovatMetoda leap frogKunzmart 5. 6. 202116:22 08e_metoda_leap_frog.tex
Kapitola36 editovatMetoda prediktor korektorKunzmart 5. 6. 202116:22 08f_metoda_prediktor_korektor.tex
Kapitola37 editovatMetoda střelbyKunzmart 5. 6. 202116:23 08g_metoda_strelby.tex
Kapitola38 editovatMetoda konečných diferencíKunzmart 5. 6. 202116:23 08h_metoda_konecnych_diferenci.tex
Kapitola39 editovatVariační metodyKunzmart 5. 6. 202116:23 08i_variacni_metody.tex

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}