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:
    
    [Graphics:Images/NevilleAlgorithmMod_gr_1.gif]        [Graphics:Images/NevilleAlgorithmMod_gr_2.gif]  
    
    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  [Graphics:Images/NevilleAlgorithmMod_gr_3.gif]   (where [Graphics:Images/NevilleAlgorithmMod_gr_4.gif] whenever [Graphics:Images/NevilleAlgorithmMod_gr_5.gif]).  There is a unique polynomial of degree [Graphics:Images/NevilleAlgorithmMod_gr_6.gif]   

        [Graphics:Images/NevilleAlgorithmMod_gr_7.gif]
        
that passes through the  n+1  points  [Graphics:Images/NevilleAlgorithmMod_gr_8.gif],  i.e.   

        [Graphics:Images/NevilleAlgorithmMod_gr_9.gif]    for    [Graphics:Images/NevilleAlgorithmMod_gr_10.gif].  

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  [Graphics:Images/NevilleAlgorithmMod_gr_11.gif]  that is to be approximated, and the set of nodes:  

        [Graphics:Images/NevilleAlgorithmMod_gr_12.gif].

For any subset of  k  nodes

        [Graphics:Images/NevilleAlgorithmMod_gr_13.gif]  

the polynomial that agrees with  f[x]  at the points [Graphics:Images/NevilleAlgorithmMod_gr_14.gif] is denoted  

        [Graphics:Images/NevilleAlgorithmMod_gr_15.gif].

The polynomial  [Graphics:Images/NevilleAlgorithmMod_gr_16.gif]  of degree  k-1  agrees with  f[x]  at these knots [Graphics:Images/NevilleAlgorithmMod_gr_17.gif]  

        [Graphics:Images/NevilleAlgorithmMod_gr_18.gif]    for    [Graphics:Images/NevilleAlgorithmMod_gr_19.gif].  

Exploration  Aitken and Neville Methods  Scroll down to this exploration.

 

Successive Interpolation

    Consider polynomial interpolation based on equally spaced nodes
    
        [Graphics:Images/NevilleAlgorithmMod_gr_20.gif]  

If all  [Graphics:Images/NevilleAlgorithmMod_gr_21.gif]  nodes are used then a loose claim is that the interpolating polynomial  [Graphics:Images/NevilleAlgorithmMod_gr_22.gif]  will have order of approximation  [Graphics:Images/NevilleAlgorithmMod_gr_23.gif].  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  [Graphics:Images/NevilleAlgorithmMod_gr_24.gif]  are of practical value:  

        

[Graphics:Images/NevilleAlgorithmMod_gr_25.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_26.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_27.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_28.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_29.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_30.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_31.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_32.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_33.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_34.gif]

  

    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  [Graphics:Images/NevilleAlgorithmMod_gr_35.gif] and  [Graphics:Images/NevilleAlgorithmMod_gr_36.gif] for  [Graphics:Images/NevilleAlgorithmMod_gr_37.gif]  are distinct  values.  Then   [Graphics:Images/NevilleAlgorithmMod_gr_38.gif],  where [Graphics:Images/NevilleAlgorithmMod_gr_39.gif] is a polynomial that can be used to approximate  [Graphics:Images/NevilleAlgorithmMod_gr_40.gif],  for example, the Lagrange polynomial   [Graphics:Images/NevilleAlgorithmMod_gr_41.gif],  and we write  

    [Graphics:Images/NevilleAlgorithmMod_gr_42.gif].

The Lagrange polynomial goes through the [Graphics:Images/NevilleAlgorithmMod_gr_43.gif] points  [Graphics:Images/NevilleAlgorithmMod_gr_44.gif],  i.e.

    [Graphics:Images/NevilleAlgorithmMod_gr_45.gif]    for   [Graphics:Images/NevilleAlgorithmMod_gr_46.gif].  

The remainder term  [Graphics:Images/NevilleAlgorithmMod_gr_47.gif] has the form

    [Graphics:Images/NevilleAlgorithmMod_gr_48.gif],  for some value [Graphics:Images/NevilleAlgorithmMod_gr_49.gif] that lies in the interval [Graphics:Images/NevilleAlgorithmMod_gr_50.gif].  

Proof  See Lagrange Polynomials  

 

The Main Results

    In practice the subset of  [Graphics:Images/NevilleAlgorithmMod_gr_51.gif]  nodes [Graphics:Images/NevilleAlgorithmMod_gr_52.gif] is not chosen at random over the larger set [Graphics:Images/NevilleAlgorithmMod_gr_53.gif].  Instead, the nodes are clustered near a specific value of  x  at which the function   f[x]  is to be approximated by  [Graphics:Images/NevilleAlgorithmMod_gr_54.gif].  Often times it is a sequential subset of nodes  [Graphics:Images/NevilleAlgorithmMod_gr_55.gif] with  [Graphics:Images/NevilleAlgorithmMod_gr_56.gif].   It is desired to have the ability to use permutations of the list [Graphics:Images/NevilleAlgorithmMod_gr_57.gif] 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  [Graphics:Images/NevilleAlgorithmMod_gr_58.gif]  that is to be approximated, and the set of [Graphics:Images/NevilleAlgorithmMod_gr_59.gif] distinct nodes  

    [Graphics:Images/NevilleAlgorithmMod_gr_60.gif].  

For any pair of nodes  [Graphics:Images/NevilleAlgorithmMod_gr_61.gif],  suppose that we have constructed the polynomials:

    [Graphics:Images/NevilleAlgorithmMod_gr_62.gif]  which agrees with [Graphics:Images/NevilleAlgorithmMod_gr_63.gif] at the nodes  [Graphics:Images/NevilleAlgorithmMod_gr_64.gif],  

    [Graphics:Images/NevilleAlgorithmMod_gr_65.gif]  which agrees with [Graphics:Images/NevilleAlgorithmMod_gr_66.gif] at the nodes  [Graphics:Images/NevilleAlgorithmMod_gr_67.gif].  

Then   [Graphics:Images/NevilleAlgorithmMod_gr_68.gif]   is formed by making a combination of the above two polynomials

    [Graphics:Images/NevilleAlgorithmMod_gr_69.gif],
    or
    [Graphics:Images/NevilleAlgorithmMod_gr_70.gif],

and it agrees with [Graphics:Images/NevilleAlgorithmMod_gr_71.gif] at all the nodes  [Graphics:Images/NevilleAlgorithmMod_gr_72.gif].

Remark. Other equivalent ways to write  [Graphics:Images/NevilleAlgorithmMod_gr_73.gif] are

    [Graphics:Images/NevilleAlgorithmMod_gr_74.gif],
    or
    [Graphics:Images/NevilleAlgorithmMod_gr_75.gif].

Proof  Aitken and Neville Methods  Scroll down to this theorem.  

 

Example 1.  Given the three distinct nodes  [Graphics:Images/NevilleAlgorithmMod_gr_76.gif]  and the function  [Graphics:Images/NevilleAlgorithmMod_gr_77.gif].  
Use recursion to construct the polynomial  [Graphics:Images/NevilleAlgorithmMod_gr_78.gif].

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 [Graphics:Images/NevilleAlgorithmMod_gr_128.gif])  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}.
    

[Graphics:Images/NevilleAlgorithmMod_gr_129.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_130.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_131.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_132.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_133.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_134.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_135.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_136.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_137.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_138.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_139.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_140.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_141.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_142.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_143.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_144.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_145.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_146.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_147.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_148.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_149.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_150.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_151.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_152.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_153.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_154.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_155.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_156.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_157.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_158.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_159.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_160.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_161.gif]


Table 1.  Neville's Method   [Graphics:Images/NevilleAlgorithmMod_gr_162.gif]    for    [Graphics:Images/NevilleAlgorithmMod_gr_163.gif].  

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

[Graphics:Images/NevilleAlgorithmMod_gr_164.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_165.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_166.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_167.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_168.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_169.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_170.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_171.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_172.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_173.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_174.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_175.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_176.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_177.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_178.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_179.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_180.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_181.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_182.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_183.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_184.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_185.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_186.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_187.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_188.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_189.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_190.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_191.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_192.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_193.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_194.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_195.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_196.gif]


Table 2.  Aitken's Method   [Graphics:Images/NevilleAlgorithmMod_gr_197.gif]    for    [Graphics:Images/NevilleAlgorithmMod_gr_198.gif].  

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

[Graphics:Images/NevilleAlgorithmMod_gr_199.gif]

Mathematica Subroutine (Aitken Polynomials).

[Graphics:Images/NevilleAlgorithmMod_gr_200.gif]

Example 2.  Given  [Graphics:Images/NevilleAlgorithmMod_gr_201.gif]  and the nodes [Graphics:Images/NevilleAlgorithmMod_gr_202.gif] compute the entries in Aitken's tableau and Neville's tableau for evaluating  [Graphics:Images/NevilleAlgorithmMod_gr_203.gif]  at  [Graphics:Images/NevilleAlgorithmMod_gr_204.gif]  
Show the details for the computations.

Solution 2.

 

Example 3.  Given  [Graphics:Images/NevilleAlgorithmMod_gr_291.gif]  and the nodes [Graphics:Images/NevilleAlgorithmMod_gr_292.gif] compute the entries in Aitken's tableau and Neville's tableau for evaluating  [Graphics:Images/NevilleAlgorithmMod_gr_293.gif]  at  [Graphics:Images/NevilleAlgorithmMod_gr_294.gif]  
Use the recursive subroutines.

Solution 3.

 

Example 4.  Given  [Graphics:Images/NevilleAlgorithmMod_gr_336.gif]  and the nodes [Graphics:Images/NevilleAlgorithmMod_gr_337.gif] compute the entries in Aitken's tableau and Neville's tableau for evaluating  [Graphics:Images/NevilleAlgorithmMod_gr_338.gif]  at  [Graphics:Images/NevilleAlgorithmMod_gr_339.gif]  
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  [Graphics:Images/NevilleAlgorithmMod_gr_373.gif]  is to be approximated at  [Graphics:Images/NevilleAlgorithmMod_gr_374.gif]  then one improvement that can be made is to rearrange the nodes so that they are "closer to [Graphics:Images/NevilleAlgorithmMod_gr_375.gif]" in the sense that is explained in the following result.  
    
Theorem(Rearrangement of Nodes).   Given the function  [Graphics:Images/NevilleAlgorithmMod_gr_376.gif],  and the set of  [Graphics:Images/NevilleAlgorithmMod_gr_377.gif] distinct nodes  [Graphics:Images/NevilleAlgorithmMod_gr_378.gif].  If  [Graphics:Images/NevilleAlgorithmMod_gr_379.gif]  is to be approximated at the point  [Graphics:Images/NevilleAlgorithmMod_gr_380.gif] ,  then let  

    [Graphics:Images/NevilleAlgorithmMod_gr_381.gif]  
    
be the rearrangement of  [Graphics:Images/NevilleAlgorithmMod_gr_382.gif] such that [Graphics:Images/NevilleAlgorithmMod_gr_383.gif] is an increasing sequence.  Then the diagonal terms  

    [Graphics:Images/NevilleAlgorithmMod_gr_384.gif]  

will converge to  [Graphics:Images/NevilleAlgorithmMod_gr_385.gif]  faster than any other rearrangement of the nodes.

 

Example 5.  Given  [Graphics:Images/NevilleAlgorithmMod_gr_386.gif]  and the nodes [Graphics:Images/NevilleAlgorithmMod_gr_387.gif] compute the entries in Aitken's tableau and Neville's tableau for evaluating  [Graphics:Images/NevilleAlgorithmMod_gr_388.gif]  at  [Graphics:Images/NevilleAlgorithmMod_gr_389.gif]  
Use the rearrangement of the nodes [Graphics:Images/NevilleAlgorithmMod_gr_390.gif] 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}.
    

[Graphics:Images/NevilleAlgorithmMod_gr_423.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_424.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_425.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_426.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_427.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_428.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_429.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_430.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_431.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_432.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_433.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_434.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_435.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_436.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_437.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_438.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_439.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_440.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_441.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_442.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_443.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_444.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_445.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_446.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_447.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_448.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_449.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_450.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_451.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_452.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_453.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_454.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_455.gif]


Table 3.  Neville's Method   [Graphics:Images/NevilleAlgorithmMod_gr_456.gif]    for    [Graphics:Images/NevilleAlgorithmMod_gr_457.gif].  

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

[Graphics:Images/NevilleAlgorithmMod_gr_458.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_459.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_460.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_461.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_462.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_463.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_464.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_465.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_466.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_467.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_468.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_469.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_470.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_471.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_472.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_473.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_474.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_475.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_476.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_477.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_478.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_479.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_480.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_481.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_482.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_483.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_484.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_485.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_486.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_487.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_488.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_489.gif]

[Graphics:Images/NevilleAlgorithmMod_gr_490.gif]


Table 4.  Aitken's Method   [Graphics:Images/NevilleAlgorithmMod_gr_491.gif]    for    [Graphics:Images/NevilleAlgorithmMod_gr_492.gif].  

 

Computer Programs  Aitken's and Neville's Interpolation Methods

Mathematica Subroutine (Neville Interpolation).

[Graphics:Images/NevilleAlgorithmMod_gr_493.gif]

Mathematica Subroutine (Aitken Interpolation).

[Graphics:Images/NevilleAlgorithmMod_gr_494.gif]

Example 6.  Given  [Graphics:Images/NevilleAlgorithmMod_gr_495.gif]  and the nodes [Graphics:Images/NevilleAlgorithmMod_gr_496.gif] compute the entries in Aitken's tableau and Neville's tableau for evaluating  [Graphics:Images/NevilleAlgorithmMod_gr_497.gif]  at  [Graphics:Images/NevilleAlgorithmMod_gr_498.gif]  
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 [Graphics:Images/NevilleAlgorithmMod_gr_505.gif] the Neville interpolation at [Graphics:Images/NevilleAlgorithmMod_gr_506.gif] is  [Graphics:Images/NevilleAlgorithmMod_gr_507.gif] where we compute:

        [Graphics:Images/NevilleAlgorithmMod_gr_508.gif]    

Computer Programs  Neville Interpolation

Mathematica Subroutine (Neville Interpolation).

[Graphics:Images/NevilleAlgorithmMod_gr_509.gif]

Algorithm (Aitken Interpolation).   Given the nodes [Graphics:Images/NevilleAlgorithmMod_gr_510.gif] the Aitken interpolation at [Graphics:Images/NevilleAlgorithmMod_gr_511.gif] is  [Graphics:Images/NevilleAlgorithmMod_gr_512.gif] where we compute:

        [Graphics:Images/NevilleAlgorithmMod_gr_513.gif]  

Computer Programs  Aitken Interpolation

Mathematica Subroutine (Aitken Interpolation).

[Graphics:Images/NevilleAlgorithmMod_gr_514.gif]

Example 7.  Given  [Graphics:Images/NevilleAlgorithmMod_gr_515.gif]  and the nodes [Graphics:Images/NevilleAlgorithmMod_gr_516.gif] compute the entries in Aitken's tableau and Neville's tableau for evaluating  [Graphics:Images/NevilleAlgorithmMod_gr_517.gif]  at  [Graphics:Images/NevilleAlgorithmMod_gr_518.gif]  
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