MATH/APPM 4650 Notes: February 18, 2008

MATH/APPM 4650
Class notes, February 20

Cubic splines, and interpolation review

Recall that we never want to use a high-order interpolating polynomial for data that is not known to high accuracy.

If the data is experimental and has some error, we should use regression (Chapter 8).

Suppose the data does not have any error, but we do not know it to high accuracy.

Typical example:
We have several points on a graph; the points are correct and known to one decimal place. Draw a curve passing through them.

A high-order polynomial will tend to magnify very slight errors in these points. It will also tend to oscillate a lot between the values.

Instead, we use a low-order polynomial, but we use a different polynomial between each two points.

Example (from before):
We have five points, (-1,5), (1,6), (1.5, 4), (2,-2), and (4,-1).
We saw that the fourth-order interpolating polynomial looked pretty strange.

A fourth-order interpolating polynomial for five points.
Instead, the idea is to use piecewise-defined polynomials.

We could do piecewise-linear. If we do that, we can certainly connect the dots, but the graph will have lots of kinks.

Connecting the dots with a piecewise linear function.

To improve things, we could do piecewise-quadratic.

At first glance, you'd think there aren't enough parameters to get this to work.
How do we know what parabola to draw between each two points?

However, we can use the extra freedom to match up the derivatives.
First parabola from -1 to 1: a₀ x² + b₀ x + c₀. Two equations come from the fact that it must pass through (-1,5) and (1,6):

a₀ - b₀ + c₀ = 5
a₀ + b₀ + c₀ = 6

Similarly we have for the second parabola from 1 to 1.5: a₁ x² + b₁ x + c₁. Two equations come from passing through (1,6) and (1.5,4).

a₁ + b₁ + c₁ = 6
2.25 a₁ + 1.5 b₁ + c₁ = 4

Finally we get an equation by matching up the derivatives at x=1.

2 a₀ + b₀ = 2 a₁ + b₁.

If we keep doing this, we will end up with four parabolas (thus twelve unknown coefficients).
Eight equations come from making them pass through the points.
Three equations come from matching the derivatives at the points.
One coefficient is unknown! So we actually have a whole family of parabolas.

Connecting the dots with a bunch of quadratic splines.
We could try to figure out an endpoint condition to determine the quadratic spline, but since nobody ever uses quadratic splines in real life, we'll just move on.

Observe that even though the quadratic spline curve looks smooth, it's really not.
Here are the graphs of the derivatives of the quadratic splines.

The derivative of the family of quadratic splines.
Imagine you're in a car, and the quadratic spline is the graph of your position. Obviously position is continuous, and its derivative (velocity) is also continuous. (Unless you crash into a wall.)
But the acceleration will not be continuous. This corresponds to the driver constantly slamming on the brakes or jamming down the gas pedal. Rather uncomfortable!

For a cubic spline, we use a third-order polynomial. This gives us four coefficients for each cubic, so 16 in all (if there are five points).
We have 8 equations which come from matching the points.
We get 3 more equations by matching the first derivative at each point.
Then we can get 3 equations by matching the second derivative at each point.
This gives 14 equations in all for 16 coefficients. Two coefficients are free.
The book suggests specifying them in various ways.

"Natural" cubic spline: require that the second derivative is zero at the left and right endpoint.
"Clamped" cubic spline: require that the first derivative matches known conditions at the left and right endpoint.


A natural cubic spline.	A clamped cubic spline. Derivatives at endpoints set to zero.

In practice, other methods are also used.

"Not-a-knot": Match the third derivatives at the points second-from-the-left and second-from-the-right. (This is what MATLAB prefers.)
"Periodic": The first and second derivatives at the left are the same as those on the right.

Commands: Each software package has several spline commands.

Maple has a package called "CurveFitting" which is loaded using
with(CurveFitting): Once you've loaded that package, you can access a customized spline command using, e.g.,
myspliney := Spline(xvals,yvals,x,degree=3,endpoints='natural');
MATLAB has a "spline" command which uses the "not-a-knot" condition.
To use other commands, you need the "Spline Toolbox." If you have it, you can customize your splines using, e.g.,
myspliney = csape(xvals,yvals,'second')
Mathematica...
Um, yeah. No splines.

It is likely that functions for spline interpolation will be added for some future version of Mathematica. In the meantime, if you need spline interpolation, we recommend that you look on MathSource for spline interpolation programs written by other users, or consider writing a short spline interpolation function of your own.
Oh well!

General review of interpolation:

In principle it is easy to write down an interpolating polynomial, using the Lagrange formula. In practice it's a slow algorithm.
Never use a high-order interpolating polynomial unless you know the function exactly. If data has any error at all, use regression instead.
Interpolating polynomials tend to do worse near endpoints, so you should add extra sampling points near there.
Divided differences, combined with Horner's method, gives a very efficient way to compute interpolating polynomials.
Both the Lagrange polynomial and the Taylor polynomial are special cases of osculating polynomials, obtained by specifying some number of derivatives at some number of points.
The Hermite polynomial (which matches both function values and derivative values) can be computed by just taking limits in the divided difference algorithm (replacing some first-order divided differences with derivatives).
If you know some points are accurate, but you don't have high precision, cubic splines are the best method of approximation. They generate curves that have continuous second derivatives, and minimize oscillations.