NEWTON’S DIVIDED 

DIFFERENCE POLYNOMIAL

 

INTERACTIVE E-BOOK

INTERPOLATION

MAJOR

GENERAL

On non Internet Explorer browsers, the equations may not show up.

As an alternative or if you prefer,

you can see the pdf version of the ebook instead

Title

An interactive e-book for illustrating Newton’s Divided Difference Polynomial Method for interpolation.

Creator

Autar K Kaw

Subject and Keywords

Newton’s Divided Difference Polynomial Method, Interpolation, Mathcad, Maple, Mathematica, Matlab, Simulations.

Description

An interactive E-book for illustrating Newton’s Divided Difference Polynomial Method for interpolation.  It includes links to simulations in Mathcad, Maple, Mathematica and Matlab for the algorithm, multiple choice quizzes, and a PowerPoint presentation.

Publisher

Holistic Numerical Methods Institute,

College of Engineering,

University of South Florida, Tampa, FL 33620-5350.

Contributors

Autar Kaw, Michael Keteltas

Format

Text/HTML

Last Revised

June 14, 2004

Identifier

 

Language

English

Rights

http://numericalmethods.eng.usf.edu/rights.htm

 

Table of Contents

Background

        What is Interpolation

Newton’s Divided Difference Polynomial Method

        Linear interpolation

        Quadratic interpolation

        General form of Newton’s Divided Difference Polynomial

        PowerPoint presentation

Examples

          Example 1: First order application problem

          Example 2: Second order application problem

          Example 3: Third order application problem

          Simulation (Mathcad Maple Mathematica Matlab)

Problem Sets

          Multiple choice question examination

 

Background

This is an example of how an instructor of a Numerical Methods course can develop an E-book on a single topic by using resources that are only available at the Holistic Numerical Methods Institute (HNMI) Website.

Although one of the primary advantages of a web-based resource is that one can use documents outside of its own domain, we are particularly using this example as a way to illustrate the holistic nature of the resources available at HNMI.   You are welcome to modify and edit this e-book to suit your purpose.

Using the textbook document written in MS Word 2000 as a foundation, it was made interactive within MS Word 2000 by putting bookmarks and hyperlinks to background information, PowerPoint presentations, Mathcad simulations, historical anecdotes, multiple choice tests, problem sets, etc.  Then the MS Word 2000 file was saved as a webpage and that is what you are about to read here.

Back to TOC

What is interpolation?

Many a times, a function  is given only at discrete points such as .  How does one find the value of ‘y’ at any other value of ‘x’?  Well, a continuous function may be used to represent the ‘n+1’ data values with  passing through the ‘n+1’ points.  Then one can find the value of y at any other value of x.   This is called interpolation.  Of course, if 'x' falls outside the range of 'x' for which the data is given, it is no longer interpolation but instead is called extrapolation. 

So what kind of function  should one choose?  A polynomial is a common choice for an interpolating function because polynomials are easy to

a)                  evaluate

b)                  differentiate, and

c)                  integrate


as opposed to other choices such as a sine or exponential series.

Figure 1: Interpolation of discrete data

 

          Polynomial interpolation involves finding a polynomial of order ‘n’ that passes through the ‘n+1’ points.  One of the methods is called the Newton’s divided difference polynomial method.  Other methods include the direct method and the Lagrangian interpolation method.  We discuss the Newton’s divided difference polynomial method in this section.

Back to TOC

 

   Newton’s Divided Difference Interpolating Polynomial Method

To illustrate this method, linear and quadratic interpolation is presented first.  Then, the general form of the Newton’s Divided Difference Polynomial method is presented.  To illustrate the general form, cubic interpolation is shown.

Back to TOC

 

Linear interpolation: Given    fit a linear interpolant through the data.  Noting  and , assume the linear interpolant,  is given by

Since at ,

,

and at ,

                     

giving

         

So

         

giving the linear interpolant to be

                                           Figure 2: Linear interpolation

             

 

Back to TOC

 

Example 1

The upward velocity of a rocket is given as a function of time in Table 1.

Table 1:  Velocity as a function of time

t

v(t)

s

m/s

0

0

10

227.04

15

362.78

20

517.35

22.5

602.97

30

901.67

Determine the value of the velocity at t=16 seconds using first order polynomial interpolation by Newton’s Divided Difference Polynomial method.

Figure 3: Velocity vs. time data for the rocket example

Solution:

For the linear interpolation, the velocity is given by

         

Since we want the velocity at , we choose two data points that are closest to  and that also bracket .  Those two points are  and .

         

         

gives

         

              

         

              

              

Hence

         

                           

At

         

                    m/s

If we expand

         

we get

                  

and this is the same expression as obtained in the direct method.

Back to TOC

 

Quadratic interpolation: Given  and  fit a quadratic interpolant through the data.  Noting  and assume the quadratic interpolant  given by

         

At

         

                                   

                              

At

         

                       

giving

                             

At

         

         

giving

        

Hence the quadratic interpolant is given by

         

 


Figure 4: Quadratic interpolation

Back to TOC

 

Example 2

The upward velocity of a rocket is given as a function of time in Table 2.

Table 2:  Velocity as a function of time

t

v(t)

s

m/s

0

0

10

227.04

15

362.78

20

517.35

22.5

602.97

30

901.67

 

Determine the value of the velocity at t=16 seconds using second order polynomial interpolation using Newton’s divided difference polynomial method.  Find the absolute relative approximate error for approximation from second order polynomial.

Solution:

The velocity profile is chosen as

         

Since we want to find the velocity at  we need to choose three data points that are closest to  and also bracket .  These three points are  and .

         

           

         

then

         

              

         

              

              

         

              

              

              

          then

                     

                                   

          At

                   

                              m/s

If we expand,

                             

we get

            ,   

          This is the same expression obtained by the direct method.

Back to TOC
 
General Form of Newton’s Divided Difference Polynomial

In the two previous cases, we found how linear and quadratic interpolation is derived by Newton’s Divided Difference polynomial method.  Let us revisit the quadratic polynomial interpolant formula

         

where

              

               

              

Note that  and  are finite divided differences.   and  are first, second, and third finite divided differences, respectively.  Denoting first divided difference by

         

the second divided difference by

         

and the third divided difference by

         

                             

where and  are called bracketed functions of their variables enclosed in square brackets.

Rewriting

         

This leads us to writing the general form of the Newton’s divided difference polynomial for  data points,  as

         

where