Module

for

Aitken's and Neville's Interpolation Methods

Background

We will now study the iterated interpolation methods of Aitken and Neville.  Alexander Craig Aitken (1895-1967) was one of  New Zealand's prominent mathematicians.  Eric Harold Neville (1889-1961) was a mathematics professor at University of Reading, Berkshire, U.K.  The algorithms we seek are remarkably similar:

To assist with understanding these algorithms we must study iterated polynomial interpolation.

Existence and Uniqueness

Theorem (Polynomial Existence and Uniqueness).  Given a set  n+1  of distinct nodes     (where whenever ).  There is a unique polynomial of degree

that passes through the  n+1  points  ,  i.e.

for    .

Iterated Interpolation

We now discuss some heuristic methods of constructing interpolation polynomials recursively.  The methods of Aitken and Neville are examples of how iteration is used to construct a sequence of polynomial approximating of increasing order.

Definition (Selected Interpolation).  Given the function    that is to be approximated, and the set of nodes:

.

For any subset of  k  nodes

the polynomial that agrees with  f[x]  at the points is denoted

.

The polynomial    of degree  k-1  agrees with  f[x]  at these knots

for    .

Exploration  Aitken and Neville Methods  Scroll down to this exploration.

Successive Interpolation

Consider polynomial interpolation based on equally spaced nodes

If all    nodes are used then a loose claim is that the interpolating polynomial    will have order of approximation  .  Usually there is an abundance of nodes (think 50, 100,...) and the degree of the interpolating polynomial is small (think 2, 3, 4, 5 or 6).  Polynomials of smaller degree    are of practical value:

The accuracy of interpolation increases with the degree of the polynomial.  Since the polynomial constructions are unique the following theorem applies for the Lagrange Polynomial, Newton polynomial and the polynomials constructed with both Aitken's method and Neville's method too.

Theorem (Remainder Term).  Assume that   and   for    are distinct  values.  Then   ,  where is a polynomial that can be used to approximate  ,  for example, the Lagrange polynomial   ,  and we write

.

The Lagrange polynomial goes through the points  ,  i.e.

for   .

The remainder term   has the form

,  for some value that lies in the interval .

Proof  See Lagrange Polynomials

The Main Results

In practice the subset of    nodes is not chosen at random over the larger set .  Instead, the nodes are clustered near a specific value of  x  at which the function   f[x]  is to be approximated by  .  Often times it is a sequential subset of nodes   with  .   It is desired to have the ability to use permutations of the list when constructing the interpolating polynomial.  It is also useful to use a sequence of polynomial approximations with increasing degree.  The following theorem gives the recursive step for generating such a sequence.

Theorem (Recursive Polynomial Construction).  Given the function    that is to be approximated, and the set of distinct nodes

.

For any pair of nodes  ,  suppose that we have constructed the polynomials:

which agrees with at the nodes  ,

which agrees with at the nodes  .

Then      is formed by making a combination of the above two polynomials

,
or
,

and it agrees with at all the nodes  .

Remark. Other equivalent ways to write   are

,
or
.

Proof  Aitken and Neville Methods  Scroll down to this theorem.

Example 1.  Given the three distinct nodes    and the function  .
Use recursion to construct the polynomial  .

Solution 1.

The Interpolation Tableau

The methods of Aitken and Neville use recursive polynomial construction.  The following tables indicate how the two constructions are made.  The extra column at the right (the values )  have been included to assist with performing hand calculations.  This extra column is not necessary for hand computations.  It will be revealed that the diagonals are equivalent.

Neville's Method.  In each new elements is computed using the element in the {same row, preceding column} and {preceding row, preceding column}.

Table 1.  Neville's Method       for    .

Aitken's Method.  In each new elements is computed using the element in the {same row, preceding column} and {top row, preceding column}.

Table 2.  Aitken's Method       for    .

Exploration  Aitken and Neville Methods  Scroll down to this exploration.

Recursive Programming

Aitken's and Neville's polynomials can be programmed recursively with the following subroutines.

Computer Programs  Aitken's and Neville's Interpolation Methods

Mathematica Subroutine (Neville Polynomials).

Mathematica Subroutine (Aitken Polynomials).

``````
``````

Example 2.  Given    and the nodes compute the entries in Aitken's tableau and Neville's tableau for evaluating    at
Show the details for the computations.

Solution 2.

Example 3.  Given    and the nodes compute the entries in Aitken's tableau and Neville's tableau for evaluating    at
Use the recursive subroutines.

Solution 3.

Example 4.  Given    and the nodes compute the entries in Aitken's tableau and Neville's tableau for evaluating    at
Use the recursive subroutines.

Solution 4.

The Rearranged Nodes

Aitken's and Neville's methods agree on the diagonal, and one usually tests for convergence of these values.  If    is to be approximated at    then one improvement that can be made is to rearrange the nodes so that they are "closer to " in the sense that is explained in the following result.

Theorem(Rearrangement of Nodes).   Given the function  ,  and the set of   distinct nodes  .  If    is to be approximated at the point   ,  then let

be the rearrangement of   such that is an increasing sequence.  Then the diagonal terms

will converge to    faster than any other rearrangement of the nodes.

Example 5.  Given    and the nodes compute the entries in Aitken's tableau and Neville's tableau for evaluating    at
Use the rearrangement of the nodes and the recursive subroutines.

Solution 5.

The Improved Interpolation Tableau

The tables for Aitken's and Neville's methods can be stored in a two-dimensional array and do not need long subscript lists as shown in the following tables.

Neville's Method.  In each new elements is computed using the element in the {same row, preceding column} and {preceding row, preceding column}.

Table 3.  Neville's Method       for    .

Aitken's Method.  In each new elements is computed using the element in the {same row, preceding column} and {top row, preceding column}.

Table 4.  Aitken's Method       for    .

Computer Programs  Aitken's and Neville's Interpolation Methods

Mathematica Subroutine (Neville Interpolation).

Mathematica Subroutine (Aitken Interpolation).

``````
``````

Example 6.  Given    and the nodes compute the entries in Aitken's tableau and Neville's tableau for evaluating    at
Use the improved interpolation subroutines.

Solution 6.

The Improved Subroutines using Matrices

The subroutines for Aitken's and Neville's methods can be modified to use matrices, this is the final improvement.

Algorithm (Neville Interpolation).   Given the nodes the Neville interpolation at is   where we compute:

Computer Programs  Neville Interpolation

Mathematica Subroutine (Neville Interpolation).

Algorithm (Aitken Interpolation).   Given the nodes the Aitken interpolation at is   where we compute:

Computer Programs  Aitken Interpolation

Mathematica Subroutine (Aitken Interpolation).

``````
``````

Example 7.  Given    and the nodes compute the entries in Aitken's tableau and Neville's tableau for evaluating    at
Use the improved interpolation subroutines with matrices.

Solution 7.

Aitken's and Neville's Methods  Internet hyperlinks to web sites and a bibliography of articles.

(c) John H. Mathews 2005