\documentclass[a4paper]{article}
\usepackage{amsmath,amsthm,amsfonts}
\usepackage{amssymb}
\usepackage[utf8]{inputenc}

\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{caption}
\usepackage{euscript}
\usepackage{units}
\usepackage{enumitem}
\usepackage[bookmarks=true,hidelinks]{hyperref}
\usepackage{cleveref}
\usepackage{bbm}
\usepackage{thmtools}
\usepackage{bm}
\usepackage{xcolor}
\usepackage{tikz}
\usepackage{mdframed}
\usepackage{titling}	% For titlingpage
\renewcommand*{\thefootnote}{\fnsymbol{footnote}}	% Use symbols for footnotes

\newtheorem*{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem*{remark}{Remark}
\newtheorem*{example}{Example}


\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\eps} {\varepsilon}
\renewcommand{\phi}{\varphi}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\renewcommand{\P}{\mathbb{P}}
\DeclareMathOperator{\sgn}{sgn}
\newcommand{\ind}{\mathbbm{1}} 
\newcommand{\ip}[2]{\langle#1,#2\rangle}


\newcommand{\update}[1]{{\textcolor{red}{#1}}}

\newlist{problems}{enumerate}{3}
\setlist[problems,1]{label=\textbf{Problem \arabic*.},ref=\arabic*,align=left}
\setlist[problems,2]{label=(\alph*)}
\setlist[problems,3]{label=(\roman*)}

\usepackage{mdframed}
\usepackage{environ}
\definecolor{light-blue}{rgb}{0.95,0.95,1}


\begin{document}


\begin{titlingpage}
    \vspace*{-8em}
    \setlength{\parskip}{1.5ex plus 0.5ex minus 0.2ex}
    \setlength{\parindent}{0pt}

    \begin{flushright}
        \small\today
    \end{flushright}

    \begin{center}
        \vspace{2em}
        {
            \bfseries\sffamily\huge
            MAT3110 -- Introduction to numerical analysis
        }
        \vskip0.2ex
        \Large
        Mandatory assignment 1 of 2
        \vskip1ex
    \end{center}

    \subsubsection*{Submission deadline}
    Thursday 24 September 2020 at 14:30 in Canvas
    (\href{https://canvas.uio.no}{\underline{canvas.uio.no}}).

    \subsubsection*{Instructions}
    Bachelor students can choose between scanning handwritten notes or use \LaTeX. Master students are required to use \LaTeX.
    The assignment must be submitted as a single PDF file.
    Scanned pages must be clearly legible; please use either the ``Color'' or ``Grayscale'' settings, not ``Black and white''.
    The submission must contain your name, course and assignment number.

    It is expected that you give a clear presentation with all necessary explanations.
    Remember to include all relevant plots and figures.
Students who fail the assignment, but have shown that they have made a genuine attempt at solving the exercises, are given a second attempt at revising their answers.
    All aids, including collaboration, are allowed, but the submission must be written by you and reflect your understanding of the subject.
    If we doubt that you have understood the content you have handed in, we may request that you give an oral account.

    In exercises where you are asked to write a computer program, you need to hand in the code along with the rest of the assignment.

    \subsubsection*{Application for postponed delivery}
    If you need to apply for a postponement of the submission deadline due to illness or other reasons, you \textbf{have to} contact the student administration at the Department of Mathematics (e-mail: \href{mailto:studieinfo@math.uio.no}{studieinfo@math.uio.no}) well before the deadline.

    All mandatory assignments in this course must be approved in the same semester, before you are allowed to take the final examination.

    \subsubsection*{Complete guidelines for delivery of mandatory assignments:}
        \texttt{\href{/english/studies/examinations/compulsory-activities/mn-math-mandatory.html}
        {
            \resizebox{\textwidth}{!}
            {\underline{www.uio.no/english/studies/examinations/compulsory-activities/mn-math-mandatory.html}}
        }}
\end{titlingpage}



\mdfdefinestyle{MyFrame}{%
    outerlinewidth=4pt,
    innertopmargin=\baselineskip,
    innerbottommargin=\baselineskip,
    innerrightmargin=20pt,
    innerleftmargin=20pt,
    backgroundcolor=red!10!white}
    
\begin{mdframed}[style=MyFrame]
\begin{center}
\textbf{Note:} You will find a list of hints on page \pageref{p:hintsstart}.%--\pageref{p:hintsend}.
\end{center}
\end{mdframed}

\noindent
\textbf{Grading:} To get your submission approved, you need to show that you have tried to solve every exercise, and have solved about $\unitfrac23$ of the problems correctly. Problems 1--3(c) are weighted by $10\%$ each, and 3(d) and 3(e) by $20\%$ each.


\begin{problems}
\item\label{prop:computebestapprox} Let $f(x) = e^x$ for $x\in[0,1]$. 
Find the best approximation to $f$ in $\P_1$ with respect to the $L^2$ norm
\[
\|g\|_{L^2}= \left(\int_0^1 |g(x)|^2\right)^{1/2}.
\]
Include a plot of the graphs of $f$ and $p$ (plotted in the same figure).



\item\label{prob:generalinterval}
If $f\in C^{n+1}([a,b])$ and $p\in\P_n$ interpolates $f$ at distinct points $x_0,\dots,x_n\in[a,b]$ then we know that
\begin{equation}\label{eq:interperror}
\begin{split}
|f(x)-p(x)| &\leq \frac{\prod_{k=0}^n|x-x_k|}{(n+1)!}\|f^{(n+1)}\|_{C([a,b])}.
\end{split}
\end{equation}

\begin{problems}
\item Prove that
\begin{equation}\label{eq:interperror2}
\|f-p\|_{C([a,b])}\leq \frac{(b-a)^{n+1}}{(n+1)!}\|f^{(n+1)}\|_{C([a,b])}
\end{equation}
where $\|g\|_{C([a,b])} = \sup_{x\in[a,b]}|g(x)|.$
\item We have also seen that if $[a,b]=[-1,1]$ then the product term in \eqref{eq:interperror} can be bounded by $2^{-n}$, provided $x_0,\dots,x_n$ are the Chebysheff points on $[-1,1]$. Use this to prove that on a general interval $[a,b]$, we can estimate
\begin{equation}\label{eq:interperrorcheb}
\|f-p\|_{C([a,b])}\leq \frac{(b-a)^{n+1}}{2^{2n+1}(n+1)!}\|f^{(n+1)}\|_{C([a,b])}
\end{equation}
when $x_0,\dots,x_n$ are the Chebysheff points on $[a,b]$.
\end{problems}




\item\label{prob:splines}
If $\|f^{(n+1)}\|_{C([a,b])}$ increases very quickly as $n$ increases, then the right-hand sides of \eqref{eq:interperror2} or \eqref{eq:interperrorcheb} might not go to zero as $n\to\infty$. For instance, it can be shown that Runge's function $R(x)=1/(1+25x^2)$ satisfies $\|R^{(m)}\|_{C([-1,1])} \approx 5^{m}m!$ for every $m\in\N$.

As we have seen, an alternative to high-order polynomial interpolation is spline interpolation, but the error analysis of these can be quite tricky. In this problem we investigate an alternative space of interpolants.

Fix an interval $[a,b]$ and, for simplicity, consider the uniform mesh $x_i=a+ih$, $i=0,1,\dots,N$, where $h=\frac{b-a}{N}$. Define
\[
S_k^j = \bigl\{s\in C^j([a,b])\::\: s\bigr|_{(x_{i-1},x_{i})}\in\P_k\ \forall\ i=1,2,\dots,N \bigr\}.
\]
\emph{Splines} lie in the space $S_k^{k-1}$. We will consider the space $S_k^0$. 

\begin{problems}
\item
Let $f\in C([a,b])$ and let $s\in S_k^0$ be the function which in each subinterval $[x_{i-1},x_i]$ interpolates $f$ over the uniform mesh
\begin{equation}\label{eq:interppoints}
x_{i-1} + \update{\frac{j}{k}h}, \qquad j=0,1,\dots,k
\end{equation}
(that is, $f$ and $s$ should be equal at these points). Explain why this uniquely determines $s$.
\end{problems}
Henceforth, let $\Pi_k^N f=s$ denote the function found above.
\begin{problems}[resume]
\item Assume that $f\in C^{k+1}([a,b])$. Prove that in each subinterval $x\in[x_{i-1},x_i]$ we have
\[
|f(x)-\Pi_k^Nf(x)| \leq \frac{h^{k+1}}{(k+1)!}\|f^{(k+1)}\|_{C([x_{i-1},x_i])}.
\]

\item Deduce that
\[
\|f-\Pi_k^Nf\|_{C([a,b])} \leq \frac{(b-a)^{k+1}}{N^{k+1}(k+1)!}\|f^{(k+1)}\|_{C([a,b])}.
\]

\item The number $k+1+(N-1)k = Nk+1$ is the number of evaluations of $f$ required to find $\Pi_k^N f$, and is therefore an indication of the computational cost of computing the interpolant. For a fixed computational cost $c=Nk+1$, explain what values of $N,k$ you should use in order to minimize the error $\|f-\Pi_k^Nf\|_{C([a,b])}$ for the two functions
\begin{problems}
\item $f(x)=\sin(x)$, $x\in[-\pi,\pi]$
\item $f(x)=1/(1+25x^2)$, $x\in[-1,1]$.
\end{problems}

\item Implement a function \texttt{piecewisepol(f, a, b, N, k)} in your favourite programming language which takes as input the function $f$, the endpoints of the interval $[a,b]$, and the integers $N,k$, and plots both $f$ and $\Pi_k^Nf$ over $x\in[a,b]$. (Make sure to plot both graphs in the same figure, to make it easier to compare the two.)

Include the plots from \texttt{piecewisepol(f, a, b, N, k)} for the two functions from the previous problem for $(N,k)=(8,1)$ and $(N,k)=(1,8)$. Explain which choices you think are best, both from the plots and from the analysis in the previous problem.
\end{problems}

\end{problems}


\clearpage
\section*{Hints}
\label{p:hintsstart}
\begin{description}
\item[Problem \ref{prop:computebestapprox}:] Find the orthogonal polynomials $p_0,p_1$ with respect to the $L^2$ inner product
\[
\ip{f}{g}=\int_0^1 f(x)g(x)\,dx.
\]

\item[Problem 3(d):] In order to compare factorials and powers, you might need Stirling's approximation:
\[
m! \approx m^{m+1/2}e^{-m} \qquad \text{for } m\in\N.
\]
(The ratio between the left-hand and right-hand expression lies somewhere in the interval $[2.5,3]$ for every $m$.)
\end{description}
\end{document}
