ChapterZero

Note: I spent a weekend writing a simple implementation of the inefficent spline paradigm described here, in PyGTK; check it out: get the python spline fitting and evaluation code, and PyGTK stub interface. The feature set is small: add new points in the interface by left clicking, and middle click to clear.

Here’s the motivating problem: you have points observed at times – say, samples of the position function of a particle tracing out a path– and you’d like to fit a smooth curve to these points. An intuitive approach to this problem is to represent parametrically, and fit smooth curves to the abscissa and ordinates; this reduces the problem to that of fitting curves to points, which we can solve in many different ways (Lagrange interpolation, etc.) One approach which has several desirable features is that of interpolating splines.

Interpolating splines can be developed under the energy minimization paradigm, in an interesting manner. Under this paradigm, the problem is to, given the points find a smooth function satisfying:

where , the energy function, represents some measure of the undesirability of using the function to represent . The energy function has two components, , the internal energy, which corresponds to a measure of the desirability of , and , the external energy, which corresponds to the compatibility of and . To develop splines, we use

that is, we look for functions whose variation (measured as the norm of their -th derivative) is minimal, and which fit the data points in a least means squared sense. The parameter controls the relative importance we assign to and ; in what follows, when it matters, we assume is fixed.

Here’s the first amazing result: Such exist, and furthermore

1. The curve is a polynomial of degree on each interval
2. At each point , the first derivatives of are continuous, while the -th can be discontinuous.
3. In each of the intervals and ,

I’d love to see a proof of this theorem– I suspect it uses the variational calculus. Certainly (ii) and (iii) are obvious, but (i) is not to me.

Now, we can define splines:

A curve that satisfies (i) and (ii) with is called a cubic or bending spline with knots . If it also satisfies (iii), it is called a natural cubic spline. An interpolation spline is a cubic spline which passes through the points .

So the above theorem guarantees the existence of interpolating cubic splines. But we can do even better, with the next theorem, which shows us how to construct such splines:

Let be values set according to . There is only one natural spline interpolating these values.

Proof:
By (i) above, on each interval , has the form

For convenience, set and , then you can show

and from (ii) above, we have for , giving

This gives us equations we can solve for the unknowns (we know by (iii) ); these relations can be written in the linear system , where is a tridiagonal matrix, is a tridiagonal matrix, is the -vector of 2nd derivatives of , and is the -vector of the values should interpolate. This system can be solved for , and these values can be used to calculate the

See my code for implementation of this scheme for 2d interpolation. At some point, I’m going to show how the energy minimization scheme can be adapted from interpolation to smoothing.