cubic interpolation with not equidistant points

I'm trying to create an interpolation of a list of points.

I've some point of 开发者_如何学Gocoordinates (ti, xi), where ti are timestamp and xi are associated values. I want to create a function that passes through these points and allows me to find the x value corresponding to a generic t that lies in the interval.

I want to interpolate them with a third-order interpolation. I've seen something like catmull-rom interpolation, but it works only if points xi are equidistant.

For example here http://www.mvps.org/directx/articles/catmull/ you can find that the timestamp points are equidistant, like also here http://www.cs.cmu.edu/~462/projects/assn2/assn2/catmullRom.pdf .

There' some way to apply cubic interpolation with non regular points?

Unequal spacing of the arguments is not a problem as long as they are all distinct. As you probably know, if you have four distinct times t[i], then there exists a unique polynomial interpolant of corresponding values x[i] having degree at most 3 (cubic or lower order).

There are two main approaches to computing the interpolant, Newton's divided-differences and Lagrange's method of interpolation.

Keeping in mind that just finding the polynomial is not the point, but rather evaluating it at another time in the interval, there are some programming tradeoffs to consider.

If the times t[i] are fixed but values x[i] are changed repeatedly, you might be well off using Lagrange's method. It basically constructs four cubic polynomials that take roots at three of the four points and gives a normalized value 1 at the remaining point. Once you have those four polynomials, interpolating the values x[i] is just a matter of taking the corresponding linear combination of them. Lagrange's method suffers from Runge's phenomenon at the edges of the interval.

However if the times t[i] keep changing, or perhaps you are evaluating the interpolating polynomial for a number of intermediate points for the same t[i], x[i] data, then Newton's divided differences may be better. If accuracy is important, one can vary the order that the times t[i] appear in the divided-difference tableau so that the evaluation is localized around the closest times to the intermediate time where the value is needed.

It's not hard to find sample code for Newton's divided difference method on the Web, e.g. in C++, Python, or Java.

One way might be to fit a least squares cubic through the points. I've found that approach here to be robust and practical, even with a small number of points.