%%  chapter-05.tex
%%  Approximation Theory: Chapter 5
%%  Neal L. Carothers
%%  Bowling Green State University
%%  Bowling Green, Ohio  43403
%%  carother@math.bgsu.edu
%%  http://www.bgsu.edu/~carother/


\input 680-setup.tex
\baselineskip = 24 true pt

\chaptertitle = {Interpolation}

\centerline{\hfil\tf A Brief Introduction to Interpolation\hfil}
\vskip-\baselineskip
\line{\sc Math 680 \hfil 7/12/94}

\noindent
Our goal in this section is to prove the
following result (and discuss its ramifications).
In fact, this result is so fundamental that
we will present three proofs!

\proclaim Theorem.
Let $x_0,x_1,\ldots,x_n$ be distinct points, and
let $y_0,y_1,\ldots,y_n$ be arbitrary points in $\R$.
Then, there exists a unique polynomial $p\in{\cal P}_n$
satisfying $p(x_i)=y_i$, $i=0,1,\ldots,n$.

First notice that uniqueness is obvious.  Indeed, if
two polynomials $p$, $q\in{\cal P}_n$ agree at $n+1$ points,
then $p\equiv q$.  (Why?)  The real work comes in proving
existence.  

\noindent
{\sc First Proof}.\quad
(Vandermonde's determinant.)
We seek $c_0,c_1,\ldots,c_n$ so that 
$p(x)=\sum_{k=0}^nc_kx^k$ satisfies
$$p(x_i)=\sum_{k=0}^nc_kx_i^k=y_i,\quad i=0,1,\ldots,n.$$
That is, we need to solve a system of $n+1$
{\sl linear\/} equations for the $c_i$'s.
In matrix form:
$$\left[\,\matrix{
    \noalign{\smallskip}
        1 & x_0 & x_0^2 & \cdots & x_0^n\cr
    \noalign{\smallskip}
        1 & x_1 & x_1^2 & \cdots & x_1^n\cr
        \vdots & \vdots & \vdots &\ddots & \vdots \cr
        1 & x_n & x_n^2 & \cdots & x_n^n\cr 
    \noalign{\smallskip}
    }\,\right]
	\left[\matrix{
	\noalign{\smallskip}
		c_0\cr 
	\noalign{\smallskip}
		c_1\cr \vdots\cr c_n\cr 
	\noalign{\smallskip}
	}\,\right]=
	\left[\matrix{
	\noalign{\smallskip}
		y_0\cr 
	\noalign{\smallskip}
		y_1\cr \vdots\cr y_n\cr 
	\noalign{\smallskip}
	}\,\right].$$
This equation always has a unique solution because
the coefficient matrix has determinant
$$D \ =\!\!\prod_{\strut0\le j<i\le n}\!\!(x_i-x_j)\ne0.$$
($D$ is called {\sl Vandermonde's determinant\/}; note that
$D>0$ if $x_0<x_1<\cdots<x_n$).  Since this
fact is of independent interest, we'll sketch a short proof
below.~\qed

\proclaim Lemma. \ 
$D \ =\!\!\prod\limits_{\strut0\le j<i\le n}\!\!(x_i-x_j)$.

\proof
Consider 
$$V(x_0,x_1,\ldots,x_{n-1},x) \ = \ 
    \left|\,\matrix{
    \noalign{\smallskip}
        1 & x_0 & x_0^2 & \cdots & x_0^n\cr
    \noalign{\smallskip}
        1 & x_1 & x_1^2 & \cdots & x_1^n\cr
        \vdots & \vdots & \vdots &\ddots & \vdots \cr
    \noalign{\smallskip}
        1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^n\cr 
   \noalign{\smallskip}
        1 & x & x^2 & \cdots & x^n\cr
    \noalign{\smallskip}
    }\,\right|.$$
$V(x_0,x_1,\ldots,x_{n-1},x)$ is a {\sl polynomial\/} of
degree $n$ in $x$, and it's $0$ whenever $x=x_i$,
$i=0,1,\ldots,n-1$.  Thus,
$V(x_0,\ldots,x)=c\,\prod_{i=0}^{n-1}(x-x_i)$,
by comparing roots and degree.  However, it's easy
to see that the coefficient of $x^n$ in
$V(x_0,\ldots,x)$ is $V(x_0,\ldots,x_{n-1})$.
Thus, 
$V(x_0,\ldots,x)=V(x_0,\ldots,x_{n-1})\prod_{i=0}^{n-1}(x-x_i)$.
The result follows by induction and the obvious case
$\left|\matrix{1 & x_0\cr 1 & x_1\cr}\right|=x_1-x_0$.~\qed

\noindent
{\sc Second Proof}.\quad
(Lagrange interpolation.)
We could define $p$ immediately if we had polynomials
$\ell_i(x)\in{\cal P}_n$ such that $\ell_i(x_j)=\delta_{i,j}$.
Indeed, $p(x)=\sum_{i=0}^ny_i\,\ell_i(x)$ would work.
In particular, $\{\ell_0,\ell_1,\ldots,\ell_n\}$ would form
a {\sl basis\/} for ${\cal P}_n$.

We'll give two formulas for $\ell_i(x)$:

\item{(a).}
Clearly, \ 
$\ell_i(x)=\displaystyle{\prod_{j\ne i}\,{{x-x_j}\over{x_i-x_j}}}$ \ 
works.

\item{(b).}
Start with $W(x)=(x-x_0)(x-x_1)\cdots(x-x_n)$, and notice that the 
polynomial we need satisfies
$$\ell_i(x)=a_i\cdot{{W(x)}\over{x-x_i}}$$
for some $a_i\in\R$. (Why?) But then,
$1=\ell_i(x)=a_i W'(x_i)$ (again, why?);
that is, 
$$\ell_i(x)={{W(x)}\over{(x-x_i)\,W'(x_i)}}.
	\eqno\qed$$

\noindent
{\sc Third Proof}.\quad
(Newton's formula.)
We seek $p(x)$ of the form
$$p(x)=a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\ \cdots\ +
	a_n(x-x_0)\cdots(x-x_{n-1}).$$
(Please note that $x_n$ does not appear on the right-hand side.)
Now we solve for the $a_i$'s by plugging in the $x_i$'s.
$$\displaylines{
y_0=p(x_0)=a_0\cr
y_1=p(x_1)=a_0+a_1(x_1-x_0) \ \implies \ 
	a_1={{y_1-a_0}\over{x_1-x_0}}.\cr
}$$
Continuing, we find
$$\displaylines{
a_2={{y_2-a_0-a_1(x_2-x_0)}\over{(x_2-x_0)(x_2-x_1)}}\cr
\noalign{\medskip}
a_3={{y_3-a_0-a_1(x_3-x_0)-a_2(x_3-x_0)(x_3-x_1)}
		\over{(x_3-x_0)(x_3-x_1)(x_3-x_2)}}\cr
}$$
and so on.~\qed

\noindent{\bf Example}

\noindent
As a quick means of comparing these three solutions,
let's find the interpolating polynomial (quadratic) passing 
through $(1,2)$, $(2,-1)$, and $(3,1)$.  You're invited to
check the following:

\noindent
\underbar{First method}:\quad
$10-{{21}\over2}\,x+{5\over2}\,x^2$.

\noindent
\underbar{Second method}:\quad
$(x-2)(x-3)+(x-1)(x-3)+{1\over2}(x-1)(x-2)$.

\noindent
\underbar{Third method}:\quad
$2-3(x-1)+{5\over2}(x-1)(x-2)$.

As you might have already surmised, Lagrange's method
is the easiest to apply in practice.  Let's set up
some notation and discuss the finer points of Lagrange's method.

Given $n+1$ distinct points $a\le x_0<x_1<\cdots<x_n\le b$
(sometimes called {\sl nodes\/}),
we first form the polynomials
$$W(x) \ = \ \prod_{i=0}^n(x-x_i)$$
and 
$$\ell_i(x) \ = \ \prod_{j\ne i}{{x-x_j}\over{x_i-x_j}} \ 
	= \ {{W(x)}\over{(x-x_i)\,W'(x_i)}}.$$
The {\sl Lagrange interpolation formula\/} is
$$L_n(f)(x) \ = \ \sum_{i=0}^nf(x_i)\,\ell_i(x).$$
That is, $L_n(f)$ is the unique polynomial in ${\cal P}_n$
that agrees with $f$ at the $x_i$'s.  In particular, notice
that we must have $L_n(p)=p$ whenever $p\in{\cal P}_n$.
In fact, $L_n$ is a {\sl linear projection\/} from
$C[\,a,b\,]$ onto ${\cal P}_n$.

Typically we're given (or construct) {\sl an array of nodes\/}:
$$X\qquad\left\{\quad\matrix{%
x_0^{(0)} &&&\cr
\noalign{\smallskip}
x_0^{(1)}&x_1^{(1)}&&\cr
\noalign{\smallskip}
x_0^{(2)}&x_1^{(2)}&\ x_2^{(2)}&\cr
\vdots &&&\ddots\cr
}\right.\qquad$$
and form the corresponding sequence of projections
$$L_n(f)(x) \ = \ \sum_{i=0}^nf(x_i^{(n)})\,\ell_i^{(n)}(x).$$
An easy (but admittedly pointless) observation is that
for a {\sl given\/} $f\in C[\,a,b\,]$ 
we can always find an array $X$ so that 
$L_n(f)=p_n^*$, the polynomial of best approximation
to $f$ out of ${\cal P}_n$ (since $f-p_n^*$ has $n+1$
zeros, we may use these for the $x_i$'s).  Thus,
$\Vert L_n(f)-f\Vert=E_n(f)\to0$ in this case.
However, the problem of convergence changes
character dramatically if we {\sl first choose\/} $X$
and then consider $L_n(f)$.  In general, there's no
reason to believe that $L_n(f)$ converges to $f$.
Quite the opposite:

\proclaim Theorem. \ {\rm(Faber)} \ 
Given any array $X$ of nodes in $[\,a,b\,]$,
there is some $f\in C[\,a,b\,]$ for which
$\Vert L_n(f)-f\Vert$ is unbounded.

The problem here has little to do with interpolation
and everything to do with projections:

\proclaim Theorem. \ {\rm(Kharshiladze, Lozinski)} \ 
For each $n$, let $L_n$ be a continuous, linear projection
from $C[\,a,b\,]$ onto ${\cal P}_n$.  Then, there is some
$f\in C[\,a,b\,]$ for which $\Vert L_n(f)-f\Vert$ is unbounded.

Evidently, the operators $L_n$ aren't positive (monotone),
for otherwise the Bohman-Korovkin theorem (and the fact
that $L_n$ is a projection onto ${\cal P}_n$\/) would imply 
that $L_n(f)$ converges uniformly to $f$ for every $f\in C[\,a,b\,]$.

The proofs of these theorems are long and difficult---we'll
save them for another day.  (Some of you will recognize the
Principle of Uniform Boundedness at work here.)
The real point here is that we can't have everything: A 
positive result about convergence of interpolation 
will require that we impose some extra conditions on 
the functions $f$ we want to approximate.  As a first
step in this direction, we prove that if $f$ has
sufficiently many derivatives, then the error
$\Vert L_n(f)-f\Vert$ can at least be measured.

\proclaim Theorem.
Suppose that $f$ has $n+1$ continuous derivatives on
$[\,a,b\,]$.  Let $a\le x_0<x_1<\cdots<x_n\le b$,
let $p\in{\cal P}_n$ be the polynomial
that interpolates to $f$ at the $x_i$'s, and let
$W(x)=\prod_{i=0}^n(x-x_i)$.  Then,
$$\Vert f-p\Vert \ \le \ 
	{1\over{(n+1)!}}\,\Vert f^{\,(n+1)}\Vert\,\Vert W\Vert.$$

\proof
We'll prove the Theorem by showing that, given $x$ in $[\,a,b\,]$, 
there is a $\xi$ in $(a,b)$ with
$$f(x)-p(x) \ = \ {1\over{(n+1)!}}\,f^{\,(n+1)}(\xi)\, W(x).\eqno(\ast)$$
If $x$ is one of the $x_i$'s, then both sides of this
formula are $0$ and we're done.  Otherwise, $W(x)\ne0$ and we
may set $\lambda=[f(x)-p(x)]/W(x)$.  Now consider
$$\varphi(t)=f(t)-p(t)-\lambda W(t).$$
Clearly, $\varphi(x_i)=0$ for each $i=0,1,\ldots,n$ and,
by our choice of $\lambda$, we also have $\varphi(x)=0$.
Here comes Rolle's theorem!  Since $\varphi$ has $n+2$
distinct zeros in $[\,a,b\,]$, we must have
$\varphi^{(n+1)}(\xi)=0$ for some $\xi$ in $(a,b)$.
(Why?)  Hence,
$$\openup1\jot\eqalign{
0=\varphi^{(n+1)}(\xi)&=f^{\,(n+1)}(\xi)-p^{(n+1)}(\xi)-\lambda W^{(n+1)}(\xi)\cr
	&=f^{\,(n+1)}(\xi)-\left({{f(x)-p(x)}\over{W(x)}}\right)\cdot(n+1)!
}$$
because $p$ has degree at most $n$ and $W$ is monic and
degree $n+1$.~\qed

\noindent
{\bf Observations}

\item{\bf 1.}
Equation $(\ast)$ is called the {\sl Lagrange formula with remainder}.

\item{\bf 2.}
The term $f^{\,(n+1)}(\xi)$ is actually a continuous function
of $x$.  That is, $[f(x)-p(x)]/W(x)$ is continuous; its value
at an $x_i$ is $[f\,'(x_i)-p\,'(x_i)]/W'(x_i)$ (why?)\ and
$W'(x_i)=\prod_{j\ne i}(x_i-x_j)\ne0$.

\item{\bf 3.}
On {\sl any\/} interval $[\,a,b\,]$, using {\sl any\/}
nodes, the sequence of Lagrange interpolating polynomials
for $e^x$ converge uniformly to $e^x$.  In this case, 
$$\Vert e^x-L_n(e^x)\Vert \ \le \ {c\over{(n+1)!}}\,(b-a)^n$$
where $c=\Vert e^x\Vert$ in $C[\,a,b\,]$.  The same would hold
true for any infinitely differentiable function satisfying, say,
$\Vert f^{\,(n)}\Vert\le M^n$ (any entire function, for example).

\item{\bf 4.}
On $[-1,1\,]$, the norm of $\prod_{i=1}^n(x-x_i)$ is minimized 
by taking $x_i=\cos((2i-1)\pi/2n)$, the zeros of the $n$-th Chebyshev
polynomial $T_n$.  (Why?)  As Rivlin points out, the zeros of
the Chebyshev polynomials are a {\sl nearly optimal\/} choice
for the nodes if good uniform approximation is desired.

The question of convergence of interpolation is actually very
closely related to the analogous question for the convergence
of Fourier series---and the answer here is nearly the same.
We'll have more to say about this analogy later.  First,
let's note that $L_n$ is continuous (bounded); this will
give us a first bit of insight into Faber's negative result.

\proclaim Lemma.
$\Vert L_n(f)\Vert\le\Vert f\Vert\,\bigl\Vert\sum_{i=0}^n|\ell_i(x)|\,\bigr\Vert$
for any $f\in C[\,a,b\,]$.

\proof
{\bf Exercise}.

The numbers $\Lambda_n=\bigl\Vert\sum_{i=0}^n|\ell_i(x)|\,\bigr\Vert$
are called the {\sl Lebesgue numbers\/} associated to this process.
It's not hard to see that $\Lambda_n$ is the smallest possible
constant that will work in this inequality (in other words, 
$\Vert L_n\Vert=\Lambda_n$\/).  Indeed, if 
$$\left\Vert\sum_{i=0}^n|\ell_i(x)|\,\right\Vert=\sum_{i=0}^n|\ell_i(x_0)|,$$
then we can find an 
$f\in C[\,a,b\,]$ with $\Vert f\Vert=1$ and $f(x_i)={\rm sgn}(\ell_i(x_0))$ 
for all $i$.  (How?)  Then, 
$$\Vert L_n(f)\Vert\ge |L_n(f)(x_0)|=\sum_{i=0}^n|\ell_i(x_0)|=\Lambda_n\Vert f\Vert.$$
As it happens,
$\Lambda_n\ge c\,\log n$ (this is where the hard work comes in);
in particular, $\Lambda_n\to\infty$ as $n\to\infty$.

A simple application of the triangle inequality will allow us
to bring $E_n(f)$ back into the picture:

\proclaim Lemma. \ {\rm(Lebesgue's theorem)} \ 
$\Vert f-L_n(f)\Vert \le (1+\Lambda_n)\,E_n(f)$,
for any $f\in C[\,a,b\,]$.

\proof
Let $p^*$ be the best approximation to $f$ out of ${\cal P}_n$.
Then, since $L_n(p^*)=p^*$, we have
$$\eqalignno{
\Vert f-L_n(f)\Vert \ &\le \ \Vert f-p^*\Vert+\Vert L_n(f-p^*)\Vert\cr
	&\le \ (1+\Lambda_n)\,\Vert f-p^*\Vert \ = \ (1+\Lambda_n)\,E_n(f).&\qed
}$$



\bye



%%  end of chapter-05.tex