\documentclass[twoside]{article}

\usepackage{palatino}
\usepackage{camnum}

\textheight=21.5cm
\textwidth=15cm
\topmargin=0cm
\oddsidemargin=0.5cm
\evensidemargin=0.5cm
\parindent=0pt
\parskip=6pt

\newcommand{\gap}{\hspace*{8pt}}

\begin{document}
\begin{center}
  {\large \textbf{Mathematical Tripos Part IB: Easter 2001}}

  {\Large \textbf{Numerical Analysis -- Exercise Sheet
        2\footnote{Corrections and suggestions to these notes should 
        be emailed to \texttt{a.shadrin@damtp.cam.ac.uk}. All handouts
        are available on the WWW at the URL
        \texttt{http://www.damtp.cam.ac.uk/user/na/PartIB/Handouts.html}.}}}
\end{center}

13.  \gap Suppose that the function values $f(0),f(1),f(2)$ and $f(3)$
are given and that we wish to estimate
$$f(6),\quad f'(0)\quad\mbox{and}\quad \int_0^3 f (x)\D x.$$
One method is to let $p$ be the cubic polynomial that interpolates these
function values, and then to employ the approximants
$$p(6),\quad p'(0)\quad\mbox{and}\quad\int_0^3 p (x)\D x$$
respectively. Deduce from the Lagrange formula for $p$ that each
approximant is a linear combination of the four data with constant
coefficients. Calculate the numerical values of these constants. Verify
your work by showing that the approximants are exact when $f$ is an
arbitrary cubic polynomial.

14. \gap Let $f$ be a function in $C^4[0,1]$ and let $p$ be a cubic 
polynomial that interpolates $f(0),f'(0),f(1)$ and $f'(1)$. Deduce
from the Rolle theorem that for every $x\in[0,1]$ there exists 
$\xi\in[0,1] $ such that the equation
$$f(x)-p(x)=\Frac{1}{24} x^2 (x-1)^2 f^{(4)}(\xi)$$
is satisfied.

15. \gap Let $a,b$ and $c$ be distinct real numbers (not necessarily
in ascending order), and let $f(a)$, $f(b)$, $f'(a)$, $f'(b)$ and
$f'(c)$ be given. Because there are five data, one might try to 
approximate $f$ by a polynomial of degree at most four that interpolates 
the data. Prove by a general argument that this interpolation problem has a 
solution and the solution is unique if and only if there is no nonzero
polynomial $p\in \BB{P}_4[x]$ that satisfies $p(a)=p(b)=p'(a)=p'(b)=p'(c)=0$. 
Hence, given $a$ and $b$, show that there exists a unique value of
$c\neq a,b$ such  that there is no unique solution.

16. \gap Let $f:\BB{R}\rightarrow\BB{R}$ be a given function and let $p$ be 
the polynomial of degree at most $n$ that interpolates $f$ at the
pairwise distinct points $x_0,x_1,\ldots,x_n$. Further, let $x$ be
any real number that is not an interpolation point. Deduce the identity
$$f(x)-p(x)=f[x_0, x_1,\ldots,x_n,x] \prod^n_{j=0}(x-x_j)$$
from the definition of the divided difference $f[x_0,x_1,\ldots,x_n,x]$.

17. \gap Simulating a computer that works to only four decimal places,
form the table of divided differences of the values  $f(0)=0$,
$f(0.1)=0.0998$, $f(0.4)= 0.3894$ and $f(0.7)=0.6442$ of $\sin x$.
Hence identify the polynomial that is given by Newton's interpolation
method. Due to rounding errors, this polynomial should differ from the one
that would be given by exact arithmetic. Take the view, however, that the 
{\em computed\/} values of $ f[0.0,0.1],f[0.0,0.1,0.4]$ and
$f[0.0,0.1,0.4,0.7]$ and the function value $f(0)$ are correct.  
Then, by working backwards through the difference table, identify the values 
of $f(0),f(0.1),f(0.4)$ and $f(0.7)$ that would give these divided
differences in exact arithmetic.

18. \gap Set $f(x)=2x-1$, $x\in[0,1]$. We require a function of form
$$p(x)=\sum^n_{k=0}a_k \cos(k\pi x),\quad 0\leq x\leq 1,$$
that satisfies the condition
$$\int_0^1[f(x)-p(x)]^2\D x < 10^{-4}.$$
Explain why it is sufficient if the value of
$a_0^2+\frac12\sum^n_{k=1} a_k^2$ exceeds $\frac13-10^{-4}$, where the
coefficients $\{a_k\}_{k=0}^n$ are calculated to minimize  this
integral. Hence find the smallest acceptable value of $n$.

19. \gap The polynomials $\{p_n\}_{n\in\bb{Z}^+}$ are defined by the
three-term recurrence formula
\begin{eqnarray*}
p_0(x)&\equiv&1,\\
p_1(x)&=&2x,\\
p_{n+1}(x)&=&2xp_n(x)-p_{n-1}(x),\qquad n=1,2,\ldots.
\end{eqnarray*}
Prove that they are orthogonal with respect to the inner product
$$\langle f,g\rangle =\int_{-1}^1 f(x) g(x) \sqrt{1-x^2}\D x$$
and evaluate $\langle p_n,p_n\rangle$ for $n\in\BB{Z}^+$. {\em [Hint: Prove
that $p_n(x)=\sin(n+1)\theta/\sin\theta$, where $x=\cos \theta$.]}

20. \gap  Calculate the coefficients $b_1,b_2,c_1$ and $c_2$ so that the
approximant
$$\int ^1_0 f(x)\D x \approx b_1 f(c_1) +b_2 f(c_2)$$
is exact when $f$ is a cubic polynomial. You may exploit the fact that
$c_1$ and $c_2$ are the zeros of a quadratic polynomial that is
orthogonal to all linear polynomials. Verify your calculation by testing
the formula when $f(x)=1,x,x^2$ and $x^3$.

21. \gap The functions $p_0,p_1,p_2,\ldots$ are generated by the Rodrigues
formula
$$p_n(x)=\CC{e}^x\frac{\D^n}{\D x^n} (x^n \CC{e}^{-x}),\qquad
0\leq x<\infty.$$
Show that these functions are polynomials and prove by integration by parts
that for every $p\in\BB{P}_{n-1}[x]$ we have the orthogonality
condition $\langle p_n, p\rangle=0$ with respect to the scalar product
$$\langle f,g\rangle:=\int_0^\infty \CC{e}^{-x}f(x)g(x)\D x.$$
Derive the coefficients of $p_3,p_4$ and $p_5$ from the Rodrigues
formula. Verify that these coefficients are compatible with a 
three term recurrence relation of the form 
$$p_5(x)=(\gamma x-\alpha) p_4 (x) - \beta p_3 (x),\qquad x\in\BB{R},$$
where $\alpha,\beta$ and $\gamma$ are constants.

22. \gap Let $p(\frac12)=\frac12(f(0) + f(1))$, where $f$ is a function in
$C^2[0,1]$. Find the least constants $c_0,c_1$ and $c_2$ such that
the error bounds
$$|f(\Frac12)-p(\Frac12)|\leq c_k \|f^{(k)}\|_\infty\ ,\qquad k=0,1,2,$$
are valid. {\em [Note: The cases $k=0 $ and $k=1$ are easy if one works from 
first principles, and the Peano kernel theorem is suitable when $k=2$. 
Also try the Peano kernel theorem when $k=1$.]\/}

23. \gap  Express the divided difference $f[0,1,2,4]$ in the form
$$f[0,1,2,4]=\int_0^4 K(\theta) f'''(\theta) \D\theta,$$
assuming that $f'''$ exists and is continuous. Sketch the kernel
function $K(\theta)$ for $0\leq\theta\leq4$. By integrating $K(\theta)$
analytically and using the mean value theorem prove that
$$f[0,1,2,4]=\Frac16 f'''(\xi)$$
for some point $\xi\in[0,4]$. Note that another proof of this result
was given in the lecture on divided differences.

24. \gap Let $f$ be a function in $C^4[0,1]$ and let $\xi$ be any fixed
point in $[0,1]$. Calculate the coefficients $\alpha,\beta,\gamma$ and
$\delta$ such that the approximant 
$$f'''(\xi)\approx\alpha f(0)+\beta f(1)+\gamma f'(0)+\delta f'(1)$$
is exact for all cubic polynomials. Prove that the inequality
$$\left|f'''(\xi)-\alpha f(0)-\beta f(1)-\gamma f'(0)-\delta
f'(1)\right| \leq \left\{ \Frac12-\xi+2\xi^3-\xi^4\right\}
\|f^{(4)}\|_\infty$$ 
is satisfied. Show that this inequality holds as an equation if we
allow $f$ to be the function
$$f(x)= \left\{\begin{array}{rcl}
-(x-\xi)^4, & \quad &0 \leq x \leq \xi,\\[6pt]
(x-\xi)^4, & \quad &\xi \leq x \leq 1.\end{array}\right.$$

25. \gap {\em [Not easy!]\/} \gap  Given $f$ and $g$ in $C[a,b]$, let
$h:=fg$. Prove by induction that the divided differences of $h$
satisfy the equation
$$h[x_0,x_1,\ldots,x_n]=\sum^n_{j=0}f [x_0,x_1,\ldots,x_j]
g[x_j,x_{j+1},\ldots,x_n].$$
By expressing the differences in terms of derivatives and by letting the 
points $x_0,x_1,\ldots,x_n$ become coincident, deduce the Leibniz
formula for the $n$th derivative of a product of two functions.

\end{document}