Newton Interpolation

Newton interpolation, or the method of finite differences, is a very interesting technique used in polynomial problems:

Example. Let $f(x)$ be a cubic polynomial such that $f(0) = 5,$ $f(1) = 4,$ $f(2) = 17,$ and $f(3) = 56.$ Compute $f(4).$

How would you first try to solve this problem (if you know about finite differences, how would you do it without them?)

A possible method would be the following:

"Well, we can say $f(x) = ax^3+bx^2+cx+d,$ where $a, b, c,$ and $d$ are some real numbers. Then, we have four equations: $$\begin{aligned} f(0) = d \;&= 5, \\f(1) = a+b+c+d \; &= 4, \\ f(2) = 8a+4b+2c+d \;&= 17, \\ f(3) = 27a+9b+3c+d \; &= 56. \end{aligned}$$ We can solve this system (four equations, four variables) for $a, b, c,$ and $d,$ and so we can determine what $f(x)$ is. Then, we can plug in $x = 4$ to get our answer!"

While this, in theory, is a good idea, it's not always very practical. Solving that system would be rather tedious without a computer or calculator, and it's very computationally error-prone (unless you're Art Benjamin). Finite differences gives us a better, and much more elegant, way to solve this problem.

Consider some arbitrary cubic polynomial, $P(x) = ax^3 + bx^2 + cx + d.$ We define the first finite difference of $P(x)$ as

$$\Delta_1(x) := P(x+1) - P(x).$$

Try computing $\Delta_1(x)$ in terms of $a, b, c,$ and $d,$ before moving on.

For $P(x),$ we get

$$\Delta_1(x) = a(x+1)^3 + b(x+1)^2 + c(x+1) + d \\ - ax^3 - bx^2 - cx - d,$$

which simplifies to $\Delta_1(x) = 3ax^2 + (3a^2+2b)x + (a+b+c).$

Anything you notice about this new polynomial, compared to the old one, $P(x)?$

The important thing for us is not the exact coefficients of $\Delta_1,$ but the fact that $\Delta_1$ is now a quadratic, not a cubic: the $x^3$ terms canceled when we subtracted $P(x)$ from $P(x+1).$

If we try the finite-difference operation again, we'll see that we cancel out the $x^2$ terms as well. This gives us the second finite difference:

$$\Delta_2(x) := \Delta_1(x+1) - \Delta_1(x),$$

which simplifies to $\Delta_2(x) = 6ax + (3a+3a^2+2b).$ Now we have a linear polynomial! If we repeat the operation once more, we get that the third finite difference is $\Delta_3(x) = 6a,$ a constant polynomial ("degree $0$").

We know that $\Delta_1(0) = P(1) - P(0) = 4 - 5 = -1,$ and $\Delta_1(1) = 13,$ and $\Delta_1(2) = 39$ also. We can also use these newfound values to determine that $\Delta_2(0) = 13-(-1) = 14$ and $\Delta_2(1) = 39-13 = 26,$ and therefore $\Delta_3(0) = 26-14 = 12.$

Recall I said that the coefficients of each polynomial were not important. What really matters here are their degrees: specifically, $\Delta_3(x)$ is constant!! This helps immensely, because $\Delta_3(0) = 12,$ so $\Delta_3(1) = 12$ as well!

This means $\Delta_2(2) - \Delta_2(1) = 12$ (that's how we defined $\Delta_3(1)$), so $\Delta_2(2) = 12 + 26 = 38.$

Then $\Delta_1(3) - \Delta_1(2) = 38,$ so $\Delta_1(3) = 38 + 39 = 77.$

Finally, $f(4) - f(3) = 77,$ so $f(4) = 77 + 56 = 133.$ Boom! $\square$

Once you understand the awesomeness behind that trick there, let's move on to more awesome stuff about finite differences:

Finite differences have a very nice visual representation as well, which is usually much easier to understand than all of the notation we used above. Place the $f(x)$ values equally spaced in a row. Then, put the $\Delta_1(x)$ values on the next row down, in-between the relevant $f(x)$ values (sort of like an upside-down Pascal's Triangle). Place $\Delta_2(x)$ down a row and between $\Delta_1(x)$ values, etc. From just the givens, we have this:

$$\begin{array}{c|ccccccc} x & 0 & & 1 & & 2 & & 3 \\\hline f & 5 & & 4 & & 17 & & 56 & \\ \Delta_1 & & -1 & & 13 & & 39 & \\ \Delta_2 & & & 14 & & 26 & & \\ \Delta_3 & & & & 12 & \end{array}$$

Following the steps in our solution above, what do we add to the table?

Since $\Delta_3(0) = \Delta_3(1) = 12,$ we add a $12$ to the right, on the bottom row of our table:

$$\begin{array}{c|ccccccc} x & 0 & & 1 & & 2 & & 3 \\\hline f & 5 & & 4 & & 17 & & 56 \\ \Delta_1 & & -1 & & 13 & & 39 \\ \Delta_2 & & & 14 & & 26 \\ \Delta_3 & & & & 12 & \to & \textbf{12} \end{array}$$

And what now?

Finally, we can snake our way back up the right side of the table to get $f(4)$:

$$\begin{array}{c|ccccccccc} x & 0 & & 1 & & 2 & & 3 & & 4 \\\hline f & 5 & & 4 & & 17 & & 56 & & \textbf{133} \\ \Delta_1 & & -1 & & 13 & & 39 & & \textbf{77} & \uparrow \\ \Delta_2 & & & 14 & & 26 & & \textbf{38} & \uparrow \\ \Delta_3 & & & & 12 & & 12 & \uparrow & \end{array}$$

Pascal's Trapezoid...! (Just kidding.)

In general, for an $n$th degree polynomial, the $n$th finite difference will be constant, the $(n-1)$th will be linear, the $(n-2)$th will be quadratic, and so on. We go down to the $n$th finite difference, extrapolate one to the right, and build our way back up!

Although it might seem daunting to take so many finite differences, with the visual table structure, it becomes just repeated subtraction! That's what makes finite differences so appealing - it takes many interesting polynomial concepts and distills them down into a simple algorithm.

Summary: We used finite difference polynomials to reduce our givens down, until we got to a constant polynomial. Then, we were cleverly able to exploit the constant polynomial to give us another value we needed. Finally, we backtracked up our finite difference chain to get what we wanted. $\square$

This exercise is meant to show one of the surprising and beautiful connections between finite differences/partial sums and "actual" calculus.

Problem. Let $f(x) = x^n,$ for some positive integer $n.$ Show that $\Delta_1(x) = nx^{n-1} + \ldots$ (where the ellipsis represents a bunch of terms of degree at most $n-2$). That is, show that $\Delta_1(x)$ is an $(n-1)$th degree polynomial, with leading coefficient $n.$

Recall that we defined

$$\Delta_1(x) := f(x+1) - f(x).$$

We have $f(x+1) = (x+1)^n,$ which by the Binomial Theorem expands to

$$x^n + nx^{n-1} + \ldots$$

(a bunch of stuff of degree at most $n-2$). Then, subtracting $f(x) = x^n$ from this leaves just $nx^{n-1},$ plus a bunch of lower-degree terms. $\square$

Do you see the connection to calculus?

The analog, if you don't see it already, is to the Power Rule from calculus:

$$\dfrac{d}{dx}(x^n) = nx^{n-1}.$$ How cool!