I was studying Newton's Forward Interpolation and backward interpolation in a computer science course and the form that I got them in, is as follows-
Forward Interpolation
$$f(x)=y=y_0+\binom u1 \Delta y_0+\binom u2 \Delta^2y_0+\dots +\binom
un \Delta^ny_0$$ where \begin{align*} x_i&=x_0+ih \;\text{ (equispaced
points)}\\ u&=\frac{x-x_0}{h}\\ \Delta y_i &= y_{i+1}-y_i,
\;i=0,1,\dots\\ \Delta^k y_i &= \Delta^{k-1}y_{i+1}-\Delta^{k-1}y_{i}
\end{align*}
Backward Interpolation
$$f(x)=y=y_n+\binom u1 \Delta y_{n-1} + \binom u2
\Delta^2y_{n-2}+\dots +\binom{u+n-1}n \Delta^n y_0$$ where
\begin{align*} x_i&=x_0+ih \;\text{ (equispaced points)}\\
u&=\frac{x-x_n}{h}\\ \Delta y_i &= y_{n-1}-y_{n-i-1}, \;i=0,1,\dots\\
\Delta^k y_i &= \Delta^{k-1}y_{n-1}-\Delta^{k-1}y_{n-i-1} \end{align*}
Now, I understood polynomial approximation (that was taught just before these interpolations). But, I don't understand why and how these interpolations work.
I can guess that we have taken equispaced points, found the values of $f$ at those points, and tried to find a better behaved approximation that satisfies those values of $f(x)$. But, I don't have any intuition regarding how this approximation function behaves. I don't understand what role the binomials (that too with non integer values) play or what extra advantage the equispaced points give, and I have no idea of how the complex definitions of $\Delta^k$ help us to get this approximation. I tried to look into some of the expressions of $\Delta^k$ and these are what I calculated (about the forward part)-
\begin{align*}
\Delta y_0 &= y_1-y_0\\
\Delta^2y_0 &= \Delta y_1- \Delta y_0\\
&=y_2-2y_1+y_0
\end{align*}
So, it's clear that these expressions wont simplify. They will just go on getting uglier.
As of now, I am completely confused about how this thing works. Also, what is the difference between Forward and Backward interpolation, and when to use which one? At this level of confusion, I don't think, rigorous proofs will be of much use. So, I would like to have a geometric interpretation, or simply a concrete intuition to arrive at such an expression.
Can somebody please help me with this? Thanks in advance.
Best Answer
Let me show the intuition with an example. Here's the sequence $a(n) = n^2$, shown in table form. Every row lists the differences between consecutive terms in the row above it. $$\begin{array}{c|ccccccccc} a(n)&0&&1&&4&&9&&16&&25&&36&&49&&64&&81\\ \hline\ \Delta^1&&1&&3&&5&&7&&9&&11&&13&&15&&17\\ \Delta^2&&&2&&2&&2&&2&&2&&2&&2&&2\\ \end{array}$$
For this particular sequence, the difference between successive elements grows by 2 each time, and the difference between the differences remains constant. So we have:
In general, you can see that the pattern is $a_n = 0 + 1n + 2(0+1+2+3+\ldots+(n-1)) = 0 + 1n+2{n \choose 2}$.
In this pattern, the numbers 0 1 and 2 come from the first entries in each row. This approximation is exact using only three terms because the third row of the table is constant. If the third row wasn't constant, we'd have to add additional rows, and each new row would add a new term to our formula.
The sequences that can be represented exactly using $n$ rows are the $n-1$ degree polynomials. In this case, we have a quadratic (degree 2) polynomial which can be represented exactly using difference formulas for three rows.
So Netwon's approximation is very much a kind of polynomial approximation. The $k$th order approximation is what you need in order to compute the function exactly, assuming the $k$th row in the table is a constant difference. The coefficients like ${u \choose k}$ come from how many times you have to add up the $k$-row differences, accumulated when going from one term to the next.
Why use equally-spaced intervals? It's easy to exactly interpolate polynomial values over equally spaced intervals. It just involves integer multiples of $f$, the derivative of $f$, the second derivative of $f$, and so on.
Why binomial coefficients? If you try to interpolate a polynomial exactly [as we did for 9 = 0 + 1 + (1+2) + (1+2+2)], you'll see that the various differences accumulate at different rates. These rates turn out to be the binomial coefficients ${u \choose k}$. For example, our formula was $a(u) = 0 + {u \choose 1}\cdot 1 + {u \choose 2} \cdot 2.$
What do the definitions of $\Delta^k$ mean? $\Delta^k$ is the $k$th row in the table, meaning that it consists of the differences between the elements in the row above it.
If a function is actually an $n$-degree polynomial, then $\Delta^{n+1}$ will be zero and the approximation will be exact.
When do you use the forward/backward versions of this formula? It depends on which values of $a(n)$ you want to predict: Use the forward version to fill in more entries on the right, e.g. $a(10)=100$. Use the backward versions to fill in more entries on the left, e.g. $a(-1) = 1$.