Background.

    We have seen how to expand a function   in a Maclaurin polynomial about involving the powers and a Taylor polynomial about involving the powers .  These polynomials have a single "center" .  Polynomial interpolation can be used to construct the polynomial of  degree    that passes through the n+1 points  ,  for  .  If multiple "centers"      are used, then the result is the so called Newton polynomial.  We attribute much of the founding theory to Sir Isaac Newton (1643-1727).

Theorem (Newton Polynomial).  Assume that   and   for    are distinct  values.  Then

    ,
    
where is a polynomial that can be used to approximate  ,

      

and we write  

    .

The Newton polynomial goes through the points  ,  i.e.

        for   .  

The remainder term   has the form

    ,

for some value that lies in the interval .  The coefficients    are constructed using divided differences.

Proof  Newton Polynomials  Newton Polynomials  

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 coefficient of the Newton polynomial   is    and it is the top element in the column of the i-th divided differences.

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

    

Proof  Newton Polynomials  Newton Polynomials  

    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  .  

Proof  Newton Polynomials  Newton Polynomials  

Animations (Newton Polynomials  Newton Polynomials).  Internet hyperlinks to animations.

Computer Programs  Newton Polynomials  Newton Polynomials  

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

Example 1.   Form the Newton polynomials of degree  n = 1,2, 3, 4, and 5  for the function    over the interval    using equally spaced nodes selected from the following list  
  
Solution 1 (a).
Solution 1 (b).
Solution 1 (c).
Solution 1 (d).
Solution 1 (e).
Solution 1 (f).
Solution 1 (g).

Example 2.  Error Analysis.  Investigate the error for the Newton polynomial approximations in Example 1.
Solution 2 (a).
Solution 2 (b).
Solution 2 (c).
Solution 2 (d).
Solution 2 (e).

Example 3.  Summary of the maximum error and the error bounds over the intervals    for the Newton polynomials in Example 2.
3 (a).  Find  .  
3 (b).  Find  .  
3 (c).  Find  .  
3 (d).  Find  .  
3 (e).  Find  .  
Solution 3.

Example 4.  Application to number theory.
4 (a).  Find the formula for the sum of the first  n  integers.
4 (b).  Find the formula for the sum of the squares of the first  n integers.  
Solution 4.

Various Scenarios and Animations for Newton Polynomials.

Example 5.  Find the Newton polynomial approximation for  , on the interval , , and .  
Solution 5 (a).
Solution 5 (b).
Solution 5 (c).

Example 6.  Find the Newton polynomial approximation for  , on the interval .  
Solution 6.

Example 7.  Find the Newton polynomial approximation for  , on the interval .  
Solution 7.

Example 8.  Find the Newton polynomial approximation for  , on the interval , and .  
Solution 8 (a).
Solution 8 (b).

Example 9.  Find the Newton polynomial approximation for  , on the interval .  
Solution 9.

Example 10.  Find the Newton polynomial approximation for  , on the interval .  
Solution 10.

Example 11.  Find the Newton polynomial approximation for  , on the interval .  
Solution 11.

Example 12.  Find the Newton polynomial approximation for  , on the interval .  
Solution 12.

Example 13.  Find the Newton polynomial approximation for  , on the interval .  
Solution 13.

Example 14.  Find the Newton polynomial approximation for  , on the interval .  
Solution 14.

Example 15.  Find the Newton polynomial approximation for  , on the interval .  
Solution 15.

Example 16.  Find the Newton polynomial approximation for  , on the interval .  
Solution 16.

Example 17.  Find the Newton polynomial approximation for  , on the interval .  
Solution 17.

Animations (Newton Polynomial Approximation  Newton Polynomial Approximation).  Internet hyperlinks to animations.

Old Lab Project (Newton Interpolation Polynomial  Newton Interpolation Polynomial).  Internet hyperlinks to an old lab project.  

Research Experience for Undergraduates

Newton Polynomials  Newton Polynomials  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook Newton Polynomials

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004