Discrete spline interpolation

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}\leq x<x_{i}{\text{ for }}i=2,3,\ldots ,n-1\\g_{n}(x)&x\geq 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{\text{ for }}j=-1,0,1{\text{ 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)={\frac {f(x+h)-f(x-h)}{2h}}

D^{(2)}f(x)={\frac {f(x+h)-2f(x)+f(x-h)}{h^{2}}}

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

D^{(j)}g_{i+1}(x_{i})=D^{(j)}g_{i}(x_{i}){\text{ for }}j=0,1,2{\text{ 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\leq x<2\\x^{3}-2(x-1)((x-1)^{2}-h^{2})+(x-2)((x-2)^{2}-h^{2})&x\geq 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}){\text{ 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]

References

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Tom-1] Tom Lyche (1979). "Discrete Cubic Spline Interpolation". BIT. 16 (3): 281–290. doi:10.1007/bf01932270.

[Mangasarin-2] Mangasarian, O. L.; Schumaker, L. L. (1971). "Discrete splines via mathematical programming". SIAM J. Control. 9 (2): 174–183. doi:10.1137/0309015.

[3] Michael A. Malcolm (April 1977). "On the computation of nonlinear spline functions". SIAM Journal on Numerical Analysis. 14 (2): 254–282. doi:10.1137/0714017.

[4] Fengmin Chen, Wong, P.J.Y. (Dec 2012). "Solving second order boundary value problems by discrete cubic splines". Control Automation Robotics & Vision (ICARCV), 2012 12th International Conference: 1800–1805.CS1 maint: multiple names: authors list (link)

[5] Averbuch, A.Z., Pevnyi, A.B., Zheludev, V.A. (Nov 2001). "Biorthogonal Butterworth wavelets derived from discrete interpolatory splines". IEEE Transactions on Signal Processing. 49 (11): 2682–2692. CiteSeerX 10.1.1.332.7428. doi:10.1109/78.960415.CS1 maint: multiple names: authors list (link)