Numerical Analysis/Divided differences

The Expanded Form of the Definition

edit

The usual definition of divided differences is equivalent to the Expanded form

 

 

 

 

 

(expanded)

With help of a polynomial functions   with   this can be written as

 

Since we will need the Expanded form (expanded) for our other work below, we first prove that it is equivalent to the usual definition.

Proof of the expanded form

edit

For  , (expanded) holds because

 

We now assume (expanded) holds for   and show that this implies it also holds for  . Thus by induction it holds for all  .

If the formula  , where  , then denoting     and  , we have

 

We have,

 
 

and

 

which gives

 

Hence, since the assertion holds for   and  , then by induction, the assertion holds for all positive integer  .

Symmetry property of divided differences

edit

The divided differences have a number of special properties that can simplify work with them. One of the property is called the Symmetry Property which states that the Divided differences remain unaffected by permutations (rearrangement) of their variables.

Now we prove this symmetry property by showing that

 

When  , we have

 

Hence  , which is the symmetry of the first divided difference.

When  , we have

 

Hence   etc., which is the symmetry of the second divided difference.

Similarly, when   we have

 

Hence   etc., which is the symmetry of the third divided difference.

In general, we can use the Expanded Form (expanded) to obtain

 

Hence   etc., which is the symmetry of the   divided difference.

Computing the divided differences in tabular form

edit

A difference table is again a convenient device for displaying differences, the standard diagonal form being used and thus the generation of the divided differences is outlined in Table below.


 

A Numerical Example 1

edit

For a function  , the divided differences are given by

 

find  .

A Numerical Example 2

edit

For a function  , the divided differences are given by

 

Determine the missing entries in the table.

Algorithm: Computing the Divided Differences

edit

Algorithm: Newton's Divided-Differences

edit
   Given the points  
   Step 1:  Initialize  
   Step 2:  
          For  
             For  
                
             End
          End
   Result: The diagonal,   now contains  

Relationship between Generalization of the Mean Value Theorem and the Derivatives

edit

Generalization of the Mean Value Theorem

edit

For any n + 1 pairwise distinct points x0, ..., xn in the domain of an n-times differentiable function f there exists an interior point

 

where the nth derivative of f equals   ! times the   divided difference at these points:

 

This is called the Generalized Mean Value Theorem. For   we have

 

for some   between   and  , which is exactly Mean Value Theorem. We have extended MVT to higher order derivatives as

 

What is the theorem telling us?

This theorem is telling us that the Newton's   divided difference is in some sense approximation to the   derivatives of   .

A Numerical Example

edit

Let  ,  . Then, Show that

  1.  
  2.  

for some   between the minimum and maximum of   and  .

Quiz

edit

1 find   where  

25
-25
50
-50

2 If   then, this is called symmetry of the

zero divided difference
first divided difference
second divided difference
third divided difference

3 Let  ,   Then,  

-0.2473009
0.2473009
-0.2474404
0.2474404

4 If   for some   between   and   then, this is exactly

Generalized Mean Value Theorem
Mean Value Theorem
Derivative of  
Rolle's Theorem

5 If   then, this is called

First Divided Difference
Second Divided Difference
Third Divided Difference
Fourth Divided Difference


Reference

edit
  • Guide to Numerical Analysis by Peter R. Turner
  • Numerical Analysis by Richard L. Burden and J. Douglas Faires (EIGHT EDITION)
  • Elementary Numerical Analysis by Kendall Atkinson (Second Edition)
  • Applied Numerical Analysis by Gerald / Wheatley (Sixth Edition)
  • Theory and Problems of Numerical Analysis by Francis Scheid