1 Definitions

Consider the space of splines of degree m (or order \(m+1\)) on the interval [a, b] with the sequence of knots

$$\begin{aligned} \delta :\; a=\xi _0\leqslant \xi _1\leqslant \cdots \leqslant \xi _k=b \end{aligned}$$

where \(\xi _i<\xi _{i+m+1}\). As a basis, we choose B-splines \(N_i=N_{i,\,m+1,\,\delta }\) of degree m, i.e., \(N_i\) is given by the rule

(1)

with the r-th divided difference of g at the points In particular,

$$\begin{aligned} N_i(x)>0 \quad \text {on} \;\; (\xi _i,\xi _{i+m+1}) \end{aligned}$$

and

$$\begin{aligned} N_i(x)=0 \quad \text {off} \;\; (\xi _i,\xi _{i+m+1}); \end{aligned}$$

to be more exact \(N_i(\xi _i)=1\) in the case \(\xi _i=\xi _{i+m}\) since splines are usually taken to be continuous from the right. To define the basis uniquely, it is necessary to specify an extension of the mesh to the left and right by m knots

$$\begin{aligned} \xi _{-m}\leqslant \xi _{-m+1}\leqslant \cdots \leqslant \xi _0, \qquad \xi _k\leqslant \xi _{k+1}\leqslant \cdots \leqslant \xi _{k+m}. \end{aligned}$$
(2)

Then the sequence of B-splines \(N_{i}\), \(i=-m,\ldots ,k-1\), will be a basis of the space of splines of degree m on the extended mesh \(\delta \) of [a, b]. Hence any spline s of degree m on the mesh \(\delta \) can be uniquely represented in this basis as

(3)

with some coefficients \(\alpha _{-m},\ldots ,\alpha _{k-1}\).

2 De Boor–Fix functionals

De Boor and Fix in the paper [2] introduced functionals \(\lambda _i^m\) defined by the formula

(4)

with \(\tau _i\in (\xi _i,\xi _{i+m+1})\),

(5)

These functionals are interesting to us because when they act on an arbitrary spline of degree m on the mesh \(\delta \), we obtain the value of the coefficient \(\alpha _i\) for \(N_{i}\) in the B-spline representation, i.e.,

In other words, any coefficient \(\alpha _i\) in the B-spline representation can be expressed in terms of the values of this spline and its derivatives at some point \(\tau _i\in (\xi _i,\xi _{i+m+1})\):

(6)

It is clear that if the point \(\tau _i\) is a mesh knot for some j with \(i\leqslant j\leqslant i+m+1\), then in the sum (6) there will be derivatives only up to order \(m-1\).

More generally, if \(\tau _i\) appears s-fold in the sequence \(\xi _{i+1},\ldots ,\xi _{i+m}\), then \(\psi _{i,m}\) has a zero of order s at \(\tau _i\), hence only the terms with \(m-r\geqslant s\) in (6) are not obviously zero. Put differently, in this case, \(\alpha _i\) is expressed as a weighted sum of \(s^{(r)}(\tau _i)\), \(r=0,\ldots ,m-s\). And if

$$\begin{aligned} \tau _i=\xi _{i+1}=\cdots =\xi _{i+m}, \end{aligned}$$

then \(\alpha _i=s(\tau _i)\), since, in this case \(\psi _{i,m}\) has a zero of order m at \(\tau _i\), hence only the \(r=0\) term in (6) is not obviously zero.

This observation proves useful in the complete spline interpolation problem which is characterized by the fact that the endpoint conditions are Hermite conditions.

3 Complete spline interpolation

Consider the interpolation problem by polynomial splines on the segment [a, b]. In order to solve the problem uniquely, in addition to known values at the nodes of some mesh (if there is less than \(k+m\) of them) more conditions are needed. The boundary conditions in the form of a certain number of derivatives at the endpoints of the segment (Hermitian boundary conditions) are most commonly used, which we will consider. For the classical splines of odd degree \(m=2n+1\), n lower derivatives of the interpolated function are given at each endpoint of the interval [1]. When the spline degree is even \(m=2n\), in Subbotin’s scheme [4, 5] these are the same boundary conditions, but the spline knots are located strictly in the middle between the interpolation points. (There is also Marsden’s scheme of interpolation by even degree splines [3], in which, on the contrary, the interpolation points are selected in the middle between the spline knots, see also [8, 9].)

Let the interpolated values \(f_0,\ldots ,f_l\) be given on the mesh

$$\begin{aligned} \Delta :\; a=x_0<x_1< \cdots <x_l=b \end{aligned}$$

and , \(r=1,\ldots ,n\), be the values of derivatives up to order n at endpoints a and b. For splines of odd degree the meshes \(\delta \) (knot mesh) and \(\Delta \) (data mesh) coincide and \(k=l\). But for splines of even degree in Subbotin’s scheme

\(i=1,\ldots ,l\), and \(l=k-1\). Further, it is convenient to consider additional nodes of the mesh \(\Delta \) as multiple:

$$\begin{aligned} \cdots =x_{-1}=x_0, \qquad x_l=x_{l+1}=\cdots \end{aligned}$$

and then additional knots (2) will be multiple too, i.e.,

$$\begin{aligned} \xi _{-m}=\xi _{-m+1}=\cdots =\xi _0, \qquad \xi _k=\xi _{k+1}=\cdots =\xi _{k+m}. \end{aligned}$$

If coefficients of the spline expansion in the basis of the B-splines (3) are chosen as the defining parameters of the required interpolation spline, then the problem consists of finding the coefficients \(\alpha _{-m},\ldots ,\alpha _{k-1}\). The system of linear equations for these parameters is immediately obtained from interpolation conditions

(7)

for given values \(\{f_i\}\) and from boundary conditions

(8)

for the given values of derivatives In both cases for splines of odd and even degree, the relations (7) lead to a \((2n+1)\)-banded system of equations, but the expressions (8) break the band structure.

4 The banded system of equations

Instead of the relations (8) we propose to use the representation of the first and last \(n+1\) coefficients from the de Boor–Fix functionals and our observation for multiple knots. We obtain explicit formulas for these coefficients which we will express in terms of elementary symmetric functions of several variables

or

Theorem 4.1

If the polynomial spline s of some degree m with knots in the mesh \(\delta \) interpolates the given values \(\{f_i\}\) on the mesh \(\Delta \) and \(\alpha _{-m},\ldots ,\alpha _{k-1}\) are the coefficients of the spline expansion in the basis of the B-splines for s then the first and last \(n+1\) coefficients can be found by the following explicit formulas:

(9)
(10)

where \(i=0,\ldots ,n\), , ,

Proof

The function \(\psi _{i,m}\) from (5) can be rewritten in the form

and its derivatives are

Now the de Boor–Fix functionals (4) have the form

Under the action of the de Boor–Fix functionals on the spline s of degree m, we obtain the following set of formulas relating the coefficients of the B-spline expansion and the derivatives of this spline:

(11)

for any point \(\tau _i\) from \((\xi _i,\xi _{i+m+1})\).

If we take as the point \(\tau _i\) the extreme knot of the mesh \(\delta \), namely \(\tau _i=\xi _0\), then the relations (11) can be written for the indices \(i=-m,\ldots ,0\). In order to, in the case of multiple additional knots, the point \(\tau _i\) belongs to \((\xi _i,\xi _{i+m+1})\), we assume that \(\tau _i=\xi _0^+\). Then some arguments of the elementary symmetric functions in (11) will be equal to zero, therefore, using the fact that

for \(r<m\), the expressions (11) take the form

with \(i=-m,\ldots ,0\). In particular, the first coefficient \(\alpha _{-m}\) will be equal just to the spline value \(s(x_0)\) at the left end of the segment [a, b], the second coefficient \(\alpha _{-m+1}\) will be expressed in terms of the spline value and its first derivative

$$\begin{aligned} \alpha _{-m+1}=s(x_0)+\frac{\xi _1-\xi _0}{m}\, s'(x_0) \end{aligned}$$

and so on. It is clear that at the right end of the interval [a, b] the situation will be similar, therefore

with \(i=0,\ldots ,m\). In terms of our interpolation problem,

and \(x_0=\xi _0\), \(x_l=\xi _k\). \(\square \)

Remark 4.2

The explicit formulas (9) and (10) for splines of odd degree were obtained in [7] without de Boor–Fix functionals.

If we eliminate the obtained parameters \(\alpha _{-m},\ldots ,\alpha _{-m+n}\) and \(\alpha _{k-1-n},\ldots ,\alpha _{k-1}\) from equations (7) for \(i=1,\ldots ,l-1\), to determine the remaining unknowns, which can be written in the form of a vector \(\varvec{\alpha }=(\alpha _{-m+n+1},\ldots ,\alpha _{k-n-2})^{\mathrm{T}}\), we obtain a system of \(l-1\) (or \(k+m-2n-2\)) equations

$$\begin{aligned} \varvec{A\alpha }=\varvec{c}, \end{aligned}$$
(12)

with the matrix

and the vector on the right-hand side \(\varvec{c}=(c_1,\ldots ,c_{l-1})^{\mathrm{T}}\). The vector on the right-hand side of the system has the following components:

The point \(x_i\) belongs to for \(i-m\leqslant j\leqslant i+2n-m\), hence the matrix \(\varvec{A}\) is banded, the band width being equal to \(2n+1\).

Note, if the coefficients of the expansion of any derivative of an interpolating spline in normalized B-splines of a relevant degree are chosen as defining parameters [6, 8], such approach of using of de Boor–Fix functionals also makes it possible to obtain explicit formulas for the first and last coefficients.

5 The quartic spline

We end our paper with an example for quartic (\(n=2\), \(m=2n=4\)) splines in Subbotin’s scheme. An example of the cubic spline was given in [7].

The interpolated values \(f_i\), \(i=0,\ldots ,l\), are given at nodes of the partition \(\Delta \): \(a=x_0<x_1<\cdots <x_l=b\) of the segment [a, b] and the derivatives \(f'_a,f''_a\) and \(f'_b,f''_b\) at the endpoints of [a, b]. The quartic spline s interpolates given values as a spline with knots in the mesh \(\delta \): \(a=\xi _0<\xi _1<\cdots <\xi _k=b\) with \(\xi _i=(x_{i-1}+x_i)/2\) and \(k=l+1\).

Let us denote , \(i=0,\ldots ,l\). In accordance with formulas (9), three parameters at the left end can be determined by the following explicit expressions:

$$\begin{aligned} \alpha _{-4}&=f_a, \qquad \alpha _{-3}=f_a+\frac{h_0}{8}f'_a, \\ \alpha _{-2}&=f_a+\frac{3h_0+h_1}{8}f'_a+\frac{h_0(2h_0+h_1)}{48}f''_a, \end{aligned}$$

since \(\xi _1-\xi _0=h_0/2\), \(\xi _2-\xi _0=h_0+h_1/2\). Similar explicit formulas hold also at the right end:

$$\begin{aligned} \alpha _{l-2}&=f_b-\frac{h_{l-1}+3h_l}{8}f'_b+\frac{h_l(h_{l-1}+2h_l)}{48}f''_b, \\ \alpha _{l-1}&=f_b-\frac{h_{l}}{8}f'_b, \qquad \alpha _{l}=f_b, \end{aligned}$$

with \(\xi _{k-1}-\xi _k=h_l/2\), \(\xi _{k-2}-\xi _k=h_{l-1}/2+h_l\). The remaining B-spline coefficients \(\alpha _{-1},\ldots ,\alpha _{l-3}\) can be found from the pentadiagonal system of equations (12). Here \(N_{-4},\ldots ,N_l\) is the basis of quartic splines on the mesh \(\delta \) of [a, b].