diff --git a/Lectures_my/NumMet/2016/Lecture7/lecture7.tex b/Lectures_my/NumMet/2016/Lecture7/lecture7.tex index 1e5beec..e2b4626 100644 --- a/Lectures_my/NumMet/2016/Lecture7/lecture7.tex +++ b/Lectures_my/NumMet/2016/Lecture7/lecture7.tex @@ -243,10 +243,12 @@ \end{itemize} \vfill The integral can then be approximated as - \begin{equation} - I \approx \sum_{k=0}^{N \cdot M + 1} \omega_k f(x_k) - \end{equation} - with $x_k = a + (b - a) \frac{k}{N\cdot M}$\,. + \begin{align*} + I = \sum_{m=1}^{M} \int_{x_{m \cdot N}}^{x_{(m+1)\cdot N}} \mathrm{d}x\, f(x) + = \sum_{m=1}^{M} \sum_{n=0}^{N} \omega_k f(x_{m\cdot N + n}) + = \sum_{k=0}^{K = N \cdot M} \Omega_k f(x_k) + \end{align*} + with $x_k = a + (b - a) \frac{k}{K\cdot M}$\,. } \only<2->{ \resizebox{.9\textwidth}{!}{ @@ -299,15 +301,29 @@ } } \end{frame} -\begin{frame}{} - \begin{equation} - \omega_k = \begin{cases} - \frac{1}{6} & k = 0 \lor k = N \cdot M + 1\\ - \frac{4}{6} & k\,\text{even}\\ - \frac{2}{6} & k\,\text{odd} - \end{cases} - \end{equation} +\begin{frame}{(Closed) Newton-Cotes Weights and error estimates} + % + + { + \centering + \renewcommand{\arraystretch}{1.2} + \begin{tabular}{c|c|c} + $\bm{N}$ & $\bm{\omega^{(N)}_k}$ & \textbf{approx. error}\\ + \hline + $1$ & $\frac{1}{2}\, \frac{1}{2}$ & $\sim (b - a) f''(\xi)$\\ + $2$ & $\frac{1}{6}\, \frac{4}{6}\, \frac{1}{6}$ & $\sim (b - a) f^{(4)}(\xi)$\\ + $3$ & $\frac18\, \frac38\, \frac38\, \frac18$ & $\sim (b - a) f^{(4)}(\xi)$\\ + $\vdots$ & $\vdots$ & $\vdots$\\ + \end{tabular} + \renewcommand{\arraystretch}{1} + } + + Comments and observations: + \begin{itemize} + \item $\xi \in [a, b]$ + \item While numerical factors change, the approximation error scales only with an even derivative of the integrand! + \end{itemize} \end{frame} \newcommand{\eps}{\varepsilon} @@ -350,7 +366,8 @@ I & = 5.57396 \end{align*} \end{block} - \begin{block}{Entire range, 7 data points} + \vspace{-\smallskipamount} + \begin{block}<2->{Entire range, 7 data points} ~\\ \vspace{-2\bigskipamount} \begin{align*} @@ -358,7 +375,8 @@ \delta_7 & = 12.26\% \end{align*} \end{block} - \begin{block}{Two integration, 5 data points} + \vspace{-\smallskipamount} + \begin{block}<3->{Two integration, 5 data points} ~\\ \vspace{-2\bigskipamount} \begin{align*} @@ -368,6 +386,46 @@ \end{block} \end{column} \end{columns} + \only<4->{ + It is benefitial to arrange the integration intervals around known special points of the integrand! + } +\end{frame} + +\begin{frame}{Rationale for Gauss quadrature} + Given that we ended up (again) using polynomial interpolation to numerically solve a problem, + we can ask ourselves the following question:\\ + \vfill + \alert{Is there a method to numerically obtain the exact integral of a polynomial of degree $2n - 1$?} + \vfill + Carl Friedrich Gau\ss{} answered in the affirmative! +\end{frame} + +\begin{frame}{General idea} + We restrict ourselves to the interval $[a, b]$, and to integrals of the type + \begin{equation*} + I = \int_{a}^{b} \mathrm{d}x\, \omega(x) f(x) + \end{equation*} + Nomenclature: + \begin{itemize} + \item $\omega(x)$ is the weight function: $\omega(x) > 0$, integrable and has finitely many roots. + \item $p_N(x)$ is a polynomial of degree $N$ over $x$. + \item $\xi_{n}$, with $n=1,\dots,N$ are the roots of $p_N(x)$. + \end{itemize} + Orthogonality relations apply: + \begin{equation*} + \langle p_i(x), p_j(x)\rangle \equiv \int_{a}^{b} \mathrm{d}x\, \omega(x) p_i(x) p_j(x) = \delta_{ij} + \end{equation*} +\end{frame} + +\begin{frame}{General idea cont'd} + We can then approximate + \begin{equation*} + I \approx \sum_{n=1}^N \alpha_n f(\xi_n) + \end{equation*} + where the coefficients $\alpha_n$ can be determined as + \begin{equation*} + \alpha_n = \int_{a}^{b} \mathrm{d}x\, \omega(x) \prod_{m=1,n\neq m}^{N} \frac{x - \xi_n}{\xi_m - \xi_n} + \end{equation*} \end{frame} \backupbegin