Divided differences
Again, let the function f be tabulated at the (not necessarily equidistant) points [x0, x1, . . . , xn]. We define the divided differences between points as follows:
As an example, we will construct from the data:
We note that the third divided differences are constant. In Section 3, we shall use the table to interpolate by means of Newton's divided difference formula and determine the corresponding interpolating cubic.
Newton's divided difference formula
According to the definitions of divided differences, we find
Multiplying the second equation by (x - x0), the third by (x - x0)(x - x1), etc., and adding the results yields Newton's divided difference forrnula, suitable for computer implementation (PSEUDO CODE)
where
.
Note that the remainder term R vamishes at x0, x1, . . . , xn, whence we infer that the other terms on the right-hand side constitute the interpolating polynomial or, equivalently, the Lagrange polynomial. If the required degree of the interpolating polynomial is not known in advance, it is customary to arrange the points x1, . . . , xn, according to their increasing distance from x and add terms until R is small enough.
Example
From the tabulated function in Section 1, we will estimate f (2) and f(4), using Newton's divided difference formula and find the corresponding interpolating polynomials.
The third divided difference being constant, we can fit a cubic through the five points. By Newton's divided difference formula, using x0 = 0, x1 = 1, x2 = 3, and x3 = 6, the interpolation cubic becomes:
so that
.
Obviously, the interpolating polynomial is
.
In order to estimate the value of f(4), we identify x0 =1, x1 = 3, x2 = 6, x3 =10, whence
and
.
As expected, the two interpolating polynomials are the same cubic, i.e., x3 - 8x + 1.
Errors in interpolating polynomials
In Section 2, we have seen that the error in an interpolating polynomial of degree n was given by
.
As it stands, this expression is not
very useful, because it involves the unknown quantity 
However, it
may be shown (cf., for example, Conte and de Boor (1980))
that, if 
and f
is (n + 1)-times differentiable on (a, b),
then there exists a 
such that
,
whence it follows that
.
This formula may be useful when we know the function generating the data and wish to find lower and upper error bounds. For example, let there be given sin 0 = 0, sin(0.2) = 0.198669, and sin(0.4) = 0.389418 to 6D (where the arguments in the sine function are in radians). Then we can form the divided difference table:
.
Thus, the quadratic approximation to sin(0.1) is:
.
.
Since n = 2, the magnitude of the error in the approximation is given by
,
where 0 < x < 0.4.
For f(x) = sin x, one has 
, so that 
It then
follows that
.
The absolute value of the actual error is 0.000492, which is within these bounds.
Aitken's method
In practice, Aitken's procedure is often adopted; it yields systematically and successively better interpolation polynomials (corresponding to successively higher order truncation of Newton's divided difference formula). Thus, one finds
and, obviously,
.
Next, since
one finds
,
noting that
,
etc. In passing, we may note that
.
At first sight, this procedure may look complicated, but it is systematic, and therefore computationally straightforward. It is represented by the scheme:
.
One of its major advantages is that the accuracy may be gauged by comparing successive steps (corresponding, of course, to gauging the appropriate truncation of Newton's divided difference formula.) As in the case of Newton's divided difference formula, as a rule, the points x0, x1, x2, . . . are ordered such that x0 - x, x - x, x2 - x, . . . form a sequence with increasing magnitude. Finally, we remark that although the derivation of Aitken's method emphasizes its relationship to the Newton formula, it is notable that it ultimately does not involve at all divided differences!
As an example, we will estimate f (2) by Aitken's method from the function, tabulated in Section I.
We have x = 2, so that we choose x0 = 1, x1 = 3, x2 = 0, x3 = 6, and x4 = 10: thus Aitken's scheme yields
The computations proceed from the left, row by row, with an appropriately divided cross multiplication of the respective entries with those in the (xk -- x) column on the right hand side. Thus,
The entry -7 (in circle) appears twice successively along the diagonal, so that one may conclude that f (2) = -7.
from the points 
.
use Newton's
divided difference formula to estimate the value of e0.25.
Find lower and upper bounds on the magnitude of the error
and verify that the actual magnitude is within the
calculated bounds.