Popper's Dreamland: Newton's Backward Interpolation Formula

Assume we are given an arbitrary function f(x), whose values are known at m +1 evenly spaced points
$\small x_0, \;\; x_0 \!-\! h, \;\;x_0 \!-\! 2h, \;\cdots,\;\;x_0 \!-\! mh$ ^.
Following Newton, define the first backward difference of f(x) by
$\small (1)\;\;\;\;\;\;\;\;\;\;\nabla f(x) = f(x) - f(x-h)$
Let F(x) be a polynomial of degree ≤ m, passing through these m+1 points. In other words, F(x) is a polynomial interpolating function (an approximation) of f(x), which agrees with f(x) at all given points.

Prove that
$\small (2)\;\;\;\;\;\;\; F(x) = \sum_{k=0}^{m}(-1)^k\frac{m!}{(m-k)!k!}\nabla^kf(x_0)$
where
$\small (3)\;\;\;\;\;x = x_0 - nh, \;\;\;\; n = \frac{x_0-x}{h}\;=\;-\frac{x-x_0}{h}, \;\;\; n \;\, \mathrm{real}$

In other words, we want to prove that the coefficients in the expansion of f(x₀ + nh) in finite backward differences are the same as the coefficients in the expansion of (x − 1)ⁿ.

This is problem #4, Chapter 49 of Tenenbaum and Pollard's Ordinary Differential Equations.

■

Solve (1) for f(x₀ − h):
   $\small f(x_0 -h) = f(x_0) - \nabla f(x_0)$

Apply ∇ to both sides:
$\small (a)\;\;\;\;\; \nabla f(x_0 -h) \;=\;\nabla f(x_0) \,-\, \nabla^2 \!f(x_0)$
By (1),
$\small (b)\;\;\;\;\;\nabla f(x_0 -h) \;=\;f(x_0-h) \,-\, f(x_0-2h)$
Equate the right-hand-sides of (a) and (b), and solve for f(x₀− 2h).
   $\small \nabla f(x_0) \,-\, \nabla^2\!f(x_0) \;=\; f(x_0 - h)\,-\,f(x_0-2h)$
$\small (c)\;\;\;\;\; f(x_0-2h)\,=\, {\color{DarkRed}f(x_0 - h)}\,-\, \nabla f(x_0) \,+\, \nabla^2\!f(x_0)$
Replace the red term with its value from (1) and collect like terms:
$\small \small (d)\;\;\;\;\; f(x_0-2h)\,=\, f(x_0) \,-\, 2\nabla f(x_0) \,+\, \nabla^2\!f(x_0)$

REPEAT.
Apply ∇ to both sides:
$\small \small (e)\;\;\;\;\; \nabla f(x_0-2h)\,=\, \nabla f(x_0) \,-\, 2\nabla^2\! f(x_0) \,+\, \nabla^3\!f(x_0)$
According to (1),
$\small \small (f)\;\;\;\;\; \nabla f(x_0-2h)\,=\, f(x_0-2h) \,-\, f(x_0-3h)$
Equating the right-hand sides of (e) and (f), and solving for f(x₀ − 3h),
$\small (g)\;\;\;\;\; f(x_0-3h)=\,{\color{DarkRed} f(x_0-2h)}\,-\, \nabla f(x_0) \,+\, 2\nabla^2\! f(x_0) \,-\, \nabla^3\!f(x_0)$
Replace the red term with its value from (d), and collecting like terms:
$\small (h)\;\;\;\;\; f(x_0-3h)=\, f(x_0)\,-\, 3\nabla f(x_0) \,+\, 3\nabla^2\! f(x_0) \,-\, \nabla^3\!f(x_0)$

STOP.
I have three consecutive increments of the expansion f(x₀ − kh), and for each k, the coefficients match, term-for-term, the binomial expansion (x − 1)^k. To prove that this is true for any k, I must establish the following relationship:   If a given (arbitrary) step is in the form of the binomial expansion, the next step will also be in that form.
The implicit assumption is that I can enumerate. Which I can. I dress myself too, and sleep with the light off.

So, let's say I have the (k −1)st expression:
$\small \begin{align*} \mathrm{(i)\;\; f[x_0- (k\!\!-\!\!1)h] =\;\; } &\mathrm{f(x_0\!)\,-\, (k\!\!-\!\!1)\nabla f(x_0\!) \,+\, \frac{(k\!\!-\!\!1)(k\!\!-\!\!2)}{2!}\nabla^2 f(x_0\!)}\\ &\mathrm{\;-\;\ldots \;+ (-1)^r\frac{(k\!\!-\!\!1)(k\!\!-\!\!2)\cdots(k\!\!-\!r)}{r!}\nabla^r f(x_0\!)\,+\;\ldots}\\ &\mathrm{\,\;+\;(-1)^{k\!-\!1}\nabla^{k\!-1}f(x_0\!) } \end{align*}$

$\small \mathrm{= \sum_{r=0}^{k-1} (-1)^r\frac{(k\!\!-\!\!1)!}{(k\!-\!1\!-\!r)!r!}\nabla^r f(x_0) }$
which is how we will all have to write in hell. But pick any integer for k−1, and it gives the same values as Pascal's triangle, with alternating signs + − + − for successive terms. I want to know if the k th expression will have the same form, too. So,

Apply ∇ to both sides of (i):
$\small \begin{align*} \mathrm{(j)\;\;\; {\color{DarkRed} \nabla f[x_0- (k\!\!-\!\!1)h]} \,=\; } &\mathrm{ \nabla f(x_0\!)\,-\, (k\!\!-\!\!1)\nabla^2 f(x_0\!) \,+\, \frac{(k\!\!-\!\!1)(k\!\!-\!\!2)}{2!}\nabla^3 f(x_0\!)}\\ &\mathrm{\;-\; \ldots \;+ (-1)^r\frac{(k\!\!-\!\!1)(k\!\!-\!\!2)\cdots(k\!\!-\!r)}{r!}\nabla^{r+1}f(x_0\!) \;+\;\ldots}\\ &\mathrm{\;\;+\;(-1)^{k-1}\nabla^{k}f(x_0\!) } \end{align*}$
Subtract the complete expressions (i) − (j). (If this were Newton's forward formula, I'd add them). Again replacing the red term according to (1), the left-hand sum becomes:
$\small \mathrm{f[x_0-(k\!-\!1)h]- {\color{DarkRed} f[x_0-(k\!-\!1)h] +f[x_0 - kh]}}$
$\small \mathrm{(k_1)\;\;\;\;\;= f[x_0-kh]}$

Now the right-hand side.
$\small \begin{align*} &\mathrm{ f(x_0)\,-\, (k\!\!-\!\!1)\nabla f(x_0) \,+\, \frac{(k\!\!-\!\!1)(k\!\!-\!\!2)}{2!}\nabla^2 f(x_0) \,-\,\ldots}\\ &\mathrm{\;\;\;\;\;+ (-1)^r\frac{(k\!\!-\!\!1)(k\!\!-\!\!2)\cdots(k\!-\!r)}{r!}\nabla^r f(x_0)\,+\;\ldots\;+\;(-1)^{k-1}\nabla^{k-1}f(x_0) }\\ &\;\; {\color{DarkBlue} \mathrm{-\, \nabla f(x_0\!)\,+\, (k\!\!-\!\!1)\nabla^2 f(x_0) \,-\, \frac{(k\!\!-\!\!1)(k\!\!-\!\!2)}{2!}\nabla^3 f(x_0)\,-\,\ldots}}\\ &{\color{DarkBlue} \mathrm{\;\;\;\;\;\;\;- (-1)^r\frac{(k\!\!-\!\!1)(k\!\!-\!\!2)\cdots(k\!\!-\!r)}{r!} \nabla^{r+1}f(x_0) \,-\;\ldots\; -\,(-1)^{k-1}\nabla^{k}f(x_0) }} \end{align*}$
The rth term of (j) contains the multiplication −(−1)^r-1∇^rf(x₀). Collecting the negatives into the power of (−1), this becomes (−1)^r∇^rf(x₀)  The power of (−1) and ∇ now match.
Matching the denominators and collecting like terms,
$\small \begin{align*} &\mathrm{ f(x_0)\,-\, [(k\!\!-\!\!1)+1]\nabla f(x_0) \,+\, \frac{(k\!\!-\!\!1)(k\!\!-\!\!2)+2(k\!\!-\!\!1)}{2!}\nabla^2 f(x_0) \,-\,\ldots}\\ &\mathrm{\;\;\;\;\;+ (-1)^r\frac{[(k\!\!-\!\!1)(k\!\!-\!\!2)\!\cdots\!(k\!\!-\!r)] \,+\, [r(k\!\!-\!\!1)(k\!\!-\!\!2)\! \cdots\!(k\!\!-\!r\!+\!1)]}{r!}\nabla^r f(x_0)\,+\;\ldots}\\ & \mathrm{\;\;\;\;\;\;\;\;\; \,+\,(-1)^k \nabla^k f(x_0) } \end{align*}$
Simplifying the coefficients, the right hand side becomes
$\small \begin{align*}&\mathrm{f(x_0)\,-\, k\nabla f(x_0) \,+\, \frac{k(k\!\!-\!\!1)}{2!}\nabla^2 f(x_0) \,-\,\ldots}\\ &\mathrm{\;\;\;\;\;+ (-1)^r\frac{k(k\!\!-\!\!1)(k\!\!-\!\!2)\!\cdots\!(k\!\!-\!r\!+\!1)}{r!}\nabla^r f(x_0)\,+\;\ldots} \mathrm{\; \,+\,(-1)^k \nabla^k f(x_0)}\\ \mathrm{(k_2)}\;&=\mathrm{\; \sum_{r=0}^k (-1)^r \frac{k!}{(k\!-\!r)!r!}\nabla^r f(x_0) } \end{align*}$

Equate (k₁) and (k₂).
$\small \small \begin{align*} \mathbf{(l)} \;\; \mathrm{f[x_0-kh] =}\mathrm{\; \sum_{r=0}^k (-1)^r \frac{k!}{(k\!-\!r)!r!}\nabla^r f(x_0) } \end{align*}$

Being the thing to be proved.

■

1 comment:

UnknownJune 25, 2013 at 8:02 PM
I am surprised to find this is one of my most visited blog posts. I'm not happy with the layout. Induction is hard to read in narrow columns.

Help me make it better. Leave a comment. What are you looking for? Did you find it? How can I make my blog more useful to you?

Popper's Dreamland

Pages

Sunday, January 13, 2013

Newton's Backward Interpolation Formula

1 comment:

Labels

Followers

Blog Archive

About Me