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 (x₀,f₀),...,(x_n,f_n) is a set of points in the plane, with x₀ < x₁ < ... < x_n, we define a set of cubic polynomials p₁(x),...,p_n(x), which satisfy p_i(x_i) = f_i, p_i(x_i-1) = f_i-1, (so that p_i(x_i) = p_i+1(x_i) for i = 1,...,n-1), and the derivatives p�_i(x_i) = p�_i+1(x_i), and likewise the second derivatives satisfy p��_i(x_i) = p��_i+1(x_i). Then, the spline function f(x) is defined so that f(x) = p_i(x) if and only if x_i-1 � x � x_i.

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�₁(x₀) and p�_n(x_n) at the endpoints, or by requiring the second derivatives p��₁(x₀) and p��_n(x_n) 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 x_i, 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.