Discrete spline interpolation explained

In the mathematical field of numerical analysis, discrete spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a discrete spline. A discrete spline is a piecewise polynomial such that its central differences are continuous at the knots whereas a spline is a piecewise polynomial such that its derivatives are continuous at the knots. Discrete cubic splines are discrete splines where the central differences of orders 0, 1, and 2 are required to be continuous.^[1]

Discrete splines were introduced by Mangasarin and Schumaker in 1971 as solutions of certain minimization problems involving differences.^[2]

Discrete cubic splines

Let x₁, x₂, . . ., x_n-1 be an increasing sequence of real numbers. Let g(x) be a piecewise polynomial defined by

g(x) = \begin{cases} g _{1(x)} & x<x _{1} \\ g _{i(x)} & x _{i-1} \le x < x _{i} for i = 2 , 3 , \ldots, n -1 \\ g _{n(x)} & x\ge x _{n-1} \end{cases}

where g₁(x), . . ., g_n(x) are polynomials of degree 3. Let h > 0. If

(g _{i+1} - g _{i)(x} _{i} + jh) =0 for j =-1 , 0 , 1 and i =1 , 2 ,\ldots, n -1

then g(x) is called a discrete cubic spline.^[1]

Alternative formulation 1

The conditions defining a discrete cubic spline are equivalent to the following:

g _{i+1} (x _{i-h)} = g _{i(x} _{i-h)} g _{i+1} (x _{i)} = g _{i(x} _{i)} g _{i+1} (x _{i+h)} = g _{i(x} _{i+h)}

Alternative formulation 2

The central differences of orders 0, 1, and 2 of a function f(x) are defined as follows:

D ^{(0)} f(x) = f(x) D ^{(1)} f(x) = (f(x + h) - f(x - h))/(2 h) D ^{(2)} f(x) = (f(x + h) -2 f(x) + f(x - h))/(h ^{2})

The conditions defining a discrete cubic spline are also equivalent to^[1]

D ^{(j)} g _{i+1} (x ^{(j)} _{i) = D} g _{i(x} _{i)} for j =0 , 1 , 2 and i =1 , 2 , \ldots, n -1 .

This states that the central differences

D ^{(j)} g(x) are continuous at x_i.

Example

Let x₁ = 1 and x₂ = 2 so that n = 3. The following function defines a discrete cubic spline:^[1]

g(x) = \begin{cases} x ^{3} & x< 1 \\ x ^{3} - 2 (x -1 )((x -1 ) ^{2-h} ^{2)} & 1 \le x < 2 \\ x ^{3} - 2 (x -1 )((x -1 ) ^{2-h} ^{2)+(x-2)((x-2)} ^{2-h} ^{2)} & x \ge 2 \end{cases}

Discrete cubic spline interpolant

Let x₀ < x₁ and x_n > x_n-1 and f(x) be a function defined in the closed interval [''x''₀ - h, ''x''_''n'' + h]. Then there is a unique cubic discrete spline g(x) satisfying the following conditions:

g(x _{i)} = f(x _{i)} for i =0 , 1 ,\ldots, n. D ^{(1)} g _{1(x} _{0)} = D ^{(1)} f(x _{0).} D ^{(1)} g _{n(x} _{n)} = D ^{(1)} f(x _{n).}

This unique discrete cubic spline is the discrete spline interpolant to f(x) in the interval [''x''₀ - h, ''x''_''n'' + h]. This interpolant agrees with the values of f(x) at x₀, x₁, . . ., x_n.

Applications

• Discrete cubic splines were originally introduced as solutions of certain minimization problems.^{[1] [2]}
• They have applications in computing nonlinear splines.^{[1] [3]}
• They are used to obtain approximate solution of a second order boundary value problem.^[4]
• Discrete interpolatory splines have been used to construct biorthogonal wavelets.^[5]

Notes and References

1. Tom Lyche. Discrete Cubic Spline Interpolation. BIT. 1979. 16. 3. 281–290. 10.1007/bf01932270. 122300608 .
2. Mangasarian, O. L. . Schumaker, L. L.. Discrete splines via mathematical programming. SIAM J. Control. 1971. 9. 2. 174–183. 10.1137/0309015.
3. Michael A. Malcolm. On the computation of nonlinear spline functions. SIAM Journal on Numerical Analysis. April 1977. 14. 2. 254–282. 10.1137/0714017.
4. Fengmin Chen, Wong, P.J.Y.. Solving second order boundary value problems by discrete cubic splines. Control Automation Robotics & Vision (ICARCV), 2012 12th International Conference. Dec 2012. 1800–1805.
5. Averbuch, A.Z., Pevnyi, A.B., Zheludev, V.A.. Biorthogonal Butterworth wavelets derived from discrete interpolatory splines. IEEE Transactions on Signal Processing. Nov 2001. 49. 11. 2682–2692. 10.1109/78.960415. 10.1.1.332.7428.