How do you fit the smoothest curve through a set of points? Suppose you have a set of increasing x values x1, x2, x3, … , xn and a corresponding set of y values y1, y2, y3, … , yn. You want to find the smoothest function f(x) such that f(xi) = yi for i = 1, 2, 3, …, n. The smoothest curve depends on how you define smoothness, but we’ll develop a common definition that leads to a nice solution.
Our definition of smoothness starts with the second derivative. If a curve is flat, it has zero second derivative. If the curve has a sharp kink, the second derivative will be high there. We want to add up the smoothness over the entire curve, so we’ll integrate the second derivative. But that won’t quite work. Second derivatives can be positive or negative, and a curve could have several sharp bends and still have average second derivative zero. Sharp bends in one direction could be canceled out by equally sharp bends in the opposite direction. So we look at the square of the second derivative. That gives a positive number whether the curve bends up or down. Also, squaring small numbers makes them smaller and squaring big numbers makes them bigger. So squaring the second derivative will penalize sharp bends and be more forgiving of small bends. In summary, we’ll measure the smoothness of a function f(x) over an interval [a, b] by the following integral.
Using the above measure of smoothness, the smoothest function interpolating a set of values is a natural cubic spline. I’ll explain this definition from right to left: first I’ll explain what a spline is, then a cubic spline, then a natural cubic spline. Cubic splines are very commonly used in graphical applications.
A spline is a function made by piecing together other functions. Most splines are piecewise polynomials, though their are other kinds of splines, such as trigonometric splines that are piecewise trig functions. The term “spline” comes from a mechanical device for drawing curves.
A cubic spline is formed by piecing together cubic polynomials. That is, the restriction of f to any interval between two x-values, from xi to xi+1 is a cubic polynomial. These piecewise cubic polynomials are formed by making their first and second derivatives match where they join. This makes a cubic spline curve appear very smooth.
Say we have n values of x and y. That means we have n-1 cubic polynomials to fit together: one over [x1, x2], another over [x2, x3], etc. Each cubic polynomial has 4 coefficients, and so we have a total of 4(n-1) coefficients to determine. At each interior node, i.e. the values from x2 to xn-1, there are four constraints. At each such xi we have
- The polynomial on the left side must have value yi.
- The polynomial on the right side must have value yi.
- The first derivatives of the left and right polynomials must match.
- The second derivatives of the left and right polynomials must match.
This gives us a total of 4(n-2) interior constraints. The values at the left and right ends are specified too, i.e. f(x1) = y1 and f(xn) = yn. This adds up to 4n-6 constraints on 4n-4 coefficients. We need two more constraints to have as many equations as unknowns. There are various ways to add these constraints but a natural cubic spline imposes the requirement that the second derivatives should be zero at the ends, i.e. f”(x1) = f”(xn) = 0.
Finding the coefficients for a natural cubic spline with n nodes requires solving 4n – 4 equations in as many unknowns. There is a unique solution to this system of equations, and the system has a special structure that can be solved very quickly.
One thing I find interesting about natural cubic splines is how a fairly ad hoc procedure — patching cubic polynomials — leads to the solution to an elegant minimization problem.
* * *