Newton's Divided Differences

As we have seen, the interpolating polynomial is unique. However, there are forms other than the Lagrange form which are more useful in some cases. We start by writing our interpolating polynomial in the form

$$p(x)=a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\cdots +a_n(x-x_0)(x-x_1)\cdots (x-x_{n-1}) .$$

When we impose the interpolating conditions, $p(x_i)=f(x_i),~i=0,1,\ldots ,n$we find successively

$$\begin{array} {lcl}a_0 & = & p(x_0)=f(x_0)\\ a_1 & = & \frac... ...2-x_0)}{(x_2-x_0)(x_2-x_1)}\\ \vdots & = & \vdots .\end{array}$$

The advantage of this procedure over the Lagrange method is that we can increase the degree of p from n to n+1 simply by adding the extra term $a_{n+1}(x-x_0)(x-x_1)\cdots (x-x_{n-1})(x-x_n)$. This already interpolates at the original n+1 points, since the added term vanishes at all these points, and we can find a_n+1 from the interpolation condition at x_n+1 (compare this with the work involved in increasing the degree using the Lagrange formulation, where every term would be altered).

Because of the uniqueness of the interpolating polynomial, we can equate the coefficient of xⁿ in the two forms to obtain

$$a_n=\sum _{i=0}^n\frac{f(x_i)}{\displaystyle{\prod _{\stackrel{j=0}{j\not= i}}^n(x_i-x_j)}}.$$

This is true whatever the degree n of the interpolating polynomial, and so gives an expression for the coefficients in the Newton formula of any degree. This shows that a_n depends only on $f,x_0,x_1,\ldots ,x_n$which motivates the following notation:

$$a_n=f[x_0,x_1,\ldots ,x_n],$$

which is called the nth divided difference of f. We note that this is independent of the order of the points.

Neither of the above forms is very convenient for evaluating divided differences, so we derive an alternative and more practical form. Since the order of points does not matter, we can write down the same interpolating polynomial with the order of the points reversed:

$$p(x)=f(x_n)+b_1(x-x_n)+b_2(x-x_n)(x-x_{n-1})+\cdots +b_n\prod _{i=n}^1(x-x_i).$$

Now equate the coefficients of xⁿ and x^n-1 in this and the previous form to obtain

$$\begin{array} {rrcl} x^n: & a_n & = & b_n\\ x^{n-1}:~~~~~ & ... ..._{i=n}^1x_i\\ & & = & b_{n-1}-a_n\sum _{i=n}^1x_i, \end{array}$$

using the first result. We find from this that

$$a_n=\frac{b_{n-1}-a_{n-1}}{x_n-x_0},$$

or using our new divided difference notation,

$$\begin{array} {lcl}f[x_0,x_1,\ldots ,x_n] & = & \frac{f[x_n,... ...,\ldots ,x_n]-f[x_0,x_1,\ldots ,x_{n-1}]}{x_n-x_0}.\end{array}$$

This formula is true for any value of n since the divided differences are the same for any degree of interpolating polynomal.

The interpolating polynomial may now be written as

$$p(x)=f(x_0)+(x-x_0)f[x_0,x_1]+(x-x_0)(x-x_1)f[x_0,x_1,x_2]+\cdots +\prod _{i=0}^{n-1}(x-x_i)f[x_0,x_1,\ldots ,x_n],$$

and is called Newton's Divided Difference Polynomial of degree n.

The divided differences are conveniently evaluated within a table, shown in symblolic form in Table . Notice that the table is arranged so that the function values required at each stage are adjacent.

  

Table: Divided Difference Table

  

Table: Divided Difference Table

Table shows a numerical example; the table would normally look more compact because the column headings would be omitted. Using the numbers in the table, we find the interpolating polynomial of degree 4 as

$$\begin{array} {lcl}p(x) & = & -240 +70(x+4)-11(x+4)(x+1)+(x+... ...x-1)+0(x+4)(x+1)(x-1)(x-2)\\ & = & x^3-7x^2+14x-8. \end{array}$$

It has actually turned out to be a cubic, since the given data was actually obtained from a cubic.

Suppose that we now wanted to add an extra point f(0)=-13; rather than insert this point in its place between x=-1 and x=1, we simply add it onto the end of the table, calling it x₅. We find $f[x_4,x_5]=\frac{-13-12}{0-5}=5$,$f[x_3,x_4,x_5]=\frac{5-4}{0-2}=-\frac{1}{2}$,$f[x_2,x_3,x_4,x_5]=\frac{3}{2}$, $f[x_1,x_2,x_3,x_4,x_5]=\frac{1}{2}$,$f[x_0,x_1,x_2,x_3,x_4,x_5]=\frac{1}{8}$. The interpolating polynomial of degree 5 is now the previous polynomial with an extra term added:

$$p(x)=x^3-7x^2+14x-8+\frac{1}{8}(x+4)(x+1)(x-1)(x-2)(x-5).$$