nag_1d_aitken_interp (e01aac) (PDF version)
e01 Chapter Contents
e01 Chapter Introduction
NAG C Library Manual

# NAG Library Function Documentnag_1d_aitken_interp (e01aac)

## 1  Purpose

nag_1d_aitken_interp (e01aac) interpolates a function of one variable at a given point $x$ from a table of function values ${y}_{i}$ evaluated at equidistant or non-equidistant points ${x}_{i}$, for $\mathit{i}=1,2,\dots ,n+1$, using Aitken's technique of successive linear interpolations.

## 2  Specification

 #include #include
 void nag_1d_aitken_interp (Integer n, double a[], double b[], double c[], double x, NagError *fail)

## 3  Description

nag_1d_aitken_interp (e01aac) interpolates a function of one variable at a given point $x$ from a table of values ${x}_{i}$ and ${y}_{i}$, for $i=1,2,\dots ,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:     nIntegerInput
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 $\left({x}_{i},{y}_{i}\right)$.
Constraint: ${\mathbf{n}}>0$.
2:     a[${\mathbf{n}}+1$]doubleInput/Output
On entry: ${\mathbf{a}}\left[\mathit{i}-1\right]$ must contain the $x$-component of the $\mathit{i}$th data point, ${x}_{\mathit{i}}$, for $\mathit{i}=1,2,\dots ,n+1$.
On exit: ${\mathbf{a}}\left[\mathit{i}-1\right]$ contains the value ${x}_{\mathit{i}}-x$, for $\mathit{i}=1,2,\dots ,n+1$.
3:     b[${\mathbf{n}}+1$]doubleInput/Output
On entry: ${\mathbf{b}}\left[\mathit{i}-1\right]$ must contain the $y$-component (function value) of the $\mathit{i}$th data point, ${y}_{\mathit{i}}$, for $\mathit{i}=1,2,\dots ,n+1$.
On exit: the contents of b are unspecified.
4:     c[${\mathbf{n}}×\left({\mathbf{n}}+1\right)/2$]doubleOutput
On exit:
• ${\mathbf{c}}\left[0\right],\dots ,{\mathbf{c}}\left[n-1\right]$ contain the first set of linear interpolations,
• ${\mathbf{c}}\left[n\right],\dots ,{\mathbf{c}}\left[2×n-2\right]$ contain the second set of linear interpolations,
• ${\mathbf{c}}\left[2n-1\right],\dots ,{\mathbf{c}}\left[3×n-4\right]$ contain the third set of linear interpolations,
• $⋮$
• ${\mathbf{c}}\left[n×\left(n+1\right)/2-1\right]$ contains the interpolated function value at the point $x$.
5:     xdoubleInput
On entry: the point $x$ at which the interpolation is required.
6:     failNagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

## 6  Error Indicators and Warnings

NE_BAD_PARAM
On entry, argument $〈\mathit{\text{value}}〉$ had an illegal value.
NE_INT
On entry, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{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.

## 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 $i$th set, for $i=1,2,\dots ,n$, is the value at $x$ of the polynomial interpolating the first $\left(i+1\right)$ data points. It is given in position $\left(i-1\right)\left(2n-i+2\right)/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 $\left|{x}_{r}-x\right|$. 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  Further Comments

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

## 9  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 .$

### 9.1  Program Text

Program Text (e01aace.c)

### 9.2  Program Data

Program Data (e01aace.d)

### 9.3  Program Results

Program Results (e01aace.r)

nag_1d_aitken_interp (e01aac) (PDF version)
e01 Chapter Contents
e01 Chapter Introduction
NAG C Library Manual