diff --git a/Lectures_my/NumMet/2016/Lecture10/lecture10.tex b/Lectures_my/NumMet/2016/Lecture10/lecture10.tex index b8aa404..9bec789 100644 --- a/Lectures_my/NumMet/2016/Lecture10/lecture10.tex +++ b/Lectures_my/NumMet/2016/Lecture10/lecture10.tex @@ -70,7 +70,7 @@ \vspace{1em} \vspace{0.5em} - \textcolor{normal text.fg!50!Comment}{Numerical Methods, \\ 07. November, 2016} + \textcolor{normal text.fg!50!Comment}{Numerical Methods, \\ 14. November, 2016} \end{center} \end{frame} } @@ -90,6 +90,7 @@ \item \alert{Specific problem of a given ODE in a boundary value problem}\\ \begin{itemize} \item How can we use our knowledge of initial value problems to solve these? + \item Can we solve these directly, w/o resorting to initial value problems? \end{itemize} \end{itemize} \end{frame} @@ -97,7 +98,10 @@ \begin{frame}{Implicit Runge-Kutta methods} \begin{itemize} \item same as before, method of stage $s$ and order $p$ - \item compare to Butcher Tableau now fully filled + \begin{equation*} + {\color{red}k_i} = f\left[x_n + c_i h, y_n + h \sum_{j} a_{i,j} {\color{red}k_j} \right] + \end{equation*} + \item compare Butcher Tableau, which is now fully populated \end{itemize} \begin{center} \renewcommand{\arraystretch}{1.2} @@ -116,11 +120,17 @@ \end{itemize} \end{frame} -\begin{frame}{Gauss-Legendre methods} +\begin{frame}{Gauss-Legendre methods \dots} + \hfill \dots a subclass of implicit Runge-Kutta methods\\ + \vfill + Revisit the integral we need: + \begin{equation*} + y_{n + 1} = y_n + {\color{red} \int_{x_n}^{x_n + h} \mathrm{d}x\, f(x, y(x))} + \end{equation*} \begin{itemize} \item reuse what we know about Gauss quadratures \item rescale the problem such that Legendre polynomials are the appropriate - orthogonal basis + orthogonal basis for $f(x, y(x))$ \item example: Gauss Legendre method of stage $2$: \end{itemize} \begin{center} @@ -133,6 +143,9 @@ \end{tabular} \renewcommand{\arraystretch}{1.0} \end{center} + \begin{itemize} + \item practical aspects of implicit Runge-Kutta methods requires a tangent + \end{itemize} \end{frame} \begin{frame}{Tangent: Fixed-point problems} @@ -158,6 +171,9 @@ \begin{equation*} || f(z^{(i+1)}) - f(z^{(i)}) || < || z^{(i + 1)} - z^{(i)} || \end{equation*} + \begin{itemize} + \item for further reading see the Banach fix-point theorem! + \end{itemize} \end{frame} \begin{frame}{Practical Aspects} @@ -181,8 +197,95 @@ \begin{frame}{Example} \begin{itemize} \item first step: Euler explicit - \item next steps: repeat Euler implicit until $| z^{(i + 1)} - z^{(i)} | < 10^{-3}$ + \item next steps: repeat Euler implicit until $| z^{(i + 1)} - z^{(i)} | < 2\cdot 10^{-3}$ \end{itemize} + + \begin{columns} + \begin{column}{.6\textwidth} + \resizebox{\textwidth}{!}{ + \begin{tikzpicture} + \begin{axis}[% + axis x line=center, + axis y line=left, + ymin=-0.40,ymax=+1.30, + xmin=+0.00,xmax=+8.50 + ] + \addplot[ + ultra thick, + gray, + mark=none, + domain=0:8.5 + ] + { exp(-0.5) }; + \addplot[ + thick, + color=ForestGreen, + mark=+, + only marks + ] + coordinates { + (1, 0.5) + (2, 0.75) + (3, 0.625) + (4, 0.6875) + (5, 0.65625) + (6, 0.671875) + (7, 0.664063) + (8, 0.667969) + (9, 0.666016) + }; + \only<2->{ + \addplot[ + thick, + color=orange, + mark=+, + only marks + ] + coordinates { + (1, 0) + (2, 1) + (3, 0) + (4, 1) + (5, 0) + (6, 1) + (7, 0) + (8, 1) + (9, 0) + }; + } + \only<3->{ + \addplot[ + thick, + color=red, + mark=+, + only marks + ] + coordinates { + (1, -0.05) + (2, +1.0525) + (3, -0.105125) + (4, +1.11038) + (5, -0.1659) + (6, +1.1742) + (7, -0.232905) + (8, 1.24455) + (9, -0.306778) + }; + } + \end{axis} + \end{tikzpicture} + } + \end{column} + \begin{column}{.4\textwidth} + \begin{itemize} + \item works {\color{ForestGreen}fine} for $f(x, y) = -y$ + \item<2-> {\color{orange}fails} for $f(x, y) = -2 y$ + \item<3-> {\color{red}fails spectacularly} + for $f(x, y) = -2.1 y$ + \end{itemize} + \end{column} + \end{columns} + \only<3->{\alert{Be careful with your starting value!}} \end{frame} \begin{frame}{Toward Boundary Problems: ODEs of order $2$} @@ -425,12 +528,162 @@ \end{frame} \begin{frame}{Example} - From Stoer/Bulirsch: + From Stoer, Bulirsch: + \begin{equation*} + w''(t) = \frac{3}{2} w^2(t) + \end{equation*} + with boundary conditions + \begin{align*} + w(0) & = 4 & w(1) & = 1 + \end{align*} + \begin{columns} + \begin{column}{.6\textwidth} + {$w'(t) = s$} + \only<1>{ + \includegraphics[width=\textwidth]{Shooting_method_trajectories} + } + \only<2->{ + \includegraphics[width=\textwidth]{Shooting_method_error} + } + \end{column} + \begin{column}{.4\textwidth} + \only<2->{ + \alert{two} solutions: + \begin{enumerate} + \item $w'(0) = -8$ + \item $w'(0) \simeq -36$. + \end{enumerate} + } + \end{column} + \end{columns} +\end{frame} + +\begin{frame}{Finite Difference Method} \begin{itemize} - \item \alert{two} solutions: $y'(a) = -8$ or $y'(a) \simeq -40$. + \item totally different approach then previous ones! + \item do not integrate the right-hand side of the ODE! + \item instead, discretize the problem (with $k = 1, \dots, K$) + \end{itemize} + \begin{align*} + x_k & = x_0 + k h & y_k &: \text{independent variables} + \end{align*} + \begin{itemize} + \item discretize the derivatives: + \end{itemize} + \begin{align*} + y'(x_k) & = \frac{y_{k + 1} - y_{k - 1}}{2 h} & + y''(x_k) & = \frac{y_{k + 1} + y_{k - 1} + 2 y_k}{h^2} & + & \dots + \end{align*} + \begin{itemize} + \item boundary value problem now boils down to solving the matrix-valued equation + \end{itemize} + \begin{equation*} + A \cdot \vec{y} = \vec{b} + \end{equation*} + \begin{itemize} + \item $A$ only depends on the ODE! + \item $y^T = (y_1, \dots, y_{K})$ + \item $b^T$ to be determined, includes boundary problem in $b_1$ and $b_{K}$ \end{itemize} \end{frame} +\begin{frame}{Finite Difference Method} + Setup: + \begin{itemize} + \item if the ODE does not depend on $x$, then the matrix $A$ can be prepared early + \item in that case, $A$ only depends on the type of differential operator acting on $y$ + \item the size $K$ of the problem can easily be adjusted at run time + \item the inverse of $A$ can be determined at compile time + \end{itemize} + $\Rightarrow$ FDMs can be implemented rather efficiently for ``easy'' differential + equations + + \vfill + + Convergence: + \begin{equation*} + |y(x_k) - y_k| \leq \frac{y^{(4)}(\xi) h^2}{24} (x_k - a) (b - x_k) + \end{equation*} + for $\xi \in [a, b]$. +\end{frame} + +\begin{frame}{Finite Difference Method} + \begin{block}{Example \hfill $K=9$, $h=1/(K+1) = 0.1$} + \begin{equation*} + y'' = 4\qquad y(0) = y_0 = -1\qquad y(1) = y_{10} = +1 + \end{equation*} + The analytic solution reads $y(x) = 2x^2 - 1$ + \begin{overlayarea}{\textwidth}{.7\textheight} + \only<1>{ + \begin{align*} + \frac{1}{h^2}\left(\begin{matrix} + -2 & +1 & 0 & \dots & 0 \\ + +1 & -2 & +1 & \ddots & \vdots \\ + 0 & +1 & \ddots & \ddots & 0 \\ + \vdots & \ddots & \ddots & \ddots & +1 \\ + 0 & \dots & 0 & +1 & -2 + \end{matrix}\right) + \cdot + \left(\begin{matrix} + y_1\\ + y_2\\ + \vdots\\ + y_{K-1}\\ + y_{K} + \end{matrix}\right) + = + \left(\begin{matrix} + 4 + \frac{1}{h^2}\\ + 4\\ + \vdots\\ + 4\\ + 4 - \frac{1}{h^2} + \end{matrix}\right) + \end{align*} + } + \only<2>{ + \resizebox{!}{.7\textheight}{ + \begin{tikzpicture} + \begin{axis}[% + axis x line=center, + axis y line=left, + ymin=-1.00,ymax=+1.00, + xmin=+0.00,xmax=+1.00, + samples=160 + ] + \addplot+[ + black, + ultra thick, + mark=none + ]{ + 2*x*x - 1 + }; + \addplot+[ + red, + thick, + mark=+, + only marks + ] coordinates{ + (0.1, -0.98) + (0.2, -0.92) + (0.3, -0.82) + (0.4, -0.68) + (0.5, -0.50) + (0.6, -0.28) + (0.7, -0.02) + (0.8, +0.28) + (0.9, +0.62) + }; + \end{axis} + \end{tikzpicture} + } + } + \end{overlayarea} + \end{block} +\end{frame} + + \backupbegin \begin{frame}\frametitle{Backup}