diff --git a/Lectures_my/NumMet/Lecture3/lecture3.tex b/Lectures_my/NumMet/Lecture3/lecture3.tex index b34fc46..f5a6dff 100644 --- a/Lectures_my/NumMet/Lecture3/lecture3.tex +++ b/Lectures_my/NumMet/Lecture3/lecture3.tex @@ -46,7 +46,7 @@ \begin{columns} \begin{column}{0.9\textwidth} \flushright%\fontspec{Trebuchet MS} - \bfseries \Huge {Introduction to \\Numerical Methods} + \bfseries \Huge {Interpolation in $D>2$\\ and Extrapolation} \end{column} \begin{column}{0.2\textwidth} %\includegraphics[width=\textwidth]{SHiP-2} @@ -58,7 +58,7 @@ \begin{columns} \begin{column}{0.6\textwidth} \flushright \vspace{-1.8em} {%\fontspec{Trebuchet MS} - \large Marcin Chrząszcz, Danny van Dyk\\\vspace{-0.1em}\small \href{mailto:mchrzasz@cern.ch}{mchrzasz@cern.ch}, \href{mailto:dany.van.dyk@gmail.com}{danny.van.dyk@gmail.com}} + \large Marcin Chrzaszcz, Danny van Dyk\\\vspace{-0.1em}\small \href{mailto:mchrzasz@cern.ch}{mchrzasz@cern.ch}, \href{mailto:dany.van.dyk@gmail.com}{danny.van.dyk@gmail.com}} \end{column} \begin{column}{0.4\textwidth} @@ -74,6 +74,20 @@ \end{frame} } +\begin{frame}{Plan for today} + \begin{itemize} + \item \alert{When does interpolation fail?}\\ + Marcin showed you how to interpolate in $D=1$. What are the pitfalls? And can we circumvent them? + \vfill + \item \alert{How to interpolate a function of $D>1$ variables?}\\ + Is there are sensible generalization of interpolation to multivariate functions? If yes, + let's apply what we learned before to $D=2$. + \vfill + \item \alert{What happens when I use my interpolation beyond the domain of data?}\\ + Why would I do that? When can I do that? How well does it work, and how can I improve it? + \end{itemize} +\end{frame} + \begin{frame}{Does interpolation always work?} \begin{block}{Weierstrass Approximation Theorem} Suppose $f$  is a continuous real-valued function defined on the real interval $[a, b]$. @@ -334,24 +348,24 @@ \end{enumerate} \end{column} \begin{column}[T]{.2\textwidth} + \begin{overlayarea}{\textwidth}{.3\textheight} \resizebox{\textwidth}{!}{ \begin{tikzpicture} - \draw[black,thick] (0,0) -- (1,0) -- (1,1) -- (0,1) -- (0,0); - \draw[black,thick] (1,0) -- (2,0) -- (2,1) -- (1,1) -- (1,0); - \draw[black,thick] (0,1) -- (1,1) -- (1,2) -- (0,2) -- (0,1); - \draw[black,thick] (1,1) -- (2,1) -- (2,2) -- (1,2) -- (1,1); + \draw[black,thick] (0,0) -- (2,0) -- (2,1) -- (0,1) -- (0,0); + \draw[black,thick] (2,0) -- (4,0) -- (4,1) -- (2,1) -- (2,0); + \draw[black,thick] (0,1) -- (2,1) -- (2,2) -- (0,2) -- (0,1); + \draw[black,thick] (2,1) -- (4,1) -- (4,2) -- (2,2) -- (2,1); \only<2->{ - \fill[gray,thick] (0,1) -- (1,1) -- (1,2) -- (0,2) -- (0,1); + \fill[gray,thick] (0,1) -- (2,1) -- (2,2) -- (0,2) -- (0,1); } \only<3->{ \fill[purple] (0,1) circle [radius=2pt]; - \fill[red] (1,1) circle [radius=2pt]; - \fill[orange] (1,2) circle [radius=2pt]; + \fill[red] (2,1) circle [radius=2pt]; + \fill[orange] (2,2) circle [radius=2pt]; \fill[Gold] (0,2) circle [radius=2pt]; } \end{tikzpicture} - \bigskip - } + }\\ \only<2->{ \resizebox{\textwidth}{!}{ \begin{tikzpicture} @@ -365,6 +379,7 @@ \end{tikzpicture} } } + \end{overlayarea} \end{column} \end{columns} \begin{enumerate} @@ -411,18 +426,18 @@ \begin{frame}[shrink]{Extrapolation Basics} In many numerical applications a common class of problems arises: - In the valuation of a function $f(x)$, we are interested in the value + Concerning a function $f(x)$ that is expensive to evaluate, we are interested in the value $f(x_0)$. However, at $x_0$ the function $f(x)$ is numerically instable, - or maybe even ill-posed.\\ \medskip + or the problem maybe even ill-posed.\\ \medskip - However, in an environment around $x_0$, $x \approx x_0 + h$, we can evaluate $f$. + Sometime there is an environment around $x_0$, $x \approx x_0 + h$, in which we can evaluate $f$. Usually, one now discusses $f(h) \equiv f(x_0 + h)$, or rather the limit $\lim_{h \to 0} f(h)$. [Note: in all generality we can map problems with - limits to either $\infty$ or a finite value to limits to $0$.]\\ \medskip + limits to either $h \to \infty$ or $h \to \text{finite value}$ onto limits $h \to 0$.]\\ \medskip Interpolation, as discussed previously, can not directly help, since $h = 0$ is not part of the domain of data points. Instead, one can take an interpolation - at finite $h > 0$, $f_\text{int}(h)$, and simply approximate $f(h = 0) \approx f_\text{int}$. + at finite $h > 0$, $f_\text{int}(h)$, and simply approximate $f(h = 0) \approx f_\text{int}(h = 0)$. This step of using the interpolation of $f$ outside the domain of data points is called \emph{extrapolation}.\\ \medskip @@ -434,8 +449,8 @@ \begin{frame}{Working example} Consider the function $\cos(x)$. Our task at hand is to estimate -$\cos(0)$ through evaluates of $\cos(h_n)$, with $h_n > 0$ but -$h_n \to 0$ with increasing $n$.\\ \medskip +$\cos(0)$ through evaluations of $\cos(h_k)$, with $h_k > 0$ but +$h_k \to 0$ with increasing $k$.\\ \medskip Let $h_k = 2^{-k}$, and construct interpolating polynomials $P_n$ that interpolate $\cos(x)$ in $\lbrace h_1, \dots, h_{n + 1}\rbrace$. \\ \medskip @@ -550,6 +565,7 @@ \begin{equation*} f(x) = \exp(-x^{-1/2}) / x^4\,,\quad\text{with}\quad \lim_{x\to 0} f(x) = 0 \end{equation*} +We use the same procedure as before: \begin{overlayarea}{\textwidth}{5cm} \begin{columns} @@ -651,10 +667,8 @@ (8, 9.77146) (9, 1.16233) }; - \addplot+[red, mark=none, domain=0:9] { 1 }; \end{axis} \end{tikzpicture} - show log of $f(x = 2^{-k})$ for $k=1$ to $10$ (with arbitrary numerical precision!) } \end{column} \end{columns} @@ -750,30 +764,48 @@ \Delta^2(p)_k & = \Delta(p)_{k + 1} - \Delta(p)_k\,. \end{align*} This could be written simpler, but in order to avoid numerical instabilities (floating point numbers!) - the version written here is preferable. + the version written here is preferable.\\ \vfill + + [This method has further applications which we will revisit next lecture.] \end{frame} \begin{frame}{Accelerating our example} - \begin{tikzpicture} - \begin{axis}[% - ymin=0.99990, - ymax=1.00010, - xlabel=$n$ - ] - \addplot[black, mark=*, only marks] coordinates { - (3, 0.99996) - (4, 1.00000) - (5, 1.00000) + \begin{columns} + \begin{column}{.5\textwidth} + \begin{center} + \begin{tikzpicture} + \node[anchor=south] (0, 0) { + \begin{tabular}{lrr} + $n$ & $p_n$ & $q_{n - 2}$\\ + 0 & 0.87758 & --- \\ + 1 & 1.06024 & --- \\ + 2 & 1.00056 & 0.999954 \\ + 3 & 0.99996 & 0.999998 \\ + 4 & 1.00000 & \dots \\ + \end{tabular} }; - \only<2->{ - \addplot[blue, mark=*, only marks] coordinates { - (3, 0.999954) - (4, 0.999998) - }; + \only<2>{ + \draw[blue,thick] (-0.40, +1.20) rectangle (+0.05, +1.55); + \draw[blue,thick] (+1.30, +1.20) rectangle (+1.90, +1.55); + \draw[draw=none, fill=blue, fill opacity=0.25] (-1.30, +1.20) rectangle (+0.05, 2.55); } - \addplot[red, mark=none, domain=0:6] { 1 }; - \end{axis} - \end{tikzpicture} + \only<3>{ + \draw[red, thick] (-0.18, +0.70) rectangle (+0.05, +1.05); + \draw[red, thick] (+1.50, +0.70) rectangle (+1.90, +1.05); + \draw[draw=none, fill=red, fill opacity=0.25] (-1.30, +0.70) rectangle (+0.05, 2.05); + } + \end{tikzpicture} + \end{center} + \end{column} + \begin{column}{.5\textwidth} + \begin{itemize} + \item compare $p_n$ with $q_{n - 2}$ to keep things fair\\ + i.e.: $p_2$ vs $q_0$, $p_3$ vs $q_1$ etc. + \item<2-> {\color{blue}$q_0(p_0, p_1, p_2)$ is competitive with $p_3$!} + \item<3-> {\color{red} $q_1(p_1, p_2, p_3)$ is competitive with $p_4$!} + \end{itemize} + \end{column} + \end{columns} \end{frame} \backupbegin