Akima algorithm

You are given a single independent variable x. The approach uses a cubic fit between the data points, so the slope is required at each data point in addition to the value of the point itself. The interpolating polynomial is written between the ith and i + 1st data points as:

y = a0 + a1 (x − xi) + a2 (x − xi)2 + a3 (x − xi)3 , (1)

with coefficients defined by

a0 = yi

a1 = y'i

a2 = ( 3mi − 2y'i − y'i+1 ) / ( xi+1 − xi )

a3 = ( y'i + y'i+1 − 2mi ) / ( xi+1 − xi)2 ,

and,

mi = ( yi+1 − yi ) / ( xi+1 − xi ), (2)

which is the slope of the line segment passing through the points. The method of determining the derivatives, y', is what makes the Akima methods unique. The derivative is

y'i = ( Σ wkf'k ) / ( Σ wk ) (3)

where f'k is the computed derivative at Pi of a third-order polynomial passing through Pi and three other nearby points:

f'1 = F (Pi−3, Pi−2, Pi−1, Pi) (4)

f'2 = F (Pi−2, Pi−1, Pi, Pi+1) (5)

f'3 = F (Pi−1, Pi, Pi+1, Pi+2) (6)

f'4 = F (Pi, Pi+1, Pi+2, Pi+3). (7)

The weights are inversely proportional to the product of what Akima calls a volatility measure and a distance measure,

wk = 1 / vkdk. (8)

The distance factor is the sum of squares of the distance from Pi and the other three points:

d1 = (xi−3 − xi)2 + (xi−2 − xi)2 + (xi−1 − xi)2

d2 = (xi−2 − xi)2 + (xi−1 − xi)2 + (xi+1 − xi)2

d3 = (xi−1 − xi)2 + (xi+1 − xi)2 + (xi+2 − xi)2

d4 = (xi+1 − xi)2 + (xi+2 − xi)2 + (xi+3 − xi)2 .

The volatility factor, vk, is the sum of squares of deviation from a least-squares linear fit of the four points. (the same sets of four points appearing in Equations 4 through 7).

H. Akima. A method of univariate interpolation that has the accuracy of a third-degree polynomial. ACM Trans. on Math. Softw., 17, 1991. (as copied from http://acdl.mit.edu/mdo/mdo_06/Single-variable.pdf

See also: http://www.alglib.net/interpolation/spline3.php#header3