Spline Approximation (Introduction)

We sometimes encounter a situation where a number of points with coordinates (x,y) are given and we want to find a function such that for all of these points we have f(x)=y (interpolation) or f(x) \approx y (approximation). Most often we say that we want on average |f(x) - y| to be as small as possible and for whatever reasons usually the quadratic mean. The most simple and well known approximation is probably linear regression, where a straight line is found that tries to approximate the points. This can be extended to other function, for example polynomials of a fixed maximum order. For something that is supposed to be periodic, linear combinations of functions of the form f(t)=\sin(at) and f(t)=\cos(at) might be useful.

Now it may not be easy to express the whole extent by one function. So the interval, in which the x-coordinates lie, might be subdivided into subintervals and linear regression or whatever is being used can be performed in each subinterval separately. This results in a polygon-like curve or worse in a curve that „jumps“ at the interval borders. This can well be good enough and it is relatively easy to implement. With the additional constraint, that it should be continuous at the interval borders, it becomes a bit more difficult.

Now there is some preference for smooth curves. For example it might be desirable that the function is continuous (i.e. it does not jump at interval boarders) and even its first and second derivative should be continuous. This roughly resembles a mechanical spline as it was used in the old days for drawing and constructing. Kind of an elastic ruler.

This is where Splines are often used to interpolate a smooth curve that passes through some given points. More precisely cubic splines, but the concept is of course more general. A lot of material can be found on the internet about spline interpolation.

But they can also be used for approximation. So we want a curve that is smooth and that approximates our given points and that is expressible as a simple third degree polynomial in each subinterval.

Just to make it clear, the subintervals are not used as a „divide et impera“ strategy, but we consider all the points at once, just give ourselves the freedom to have different functions in different subintervals to get a combined function that behaves better than polynomials of very high degree. We do need to think also a bit about the inaccuracy of floating point arithmetic. So polynomials of degree three are still somewhat precise within the subinterval, but a higher order polynomial that is applied to a large interval will become less accurate with normal floating point arithmetic („double“).

I will leave this as a starting point for thinking. In some of the next articles, the spline approximation will be derived mathematically and then there will be a cookbook how to use it programmatically. My advice is to experiment with the implementation and its parameters until you are confident that it give sufficiently precise result, have a look at the math behind it to understand the question of the precision or have someone else have a look. With floating point arithmetic it is always a bad idea just to program something that looks right and totally ignore the rounding errors of floating point arithmetic, that can have huge impact on the result.

There is a lot of material on spline interpolation on the internet. On spline approximation there have been some papers, but very little can be found on the internet.

A followup article covering the mathematics behind spline approximation has been written.

Share Button

Beteilige dich an der Unterhaltung

2 Kommentare

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert