The usual definition of divided differences is equivalent to the
Expanded form
-
![{\displaystyle 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})}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0af78e21e5ccee96ecda3985867a2754f22e8fc8)
|
|
(expanded)
|
With help of a polynomial functions
with
this can be written as
![{\displaystyle f[x_{0},\dots ,x_{n}]=\sum _{j=0}^{n}{\frac {f(x_{j})}{q'(x_{j})}}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97116bef80032373a3071a7cf9f0901464439454)
Since we will need the Expanded form (expanded) for our other work below, we first prove that it is equivalent to the usual definition.
For
, (expanded) holds because
![{\displaystyle 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})}}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e52d5498d86c961d4f47b41b30ac345e80e57e4e)
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
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3311f493e1896951098169231d3acf08ce91b643)
We have,
![{\displaystyle (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}),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dec21e6c33bc9833399b96884a29b61f26f6248f)
![{\displaystyle (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})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c796c90ac327d382eb0b41d3a3a73ef4bc23121)
and
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fad7b1249c42a97aee78820c6dbcf446a1b8678)
which gives
![{\displaystyle 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})}}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/839c0cbd484b2d07c269aabeded396cacf319443)
Hence, since the assertion holds for
and
, then by induction, the assertion holds for all positive integer
.
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
![{\displaystyle f[x_{0},x_{1}\dots ,x_{n}]=f[x_{1},x_{0}\dots ,x_{n}]\quad {\text{etc.}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81b9da15b7e6065c19a762f2ba9eb658bb71cebd)
When
, we have
![{\displaystyle 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}]\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7fca0461f586461623dede0a8dfe7b369659cca4)
Hence
, which is the symmetry of the first divided difference.
When
, we have
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81c205acf657a96bc6de20c3365461c683a14e7a)
Hence
etc., which is the symmetry of the second divided difference.
Similarly, when
we have
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f220e9a2598cdb10a45ecd71ec03d0b0a87b637)
Hence
etc., which is the symmetry of the third divided difference.
In general, we can use the Expanded Form (expanded) to obtain
![{\displaystyle 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.}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b4b81e2cfe982e3c30cc115c25e9e7d823259c0)
Hence
etc., which is the symmetry of the
divided difference.
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.
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/956090b962623b99ad1c892d003f49f15e24aee1)
For a function
, the divided differences are given by
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c17dffe7389f40623a27583d63ebeae248761b06)
find
.
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22b8355206caf4085701e5f8afea543ea72e7069)
Hence,
and by symmetry property we know that
, Hence
.
For a function
, the divided differences are given by
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e5e07e5beee6109470e8e6bd759998830a41bc3)
Determine the missing entries in the table.
We have the formula
![{\displaystyle f[x_{0},x_{1},x_{2}]={\frac {f[x_{1},x_{2}]-f[x_{0},x_{1}]}{x_{2}-x_{0}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/388ecbcbbcad736cc439d7c0f14acfef81e9a913)
and substituting gives
![{\displaystyle {\frac {50}{7}}={\frac {(10-f[x_{0},x_{1}])}{0.7}}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee0573a61033267e5fa26659f3e69329d8da156e)
Thus,
![{\displaystyle f[x_{0},x_{1}]=-0.7\cdot ({\frac {50}{7}})+{10}=5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b198093d8245afb070ddea96c78940a76d127e2)
Using the formula
![{\displaystyle f[x_{1},x_{2}]={\frac {f[x_{2}]-f[x_{1}]}{x_{2}-x_{1}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/465fd4fa900214b1ad33d835dbe405e0f22f5d30)
and substituting gives
![{\displaystyle 10={\frac {(6-f[x_{1}])}{0.3}}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27e442dbbc52de4a4fbb8e41c125e10d68c54a86)
Thus,
![{\displaystyle f[x_{1}]=6-3=3\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29a36de7b3e34827bd1fe4b2b2b616a2dddbb4dc)
Further,
![{\displaystyle f[x_{0},x_{1}]={\frac {f[x_{1}]-f[x_{0}]}{x_{1}-x_{0}}}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2faaf3b74f90174c80a4443af06e7be5d973654)
So,
![{\displaystyle 5={\frac {(3-f[x_{0}])}{0.4}}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/317f447c844d8a9d0dabdad4f20409d83ebc77f2)
Thus,
.
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 | edit source]
For any n + 1 pairwise distinct points x0, ..., xn in the domain of an n-times differentiable function f there exists an interior point
![{\displaystyle \xi \in (\min\{x_{0},\dots ,x_{n}\},\max\{x_{0},\dots ,x_{n}\})\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d300a060ababe29bb9de6fdc592cfdea6fc9ddc0)
where the nth derivative of f equals
! times the
divided difference at these points:
![{\displaystyle f[x_{0},\dots ,x_{n}]={\frac {f^{(n)}(\xi )}{n!}}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abb353a74c8e781757c67c94e8817bcbe923acad)
This is called the Generalized Mean Value Theorem.
For
we have
![{\displaystyle f[x_{0},x_{1}]={\frac {f[x_{1}]-f[x_{0}]}{x_{1}-x_{0}}}=f'(\xi )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33e7fbc3247f56bc1d880cd7cf5cba5e88b5882b)
for some
between
and
,
which is exactly Mean Value Theorem.
We have extended MVT to higher order derivatives as
![{\displaystyle f[x_{0},\dots ,x_{n}]={\frac {f^{(n)}(\xi )}{n!}}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abb353a74c8e781757c67c94e8817bcbe923acad)
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
.
Let
,
. Then, Show that
![{\displaystyle f[x_{0},x_{1}]\approx f'(\xi )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2d698979afbdf6b70d4a82e3ebc51f63f1c5937)
![{\displaystyle f[x_{0},x_{1},x_{2}]\approx {\frac {1}{2}}f''(\xi )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ffda46c9ff19ea35aaebbcb9cd2e3a9839cdd57)
for some
between the minimum and maximum of
and
.
![{\displaystyle 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63d12a17eb5450098ae31dafcec7f3364f7dda3c)
If we chose
Where
and we get
and we can see that
is a very good approximation of this derivative.
Similarly,
![{\displaystyle 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1bd5c808de1e9aa1834d055245bbc18fb2cc8ae7)
and
![{\displaystyle 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\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bef4de90aaa3b90e9b86de6b440a0b2d73000a89)
Thus, by the Generalized Mean Value Theorem with
we have
![{\displaystyle f[x_{0},x_{1},x_{2}]={\frac {1}{2}}f''(\xi )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1cb6cc45a74be8376485f99035d4bb57c785b9fb)
for some
between the minimum and maximum of
and
.
Taking
with
, we have
which is nearly equal to the result of
Thus with this example we conclude that the Newton's
divided difference is in some sense an approximation to the
derivatives of
.
- 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