NME01:Kapitola8
Z WikiSkripta FJFI ČVUT v Praze
Verze z 5. 6. 2021, 16: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ě}…“)
[ 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. |
ZIP | Kompletní zdrojový kód včetně obrázků. |
Součásti dokumentu NME01
součást | akce | popis | poslední editace | soubor | |||
---|---|---|---|---|---|---|---|
Hlavní dokument | editovat | Hlavní stránka dokumentu NME01 | Kunzmart | 5. 6. 2021 | 17:33 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Kunzmart | 5. 6. 2021 | 17:59 | ||
Header | editovat | Hlavičkový soubor | Kunzmart | 5. 6. 2021 | 16:54 | header.tex | |
Kapitola1 | editovat | Reprezentace čísel v počítači | Kunzmart | 5. 6. 2021 | 16:55 | 01_reprezentace_cisel_v_pocitaci.tex | |
Kapitola2 | editovat | Chyby | Kunzmart | 5. 6. 2021 | 16:55 | 02_chyby.tex | |
Kapitola3 | editovat | Úlohy lineární algebry | Kunzmart | 5. 6. 2021 | 17:30 | 03_ulohy_lin_alg.tex | |
Kapitola4 | editovat | Řešení soustav Ax - b | Kunzmart | 5. 6. 2021 | 16:56 | 03a_reseni_soustav_Ax-b.tex | |
Kapitola5 | editovat | Vlastní čísla | Kunzmart | 5. 6. 2021 | 16:56 | 03b_vlastni_cisla.tex | |
Kapitola6 | editovat | Determinant | Kunzmart | 5. 6. 2021 | 16:57 | 03c_determinant.tex | |
Kapitola7 | editovat | Aproximace funkcí | Kunzmart | 5. 6. 2021 | 17:31 | 04_aproximace_funkci.tex | |
Kapitola8 | editovat | Interpolace | Kunzmart | 5. 6. 2021 | 16:57 | 04a_interpolace.tex | |
Kapitola9 | editovat | Čebyševova aproximace | Kunzmart | 5. 6. 2021 | 16:58 | 04b_cebysevovy_aproximace.tex | |
Kapitola10 | editovat | Metoda nejmenších čtverců | Kunzmart | 5. 6. 2021 | 16:58 | 04c_metoda_nejmensich_ctvercu.tex | |
Kapitola11 | editovat | Řešení nelineárních rovnic | Kunzmart | 5. 6. 2021 | 17:32 | 05_reseni_nelinearnich_rovnic.tex | |
Kapitola12 | editovat | Bisekce | Kunzmart | 5. 6. 2021 | 16:59 | 05a_bisekce.tex | |
Kapitola13 | editovat | Metoda sečen | Kunzmart | 5. 6. 2021 | 16:59 | 05b_metoda_secen.tex | |
Kapitola14 | editovat | Regula falsi | Kunzmart | 5. 6. 2021 | 17:00 | 05c_regula_falsi.tex | |
Kapitola15 | editovat | Metoda Newton-Raphsonova | Kunzmart | 5. 6. 2021 | 17:00 | 05d_newton_raphsonova_metoda.tex | |
Kapitola16 | editovat | Hledání kořenu polynomu | Kunzmart | 5. 6. 2021 | 17:00 | 05e_hledani_korenu_polynomu.tex | |
Kapitola17 | editovat | Mullerova metoda | Kunzmart | 5. 6. 2021 | 17:01 | 05f_mullerova_metoda.tex | |
Kapitola18 | editovat | Prostá iterace | Kunzmart | 5. 6. 2021 | 17:01 | 05g_prosta_iterace.tex | |
Kapitola19 | editovat | Metoda Newton-Raphson pro systémy rovnic | Kunzmart | 5. 6. 2021 | 17:01 | 05h_newton_raphsonova_metoda_pro_systemy_rovnic.tex | |
Kapitola20 | editovat | Hledání extrémů funkcí | Kunzmart | 5. 6. 2021 | 17:32 | 06_hledani_extremu_funkci.tex | |
Kapitola21 | editovat | Metoda zlatého řezu | Kunzmart | 5. 6. 2021 | 17:03 | 06a_metoda_zlateho_rezu.tex | |
Kapitola22 | editovat | Parabolická iterpolace | Kunzmart | 5. 6. 2021 | 17:04 | 06b_parabolicka_iterpolace.tex | |
Kapitola23 | editovat | Nelder Meadova metoda | Kunzmart | 5. 6. 2021 | 17:09 | 06c_nelder_meadova_metoda.tex | |
Kapitola24 | editovat | Gradientní metody | Kunzmart | 5. 6. 2021 | 17:09 | 06d_gradientni_metody.tex | |
Kapitola25 | editovat | Numerická integrace | Kunzmart | 5. 6. 2021 | 17:32 | 07_numericka_integrace.tex | |
Kapitola26 | editovat | Kvadraturní vzorce | Kunzmart | 5. 6. 2021 | 17:09 | 07a_kvadraturni_vzorce.tex | |
Kapitola27 | editovat | Integrály se singularitami | Kunzmart | 5. 6. 2021 | 17:10 | 07b_integraly_se_singularitami.tex | |
Kapitola28 | editovat | Gaussovy kvadratury | Kunzmart | 5. 6. 2021 | 17:20 | 07c_gaussovy_kvadratury.tex | |
Kapitola29 | editovat | Integrace Monte Carlo | Kunzmart | 5. 6. 2021 | 17:20 | 07d_integrace_monte_carlo.tex | |
Kapitola30 | editovat | Obyčejné diferenciální rovnice | Kunzmart | 5. 6. 2021 | 17:33 | 08_obycejne_diferencialni_rce.tex | |
Kapitola31 | editovat | Eulerova metoda | Kunzmart | 5. 6. 2021 | 17:21 | 08a_eulerova_metoda.tex | |
Kapitola32 | editovat | Metoda středního bodu | Kunzmart | 5. 6. 2021 | 17:21 | 08b_metoda_stredniho_bodu.tex | |
Kapitola33 | editovat | Heunova metoda | Kunzmart | 5. 6. 2021 | 17:22 | 08c_heunova_metoda.tex | |
Kapitola34 | editovat | Runge Kuttovy metody | Kunzmart | 5. 6. 2021 | 17:22 | 08d_runge_kuttovy_metody.tex | |
Kapitola35 | editovat | Metoda leap frog | Kunzmart | 5. 6. 2021 | 17:22 | 08e_metoda_leap_frog.tex | |
Kapitola36 | editovat | Metoda prediktor korektor | Kunzmart | 5. 6. 2021 | 17:22 | 08f_metoda_prediktor_korektor.tex | |
Kapitola37 | editovat | Metoda střelby | Kunzmart | 5. 6. 2021 | 17:23 | 08g_metoda_strelby.tex | |
Kapitola38 | editovat | Metoda konečných diferencí | Kunzmart | 5. 6. 2021 | 17:23 | 08h_metoda_konecnych_diferenci.tex | |
Kapitola39 | editovat | Variační metody | Kunzmart | 5. 6. 2021 | 17: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}