Interpolation by splines: how to set up the equation system for finding the coefficients of the spline (in a B-spline basis)

Question

Problem. I want to interpolate a function $f$ in some equidistant points $x_0<x_1<x_2<x_3<x_4$ using a quadratic spline.

My attempt. I assume that we can use the interpolation points as knots. We then want to find a spline $s$ from the space $\mathscr{S}(2,x_0,x_1,x_2,x_3,x_4)$ (which dimension is the degree + the number of points minus 1$=2+4=6$) that satisfy the conditions $$s(x_i)=f(x_i)\quad \forall i=1,2,3,4\,.$$ By adding extra knots to the right and the left, to obtain a new set of knots, namely $$\xi_0< \xi_1<\overbrace{\xi_2< \xi_3< \xi_4< \xi_5< \xi_6}^\mathrm{interpolation\:points}<\xi_7< \xi_8\,,$$ I think I have been able to fins a basis consisting of 6 B-splines, $B_0, B_1,\ldots B_5$, where $$B_p=\sum_{j=p}^{p+3}\left(\prod_{i=p,\,i\neq j}^{p+3}\frac{1}{\xi_i-\xi_j}\right)\left(\max\{0,\,x-\xi_j\}\right)^k\,.$$ What I'm trying to do now is to find my interpolating spline $s$ on the form $$s(x)=c_0B_0(x)+\cdots+c_5B_5(x)\,,$$ by setting up some sort of equation system. The interpolation conditions give me five rows of the system, but I need one more row in order to get a unique solution, right? I have some vague memory of some derivative condition, but I don't see how I can make something productive out of that. Any ideas? Am I at all on the right track here?

Edit. Maybe it is wrong to assume that I can use the interpolation points as knots? But if I don't do that, how should I choose them?

Answer 1

In general B-spline interpolation, interpolation points are not the knots. So, if you want to interpolate $N$ points with a degree $m$ B-spline, the B-spline will have $N$ control points, $(N-m)$ Bezier segments of degree $m$ and require $(N+m+1)$ knots.

If you want to enforce interpolation points to be the same as knots, this mean that you will end up having $(N+m-1)$ control points, $(N-1)$ Bezier segments and require $(N+2m)$ knots. Since there are more control points than the number of interpolation points, you will have add "artificial constraints" to make the linear equations solvable. When $m=3$ (cubic), the two "artificial constraints" are typically zero second derivatives at the ends (which lead to the so-called natural B-spline) or two pre-defined first derivatives at the end. When $m=2$ (quadratic), the artificial constraint can be a pre-defined first derivative at the start of the curve.

For your particular case, without enforcing interpolation points to be the same as knots, you can use

($x_0$, $x_0$, $x_0$, $\frac{x_1+x_2}{2}$, $\frac{x_2+x_3}{2}$, $x_4$, $x_4$,$x_4$)

as the knot sequence.

Answer 2

A b-spline of order $k$ (degree $m = k-1$) that has $n$ control points will have $n+k$ knots. And, if you want to interpolate $n$ points, you will need $n$ control points.

So, in your case, we have $n=5$ and $k=3$, so we need $n+k = 8$ knots. To force interpolation at the two ends, the first and last knots should have multiplicity 3. That accounts for 6 knots, so we now need two more interior knots to give us the desired total of 8. In other words, the knot sequence will have the form $$ (x_0, x_0, x_0, a, b, x_4, x_4, x_4) $$ for some $a$ and $b$ with $x_0 < a < b < x_4$.

The only restrictions we need to impose on $a$ and $b$ are those arising from the Schoenberg-Whitney theorem. This says that the knot sequence $(\xi_i)$ and the interpolation sites $(x_i)$ must satisfy $$ x_i < \xi_i < x_{i+k} \quad \text{for all $i$} $$ In effect this says that at each interpolation point there should be at least one basis function that is non-zero. This ensures that the linear system of equations expressing the interpolation conditions has a unique solution.

Carl de Boor's book "A Practical Guide to Splines" explains the Schoenberg-Whitney theorem and has a whole chapter on quadratic splines, including code. Much of the same code is in the Matlab spline package.