The Cubic Spline
A spline curve is a curve passing through a set of points which
is defined piecewise using simple formulas, so that it will appear
to be reasonably smooth overall. The most commonly used is the
cubic spline, which uses a piecewise cubic function.
In more detail, if (x0,f0),...,(xn,fn) is a set of points in the
plane, with x0 < x1 < ... < xn, we define a set of cubic polynomials
p1(x),...,pn(x), which satisfy pi(xi) = fi, pi(xi-1) = fi-1,
(so that pi(xi) = pi+1(xi) for i = 1,...,n-1), and the derivatives
p�i(xi) = p�i+1(xi), and likewise the second derivatives satisfy
p��i(xi) = p��i+1(xi). Then, the spline function f(x) is defined
so that f(x) = pi(x) if and only if xi-1 � x � xi.
Since there are n cubic polynomials, the coefficients give 4n unknown
variables. The above conditions, however, only give 4n-2 equations.
To determine a unique spline function, two extra conditions must be imposed.
Normally, this is done by specifying the slopes p�1(x0) and p�n(xn)
at the endpoints, or by requiring the second derivatives p��1(x0) and
p��n(xn) to equal zero.
The DotPlacer Applet (on this site) allows you to
place a set of points on the screen, and have it draw the cubic spline with
slope equal to zero at the endpoints.
You can even move the points around, and watch the curve change. Try it!
There exist quite efficient algorithms for finding the cubic spline.
In my applet, I find the slopes of the polynomials at the points xi,
by solving an n by n tridiagonal system of equations (via the Thomas
algorithm). This takes O(n) calculations. Once I have the slopes, it
is a simple matter to find the coefficients of the individual polynomials.
Since there are n polynomials, this again takes O(n) time. Plotting
the curve would take a longer time than actually finding it.
If the above information is not helpful, you may like to consider the book
displayed on the left. It is a somewhat technical book, but devoted entirely
to cubic splines in their many shapes and forms. It would be good for a person
seeking to seriously apply just the right spline function to a problem at hand.
The book on the right, with code samples and good explanations,
is regarded by many as one of the best books around for
applying java (and smalltalk) to numerical methods.
File translated from TEX by TTH, version 2.25.