NAG CL Interface
e01aac (dim1_​aitken)

Settings help

CL Name Style:


1 Purpose

e01aac interpolates a function of one variable at a given point x from a table of function values yi evaluated at equidistant or non-equidistant points xi, for i=1,2,,n+1, using Aitken's technique of successive linear interpolations.

2 Specification

#include <nag.h>
void  e01aac (Integer n, double a[], double b[], double c[], double x, NagError *fail)
The function may be called by the names: e01aac, nag_interp_dim1_aitken or nag_1d_aitken_interp.

3 Description

e01aac interpolates a function of one variable at a given point x from a table of values xi and yi, for i=1,2,,n+1 using Aitken's method (see Fröberg (1970)). The intermediate values of linear interpolations are stored to enable an estimate of the accuracy of the results to be made.

4 References

Fröberg C E (1970) Introduction to Numerical Analysis Addison–Wesley

5 Arguments

1: n Integer Input
On entry: the number of intervals which are to be used in interpolating the value at x; that is, there are n+1 data points (xi,yi).
Constraint: n>0.
2: a[n+1] double Input/Output
On entry: a[i-1] must contain the x-component of the ith data point, xi, for i=1,2,,n+1.
On exit: a[i-1] contains the value xi-x, for i=1,2,,n+1.
3: b[n+1] double Input/Output
On entry: b[i-1] must contain the y-component (function value) of the ith data point, yi, for i=1,2,,n+1.
On exit: the contents of b are unspecified.
4: c[n×(n+1)/2] double Output
On exit:
  • c[0],,c[n-1] contain the first set of linear interpolations,
  • c[n],,c[2×n-2] contain the second set of linear interpolations,
  • c[2n-1],,c[3×n-4] contain the third set of linear interpolations,
  • c[n×(n+1)/2-1] contains the interpolated function value at the point x.
5: x double Input
On entry: the point x at which the interpolation is required. Note that x may lie outside the interval defined by the minimum and maximum values in a, in which case an extrapolated value will be computed; extrapolated results should be treated with considerable caution since there is no information on the behaviour of the function outside the defined interval.
6: fail NagError * Input/Output
The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).

6 Error Indicators and Warnings

NE_ALLOC_FAIL
Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
NE_BAD_PARAM
On entry, argument value had an illegal value.
NE_INT
On entry, n=value.
Constraint: n>0.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
NE_NO_LICENCE
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library CL Interface for further information.

7 Accuracy

An estimate of the accuracy of the result can be made from a comparison of the final result and the previous interpolates, given in the array c. In particular, the first interpolate in the ith set, for i=1,2,,n, is the value at x of the polynomial interpolating the first (i+1) data points. It is given in position (i-1)(2n-i+2)/2 of the array c. Ideally, providing n is large enough, this set of n interpolates should exhibit convergence to the final value, the difference between one interpolate and the next settling down to a roughly constant magnitude (but with varying sign). This magnitude indicates the size of the error (any subsequent increase meaning that the value of n is too high). Better convergence will be obtained if the data points are supplied, not in their natural order, but ordered so that the first i data points give good coverage of the neighbourhood of x, for all i. To this end, the following ordering is recommended as widely suitable: first the point nearest to x, then the nearest point on the opposite side of x, followed by the remaining points in increasing order of their distance from x, that is of |xr-x|. With this modification the Aitken method will generally perform better than the related method of Neville, which is often given in the literature as superior to that of Aitken.

8 Parallelism and Performance

e01aac is not threaded in any implementation.

9 Further Comments

The computation time for interpolation at any point x is proportional to n×(n+1)/2.

10 Example

This example interpolates at x=0.28 the function value of a curve defined by the points
( xi -1.00 -0.50 0.00 0.50 1.00 1.50 yi 0.00 -0.53 -1.00 -0.46 2.00 11.09 ) .  

10.1 Program Text

Program Text (e01aace.c)

10.2 Program Data

Program Data (e01aace.d)

10.3 Program Results

Program Results (e01aace.r)