\section {POLYNOMIAL INTERPOLATION}
The central problem in function approximation is to take a given
function $f(x)$ and construct a simple function $s(x)$ which
approximates $f(x)$ in some sense. The precise meaning of ``simple''
and ``approximates'' depends on the problem context and goals.
Polynomial interpolation represents a first attempt to solve the
approximation problem.

Let $f(x)$ be a function defined on $[a,b]$, and let $x_0$, $x_1$,
$\ldots$, $x_n$ be $n+1$ distinct points in $[a,b]$. The Lagrange
polynomials for $x_0$, $\ldots$, $x_n$ are defined by
$$L_k(x)=\prod_{i=0 \atop i\ne k}^n {(x-x_i) \over (x_k-x_i)}, \quad
k=0,1,\ldots,n.$$ \noindent{Note that $L_k(x_i)= \delta_{ik}= \cases{1,
k=i\cr 0,k\ne i}$. A polynomial $P(x)$ is said to {\it interpolate\/}
$f$ at $x_0$, $\ldots$, $x_n$ if $P(x_i)=f(x_i), \quad i=0$, 1,
$\ldots$, $n$.}

\medskip\noindent{\bf Theorem}. Let $x_0$, $x_1$, $\ldots$, $x_n$ be $n+1$
distinct points, and $f(x_0)$, $\ldots$, $f(x_n)$ arbitrary values. Then 
$\exists$ a unique polynomial $P(x)$ of degree $\le n$ such that
$P(x_i)=f(x_i), \quad i=0$, 1, $\ldots$, $n$.

Proof. The polynomial $P(x)=\sum_{k=0}^n{f(x_k)L_k(x)}$, called the
Lagrange interpolating polynomial to $f(x)$ at $x_0$, $\ldots$, $x_n$,
has degree $\le n$, and clearly satisfies $P(x_i)=f(x_i), \quad i=0$,
1, $\ldots$, $n$. To prove the uniqueness, suppose $Q(x)$ is another
polynomial of degree $\le n$ also interpolating $f$ at $x_0$, $\ldots$,
$x_n$. Then $P(x_i)-Q(x_i)=f(x_i)-f(x_i)=0$ for $i=0$, 1, $\ldots$,
$n$. Thus $P-Q$ is a polynomial of degree $\le n$ with $n+1$ distinct
roots, which implies $P-Q \equiv 0$, i.e., $P=Q$.\QED

The Hermite interpolating polynomial $$H(x)
=\sum_{k=0}^n{f(x_k)\psi_k(x)} +\sum_{k=0}^n{f'(x_k)\Psi_k(x)},$$ where
$$\psi_k(x) =(1-2L'_k(x_k)(x-x_k))L_k^2(x), \quad \Psi_k(x)
=(x-x_k)L_k^2(x),$$ matches both $f$ and $f'$ at $x_0$, $\ldots$,
$x_n$, and is unique.

Disadvantages of Lagrange forms:
\item{1)} difficult to incorporate higher order derivative data or mixed
data,
\item{2)} Lagrange form is expensive to evaluate,
\item{3)} new data cannot be easily incorporated.

Let $P(x)$ be the unique polynomial of degree $\le n$ interpolating
$f(x)$ at distinct points $x_0$, $\ldots$, $x_n$. The Newton form of
$P(x)$ is $$\eqalign{P(x)&=\sum_{k=0}^n a_k \prod_{i=0}^{k-1}(x-x_i)\cr&= 
a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\cdots+a_n(x-x_0)(x-x_1)
\cdots(x-x_{n-1}).\cr}$$ 
Note that any polynomial can be expanded this way since 1, $(x-x_0)$,
$(x-x_0)(x-x_1)$, $\ldots$, $(x-x_0)(x-x_1)\cdots(x-x_{n-1})$ are a
basis for the vector space of polynomials of degree $\le n$. The Newton
form and Lagrange form of the interpolating polynomial are just
different expansions of the same polynomial $P(x)$.

\medskip\noindent{\bf Definition}. $a_k=f[x_0,\ldots,x_k]$ is called
the $k$th divided difference of $f$ at $x_0$, $\ldots$, $x_k$.

\noindent{Properties of divided differences:}
\item{1)} Let $i_0$, $i_1$, $\ldots$, $i_k$ be any permutation of 0, 1,
$\ldots$, $k$. Then \hfil\break $f[x_{i_0}, x_{i_1}, \ldots,
x_{i_k}]=f[x_0, x_1, \ldots, x_k]$.
\item{2)} $f[x_0, x_1, \ldots, x_k]= \displaystyle{{f[x_1,
\ldots, x_k]-f[x_0, \ldots, 
x_{k-1}]} \over x_k-x_0}$, \quad$f[x_i]=f(x_i)$.
\item{3)} $f[x_0, x_1, \ldots, x_k]$ is a continuous function of $x_0$,
$\ldots$, $x_k$.
\item{4)} $f[x_0, x_1, \ldots, x_k]= \displaystyle{f^{(k)}(\xi)\over
k!}$ for some
point $\xi$, $\min(x_0,\ldots,x_k)<\xi<\max(x_0,\ldots,x_k)$.

\bigskip
\centerline{\bf Divided Difference Table}
$$\vbox{\tabskip=0pt\offinterlineskip\halign
{& \strut\hfil\hskip5pt$#$\hskip5pt\cr
x_0&f(x_0)\cr
&&f[x_0,x_1]\cr
x_1&f(x_1)&&f[x_0,x_1,x_2]\cr
&&f[x_1,x_2]&&f[x_0,x_1,x_2,x_3]\cr
x_2&f(x_2)&&f[x_1,x_2,x_3]&&f[x_0,x_1,x_2,x_3,x_4]\cr
&&f[x_2,x_3]&&f[x_1,x_2,x_3,x_4]\cr
x_3&f(x_3)&&f[x_2,x_3,x_4]\cr
&&f[x_3,x_4]\cr
x_4&f(x_4)\cr
}}$$

\noindent{Evaluation algorithm for
$\displaystyle P(x)=\sum_{k=0}^n{a_k\prod_{i=0}^{k-1}(x-x_i)} \quad$ at $x=z$:}

$b_n:=a_n$;

for $k:=n-1$ step $-1$ until 0 do 

\quad$b_k:=b_{k+1}*(z-x_k)+a_k$; 

\noindent Then $b_0=P(z)$, and $P(x)= b_0+b_1(x-z) +b_2(x-z)(x-x_0)
+\cdots +b_n(x-z)(x-x_0)\cdots(x-x_{n-2})$.

\medskip \noindent{\bf Theorem}. Let $f\in C^{n+1}[a,b]$, $x_0, x_1,
\ldots, x_n$ distinct points in $[a,b]$, and $P(x)$ be the unique
polynomial of degree $\le n$ interpolating $f$ at $x_0,\ldots,x_n$.
Then for any $x\in [a,b]$, $$f(x)-P(x)={f^{(n+1)}(\xi) \over (n+1)!}
\prod_{i=0}^n(x-x_i),$$ where $\min(x,x_0,\ldots,x_n) <\xi
<\max(x,x_0,\ldots,x_n)$.

Proof. If $x=x_i$ for some $i$, the result holds trivially. So assume
$x\ne x_i$ for any $i$, and define $$A(t)=f(t)-P(t)-{f(x)-P(x) \over
\prod_{i=0}^n(x-x_i)}\prod_{i=0}^n(t-x_i).$$ $A(t)$ has $n+2$ distinct
zeros, $x$, $x_0$, $\ldots$, $x_n$. By Rolle's Theorem, $A'(t)$ has at
least $n+1$ distinct zeros separating the zeros
of $A(t)$. Applying Rolle's Theorem
repeatedly yields that $A^{(n+1)}(t)$ has at least one zero, say $\xi$.
Then $$0=A^{(n+1)}(\xi)=f^{(n+1)}(\xi)-{f(x)-P(x) \over
\prod_{i=0}^n(x-x_i)}(n+1)!,$$ which is the theorem. \QED

\bigskip
\centerline{\bf OSCULATORY INTERPOLATION}
Question: What is the meaning of $P(x)$ as $x_1 \rightarrow x_0$?

Answer: $\tilde P(x)=\lim\limits_{x_1 \to x_0}P(x)$ matches {\it both\/}
$f$ and $f'$ at $x_0$.

\midinsert\vglue -.7in
\centerline{\vtop{\null \epsfxsize=3in\epsffile{osculat.eps}}\hfil
\vtop{\null\vskip30pt\hsize=2.5in
$$\displaylines{P(x)=f[x_0]+f[x_0,x_1](x-x_0)\cr
\tilde P(x)=f(x_0)+f'(x_0)(x-x_0)\cr}$$}}
\vglue -.7in
\endinsert

Since $\tilde P(x)=f(x_0)+f'(x_0)(x-x_0)=\lim\limits_{x_1 \rightarrow
x_0}P(x)= \lim\limits_{x_1 \rightarrow x_0}(f[x_0]+f[x_0,x_1](x-x_0))$
it is reasonable to define $f[x_0,x_0]=f'(x_0)$, and in general
$\displaystyle f[\underbrace{x_0, \ldots, x_0}_{k+1 \;\rm
times}]={f^{(k)}(x_0) \over k!}$.

\medskip\noindent{\bf Definition}. For $x_0 \le x_1 \le x_2 \le \cdots
\le x_n$, distinct or not, define $$f[x_0,x_1,\ldots,x_n]=\cases{
\displaystyle {f[x_1,\ldots,x_n] -f[x_0,\ldots,x_{n-1}] \over
x_n-x_0},& $x_n\ne x_0$,\cr \displaystyle{f^{(n)}(x_0)\over n!},&
$x_n=x_0$.\cr}$$

To construct a polynomial $P(x)$ such that $$P^{(j)}(x_k)
=f^{(j)}(x_k), \qquad \hbox{for } j=0,1,\ldots,r_k-1,\quad
k=0,1,\ldots,n,$$ simply compute the Newton form of the polynomial
interpolating $f$ at the points:  $$\underbrace{x_0,\ldots,x_0}_{r_0
\;\rm times}, \underbrace{x_1,\ldots,x_1}_{r_1 \;\rm times},
\underbrace{x_2,\ldots,x_2}_{r_2 \;\rm times},\ldots,
\underbrace{x_n,\ldots,x_n}_{r_n \;\rm times}.$$ For a rigorous proof
see Isaacson and Keller (1966).

\medskip\noindent{\bf Weierstrass Approximation Theorem}. Let $f$ be a
continuous function on a closed, bounded interval [a,b]. Then
$\forall \epsilon >0 \;\exists$ a polynomial $P$ such that
$\max\limits_{a\le x\le b} |f(x)-P(x)| <\epsilon$.

Proof (convolution with an ``approximate identity''). Assume that
$[a,b]=[0,1]$ and $f(0)=f(1)=0$ (possible by adding a linear function
to $f$). Extend $f$ to the whole line by $f(x)=0$ $\forall x
\notin[0,1]$.  Consider the kernal $Q_n(t)=c_n(1-x^2)^n$,
$\int_{-1}^1Q_n(x)dx=1$.  Define $$P_n(x) =\int_{-1}^1Q_n(t)f(x+t)dt
=\int_{-x}^{1-x} Q_n(t)f(x+t)dt= \int_0^1Q_n(t-x)f(t)dt,$$ (note that
$P_n(x)\approx f(x)$ since $Q_n$ has all its weight at 0) which is a
polynomial in $x$. Let $|f(t)|\le M$ on $[0,1]$ and $\delta$ be such
that $|f(x)-f(y)|<\epsilon$ for $|x-y|<2\delta$. Observe that
$\forall\epsilon, \delta>0$ $\exists N:Q_N(t)\le\epsilon$ for
$|t|\ge\delta$. Then $$\eqalign{|P_N(x)-f(x)| &=\left|\int_{-1}^1
Q_N(t)[f(x+t)-f(x)]dt \right|\le \left|\int_{-1}^{-\delta} \right|
+\left|\int_{-\delta}^{\delta}\right| + \left|\int_{\delta}^1\right|
\cr &\le 2M\epsilon+\epsilon+2M\epsilon=(4M+1)\epsilon.\cr}$$\QED

\medskip\noindent{\bf Theorem (Weierstrass)}. Let $f$ be continuous on
$[-\pi,\pi],f(-\pi)=f(\pi)$. Then $\forall\epsilon>0$ $\exists$ a
trigonometric polynomial $T_n(x)=A_0 +\sum\limits_{k=1}^n (A_k\cos kx
+B_k\sin kx)$ such that $\Vert T_n-f\Vert_\infty <\epsilon$.

\medskip\noindent{\bf Definition}. Let $s_i$ be the $i$th partial sum of a
sequence ${a_i}$. Then the $n$th Ces\'aro mean is
$$\sigma_n={s_0+s_1+\cdots+s_n\over n+1}.$$

\medskip\noindent{\bf Fej\'er's Theorem}. If $f$ is continuous and
periodic with period $2\pi$ on $(-\infty,\infty)$, then the
Ces\'aro means of the Fourier series of $f$ coverage uniformly to $f$ on
$(-\infty,\infty)$.

\vfil\eject