Copyright (c) Susan Laflin. August 1999.

Spline Interpolation

References: "text on splines by Booth for a discussion of theory - get ref from home.
Rogers and Adams section 5.3 to 5.5 for derivation of cubic spline equation.
Williams "Numerical Computation" for the Gaussian Elimination Method.

This is a special case of piece-wise interpolation. In this case, no attempt is made to calculate the values of s[i] from small numbers of points along the curve. Instead the whole set of points is used, and it is assumed that both the first and the second derivative are continuous at the points x[i]. These two conditions at the `knot points' (the points where two cubics join) allow us to derive a recurrance relation connecting s[i-1], s[i] and s[i+1] and this can be used to obtain a set of n-2 simultaneous linear equations for the s[i]. Two extra conditions relating to the end points are needed to give n equations which can be solved for the n values of s[i].

This method may be used to fit a cubic to each interval, with the cubics joining smoothly at the `knot-points'. The exact form of the equation used for this method depends on the shape of the curve to be interpolated. If one variable, say x, is strictly increasing leading to a curve as shown in (a), then the form y = f(x) may be used. For any chosen value of x, there is only one value of y but a given value of y will have several values of x as the curve moves up and down. The case where the other variable, y, is strictly increasing and so the form x = f(y) is appropriate is shown in (b). In this case, some values of x correspond to several values of y as the curve moves from side to side.

The most complicated case is shown in (c) and in this case you will have to use the parametric forms y = f1(s) and x = f2(s). The parameter s has to be strictly increasing as you move along the curve, so one possible measure is the arc-length (i.e. distance along the curve). When relating this method to the three dimensional case, students should remember that one set of cubics is obtained for y = F(x) and a second set is obtained for z = G(x). Alternatively there may be some curves for which we need to fit x=F1(t), y=F2(t) and z=F3(t) with the parameter t chosen as a variable, such as arc length, which increases steadily from one end of the curve to the other.

Odd-Degree Splines.

The cubic is a special case of an odd-degree spline. Now let us consider the general polynomial spline of of degree 2n-1 (n=2 for a cubic) over a mesh of N+1 points a = x0 < x1 < ..... < xN = b. In this case, there are 2nN constants to be calculated. (A polynomial of degree 2n-1 has 2n constants and N+1 points, which implies N intervals and so N polynomials.)

1. Continuity.

We require derivatives of orders 0, 1, ..., 2n-2 to be continuous at the N-1 interior mesh points. This accounts for (2n-1)(N-1) degrees of freedom. For a cubic, n=2. Thus derivatives of orders 0, 1, and 2 must be continuous and this accounts for 3(N-1) degrees of freedom.

2. Interpolation.

We require interpolation at the N+1 mesh points and this accounts for N+1 degrees of freedom. (We could require some other condition instead of interpolation.)

So of the 2nN degrees of freedom required, we have supplied
(2n-1)(N-1) + N+1 = 2nN -2n -N +1 +N +1 = 2nN -2(n-1)

3. End-Conditions.

If we impose n-1 end-conditions at each end of the curve (points x0 and xN), this will account for the remaining degrees of freedom. For a cubic, n=2 and so this requires one end-condition at each end of the curve.

Even-degree splines.

By contrast, let us now consider the case of even-degree splines. Consider a general polynomial spline of degree 2n over a mesh of N intervals. In this case, there are (2n+1)N constants to be determined.

1. Continuity.

We require derivatives of orders 0,1,....,2n-1 to be continuous at the N-1 interior points. This accounts for 2n(N-1) degrees of freedom.

2. Interpolation.

We may require interpolation at N points, one in each interval. This accounts for N degrees of freedom.

3. End-Conditions.

We may impose n end-conditions at each end of the curve. This accounts for 2n degrees of freedom.

So we have (2n+1)N + N + 2n = (2n+1)N degrees of freedom, which is sufficient for full definition of the even-degree spline.

The simplest case is a quadratic spline, where n=1 and so we have derivatives of orders 0 and 1 continuous at the knot points and 1 end-condition at each end of the curve.

Cubic Splines

We need to interpolate the N+1 points x0, x1,...., xN by means of cubic splines. This gives N cubics over the N intervals. For the cubic spline, let us choose the knot-points (at which the curves meet) as the points xi and also choose these as the interpolation points (at which we specify the values of y (and z in three dimensions)). Let the equation of the cubic be

		Pi = ai t^3 + bi t^2 + ci t + di 
where 		 t = x - xi 
Then the derivatives are
		dPi/dt (= dPi/dx) =  3 ai t^2 + 2 bi t + ci 
		d^2Pi/dt^2 (= d^2P/dx^2) = 6 ai t + 2 bi 
Continuity conditions: 
		 P{i-1}(xi) = Pi (xi)
		dP{i-1}(xi)/dx = dP{i-1}( xi)/dx
		d^2P{i-1}(xi)/dx^2 = d^2 Pi (xi)/dx^2
for all i = 1,2,...,N-1. 

Interpolation. 
		Pi (xi) = yi 

End-Conditions.

Two end-conditions are required. If we call the values of the first derivative, at the points xi, f(i), then the end-conditions may be expressed as values for f(0) and f(N+1).

From these conditions, we may obtain a recurrance relation connecting f(i-1), f(i) and f(i+1). This, together with the end-conditions, gives a tri-diagonal set of equations which may be solved for the f(i), and hence the coefficients of all the cubics may be evaluated.