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    .  

Proof  Aitken and Neville Methods  

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.

Research Experience for Undergraduates

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

Download this Mathematica Notebook Aitken's and Neville's Methods

(c) John H. Mathews 2005