6.3 Divided Differences

   

 
Java Number Cruncher: The Java Programmer's Guide to Numerical Computing
By Ronald  Mak

Table of Contents
Chapter  6.   Interpolation and Approximation

6.3 Divided Differences

We can use the notation f [ x i , x j ] to represent the first divided difference:

graphics/06equ16.gif


For the second divided difference:

graphics/06equ17.gif


In general, we can define the n th divided difference recursively:

graphics/06equ18.gif


although they can be computed more efficiently by starting with the first divided differences, then computing the second, then the third, and so on.

Now, here's our payoff. For a polynomial interpolation functions in Newton form, we have

graphics/06equ19.gif


Thus, an interpolating line is

graphics/06equ20.gif


and an interpolating parabola is

graphics/06equ21.gif


Adding another data point means we simply compute and add another term to the interpolation function. The data points do not have to be in any particular order, nor do they need to be spaced evenly along the x axis.

We can visualize the computation of divided differences using a divided difference table, as shown in Table 6-1.

Table 6-1. A divided difference table showing the first through the fourth divided differences for a function f ( x ) and five data points x , x 1 , x 2 , x 3 , and x 4 . The gray shading shows an example of how to "fan back" diagonally from a divided difference to see how it is recursively defined and to determine its denominator:

graphics/06inl01.gif

i

x

f ( x )

First

Second

Third

Fourth

x

f ( x )

       
     

f [ x 1 , x ]

     

1

x 1

f ( x 1 )

 

f [ x 2 , x 1 , x ]

   
     

f [ x 2 , x 1 ]

 

f [ x 3 , x 2 , x 1 , x ]

 

2

x 2

f ( x 2 )

 

f [ x 3 , x 2 , x 1 ]

 

f [ x 4 , x 3 , x 2 , x 1 , x ]

     

f [ x 3 , x 2 ]

 

f [ x 4 , x 3 , x 2 , x 1 ]

 

3

x 3

f ( x 3 )

 

f [ x 4 , x 3 , x 2 ]

   
     

f [ x 4 , x 3 ]

     

4

x 4

f ( x 4 )

       

   
Top
 


Java Number Cruncher. The Java Programmer's Guide to Numerical Computing
Java Number Cruncher: The Java Programmers Guide to Numerical Computing
ISBN: 0130460419
EAN: 2147483647
Year: 2001
Pages: 141
Authors: Ronald Mak

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net