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    

            for    .  

Proof.

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.

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  

Theorem.  (Error Bounds for Lagrange Interpolation, Equally Spaced Nodes)  Assume that    defined on ,  which contains the equally spaced nodes  .  Additionally, assume that      and the derivatives of    up to the order    are continuous and bounded on the special subintervals  , , , , and , respectively;  that is,

    ,  

for  .  The error terms corresponding to these three cases have the following useful bounds on their magnitude  

(i).       is valid for  ,  

(ii).       is valid for  ,  

(iii).       is valid for  ,  

(iv).       is valid for  ,  

(v).       is valid for  .  

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.

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.

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.

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    .  

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:

            

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

          

References

1. Elementary Numerical Analysis, Section 2.4, Interpolation at an Increasing Number of Points  
   S.D.Conte; Carl de Boor  
   McGraw-Hill Book Co., Inc., (1980), New York, pp. 46-51.  
2. Introduction to Numerical Analysis, Section  2.7, Iterated Interpolation  
   F. B. Hildebrand   
   McGraw-Hill Book Co., Inc., (1974), New York, pp. 66-68.  
3. A First Course in Numerical Analysis, Section 3.6, Iterated Interpolation  
   Anthony Ralston    
   McGraw-Hill Book Co., Inc., (1965), New York, pp.  57-59.  
4. Principles of Numerical Analysis, Section 5.1, Polynomial Interpolation   
   Alston S. Householder  
   McGraw-Hill Book Co., Inc., (1953), New York, pp. 200-204.  
5. Iterative Interpolation  
   Eric Harold Neville  
   Indian Math. Soc., Jn., v. 20, 1933, p. 87-120.  
6. On interpolation by iteration of proportional parts, without the use of differences  
   A. C. Aitken  
   Edinburgh Math. Soc., Proc., ser. 2, v. 3, 1932, p. 56-76.  

(c) John H. Mathews 2005