Zobrazení zdroje stránky NME01:Kapitola23

% \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 > %