Aitken's and Neville's Interpolation Methods

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.  

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    .  

 

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 .  

 

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
    .

 

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.  

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).

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    .   

 

Mathematica Subroutine (Neville Interpolation).

Mathematica Subroutine (Aitken Interpolation).

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:

            

Mathematica Subroutine (Neville Interpolation).

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

          

 

Mathematica Subroutine (Aitken Interpolation).