2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.