Given n + 1 data points
where the are assumed to be pairwise distinct, the forward divided differences are defined as:
To make the recursive process of computation clearer, the divided differences can be put in tabular form, where the columns correspond to the value of j above, and each entry in the table is computed from the difference of the entries to its immediate lower left and to its immediate upper left, divided by a difference of corresponding x-values:
Notation
Note that the divided difference depends on the values and , but the notation hides the dependency on the x-values. If the data points are given by a function f,
one sometimes writes the divided difference in the notation
Other notations for the divided difference of the function ƒ on the nodes x0, ..., xn are:
Example
Divided differences for and the first few values of :
Thus, the table corresponding to these terms upto two columns has the following form:
The divided difference scheme can be put into an upper
triangular matrix:
Then it holds
if is a scalar
This follows from the Leibniz rule. It means that multiplication of such matrices is
commutative. Summarised, the matrices of divided difference schemes with respect to the same set of nodes x form a
commutative ring.
Since is a triangular matrix, its
eigenvalues are obviously .
Let be a
Kronecker delta-like function, that is Obviously , thus is an
eigenfunction of the pointwise function multiplication. That is is somehow an "
eigenmatrix" of : . However, all columns of are multiples of each other, the
matrix rank of is 1. So you can compose the matrix of all eigenvectors of from the -th column of each . Denote the matrix of eigenvectors with . Example The
diagonalization of can be written as
Polynomials and power series
The matrix
contains the divided difference scheme for the
identity function with respect to the nodes , thus contains the divided differences for the
power function with
exponent.
Consequently, you can obtain the divided differences for a
polynomial function by applying to the matrix : If
and
then
This is known as Opitz' formula.[2][3]
Now consider increasing the degree of to infinity, i.e. turn the Taylor polynomial into a
Taylor series.
Let be a function which corresponds to a
power series.
You can compute the divided difference scheme for by applying the corresponding matrix series to :
If
and
then
If and , the divided differences can be expressed as[4]
where is the -th
derivative of the function and is a certain
B-spline of degree for the data points , given by the formula
This is a consequence of the
Peano kernel theorem; it is called the Peano form of the divided differences and is the Peano kernel for the divided differences, all named after
Giuseppe Peano.
When the data points are equidistantly distributed we get the special case called forward differences. They are easier to calculate than the more general divided differences.
Given n+1 data points
with
the forward differences are defined as
whereas the backward differences are defined as:
Thus the forward difference table is written as:whereas the backwards difference table is written as:
The relationship between divided differences and forward differences is[5]whereas for backward differences:[citation needed]
Myron B. Allen; Eli L. Isaacson (1998). Numerical Analysis for Applied Science. John Wiley & Sons. Appendix A.
ISBN978-1-118-03027-1.
Ron Goldman (2002). Pyramid Algorithms: A Dynamic Programming Approach to Curves and Surfaces for Geometric Modeling. Morgan Kaufmann. Chapter 4:Newton Interpolation and Difference Triangles.
ISBN978-0-08-051547-2.
Given n + 1 data points
where the are assumed to be pairwise distinct, the forward divided differences are defined as:
To make the recursive process of computation clearer, the divided differences can be put in tabular form, where the columns correspond to the value of j above, and each entry in the table is computed from the difference of the entries to its immediate lower left and to its immediate upper left, divided by a difference of corresponding x-values:
Notation
Note that the divided difference depends on the values and , but the notation hides the dependency on the x-values. If the data points are given by a function f,
one sometimes writes the divided difference in the notation
Other notations for the divided difference of the function ƒ on the nodes x0, ..., xn are:
Example
Divided differences for and the first few values of :
Thus, the table corresponding to these terms upto two columns has the following form:
The divided difference scheme can be put into an upper
triangular matrix:
Then it holds
if is a scalar
This follows from the Leibniz rule. It means that multiplication of such matrices is
commutative. Summarised, the matrices of divided difference schemes with respect to the same set of nodes x form a
commutative ring.
Since is a triangular matrix, its
eigenvalues are obviously .
Let be a
Kronecker delta-like function, that is Obviously , thus is an
eigenfunction of the pointwise function multiplication. That is is somehow an "
eigenmatrix" of : . However, all columns of are multiples of each other, the
matrix rank of is 1. So you can compose the matrix of all eigenvectors of from the -th column of each . Denote the matrix of eigenvectors with . Example The
diagonalization of can be written as
Polynomials and power series
The matrix
contains the divided difference scheme for the
identity function with respect to the nodes , thus contains the divided differences for the
power function with
exponent.
Consequently, you can obtain the divided differences for a
polynomial function by applying to the matrix : If
and
then
This is known as Opitz' formula.[2][3]
Now consider increasing the degree of to infinity, i.e. turn the Taylor polynomial into a
Taylor series.
Let be a function which corresponds to a
power series.
You can compute the divided difference scheme for by applying the corresponding matrix series to :
If
and
then
If and , the divided differences can be expressed as[4]
where is the -th
derivative of the function and is a certain
B-spline of degree for the data points , given by the formula
This is a consequence of the
Peano kernel theorem; it is called the Peano form of the divided differences and is the Peano kernel for the divided differences, all named after
Giuseppe Peano.
When the data points are equidistantly distributed we get the special case called forward differences. They are easier to calculate than the more general divided differences.
Given n+1 data points
with
the forward differences are defined as
whereas the backward differences are defined as:
Thus the forward difference table is written as:whereas the backwards difference table is written as:
The relationship between divided differences and forward differences is[5]whereas for backward differences:[citation needed]
Myron B. Allen; Eli L. Isaacson (1998). Numerical Analysis for Applied Science. John Wiley & Sons. Appendix A.
ISBN978-1-118-03027-1.
Ron Goldman (2002). Pyramid Algorithms: A Dynamic Programming Approach to Curves and Surfaces for Geometric Modeling. Morgan Kaufmann. Chapter 4:Newton Interpolation and Difference Triangles.
ISBN978-0-08-051547-2.