3
$\begingroup$

I am new to Math Overflow, so I am not really sure whether this question fits the community standards. But, I posted this question in Stack Exchange and recieved no answers. Moreover, nothing even close to an answer to my question can be (easily) found online. So, I decided to post it among researchers to see whether I can get any significant explations.

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.

$\endgroup$
7
  • 8
    $\begingroup$ your question on MSE was posted 3 hours ago! You really have to wait a week or so before you can conclude that no help is forthcoming. The question itselfs seem to be much more suitable for MSE than for MO. $\endgroup$ Commented Jun 30, 2021 at 20:09
  • $\begingroup$ @CarloBeenakker Thanks for your comment, but what actually troubled me the most was that no such geometric intuitions were available online. So, I thought maybe my question doesn't have a standard answer. That's why I decided to put the question among researchers to see if they can cook something up. Also, to be honest, I need an answer sooner than within a week :). Anyways, since I posted it, let me just keep it here for a few days. If there's too much of negative reaction from the members, I'll delete it. Is that okay? $\endgroup$ Commented Jul 1, 2021 at 4:47
  • 1
    $\begingroup$ Well, if you think the Pascal matrix is ugly, I can understand your sentiment about the finite differences, but that sentiment is not the norm. $\endgroup$ Commented Jul 7, 2021 at 20:02
  • 1
    $\begingroup$ I'm basically using this Q as an opportunity to address partially the Q "Where do Newton series come from, and how are their reps, based on different finite differences, and the Taylor series related?" $\endgroup$ Commented Jul 7, 2021 at 20:10
  • $\begingroup$ $u$ in the formulas should be $x$, I guess. $\endgroup$ Commented Jul 8, 2021 at 6:15

2 Answers 2

3
$\begingroup$

The forward and backward finite differences and the derivative lower the degree of a polynomial by one.

This property underlies the construction of series expansions of polynomials and, therefore, analytic functions with appropriate convergence properties in terms of diverse polynomial sequences, in particular, Sheffer sequences. In the terminology of the Sheffer operator calculus, these three operators are delta ops, or lowering ops.

The derivative acting on the power $x^n$ lowers the degree by one. In other words, the derivative is the lowering operator for the fundamental Sheffer sequence of polynomials $S_n(x) = x^n$, the simplest such sequence. Specifically,

$$D \; x^n = n \; x^{n-1}.$$

Consequently,

$$\frac{D^k}{k!} \; x^n \; |_{x=0} = \binom{n}{k} \; x^{n-k} \; |_{x=0} = \delta_{n-k}.$$

A polynomial of degree $n$ can be expanded as

$$p_n(x) = \sum_{k=0}^n \; c_k \; x^k,$$

and the coefficients determined as

$$c_k = \frac{D_{x=0}^k}{k!} \; p_n(x) ,$$

giving the Taylor series expansion

$$p_n(x) = \sum_{k \geq 0} [\; D_{x=0}^k \; p_n(x) \;] \; \frac{x^k}{k!}.$$

Now instead of the sequence of power monomials $x^n$, consider the polynomial falling factorials

$$(x)_n = \frac{x!}{(x-n)!} = (x)(x-1) \cdots (x-n+1) = n! \; \binom{x}{n}.$$

The e.g.f. of a binomial Sheffer polynomial sequence $B_n(x) = (B.(x))^n$ is

$$ e^{B.(x)t} = e^{xB(t)},$$

and the lowering operator defined by

$$L \; B_n(x) = n \; B_{n-1}(x)$$

is

$$L = B^{(-1)}(D),$$

where $B^{(-1)}(t)$ is the compositional inverse about the origin of $B(t)$. This is verified by

$$ B^{(-1)}(D) \; e^{B.(x) t} = B^{(-1)}(D) \; e^{x B(t)} = B^{(-1)}(B(t)) \; e^{x B(t)} = t \; e^{B.(x)t}.$$

The falling factorials have the e.g.f

$$e^{(x).t} = (1+t)^x = e^{x \ln(1+t)},$$

so their lowering op is

$$L = e^{D}-1 .$$

Check:

$$L \; (x)_n = (e^{D}-1) \; (x)_n = \frac{(x+1)!}{(x+1-n)} - \frac{x!}{(x-n)!}$$

$$= (x+1 -(x-n+1)) \; \frac{x!}{(x-n+1)!} = n \; (x)_{n-1} . $$

Consequently,

$$\frac{(e^D-1)^k}{k!} \; (x)_n \; |_{x=0}= \binom{n}{k} \; (0)_{n-k} = \delta_{n-k}.$$

A polynomial of degree $n$ can be expanded as

$$p_n(x) = \sum_{k=0}^n \; c_k \; (x)_k$$

and the coefficients determined as

$$c_k = \frac{(e^{D_{x=0}}-1)^k }{k!} \; p_n(x) ,$$

giving the series expansion

$$p_n(x) = \sum_{k \geq 0} [\; (e^D-1)^k \; p_n(x) \; |_{x=0} \;] \; \frac{(x)_k}{k!}.$$

The lowering op is the forward difference op

$$(e^D -1) \; f(x) = f(x+1) - f(x), $$

and the $n$-th finite forward difference is

$$(e^D -1)^n \; f(x) = (-1)^n \; \sum_{k=0}^n (-1)^k \; \binom{n}{k} \; e^{kD} \; f(x)$$

$$ = (-1)^n \; \sum_{k=0}^\infty \; (-1)^k \; \binom{n}{k} \; f(x+k) := (-1)^n \; \nabla_{k=0}^n \; f(x+k).$$

(For the purists: I use the convenient convention consistent with limits of the entire reciprocal of Euler's gamma function that $\binom{n}{m}$ vanishes for $m > n$. This allows invariance of the notation when $n$ is generalized to real or complex numbers.)

Then

$$p_n(x) = \sum_{k \geq 0} [\;(e^D-1)^k \; p_n(x) \; |_{x=0} \;] \; \frac{(x)_k}{k!}$$

$$ = \sum_{k \geq 0} \binom{x}{k} \; (-1)^k \; \nabla_{m=0}^k \; p_n(m)$$

$$ = \nabla_{k=0}^{x} \; \nabla_{m=0}^k \; p_n(m),$$

the Newton series for the polynomial $p_n(x)$.

The backward difference operator is

$$(1- e^{-D}) \; f(x) = f(x) - f(x-1).$$

The compositional inverse of $1-e^{-t}$ is $-\ln(1-t)$, so the backward difference operator is the lowering op of the binomial Sheffer sequence with the e.g.f

$$ e^{B.(x)t} = e^{-x \ln(1-t)} = (1-t)^{-x},$$

which is the e.g.f. for the rising factorials, a.k.a. the Pochhammer symbol,

$$(x)_\bar{n} = (x+n-1)(x+n) \cdots (x) = n! \; \binom{x-1+n}{n} = (-1)^n\; n! \; \binom{-x}{n}.$$

The $n$-th order backward difference is

$$(1-e^{-D})^n \; f(x) = \sum_{k=0}^n (-1)^k \; \binom{n}{k} \; e^{-kD} \; f(x)$$

$$ = \; \sum_{k=0}^\infty \; (-1)^k \; \binom{n}{k} \; f(x-k) := \nabla_{k=0}^n \; f(x-k),$$

and

$$p_n(x) = \sum_{k \geq 0} [\;(1-e^{-D})^k \; p_n(x) \; |_{x=0} \;] \; (-1)^k \; \frac{(-x)_k}{k!}$$

$$ = \sum_{k \geq 0} (-1)^k \; \binom{-x}{k} \; \nabla_{m=0}^k \; p_n(-m)$$

$$ = \nabla_{k=0}^{-x} \; \nabla_{m=0}^k \; p_n(-m).$$

Check: $p_n(-n) = \nabla_{k=0}^{n} \; \nabla_{m=0}^k \; p_n(-m).$

These are the umbral relations cast by

$$y^x= (1-(1-y))^x = \nabla_{k=0}^{x} \; \nabla_{m=0}^k \; y^m$$

$$ = (1-(1-\frac{1}{y})^{-x} = \nabla_{k=0}^{-x} \; \nabla_{m=0}^k \; y^{-m}$$

where $=$ is understood to mean equivalence under analytic continuation, and in umbral notation, these Newton series may be expressed succinctly as

$$p_n(x) = (p_n(.))^x = (1-(1-p_n(.)))^x =\nabla_{k=0}^{x} \; (1-p_n(.))^k $$

$$= \nabla_{k=0}^{x} \; \nabla_{m=0}^k \; p_n(.)^m = \nabla_{k=0}^{x} \; \nabla_{m=0}^k \; p_n(m)$$

$$ = (1-(1-\frac{1}{p_n(.)}))^{-x} =\nabla_{k=0}^{-x} \; (1-\frac{1}{p_n(.)})^k $$

$$= \nabla_{k=0}^{-x} \; \nabla_{m=0}^k \; p_n(.)^{-m} = \nabla_{k=0}^{-x} \; \nabla_{m=0}^k \; p_n(-m).$$

(Info on connections between Mellin transform and Newton series interpolation and on the relations of the forward, backward, and central finite differences to the derivative and, therefore, to the slope of the tangent line to a point on a curve (and curvature, etc.) will appear in a couple of days on my blog.)

$\endgroup$
1
1
$\begingroup$

Newton series is similar to the Taylor series, except we use delta operators instead of derivatives:

$$f(x) = \sum_{k=0}^\infty \binom{x-a}k \Delta^k f\left (a\right)$$

The binomial coefficients work similar to factorials.

We can expand the deltas so to have:

$$f(x)=\sum_{m=0}^{\infty} \binom {x}m \sum_{k=0}^m\binom mk(-1)^{m-k}f(k)$$

The later formula is similar to forward and backward Fourier or Laplace transform, but with sums instead of integrals.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .