The Newton Polynomial

Definition. Divided Differences.

The divided differences for a function are defined as follows:

      

The divided difference formulae are used to construct the divided difference table:

The Newton polynomial of  degree    that passes through the   points  ,  for    is  

    

    The cubic curve in the figure below illustrates a Newton polynomial of degree n = 3.  
    
    

Theorem.  (Error Bounds for Newton 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  .  

 

Algorithm ( Newton Interpolation Polynomial ).   To construct and evaluate the Newton polynomial of  degree    that passes through the n+1 points  ,  for       

      

where  
      
and  
      

Remark 1.  Newton polynomials are created "recursively."

    .

Remark 2.  Mathematica's arrays are lists and the subscripts must start with  1  instead of  0.

 

Mathematica Subroutine (Newton Polynomial).