Chaitanya's Random Pages

February 28, 2012

Finite differences for polynomial extrapolation

Filed under: mathematics — ckrao @ 9:41 pm

If I am given the values of a polynomial at some consecutive integers and I want to find its value at the next integer, how might I proceed? For example, if I know $p(0) = 1, p(1) = 3, p(2) = 11, p(3) = 28, p(4) = 57,$ how would I find $p(5)$?

The easiest way I know is to set up a finite difference table. Write the polynomial values in a row, then underneath each row write the difference of the two numbers above it. Continue until all the numbers in a row are equal (or the row below it contains 0s).

For example:

Then we extrapolate by starting at the bottom row and writing the next equal number (in this case 6), then proceeding upwards by writing the sum of the number to its left and below it. In our example we obtain the following.

Hence we conclude that $p(5) = 101$. Notice that we did not need to find $p(x)$ for general $x$ (it turns out to be $p(x) = (x^3 + 3x^2 + 2)/2$ in this example).

The above principle works based on the fact that if $p(x)$ is a polynomial, then $p(x+1) - p(x)$ reduces its degree by $1$. By doing this successively the degree eventually becomes 0. Constant polynomials are uniquely determined by one value so by extrapolating this and propagating the result upwards, we can extrapolate any degree of polynomial in a unique manner provided we have a complete table.

What if we wanted to find $p(10)$ in the above example? Would we have to resort to finding $p(x)$ by solving a system of linear equations in its coefficients? That is, do we need to set $p(x) = ax^3 + bx^2 + cx + d$, substitute known values and then solve for $a, b, c, d$? In this post I want to show how to proceed in a different way.

Firstly, consider what occurs if our original row were taken from a diagonal of Pascal’s triangle (i.e. binomial coefficients). For example, here in the first row we show numbers of the form $\binom{n}{3} = n(n-1)(n-2)/6$.

We find the second row has numbers of the form $\binom{n}{2}$ and the third row has numbers of the form $\binom{n}{1}$. In general if the first row has numbers of the form $\binom{n}{k}$ (where $k$ is fixed and $n$ varies), then the $i$‘th row has numbers of the form $\binom{n}{k-i+1}$. This is a consequence of the fundamental identity

$\displaystyle \binom{n+1}{k} - \binom{n}{k} = \binom{n}{k-1}.$

Given this, it makes sense to try to write our polynomial as a linear combination of binomial coefficients ($\binom{n}{k}$) rather than as a linear combination of monomials ($x^n$).

Returning to our previous example, we wish to evaluate $p(10)$ given $p(0) = 1, p(1) = 3, p(2) = 11, p(3) = 28, p(4) = 57$. Notice how the entire finite difference table can be generated from its first diagonal (running NW-SE). For example,

$\begin{array}{lcl} 28 &=& 11 + 17\\ &=& (3 + 8) + (8 + 9)\\ &=& 3 + 2\times 8 + 9\\ &=& (1+2) + 2(2 + 6) + (6 + 3)\\ &=& 1 + 3.2 + 3.6 + 3.\end{array}$

This shows that $p(3) = 28$ can be written in terms of the first diagonal $(1, 2, 6, 3)$ with the binomial coefficients $1,3,3,1$. Another way of thinking of this is to see how many ways each number in the first diagonal can trickle across the table. In the above example, the number $6$ can trickle up to $p(3)$ in $\binom{3}{2}$ ways: it needs to go up twice and across once in three total moves (up-up-across, up-across-up or across-up-up). This should hopefully explain how the binomial coefficients enter the picture. In general if we need to go across $p$ places and up $q$ places, this can be done in $\binom{p+q}{p}$ ways.

Now if we wish to find $p(10)$, we need to go $10$ spaces across from $p(0) = 1$, nine spaces across and one space up from  $2 = p(1)-p(0)$, eight spaces across and two spaces up from $6$, and seven spaces across and three spaces up from $3$. We conclude that we may write

$\displaystyle p(10) = 1\binom{10}{0} + 2\binom{10}{1} + 6\binom{10}{2} + 3\binom{10}{3}.$

Hence $p(10) = 1 + 2\times 10 + 6\times (10.9)/2 + 3\times (10.9.8)/6 = 1 + 20 + 270 + 360 = 651$. In general, if the first diagonal of the table is $a_0, a_1, \ldots, a_n$ and $a_0= p(0)$, then

$\displaystyle p(x) = \sum_{i=0}^n a_i \binom{x}{i}.$

There is actually a strong link here between this formula and the Taylor series expansion, forming the basis for umbral calculus. See [2] for more details.

References

[1] Jim Loy’s pages, Finite Difference

[2] Weisstein, Eric W. “Newton’s Forward Difference Formula.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/NewtonsForwardDifferenceFormula.html