\section{CUBIC SPLINES (an elementary approach)}
The Weierstrass Approximation Theorem says that polynomials converge to
$f\in C[a,b]$, but it does not say that interpolating polynomials
converge. The Bernstein and Runge examples show that interpolating
polynomials of higher and higher degree are not necessarily more
accurate. Consider the error in polynomial interpolation: $$
f^{(n+1)}(\xi)\prod_{i=0}^n (x-x_i)/(n+1)!.$$ Since derivatives of $f$
are usually an unknown quantity, the surest way to make the error small
is to make the interval $[a,b]$ containing $x_0$, $\ldots$, $x_n$ small.
Now the original interval $[a,b]$ is usually large, but one can
interpolate on small subintervals, getting a {\it piecewise
polynomial\/} approximation. The simplest case is a piecewise linear
approximation, which is just a broken line.

\noindent{\bf Piecewise Hermite cubic}. $f$ is to be approximated by a
piecewise cubic polynomial $g(x)$ with the properties that
$g(x_i)=f(x_i)$, $g'(x_i)=f'(x_i)$, and $g(x)$ is a cubic polynomial
$P_i(x)$ on each interval $[x_i,x_{i+1}]$, where $x_0<x_1<\cdots<x_n$.
Newton's form for the Hermite cubic $P_i(x)$ in $[x_i,x_{i+1}]$
interpolates at $x_i$, $x_i$, $x_{i+1}$, $x_{i+1}$ and is given by
$$P_i(x)=f[x_i]+f[x_i,x_i](x-x_i) +f[x_i,x_i,x_{i+1}](x-x_i)^2 +
f[x_i,x_i,x_{i+1},x_{i+1}](x-x_i)^2(x-x_{i+1}).$$
Let $f_i=f(x_i)$, $s_i=f'(x_i)$, and rewrite $P_i(x)$ in terms of powers
of $(x-x_i)$: $$P_i(x)=c_{1,i} + c_{2,i}(x-x_i) + c_{3,i}(x-x_i)^2 +
c_{4,i}(x-x_i)^3,$$ where $$c_{1,i}=f_i,\qquad c_{2,i}=s_i,\qquad
c_{3,i}={f[x_i,x_{i+1}]-s_i\over\Delta x_i} - c_{4,i}\Delta x_i,\qquad
c_{4,i}={s_i+s_{i+1}-2f[x_i,x_{i+1}]\over(\Delta x_i)^2}.$$

Note that $g(x)$ is $C^1$ on $[x_0,x_n]$, since
$P_i'(x_{i+1})=P_{i+1}'(x_{i+1})=s_{i+1}$. $g(x)$ matches both $f$ and
$f'$, so it is a good approximation to $f$, but it is not as ``smooth''
as it could be. By choosing the $s_i$, it is possible to construct a
piecewise cubic which is $C^2$ and interpolates $f$. A $C^2$ curve is
esthetically nicer than a $C^1$ curve; draftsmen can even ``see'' $C^2$
and $C^3$ discontinuities.

A $C^2$ piecewise cubic polynomial is called a {\it cubic spline}. In
general,

\noindent{\bf Definition}. A spline of degree $m$ with nodes $x_0<x_1<
\cdots<x_n$ is a $C^{m-1}$ function which is a polynomial of degree $\le
m$ in $(-\infty,x_0)$, $(x_0,x_1)$, $\ldots$, $(x_{n-1},x_n)$,
$(x_n,\infty)$. A natural spline of degree $2k+1$ is a spline of degree
$2k+1$ which is a polynomial of degree $\le k$ in $(-\infty,x_0)$ and
$(x_n,\infty)$.

The basic result is

\noindent{\bf Theorem}. Let $0\le k\le n$, $x_0<x_1<\cdots<x_n$. Then
for any set of values $y_0$, $\ldots$, $y_n\;\exists$ a unique natural
spline $S(x)$ of degree $2k+1$ with nodes $x_0$, $\ldots$, $x_n$ such
that $S(x_i)=y_i$ for $i=0,1,\ldots,n$.

Proof. Greville, {\sl Theory and Applications of Spline Functions},
1969.

\vfil\goodbreak
\medskip\hrule\medskip\noindent{\bf Construction of a cubic spline
(using first derivatives)}: In each interval $[x_i,x_{i+1}]$ the spline
$g(x)$ has the form $P_i(x)=c_{1,i} + c_{2,i}(x-x_i) + c_{3,i}(x-x_i)^2
+ c_{4,i}(x-x_i)^3$. The $C^2$ requirement means
$P_{i-1}''(x_i)=P_i''(x_i) \Leftrightarrow 2c_{3,i-1} + 6c_{4,i-1}
\Delta x_{i-1}= 2c_{3,i}$. Using the expressions for $c_{3,i}$,
$c_{4,i}$ in terms of $f_i$, $s_i$ (the $s_i$ are now unspecified), this
becomes $$\Delta x_i s_{i-1} + 2(\Delta x_{i-1}+\Delta x_i)s_i + \Delta
x_{i-1}s_{i+1} = 3\bigl(\Delta x_{i-1}f[x_i,x_{i+1}] + \Delta x_i
f[x_{i-1},x_i]\bigr),\; i=1,\ldots,n-1.$$
These are $n-1$ linear equations in the $n+1$ unknowns $s_0$, $\ldots$,
$s_n$. By specifying $s_0$, $s_n$, these become $n-1$ equations in $n-1$
unknowns, which have a unique solution since the coefficient matrix 
$$\pmatrix{2(\Delta x_0+\Delta x_1)&\Delta x_0&0&0&\cdots\cr
\Delta x_2&2(\Delta x_1+\Delta x_2)&\Delta x_1&0&\cdots\cr
0&\Delta x_3&2(\Delta x_2+\Delta x_3)&\Delta x_2&\cdots\cr
0&0&\Delta x_4&2(\Delta x_3+\Delta x_4)&\ddots\cr
\vdots&\vdots&\vdots&\ddots&\ddots\cr}$$
is strictly row diagonally dominant.

In summary, given $x_0<x_1<\cdots<x_n$ and $f(x_i)$, $i=0$, 1, \dots,
$n$: \item{(1)}Choose $s_0$, $s_n$ (ideally $s_0=f'(x_0)$,
$s_n=f'(x_n)$, the {\it complete spline interpolant\/}).
\item{(2)}Solve the tridiagonal system of linear equations for $s_1$,
$\ldots$, $s_{n-1}$.
\item{(3)}Construct the piecewise Hermite cubic $g(x)$ using $f(x_i)$
and $s_i$.
\item{(4)}Then $g(x)$ is a cubic spline on $[x_0,x_n]$ interpolating $f$
at $x_0$, $\ldots$, $x_n$.

\medskip\hrule\medskip\noindent{\bf Construction of a cubic spline
(using second derivatives)}: Let $g(x)$ be a piecewise cubic given by
$P_i(x)$ on $[x_i,x_{i+1}]$, with $g''(x_i\pm)=s_i$, $i=0$, 1, \dots,
$n$. Note that here the unknowns $s_i$ are second derivatives. Since
$P_i(x)$ is a cubic, $P_i''(x)= s_i(x_{i+1}-x)/\Delta x_i +
s_{i+1}(x-x_i)/\Delta x_i$ is linear. Integrating twice and requiring
that $P_i(x_i)=f(x_i)=f_i$, $P_i(x_{i+1})=f(x_{i+1})=f_{i+1}$ yields
$$\eqalign{
P_i(x)={s_i\over6\Delta x_i}(x_{i+1}-x)^3 &+ {s_{i+1}\over6\Delta
x_i}(x-x_i)^3 + \left({f_{i+1}\over\Delta x_i} - {s_{i+1}\Delta x_i
\over6}\right)(x-x_i)\cr
&{}+ \left({f_i\over\Delta x_i} - {s_i\Delta x_i
\over6}\right)(x_{i+1}-x),\qquad i=0,1,\ldots,n-1.\cr}$$
So far the pieces $P_i(x)$ and their second derivatives match at the
nodes. The first derivatives must also match, so another condition is
$P_{i-1}'(x_i)=P_i'(x_i)$, $i=1$, $\ldots$, $n-1$. This results in the
following system of $n-1$ equations in the $n+1$ unknowns $s_0$,
$\ldots$, $s_n$: $$\Delta x_{i-1}s_{i-1} + 2(\Delta x_{i-1} +\Delta x_i)
s_i + \Delta x_is_{i+1} =6\bigl(f[x_i,x_{i+1}] -f[x_{i-1},x_i]\bigr),
\qquad i=1,\ldots,n-1.$$
Choosing $s_0$ and $s_n$ uniquely determines the other $s_i$, since the
coefficient matrix of the resulting linear system is strictly row
diagonally dominant. The choice $s_0=s_n=0$ gives a {\it natural
spline}.

In summary, given $x_0<x_1<\cdots<x_n$ and $f(x_i)=f_i$, $i=0$,
1, \dots, $n$:
\item{(1)}Choose $s_0=s_n=0$.
\item{(2)}Solve the tridiagonal linear system for $s_i$, $i=1$,
$\ldots$, $n-1$.
\item{(3)}Using these $s_i$, $g(x)$ given by $P_i(x)$ in
$[x_i,x_{i+1}]$ is the unique natural cubic spline with nodes $x_0$,
$x_1$, $\ldots$, $x_n$ interpolating $f$ at $x_0$, $x_1$, $\ldots$,
$x_n$.

\medskip\hrule\medskip\noindent{\bf Theorem}. Let $f\in C^2[x_0,x_n]$,
$x_0<x_1<\cdots<x_n$, $S(x)$ be the natural cubic spline interpolating
$f$ at $x_0$, $\ldots$, $x_n$, and let $g\in C^2[x_0,x_n]$ also
interpolate $f$ at $x_0$, $\ldots$, $x_n$. Then $$
\int_{x_0}^{x_n}\bigl(g''(x)\bigr)^2 dx \ge\int_{x_0}^{x_n}\bigl(
S''(x)\bigr)^2 dx$$ with equality if and only if $g=S$.

Proof. $\int\bigl[g''(x)-S''(x)\bigr]^2dx = \int\bigl(g''(x)\bigr)^2dx -
2\int\bigl[g''(x)-S''(x)\bigr]S''(x)dx - \int\bigl(S''(x)\bigr)^2dx$.
The inequality will follow if the middle term is zero.
$$\eqalign{ \int_{x_0}^{x_n} (g''-S'')S''&= \sum_{i=0}^{n-1}
\int_{x_i}^{x_{i+1}} (g''-S'')S'' \cr
&=\sum_{i=0}^{n-1} S''(x)\bigl(g'(x)-S'(x)\bigr)\Big|_{x_i}^{x_{i+1}}
- \sum_{i=0}^{n-1} \int_{x_i}^{x_{i+1}} \bigl(g'(x)-S'(x)\bigr)
S'''(x)dx \cr &= S''(x_n)\bigl(g'(x_n)-S'(x_n)\bigr)
- S''(x_0)\bigl(g'(x_0)-S'(x_0)\bigr)\cr
&\hskip40pt{}- \sum_{i=0}^{n-1} \alpha_i
\int_{x_i}^{x_{i+1}} \bigl(g'(x)-S'(x)\bigr)dx\cr }$$
since $S'''(x)$ is a constant $\alpha_i$ on $(x_i,x_{i+1})$. 
$$\int_{x_i}^{x_{i+1}} \bigl(g'(x)-S'(x)\bigr)dx =
g(x)-S(x)\Big|_{x_i}^{x_{i+1}} =0$$ since both $g$ and $S$ interpolate
$f$ at $x_0$, $\ldots$, $x_n$. Also $S''(x_0)=S''(x_n)=0$ since $S$ is a
natural cubic spline. Hence $\int\bigl(g''-S''\bigr)^2 = \int(g'')^2 -
\int(S'')^2\ge0 \Rightarrow \int(g'')^2 \ge \int(S'')^2$.

There is equality $\Leftrightarrow \int\bigl(g''-S''\bigr)^2 = 0
\Leftrightarrow g''-S''=0$ since $g''$ and $S''$ are continuous. Now
$g''=S'' \Rightarrow g(x)=S(x)+c_1x+c_2$. But $g(x_0)=S(x_0)$,
$g(x_1)=S(x_1)$, $x_1\ne x_0$ $\Rightarrow c_1x_0+c_2=0$, $c_1x_1+c_2=0
\Rightarrow c_1=c_2=0 \Rightarrow g(x)=S(x)$.\QED

\noindent{\bf Corollary}. Let $f\in C^2[x_0,x_n]$,
$x_0<x_1<\cdots<x_n$, $S(x)$ be the complete cubic spline interpolant
to $f$ at $x_0$, $\ldots$, $x_n$, with $S'(x_0)=f'(x_0)$,
$S'(x_n)=f'(x_n)$, and let $g\in C^2[x_0,x_n]$ also interpolate $f$ at
$x_0$, $\ldots$, $x_n$, with $g'(x_0)=f'(x_0)$, $g'(x_n)=f'(x_n)$.
Then $$ \int_{x_0}^{x_n}\bigl(g''(x)\bigr)^2 dx
\ge\int_{x_0}^{x_n}\bigl( S''(x)\bigr)^2 dx$$ with equality if and only
if $g=S$.

\vfil\goodbreak
\noindent{\bf Theorem}. Let $f\in C^2[a,b]$, $S(x)$ be the natural
cubic spline interpolating $f$ at $a=x_0<x_1<\cdots<x_n=b$, and
$h=\max\limits_{0\le i\le n-1} (x_{i+1}-x_i)$. Then $$\mn{f-S}\le
h^{3/2}\tn{f''}\qquad\hbox{and} \qquad \mn{f'-S'}\le h^{1/2}\tn{f''}.$$

Proof. Let $x\in[a,b]$. $x$ is in some $[x_i,x_{i+1}]$, and since
$f(t)-S(t)$ is zero at $x_i$ and $x_{i+1}$, $f'(z)-S'(z)=0$ for some
$z\in(x_i,x_{i+1})$ by Rolle's Theorem. Then $$\int_z^x \bigl[f''(t)
-S''(t)\bigr]dt = f'(t)-S'(t)\Big|_z^x = f'(x)-S'(x).$$ Using the
Cauchy-Schwarz Inequality, $$\eqalign{ |f'(x)-S'(x)| &= \left| \int_z^x
\bigl[f''(t)-S''(t)\bigr]\cdot1 dt\right|
\le\left| \int_z^x \bigl[f''(t)-S''(t)\bigr]^2dt\right|^{1/2} \left|
\int_z^x 1^2dt\right|^{1/2} \cr
&\le\left| \int_z^x \bigl[f''(t)-S''(t)\bigr]^2dt\right|^{1/2}
h^{1/2}.\cr}$$ From the previous theorem, with $g=f$, $\int_a^b 
\bigl[f''(t)-S''(t)\bigr]^2dt = \int_a^b f''(t)^2dt - \int_a^b
S''(t)^2dt \le\int_a^b f''(t)^2dt$. Since $z$ and $x$ are in $[a,b]$,
$$|f'(x)-S'(x)|\le\left(\int_a^b f''(t)^2dt\right)^{1/2} h^{1/2} =
\tn{f''}h^{1/2}.$$

Finally, $f(x)-S(x)=\int_{x_i}^x \bigl[f'(t)-S'(t)\bigr]dt$, so $$
\eqalign{ |f(x)-S(x)| &= \left|\int_{x_i}^x \bigl[f'(t)-S'(t)\bigr]dt
\right| \cr &\le\int_{x_i}^x \max_{[a,b]}|f'(\tau)-S'(\tau)|dt =
\max_{[a,b]}|f'(\tau)-S'(\tau)|(x-x_i)\cr
&\le\tn{f''}h^{1/2}(x-x_i) \le\tn{f''}h^{3/2}.\cr}$$ \QED

\medskip\hrule\medskip\noindent{\bf Theorem} (deBoor, 1978). Let $f\in
C^4[a,b]$, $S(x)$ be the complete cubic spline interpolating $f$ at
$a=x_0<x_1<\cdots<x_n=b$, $S'(x_0)=f'(x_0)$, $S'(x_n)=f'(x_n)$, and
$h=\max\limits_{0\le i\le n-1}(x_{i+1}-x_i)$.  Then
$$\mn{f^{(k)}-S^{(k)}}={\cal O}\bigl(h^{4-k}\bigr), \qquad k=0,1,2.$$

\vfil\eject