3.3. Gregory-Newton Interpolation Formulae

3.3.1. The need for interpolation

Question

Given a general sequence \(\left\{f_j\right\}_{j=-\infty}^{+\infty}\), if we know the value of each member \(f_j\), how can we find the value of \(f(x)\) for \(x_j < x < x_{j+1}\)?

Fig. 3.2 Sequence and interpolation.

Possiple options are:

• Take an average: \(f(x)=\dfrac{f_j + f_{j+1}}{2}\)

• A precise forward-shift: \(f(x)=\E ^{s} f_j\), \(0<s=\dfrac{x-x_j}{x_{j+1}-x_j}<1\)

For the first option, we may ask “Is this accurate?” For the second option, we may ask “How to SHIFT?”

3.3.2. Gregory-Newton Forward Interpolation

Let \(f_j\) denote \(f(x_j)\). We wish to obtain an approximate value for \(f_{j+s}\), where:

\[s \>=\> \dfrac{x - x_j}{h}\]

Note that we have \(\,f_{j+s}=f(x_j\!+\!sh)=\E ^sf(x_j)=\E ^sf_j\,\).

To obtain a formula involving forward differences we substitute \(\,\E =1+\Delta\,\) therefore:

\[\begin{split}\begin{aligned} f_{j+s} &= \E ^{s} f_j \\ &= (1 + \Delta)^s f_j \end{aligned} \end{split}\]

By using Newton’s generalised binomial theorem, we can expand the shift operator as

\[\begin{split} \begin{align} \E ^{s} & = (1+\Delta)^s \\ & = \sum_{n=0}^{\infty} \begin{pmatrix} s \\ n \end{pmatrix} 1^{s-n}\Delta^{n} \\ & = \begin{pmatrix} s \\ 0 \end{pmatrix} \Delta^{0} + \begin{pmatrix} s \\ 1 \end{pmatrix} \Delta^{1} + \begin{pmatrix} s \\ 2 \end{pmatrix} \Delta^{2} + \cdots + \begin{pmatrix} s \\ k \end{pmatrix} \Delta^{k} + \cdots \\ & = 1+ s\Delta + \frac{s(s-1)}{2!} \Delta^2 + \frac{s(s-1)(s-2)}{3!} \Delta^3 +\cdots + \frac{s(s-1)(s-2)\cdots(s-k+1)}{k!}\Delta^k + \cdots \end{align} \end{split}\]

Note

\(\begin{pmatrix} s \\ k \end{pmatrix} = \dfrac{s!}{k!(s-k)!} =\dfrac{s(s-1)(s-2)\cdots(s-k+1)}{k!}\),

\(\begin{pmatrix} s \\ 0 \end{pmatrix} = \dfrac{s!}{0!(s-0)!}=1\).

Therefore, the forward Gregory-Newton Interpolation formulae is

(3.7)\[f_{j+s} = f_j + s\Delta f_j + \frac{s(s-1)}{2!}\Delta^2 f_j + \cdots + \frac{s(s-1)(s-2)\cdots(s-k+1)}{k!}\Delta^k f_j + \cdots \]

This is an infinite series in \(s\) and in practice we terminate it after a finite number of terms \(k\). Thus, we can write:

\[f(x_j+sh) \>=\> P_k(x_s) + e_k(x_s) \>\simeq\> P_k(x_s)\]

where \(P_k(x_s)\) represents the polynomial, and \(e_k(x_s)\) is the error caused by terminating the series

\[ P_k(x_s)\>=\> f_j + s\Delta f_j + \frac{s(s-1)}{2!}\Delta^2 f_j + \dots + \frac{s(s-1)(s-2)\dots(s-k+1)}{k!}\Delta^{k} f_j \]

Note

The G-N forward interpolation formula (polynomial) is useful for interpolating near the beginning of a sequence.

3.3.3. Gregory-Newton Backward Interpolation

To find \(f(x)=f(x_j+sh)\) for \(x_{j-1}<x<x_j\), we can use backward shifting to derive the interpolation formula:

\[ s=\frac{x-x_j}{h}<0 \]

(3.8)\[ f_{j+s}= f_j + s\nabla f_j + \frac{s(s+1)}{2!}\nabla^2 f_j + \cdots + \frac{s(s+1)\cdots(s+k-1)}{k!}\nabla^k f_j + \cdots \]

We can separate the whole polynomial into two parts:

\[f(x_j + sh) = P_k(x_s) + e_k(x_s) \simeq P_k(x_s)\]

Note

The G-N backward interpolation formula (polynomial) is useful for interpolating near the end of a sequence.