Numerical Analysis/Divided differences

The Expanded Form of the Definition

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

f[x_{0},x_{1}\dots ,x_{n}]=\sum _{j=0}^{n}{\frac {f(x_{j})}{\prod _{k\in \{0,\dots ,n\}\setminus \{j\}}(x_{j}-x_{k})}}

(expanded)

With help of a polynomial functions $q$ with $q(\xi )=(\xi -x_{0})\cdots (\xi -x_{n})$ this can be written as

f[x_{0},\dots ,x_{n}]=\sum _{j=0}^{n}{\frac {f(x_{j})}{q'(x_{j})}}\,.

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

For $n=1$ , (expanded) holds because

f[x_{0},x_{1}]={\frac {f[x_{1}]-f[x_{0}]}{x_{1}-x_{0}}}={\frac {f(x_{0})}{(x_{0}-x_{1})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})}}\,.

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

If the formula $f[x_{0},x_{1},\ldots ,x_{n}]=\sum _{j=0}^{n}{\frac {f(x_{j})}{q'(x_{j})}}$ , where $q(\xi )=\prod _{k=0}^{n}(\xi -x_{k})$ , then denoting $q_{1}(\xi )=\prod _{k=1}^{n+1}(\xi -x_{k}),$ $q_{2}(\xi )=\prod _{k=0}^{n}(\xi -x_{k})$ and $Q(\xi )=\prod _{k=0}^{n+1}(\xi -x_{k})$ , we have

{\begin{aligned}f[x_{0},x_{1},\ldots ,x_{n+1}]&={\frac {f[x_{1},\ldots ,x_{n+1}]-f[x_{0},\ldots ,x_{n}]}{x_{n+1}-x_{0}}}\\&={\frac {1}{x_{n+1}-x_{0}}}\left(\sum _{j=0}^{n}{\frac {f(x_{j+1})}{q_{1}'(x_{j+1})}}-\sum _{j=0}^{n}{\frac {f(x_{j})}{q_{2}'(x_{j})}}\right)\\&={\frac {1}{x_{n+1}-x_{0}}}\left(\sum _{k=1}^{n+1}{\frac {f(x_{k})}{q_{1}'(x_{k})}}-\sum _{k=0}^{n}{\frac {f(x_{k})}{q_{2}'(x_{k})}}\right)\\&={\frac {1}{x_{n+1}-x_{0}}}\left({\frac {f(x_{n+1})}{q_{1}'(x_{n+1})}}+\sum _{k=1}^{n}f(x_{k})\left({\frac {1}{q_{1}'(x_{k})}}-{\frac {1}{q_{2}'(x_{k})}}\right)-{\frac {f(x_{0})}{q_{2}'(x_{0})}}\right)\,.\end{aligned}}

We have,

(x_{n+1}-x_{0})q_{1}'(x_{n+1})=(x_{n+1}-x_{0})\prod _{k=1}^{n}(x_{n+1}-x_{k})=\prod _{k=0}^{n}(x_{n+1}-x_{k})=Q'(x_{n+1}),

(x_{n+1}-x_{0})q_{2}'(x_{0})=(x_{n+1}-x_{0})\prod _{k=1}^{n}(x_{0}-x_{k})=-\prod _{k=1}^{n+1}(x_{0}-x_{k})=-Q'(x_{0})

and

{\begin{aligned}{\frac {1}{q_{1}'(x_{k})}}-{\frac {1}{q_{2}'(x_{k})}}&=\prod _{j=1,j\neq k}^{n+1}{\frac {1}{x_{k}-x_{j}}}-\prod _{j=0,j\neq k}^{n}{\frac {1}{x_{k}-x_{j}}}\\&=\prod _{j=0,j\neq k}^{n+1}{\frac {1}{x_{k}-x_{j}}}(x_{k}-x_{0}-(x_{k}-x_{n+1}))\\&=(x_{n+1}-x_{0})\prod _{j=0,j\neq k}^{n+1}{\frac {1}{x_{k}-x_{j}}}\,,\end{aligned}}

which gives

f[x_{0},x_{1},\ldots ,x_{n+1}]=\sum _{j=0}^{n+1}{\frac {f(x_{j})}{Q'(x_{j+1})}}=\sum _{j=0}^{n+1}{\frac {f(x_{j})}{\prod _{k\in \{0,\dots ,n\}\setminus \{j\}}(x_{j}-x_{k})}}\,.

Hence, since the assertion holds for $n=1$ and $n+1$ , then by induction, the assertion holds for all positive integer $n$ .

Symmetry property of divided differences

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

f[x_{0},x_{1}\dots ,x_{n}]=f[x_{1},x_{0}\dots ,x_{n}]\quad {\text{etc.}}

When $n=1$ , we have

f[x_{1},x_{0}]={\frac {f[x_{1}]-f[x_{0}]}{x_{1}-x_{0}}}={\frac {f(x_{0})}{(x_{0}-x_{1})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})}}={\frac {f[x_{0}]-f[x_{1}]}{x_{0}-x_{1}}}=f[x_{0},x_{1}]\,.

Hence $f[x_{1},x_{0}]=f[x_{0},x_{1}]$ , which is the symmetry of the first divided difference.

When $n=2$ , we have

{\begin{aligned}f[x_{2},x_{1},x_{0}]&={\frac {f[x_{2},x_{1}]-f[x_{1},x_{0}]}{x_{2}-x_{0}}}={\frac {{\frac {f[x_{2}]-f[x_{1}]}{x_{2}-x_{1}}}-{\frac {f[x_{1}]-f[x_{0}]}{x_{1}-x_{0}}}}{x_{2}-x_{0}}}\\&={\frac {f(x_{2})}{(x_{2}-x_{0})\cdot (x_{2}-x_{1})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})\cdot (x_{1}-x_{2})}}+{\frac {f(x_{0})}{(x_{0}-x_{1})\cdot (x_{0}-x_{2})}}\\&=f[x_{0},x_{1},x_{2}]=f[x_{1},x_{0},x_{2}]\quad {\text{etc.}}\end{aligned}}

Hence $f[x_{2},x_{1},x_{0}]=f[x_{0},x_{1},x_{2}]=f[x_{1},x_{0},x_{2}]$ etc., which is the symmetry of the second divided difference.

Similarly, when $n=3$ we have

{\begin{aligned}f[x_{3},x_{2},x_{1},x_{0}]&={\frac {f[x_{3},x_{2},x_{1}]-f[x_{2},x_{1},x_{0}]}{x_{3}-x_{0}}}\\&={\frac {f(x_{0})}{(x_{0}-x_{1})\cdot (x_{0}-x_{2})\cdot (x_{0}-x_{3})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})\cdot (x_{1}-x_{2})\cdot (x_{1}-x_{3})}}+{\frac {f(x_{2})}{(x_{2}-x_{0})\cdot (x_{2}-x_{1})\cdot (x_{2}-x_{3})}}+\\&\quad \quad {\frac {f(x_{3})}{(x_{3}-x_{0})\cdot (x_{3}-x_{1})\cdot (x_{3}-x_{2})}}\\&=f[x_{0},x_{1},x_{2},x_{3}]=f[x_{1},x_{0},x_{2},x_{3}]\quad {\text{etc.}}\end{aligned}}

Hence $f[x_{3},x_{2},x_{1},x_{0}]=f[x_{0},x_{1},x_{2},x_{3}]=f[x_{1},x_{0},x_{3},x_{2}]$ etc., which is the symmetry of the third divided difference.

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

f[x_{0},x_{1}\dots ,x_{n}]=\sum _{j=0}^{n}{\frac {f(x_{j})}{\prod _{k\in \{0,\dots ,n\}\setminus \{j\}}(x_{j}-x_{k})}}=f[x_{1},x_{0}\dots ,x_{n}]\quad {\text{etc.}}

Hence $f[x_{0},x_{1}\dots ,x_{n}]=f[x_{1},x_{0}\dots ,x_{n}]$ etc., which is the symmetry of the $n^{th}$ divided difference.

Computing the divided differences in tabular form

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.

{\begin{matrix}x&f(x)&{\text{First Divided Difference}}&{\text{Second Divided Difference}}&{\text{Third Divided Difference}}&{\text{Fourth Divided Difference}}\\x_{0}&f[x_{0}]&&&\\&&f[x_{0},x_{1}]={\frac {f[x_{1}]-f[x_{0}]}{x_{1}-x_{0}}}&\\x_{1}&f[x_{1}]&&f[x_{0},x_{1},x_{2}]={\frac {f[x_{1},x_{2}]-f[x_{0},x_{1}]}{x_{2}-x_{0}}}&\\&&f[x_{1},x_{2}]={\frac {f[x_{2}]-f[x_{1}]}{x_{2}-x_{1}}}&&f[x_{0},x_{1},x_{2},x_{3}]={\frac {f[x_{1},x_{2},x_{3}]-f[x_{0},x_{1},x_{2}]}{x_{3}-x_{0}}}\\x_{2}&f[x_{2}]&&f[x_{1},x_{2},x_{3}]={\frac {f[x_{2},x_{3}]-f[x_{1},x_{2}]}{x_{3}-x_{1}}}&&f[x_{0},x_{1},x_{2},x_{3},x_{4}]={\frac {f[x_{1},x_{2},x_{3},x_{4}]-f[x_{0},x_{1},x_{2},x_{3}]}{x_{4}-x_{0}}}\\&&f[x_{2},x_{3}]={\frac {f[x_{3}]-f[x_{2}]}{x_{3}-x_{2}}}&&f[x_{1},x_{2},x_{3},x_{4}]={\frac {f[x_{2},x_{3},x_{4}]-f[x_{1},x_{2},x_{3}]}{x_{4}-x_{1}}}\\x_{3}&f[x_{3}]&&f[x_{2},x_{3},x_{4}]={\frac {f[x_{3},x_{4}]-f[x_{2},x_{3}]}{x_{4}-x_{2}}}&\\&&f[x_{3},x_{4}]={\frac {f[x_{4}]-f[x_{3}]}{x_{4}-x_{3}}}&\\x_{4}&f[x_{4}]&\\\end{matrix}}

A Numerical Example 1

For a function $f$ , the divided differences are given by

{\begin{matrix}x_{1}=2&f[x_{1}]=2&\\&\\x_{0}=1&f[x_{0}]=-6&\\&\\x_{2}=4&f[x_{2}]=12&\\\end{matrix}}

find $f[x_{0},x_{1},x_{2}]$ .

Solution:

{\begin{matrix}x&f(x)&{\text{First Divided Difference}}&{\text{Second Divided Difference}}\\x_{1}=2&f[x_{1}]=2&&\\&&f[x_{1},x_{0}]={\frac {(-6)-2}{1-2}}=8&&\\x_{0}=1&f[x_{0}]=-6&&f[x_{1},x_{0},x_{2}]={\frac {6-8}{4-2}}=-1\\&&f[x_{0},x_{2}]={\frac {12-(-6)}{4-1}}=6&&\\x_{2}=4&f[x_{2}]=12&&\\\end{matrix}}

Hence, $f[x_{1},x_{0},x_{2}]=-1$ and by symmetry property we know that $f[x_{1},x_{0},x_{2}]=f[x_{0},x_{1},x_{2}]$ , Hence $f[x_{0},x_{1},x_{2}]=-1$ .

A Numerical Example 2

For a function $f$ , the divided differences are given by

{\begin{matrix}x_{0}=0.0&f[x_{0}]&&\\&&f[x_{0},x_{1}]&&\\x_{1}=0.4&f[x_{1}]&&&f[x_{0},x_{1},x_{2}]={\frac {50}{7}}&\\&&f[x_{1},x_{2}]=10&&\\x_{2}=0.7&f[x_{2}]=6&&\\\end{matrix}}

Determine the missing entries in the table.

Solution:

We have the formula

f[x_{0},x_{1},x_{2}]={\frac {f[x_{1},x_{2}]-f[x_{0},x_{1}]}{x_{2}-x_{0}}}

and substituting gives

{\frac {50}{7}}={\frac {(10-f[x_{0},x_{1}])}{0.7}}\,.

Thus,

f[x_{0},x_{1}]=-0.7\cdot ({\frac {50}{7}})+{10}=5

Using the formula

f[x_{1},x_{2}]={\frac {f[x_{2}]-f[x_{1}]}{x_{2}-x_{1}}}

and substituting gives

10={\frac {(6-f[x_{1}])}{0.3}}\,.

Thus,

f[x_{1}]=6-3=3\,.

Further,

f[x_{0},x_{1}]={\frac {f[x_{1}]-f[x_{0}]}{x_{1}-x_{0}}}\,.

So,

5={\frac {(3-f[x_{0}])}{0.4}}\,.

Thus,

f[x_{0}]=3-2=1

.

Algorithm: Computing the Divided Differences

Algorithm: Newton's Divided-Differences

   Given the points  $(x_{i},f(x_{i})),i=0,1,...,n.$ 
   Step 1:  Initialize  $F_{i},_{0}=f(x_{i}),i=0,1,...,n.$ 
   Step 2:  
          For  $i=1:n.$ 
             For  $j=1:i.$ 
                $F_{i},_{j}={\frac {F_{i},_{j-1}-F_{i-1},_{j}}{x_{i}-x_{i-j}}}$ 
             End
          End
   Result: The diagonal,  $F_{i},_{j}$  now contains  $f[x_{0},...,x_{i}].$

Relationship between Generalization of the Mean Value Theorem and the Derivatives

Generalization of the Mean Value Theorem

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

\xi \in (\min\{x_{0},\dots ,x_{n}\},\max\{x_{0},\dots ,x_{n}\})\,

where the nth derivative of f equals $n$ ! times the $n^{th}$ divided difference at these points:

f[x_{0},\dots ,x_{n}]={\frac {f^{(n)}(\xi )}{n!}}\,.

This is called the Generalized Mean Value Theorem. For $n=1$ we have

f[x_{0},x_{1}]={\frac {f[x_{1}]-f[x_{0}]}{x_{1}-x_{0}}}=f'(\xi )

for some $\xi$ between $x_{0}$ and $x_{1}$ , which is exactly Mean Value Theorem. We have extended MVT to higher order derivatives as

f[x_{0},\dots ,x_{n}]={\frac {f^{(n)}(\xi )}{n!}}\,.

What is the theorem telling us?

This theorem is telling us that the Newton's

n^{th}

divided difference is in some sense approximation to the

n^{th}

derivatives of

f

.

A Numerical Example

Let $f(x)=\cos(x)$ , $x_{0}=0.2,x_{1}=0.3,x_{2}=0.4$ . Then, Show that

$f[x_{0},x_{1}]\approx f'(\xi )$
$f[x_{0},x_{1},x_{2}]\approx {\frac {1}{2}}f''(\xi )$

for some $\xi$ between the minimum and maximum of $x_{0},x_{1}$ and $x_{2}$ .

Solution:

f[x_{0},x_{1}]={\frac {f[x_{1}]-f[x_{0}]}{x_{1}-x_{0}}}={\frac {\cos(0.3)-\cos(0.2)}{0.3-0.2}}=-0.2473009

If we chose $\xi =0.25,$ Where $0.25\in (0.2,0.3)$ and we get $f'(\xi )=-\sin(0.25)=-0.24744040$ and we can see that $f[x_{0},x_{1}]$ is a very good approximation of this derivative. Similarly,

f[x_{1},x_{2}]={\frac {f[x_{2}]-f[x_{1}]}{x_{2}-x_{1}}}={\frac {\cos(0.4)-\cos(0.3)}{0.4-0.3}}=-0.3427550

and

f[x_{0},x_{1},x_{2}]={\frac {f[x_{1},x_{2}]-f[x_{0},x_{1}]}{x_{2}-x_{0}}}={\frac {-0.3427550-(-0.2473009)}{0.4-0.2}}=-0.4772705\,.

Thus, by the Generalized Mean Value Theorem with $n=2$ we have

f[x_{0},x_{1},x_{2}]={\frac {1}{2}}f''(\xi )

for some $\xi$ between the minimum and maximum of $x_{0},x_{1}$ and $x_{2}$ . Taking $f''(\xi )=-\cos(\xi )$ with $\xi =x_{1}$ , we have ${\frac {1}{2}}f''(0.3)=-{\frac {1}{2}}\cos(0.3)=-0.4776682$ which is nearly equal to the result of $f[x_{0},x_{1},x_{2}]=-0.4772705$ Thus with this example we conclude that the Newton's $n^{th}$ divided difference is in some sense an approximation to the $n^{th}$ derivatives of $f$ .