\documentclass[11pt]{article}

%\usepackage{epsfig,psfrag}
%\newcommand{\psfrag}[2]{}
%\newcommand{\epsfig}[1]{}

%\usepackage{amstex}

%\usepackage{cite}
%\usepackage{theorem}
%\usepackage{fancyheadings}
%\usepackage{/home/rjl/tex/subeqn}

\setlength{\textwidth}{6.2in}
\setlength{\oddsidemargin}{0.3in}
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{8.7in}
\setlength{\voffset}{-.7in}
\setlength{\headsep}{26pt}

\input{macros}
\def\hull{\mbox{Int}}

\begin{document}

\noindent
AMath 584 \hfill R. J. LeVeque\\
For Homework 4\hfill Autumn, 2011
\vskip .2in
\hrule
\vskip .3in

\bc\Large\bf Review of Interpolation\ec
\vskip 10pt

\section{General interpolation problem}
Given a set of discrete points $x_i$ for $i=1,~2,~\ldots,~n$ and function
values $F_i$, determine a function $\phi(x)$ passing through these points,
\eql{interp1}
\phi(x_i) = F_i \quad\mbox{for}~i=1,~2,~\ldots,~n.
\end{equation}
We use the notation $\hull(x_1,\ldots,x_n)$ to denote the smallest interval
containing all these points (which need not be in increasing order but which
are assumed to be distinct).

Some uses of interpolation:
\bi
\item May only have discrete data values and want to estimate values in
between, $x\in\hull(x_1,\ldots,x_n)$.
This is the origin of the term {\it interpolation}.
We might also use this function to {\it extrapolate} if we evaluate it
outside the interval where data is given.
\item May know true function $F(x)$ but want to approximate it by a
function $\phi(x)$ that is  cheaper to evaluate, or easier to work with
symbolically (to differentiate or integrate, for example).
\item As a starting point for deriving numerical methods for differential
equations (or for integral equations or numerical integration).
\ei

There are infinitely many possible functions $\phi$. 
Typically $\phi$ is chosen to be a linear combination of some $n$ given {\it
basis functions} $\phi_1(x),~\ldots,~\phi_n(x)$,
\eql{phi1}
\phi(x) = c_1\phi_1(x) + \cdots+ c_n\phi_n(x).
\end{equation}
Then condition \eqn{interp1} gives a linear system of $n$ equations to solve
for the coefficients $c_1,~\ldots,~c_n$,
\eql{Phi}
\bcm \phi_1(x_1) & \phi_2(x_1) & \cdots & \phi_n(x_1)\\
\phi_1(x_2) & \phi_2(x_2) & \cdots & \phi_n(x_2)\\
\vdots & & & \vdots\\
\phi_1(x_n) & \phi_2(x_n) & \cdots & \phi_n(x_n)\ecm
\bcm c_1 \\ c_2 \\ \vdots \\ c_n\ecm
= \bcm F_1 \\ F_2 \\ \vdots \\ F_n\ecm
\end{equation}
This system can we written as $\Phi c = F$.
Different choices of basis functions lead to different types of
interpolation.  Using trigonometric functions gives Fourier series, for
example.


\section{Polynomial interpolation}
Through any $n$ points there is a unique interpolating polynomial $p(x)$ of
degree $n-1$.  There are many ways to represent this function depending on
what basis is chosen for ${\cal P}_{n-1}$, the set of all polynomials of
degree $n-1$.

\subsection{Monomial basis}
\eql{monomials}
\phi_1(x) = 1,\quad \phi_2(x) = x, \quad \phi_3(x)= x^2,\quad \ldots,\quad 
\phi_n(x) = x^{n-1}.
\end{equation}
The matrix $\Phi$ appearing in \eqn{Phi} is then the {\it Vandermonde
matrix}.  This matrix may be quite ill-conditioned.

\subsection{Lagrange basis}
\eql{lagrange}
\phi_j(x) = \prod_{\stackrel{i=1}{i\neq j}}^n \frac{(x-x_i)}{(x_j-x_i)}.
\end{equation}
This is a polynomial of degree $n-1$.  Note that
\[
\phi_j(x_i) = \delta_{ij} = \choose 1\when i=j\\ 0\when i\neq j. \endch
\]
Then the matrix in \eqn{Phi} is the identity matrix and $c_i=F_i$.
The coefficients are easy to determine in this form but the basis functions
are a bit cumbersome.

\subsection{Newton form}
The Newton form of the interpolating polynomial is
\eql{newton1}
p(x) = c_1 + c_2(x-x_1) + c_3(x-x_1)(x-x_2) + \cdots +
c_n(x-x_1)(x-x_2)\cdots (x-x_{n-1}).
\end{equation}
For these basis functions the matrix $\Phi$ is {\it lower triangular} and the
$c_i$ may be found by forward substitution.  Alternatively they are most
easily computed using {\it divided differences}, $c_i=F[x_1,\ldots,x_i]$.
These can be computed from a tableau of the form
\eql{ddtab}
\begin{array}{cccccc}
x_1&F[x_1] \\
&& F[x_1,x_2]\\
x_2 & F[x_2] && F[x_1,x_2,x_3]\\
&& F[x_2,x_3]\\
x_3 & F[x_3] 
\end{array}
\end{equation}
where
\[
F[x_j] = F_j
\]
and for $k>0$,
\eql{Fdiff2}
F[x_j,\ldots,x_{j+k}] = \frac{F[x_{j+1},\ldots,x_{j+k}] -
F[x_{j},\ldots,x_{j+k-1}]}{x_{j+k}-x_j}.
\end{equation}
Then the Newton form can be built up as follows:
\eqmno
&&p_0(x) = F[x_1] \\
&&\qquad\qquad \mbox{is the polynomial of degree 0 interpolating at
$x_1$}\\
&&p_1(x) = F[x_1] + F[x_1,x_2](x-x_1) \\
&&\qquad\qquad \mbox{is the polynomial of degree 1 interpolating at
$x_1,x_2$}\\
&&p_1(x) = F[x_1] + F[x_1,x_2](x-x_1) +F[x_1,x_2,x_3](x-x_1)(x-x_2)\\
&&\qquad\qquad \mbox{is the polynomial of degree 2 interpolating at
$x_1,x_2,x_3$}\\
&&\mbox{etc.}
\enmno
Each step we add a term which vanishes at all the preceding  interpolation
points and makes the function also interpolate at one new point.  Note that
the coefficients of previous basis functions do not change.

{\bf Relation to Taylor series.} Note that
\[
F[x_j,x_{j+1}] = \frac{F_{j+1}-F_j}{x_{j+1}-x_j}
\]
approximates a derivative $F'(x_j)$.  Similarly, if $x_j,\ldots,x_{j+k}$ are
close together then 
\eql{Fkdif}
F[x_j,\ldots,x_{j+k}] \approx \frac{1}{k!} F^{(k)}(x_j)
\end{equation}
where $F^{(k)}(x)$ is the $k$th derivative.  In fact one can show that
\eql{Fkdif2}
F[x_j,\ldots,x_{j+k}] = \frac{1}{k!} F^{(k)}(\xi)
\end{equation}
for some $\xi$ lying in the interval $\hull(x_j,\ldots,x_{j+k})$.
The Newton form \eqn{newton1}
thus is similar to the Taylor series
\eql{taylor}
F(x) = F(x_1) + F'(x_1)(x-x_1) + \frac{1}{2!} F''(x_1)(x-x_1)^2 + \cdots
\end{equation}
and gives this in the limit as $x_j\goto x_1$ for all $j$.

\subsection{Error in polynomial interpolation}
Suppose $F(x)$ is a smooth function, we evaluate $F_i=F(x_i)$
($i=1,~2,~\ldots,~n$), and now fit a
polynomial $p(x)$ of degree $n-1$
through these points.  How well does $p(\bar x)$ approximate
$F(\bar x)$ at some other point $\bar x$?

Note that we could add $\bar x$ as another interpolation point and 
create an interpolating polynomial $\bar p(x)$ of degree $n$ that
interpolates also at this point,
\[
\bar p(x) = p(x) + F[x_1,~\ldots,~x_n,~\bar x](x-x_1)\cdots(x-x_n).
\]
Then $\bar p(\bar x) = F(\bar x)$ and so
\[
F(\bar x) - p(\bar x) =  F[x_1,~\ldots,~x_n,~\bar x](\bar x-x_1)\cdots(\bar x-x_n).
\]

Using \eqn{Fkdif2}, we obtain
an error formula similar to the remainder formula for Taylor
series, which states that if $p(x)$ is given by \eqn{newton1}, then
\eql{err1}
F(x)-p(x) = \frac{1}{n!} F^{(n)}(\xi) (x-x_1)\cdots(x-x_n)
\end{equation}
where $\xi$ is some point lying in $\hull(x, x_1,\ldots,x_n)$. How
large this is depends on 
\bi
\item How close the point $x$ is  to the interpolation points
$x_1,\ldots,x_n$,
\item How small the derivative $F^{(n)}(\xi)$ is over this interval, \ie,
how smooth the function is.
\ei
For a given $x$ we don't know exactly what $\xi$ is in general, but we can
often use this to obtain an {\it error bound} of the form
\eql{ebound}
|p(x)-F(x)| \leq K |(x-x_1)\cdots(x-x_n)|
\end{equation}
where $K = \frac{1}{n!} \max_{\xi\in\hull(x_1,\ldots,x_n)} |F^{(n)}(\xi)|$.


\subsection{Chebyshev points}
Suppose we wish to approximate some $F(x)$ over $[-1,1]$ by a polynomial of
degree $n-1$ based on interpolation at some $n$ points in this interval. If
we are free to pick these points however we want, then we might want to
minimize
\eql{chebmin}
\max_{-1\leq x \leq 1}|(x-x_1)\cdots(x-x_n)|.
\end{equation}
This mini-max problem can be solved and the best points are the $n$ {\it
Chebyshev points}
\eql{chebpts}
x_j = \cos \theta_j \qquad \mbox{where}~~ \theta_j=\frac{(j-1/2)\pi}{n}
\end{equation}
for $j=1,2,\ldots,n$.  Now let
\eql{chebp}
T_n(x) = (x-x_1)\cdots(x-x_n)
\end{equation}
be the polynomial of degree $n$ with these points as its roots (which
appears in \eqn{err1}).   This is
the {\it Chebyshev polynomial} of degree $n$.  The first few are
\eqmno
T_0(x) &=& 1\\
T_1(x) &=& x\\
T_2(x) &=& 2x^2 - 1\\
T_3(x) &=& 4x^3 - 3x
\enmno
In general they satisfy a 3-term recurrence relation
\eql{chebr}
T_{n+1}(x) = 2xT_n(x) - T_{n-1}(x).
\end{equation}
For $-1\leq x \leq 1$ they also have the property that
\eql{chebc}
T_n(x) = \cos(n\arccos x).
\end{equation}
This doesn't look so much like a polynomial in this form, 
but shows that $T_n(x)$
oscillates between $\pm 1$ over this interval.



\end{document}
