Akima algorithm [wiki.met.no]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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 = a<sub>0</sub> + a<sub>1</sub> (x − x<sub>i</sub>) + a<sub>2</sub> (x − x<sub>i</sub>)<sup>2</sup> + a<sub>3</sub> (x − x<sub>i</sub>)<sup>3</sup> , (1)

with coefficients defined by

a<sub>0</sub> = y<sub>i</sub>

a<sub>1</sub> = y<sup>'</sup><sub>i</sub>

a<sub>2</sub> = ( 3m<sub>i</sub> − 2y<sup>'</sup><sub>i</sub> − y<sup>'</sup><sub>i+1</sub> ) / ( x<sub>i+1</sub> − x<sub>i</sub> )

a<sub>3</sub> = ( y<sup>'</sup><sub>i</sub> + y<sup>'</sup><sub>i+1</sub> − 2m<sub>i</sub> ) / ( x<sub>i+1</sub> − x<sub>i</sub>)<sup>2</sup> ,

and,

m<sub>i</sub> = ( y<sub>i+1</sub> − y<sub>i</sub> ) / ( x<sub>i+1</sub> − x<sub>i</sub> ),  (2)

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

y<sup>'</sup><sub>i</sub> = ( Σ w<sub>k</sub>f<sup>'</sup><sub>k</sub> ) / ( Σ w<sub>k</sub> )  (3)

where f<sup>'</sup><sub>k</sub> is the computed derivative at P<sub>i</sub> of a third-order polynomial passing through P<sub>i</sub> and
three other nearby points:

f<sup>'</sup><sub>1</sub> = F (P<sub>i−3</sub>, P<sub>i−2</sub>, P<sub>i−1</sub>, P<sub>i</sub>)  (4)

f<sup>'</sup><sub>2</sub> = F (P<sub>i−2</sub>, P<sub>i−1</sub>, P<sub>i</sub>, P<sub>i+1</sub>)  (5)

f<sup>'</sup><sub>3</sub> = F (P<sub>i−1</sub>, P<sub>i</sub>, P<sub>i+1</sub>, P<sub>i+2</sub>)  (6)

f<sup>'</sup><sub>4</sub> = F (P<sub>i</sub>, P<sub>i+1</sub>, P<sub>i+2</sub>, P<sub>i+3</sub>).  (7)

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

w<sub>k</sub> = 1 / v<sub>k</sub>d<sub>k</sub>.  (8)

The distance factor is the sum of squares of the distance from P<sub>i</sub> and the other three points:

d<sub>1</sub> = (x<sub>i−3</sub> − x<sub>i</sub>)<sup>2</sup> + (x<sub>i−2</sub> − x<sub>i</sub>)<sup>2</sup> + (x<sub>i−1</sub> − x<sub>i</sub>)<sup>2</sup>

d<sub>2</sub> = (x<sub>i−2</sub> − x<sub>i</sub>)<sup>2</sup> + (x<sub>i−1</sub> − x<sub>i</sub>)<sup>2</sup> + (x<sub>i+1</sub> − x<sub>i</sub>)<sup>2</sup>

d<sub>3</sub> = (x<sub>i−1</sub> − x<sub>i</sub>)<sup>2</sup> + (x<sub>i+1</sub> − x<sub>i</sub>)<sup>2</sup> + (x<sub>i+2</sub> − x<sub>i</sub>)<sup>2</sup>

d<sub>4</sub> = (x<sub>i+1</sub> − x<sub>i</sub>)<sup>2</sup> + (x<sub>i+2</sub> − x<sub>i</sub>)<sup>2</sup> + (x<sub>i+3</sub> − x<sub>i</sub>)<sup>2</sup> .

The volatility factor, v<sub>k</sub>, 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]]