\documentclass[twoside]{article}

\usepackage{palatino}
\usepackage{camnum}

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

\setcounter{section}{6}
\setcounter{subsection}{0}
\setcounter{equation}{0}

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

  {\Large \textbf{Numerical Analysis -- Lecture
      8\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}

\subsection{The error of polynomial interpolation}

Let $[a,b]$ be a closed interval of $\BB{R}$. We denote by $C[a,b]$ the
space of all continuous functions from $[a,b]$ to $\BB{R}$ and let
$C^s[a,b]$, where $s$ is a positive integer, stand for the linear
space of all functions in $C[a,b]$ that possess $s$ continuous
derivatives. 

{\bf Theorem} Given $f\in C^{n+1}[a,b]$, let $p\in\BB{P}_n[x]$
interpolate the values $f(x_i)$, $i=0,1,\ldots,n$, where
$x_0,\ldots,x_n\in[a,b]$ are pairwise distinct. Then for every
$x\in[a,b]$ there exists $\xi\in[a,b]$ such that
\begin{equation}\label{6.1}
f(x)-p(x)=\frac{1}{(n+1)!} f^{(n+1)}(\xi)\prod_{i=0}^n (x-x_i).
\end{equation}
\hspace*{8pt}{\bf Proof.} The formula \R{6.1} is true when $x=x_j$ for
$j\in\{0,1,\ldots,n\}$, since both sides of the equation vanish. Let
$x\in[a,b]$ be any other point and define
$$\phi(t):=[f(t)-p(t)]\prod_{i=0}^n (x-x_i)-[f(x)-p(x)]
\prod_{i=0}^n (t-x_i),\qquad t\in[a,b].$$
{\em [Note: The variable in $\phi$ is $t$, whereas $x$ is a fixed
parameter.]\/} Note that $\phi(x_j)=0$, $j=0,1,\ldots,n$, and
$\phi(x)=0$. Hence, $\phi$ has at least $n+2$ distinct zeros in $[a,b]$.
Moreover, $\phi\in C^{n+1}[a,b]$.\\
We now apply the {\em Rolle theorem:\/} if the function $g\in
C^1[a,b]$ vanishes 
at two distinct points in $[a,b]$ then its derivative vanishes at an
intermediate point. We deduce that $\phi'$ vanishes at (at least)
$n+1$ distinct 
points in $[a,b]$. Next, applying Rolle to $\phi'$, we conclude that
$\phi''$ vanishes at $n$ points in $[a,b]$. In general, we prove by
induction that $\phi^{(s)}$ vanishes at $n+2-s$ distinct points of
$[a,b]$ for $s=0,1,\ldots,n+1$. Letting $s=n+1$, we have
$\phi^{(n+1)}(\xi)=0$ for some $\xi\in[a,b]$. Hence
$$0=\phi^{(n+1)}(\xi)=[f^{(n+1)}(\xi)-p^{(n+1)}(\xi)] \prod_{i=0}^n
(x-x_i) -[f(x)-p(x)]\frac{\CC{d}^{n+1}}{\CC{d}t^{n+1}} \prod_{i=0}^n
(\xi-x_i).$$
Since $p^{(n+1)}\equiv0$ and $\CC{d}^{n+1} \prod_{i=0}^n
(t-x_i)/\CC{d} t^{n+1}\equiv (n+1)!$, we obtain \R{6.1}. \QED

{\bf Runge's example} We interpolate $f(x)=1/(1+x^2)$, $x\in[-5,5]$,
at the equally-spaced points $x_j=-5+10\frac{j}{n}$, $j=0,1,\ldots,n$.
Some of the errors are displayed below

\vspace{8pt}
\parbox[t]{61mm}{\begin{tabular}{|c||c|c|}
$x$ & $f(x)-p(x)$ & $\prod_{i=0}^n (x-x_i)$\\\hline\hline
$0.75$ & $3.2\times 10^{-3}$ & $-2.5\times10^6$\\
$1.75$ & $7.7\times10^{-3}$ & $-6.6\times10^6$\\
$2.75$ & $3.6\times10^{-2}$ & $-4.1\times10^7$\\
$3.75$ & $5.1\times10^{-1}$ & $-7.6\times10^8$\\
$4.75$ & $4.0\times10^{+2}$ & $-7.3\times10^{10}$
\end{tabular}\\[8pt]
{\bf Table:} Errors for $n=20$\\[5pt]
\hspace*{60pt}{\bf Figure:} Errors for $n=15$}
\special{psfile=Runge.ps hoffset=5 voffset=-117 vscale=27 hscale=45}

The growth in the error is explained
by the product term in \R{6.1} (the rightmost column of the table).
Adding more interpolation points makes the largest error even worse. A
remedy to this state of affairs is to cluster points toward the end of
the range. A considerably smaller error is attained for
$x_j=5\cos\frac{(n-j)\pi}{n}$, $j=0,1,\ldots,n$ (so-called {\em
Chebyshev points\/}). It is possible to prove that this choice of
points minimizes the magnitude of
$\max_{x\in[-5,5]}\left|\prod_{i=0}^n (x-x_i)\right|$.

\subsection{Divided differences: a definition}

Given $f\in C[a,b]$ and pairwise-distinct 
points $x_0,\ldots,x_n\in[a,b]$, 
the {\em divided difference} $f[x_0,\ldots,x_n]$ of degree $n$ 
is, by definition, the leading coefficient of $p \in \BB{P}_n[x]$ 
which interpolates $f$ at these points 
(i.e., the coefficient of $x^n$ in $p$).

We can derive the expression for $f[x_0,\ldots,x_n]$ from the Lagrange formula,
\begin{equation}\label{6.2}
f[x_0,x_1,\ldots,x_n]=\sum_{k=0}^n f(x_k)
\prod_{\stackrel{\scriptstyle \ell=0}{\ell\neq k}}^n
\frac{1}{x_k-x_\ell}.
\end{equation}

{\bf Theorem} Let $[\bar{a},\bar{b}]$ be the smallest interval that
contains $x_0,x_1,\ldots,x_n$ and let $f\in C^n[\bar{a},\bar{b}]$.
Then there exists $\xi\in[\bar{a},\bar{b}]$ such that
\begin{equation}\label{6.3}
f[x_0,x_1,\ldots,x_n]=\Frac{1}{n!} f^{(n)}(\xi).
\end{equation}
\hspace*{8pt}{\bf Proof.} Let $p$ be the interpolating polynomial. The
error function $f-p$ has at least $n+1$ zeros in $[\bar{a},\bar{b}]$
and, applying Rolle's theorem $n$ times, it follows that
$f^{(n)}-p^{(n)}$ vanishes at some $\xi\in[\bar{a},\bar{b}]$. But
$p(x)=\frac{1}{n!} p^{(n)}(\zeta)x^n+\mbox{lower order terms}$ (for any
$\zeta\in\BB{R}$), therefore, letting $\zeta=\xi$,
$$f[x_0,x_1,\ldots,x_n]=\Frac{1}{n!} p^{(n)}(\xi)=\Frac{1}{n!}
f^{(n)}(\xi)$$ 
and we deduce \R{6.3}. \QED

{\bf Application} It is a consequence of the theorem that divided
differences can be used to approximate derivatives.

\subsection{Recurrence relations for divided differences}

Our next topic is a useful way to calculate divided differences (and,
ultimately, to deduce yet another means to construct an interpolating
polynomial). We commence with the remark that $f[x_i]$ is the
coefficient of $x^0$ in the polynomial of degree $0$ (i.e., a
constant) that interpolates $f(x_i)$, hence $f[x_i]=f(x_i)$.

{\bf Theorem} Suppose that $x_0,x_1,\ldots,x_{k+1}$ are pairwise
distinct, where $k\geq0$. Then
\begin{equation}\label{6.4}
f[x_0,x_1,\ldots,x_{k+1}]=\frac{f[x_1,x_2,\ldots,x_{k+1}]-
f[x_0,x_1,\ldots,x_k]}{x_{k+1}-x_0}.
\end{equation}
\hspace*{8pt}{\bf Proof.} Let $p,q\in\BB{P}_k[x]$ be the polynomials
that interpolate $f$ at
$$\{x_0,x_1,\ldots,x_k\}\qquad\mbox{and}\qquad
\{x_1,x_2,\ldots,x_{k+1}\}$$ 
respectively and define
$$r(x):=\frac{(x-x_0)q(x)+(x_{k+1}-x)p(x)}{x_{k+1}-x_0}\in
\BB{P}_{k+1}[x].$$ 
We readily verify that $r(x_i)=f(x_i)$, $i=0,1,\ldots,k+1$, hence, $r$
is the $(k+1)$-degree interpolating polynomial for $f$. Moreover,
the leading coefficient of $r$ is equal to the difference of those 
of $q$ and $p$ divided by $x_{k+1}-x_0$, 
what actually the recurrence \R{6.4} is.
 \QED

\end{document}