NME01:Kapitola24

Z WikiSkripta FJFI ČVUT v Praze
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{Gradientní metody}
\begin{itemize}
	\item \underline{odvození:}
	      \begin{enumerate}[label=\roman*)]
		      \item mějme funkci \(f(\vec{x})\) a proveďme její Taylorův rozvoj na okolí \(\vec{x}=\vec{x}_{0} \in \mathcal{U}(\vec{0})\)\ldots počáteční bod
		            \[
			            f(\vec{x}) = f(\vec{x}_{0}) + \sum_{i=1}^{r} \frac{\partial f}{\partial x_i} (\vec{x}_{0}) x_i + \frac{1}{2}\sum_{i,j=1}^{r} \frac{\partial^2 f}{\partial x_{i} \partial x_j} (\vec{x}_{0}) x_{i}x_{j} + \ldots
		            \]
		            což se dá přepsat jako
		            \[
			            f(\vec{x}) = f(\vec{x}_{0}) + (\grad(f(\vec{x}_{0})))^{\intercal}\cdot \vec{x} + \frac{1}{2}\vec{x}^{\intercal}\cdot \mathbb{H}_{\vec{x}_{0}}\cdot \vec{x},
		            \]
		            kde \(\mathbb{H}_{\vec{x}_{0}}\) je pozitivně definitní Hessova matice \(\leftarrow\) hledáme minimum (viz. MAB4)
		      \item označíme \underline{\(b\coloneqq -\grad(f(\vec{x}_{0}))\)}, \underline{\(\mathbb{A}\coloneqq \mathbb{H}_{\vec{x}_{0}}\)}
		            \[
			            f(\vec{x}) = f(\vec{x}_{0}) + \frac{1}{2}\vec{x}^{\intercal}\cdot \mathbb{A} \cdot \vec{x} - \vec{b}^{\intercal}\cdot \vec{x} \quad /\frac{\D}{\D\vec{x}}\text{\scriptsize\ \ldots\ (provedeme totální derivaci)}
		            \]
		            \(\rightarrow \grad f(\vec{x}) = 0 + \mathbb{A}\vec{x} - \vec{b} \)
		      \item protože z předpokladu hledáme minimum funkce \(\implies \underline{\grad f(\vec{x})\text{\stackon{ \(=\) }{ \(!\) }} 0}\)\\
		            \(\implies\) dostáváme \(\underline{\mathbb{A}\vec{x}=\vec{b}}\)
		      \item nyní budeme postupovat z počátečního bodu ve směru záporného \hookannotateunder{\text{gradientu}}{jdeme po směru klesání} v bodě \(\vec{x}_0 \implies \vec{s}_0 = -\grad f (\vec{x}_0)  = -\mathbb{A} \vec{x}_0 + \vec{b}\)\\
		            \(\implies\) minimum potom bude v bodě \(\underline{\vec{x}_1 = \vec{x}_0 + \delta \vec{s}_0}\)
		      \item určíme koeficient \(\delta\) z podmínky, že pro další směr musí platit kolmost gradientu v bodě \(\vec{x}_1\) a směru \(\vec{s}_0\), \\
		            \hookannotateunder{tj.}{jinak bychom nedosáhli minima} \(\underline{\left<\vec{s}_0 \mid \grad f(\vec{x}_1) \right>\text{\stackon{ \(=\) }{ \(!\) }} 0 }\)
		            \[
			            \begin{aligned}
				            \implies 0 & = \vec{s}_0^{\intercal} \cdot \grad f (\vec{x}_1) = \vec{s}_0^{\intercal}(\mathbb{A}\vec{x}_1 - \vec{b} )=                                                                                                                                                                                                                                           \\
				                       & = \vec{s}_0^{\intercal}\left(\mathbb{A}\left(\vec{x}_0 + \delta \vec{s}_0\right)-\vec{b}\right) = \vec{s}_0^{\intercal} (\underbrace{\mathbb{A}\vec{x}_0 - \vec{b}}_{= -\vec{s}_0}) + \delta \vec{s}_0^{\intercal} \mathbb{A}\vec{s}_0                                                                                                               \\
				            0          & = -\vec{s}_0^{\intercal} \vec{s}_0 + \delta \vec{s}_0^{\intercal} \mathbb{A} \vec{s}_0                                                                                                                                                 & \implies \boxed{\delta = \frac{\vec{s}_0^{\intercal}\vec{s}_0}{\vec{s}_0^{\intercal} \mathbb{A} \vec{s}_0}}
			            \end{aligned}
		            \]
		      \item pomocí \(\delta\) spočítáme nový bod \(\vec{x}_1\) a dále postupujeme ve směru nového záporného gradientu \(\underline{\vec{s}_1 = - \mathbb{A}\vec{x}_1 + \vec{b}}\)
	      \end{enumerate}
	\item tato \underline{metoda konjugovaných gradientů} bere v úvahu \underline{předchozí směry!}\\
	      \(\hookrightarrow\) tj. směr minimalizace \(\vec{s}_i\) je konjugovaný ke starému gradientu
	\item existují i způsoby, kdy jednoduše dojdeme do bodu \(\vec{x}_i\) a odtud se vydáme po největším spádu\\ \(\rightarrow\) \underline{problém pomalé konvergence!}
\end{itemize}
% TODO: figure here  <17-07-20, kunzaatko > %

Citováno z „https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=NME01:Kapitola24&oldid=8398“