19 May 2025
Newton Forward and Backward Interpolation
Suppose $y_i=f(x_i)$ is known at equally spaced points
\[x_i=x_0+ih,\qquad i=0,1,\ldots,n.\]Newton’s forward formula is convenient near the beginning of the table; the backward formula is convenient near its end.
Difference operators
The forward differences are
\[\Delta y_i=y_{i+1}-y_i,\] \[\Delta^2y_i=\Delta y_{i+1}-\Delta y_i,\]with higher differences defined repeatedly. The backward differences are
\[\nabla y_i=y_i-y_{i-1},\qquad \nabla^2y_i=\nabla y_i-\nabla y_{i-1}.\]At the final tabulated point,
\[\nabla^r y_n=\Delta^r y_{n-r}.\]Derivation of the forward formula
Let $E$ be the shift operator, $Ey_i=y_{i+1}$. Since $\Delta=E-1$,
\[E=1+\Delta.\]Put $p=(x-x_0)/h$. Extending the shift from an integer to the interpolation variable gives
\[f(x)=E^p y_0=(1+\Delta)^p y_0.\]The generalized binomial expansion is
\[(1+\Delta)^p =1+p\Delta+\frac{p(p-1)}{2!}\Delta^2 +\frac{p(p-1)(p-2)}{3!}\Delta^3+\cdots.\]Therefore
\[\boxed{ f(x)=y_0+p\Delta y_0 +\frac{p(p-1)}{2!}\Delta^2y_0 +\frac{p(p-1)(p-2)}{3!}\Delta^3y_0+\cdots }.\]When $p$ is a non-negative integer, this reduces exactly to the corresponding tabulated value because $E^p y_0=y_p$.
Derivation of the backward formula
Since $\nabla=1-E^{-1}$, one has
\[E=(1-\nabla)^{-1}.\]With $q=(x-x_n)/h$,
\[f(x)=E^q y_n=(1-\nabla)^{-q}y_n.\]Using the negative-binomial expansion,
\[(1-\nabla)^{-q} =1+q\nabla+\frac{q(q+1)}{2!}\nabla^2 +\frac{q(q+1)(q+2)}{3!}\nabla^3+\cdots.\]Hence
\[\boxed{ f(x)=y_n+q\nabla y_n +\frac{q(q+1)}{2!}\nabla^2y_n +\frac{q(q+1)(q+2)}{3!}\nabla^3y_n+\cdots }.\]For a degree-$n$ interpolating polynomial through $n+1$ points, the remainder has the form
\[R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j),\]for some $\xi$ in the data interval.
Cubic table
Take
\[f(x)=x^3-2x+1\]at $x=0,1,2,3$:
| $x$ | $y$ | $\Delta y$ | $\Delta^2y$ | $\Delta^3y$ |
|---|---|---|---|---|
| 0 | 1 | -1 | 6 | 6 |
| 1 | 0 | 5 | 12 | Â |
| 2 | 5 | 17 | Â | Â |
| 3 | 22 | Â | Â | Â |
At $x=0.5$, $p=0.5$. The forward formula gives
\[f(0.5)=1+\frac12(-1) +\frac{(1/2)(-1/2)}2(6) +\frac{(1/2)(-1/2)(-3/2)}6(6) =0.125.\]At $x=2.5$, $q=-0.5$, while
\[\nabla y_3=17,\qquad\nabla^2y_3=12,\qquad\nabla^3y_3=6.\]The backward formula gives
\[f(2.5)=22-\frac12(17) +\frac{(-1/2)(1/2)}2(12) +\frac{(-1/2)(1/2)(3/2)}6(6) =11.625.\]The Maxima worksheet expands both finite-difference polynomials and displays
forward_residual = 0
backward_residual = 0
Thus both formulae reproduce the entire cubic exactly, not only the two evaluated points.
Solved Problems
1. Forward interpolation of a quadratic table
The equally spaced data
| $x$ | 0 | 1 | 2 |
|---|---|---|---|
| $y$ | 1 | 2 | 5 |
have first differences $1,3$ and constant second difference $2$. At $x=0.5$, $h=1$ and
\[p=\frac{x-x_0}{h}=\frac12.\]The forward formula terminates after $\Delta^2y_0$:
\[\begin{aligned} f(0.5) &=y_0+p\Delta y_0+\frac{p(p-1)}{2}\Delta^2y_0\\ &=1+\frac12(1) +\frac{(1/2)(-1/2)}{2}(2)\\ &=\boxed{1.25}. \end{aligned}\]The constant second difference identifies a quadratic, so no omitted higher-difference term remains; indeed the table is generated by $1+x^2$.
2. Backward interpolation near the end of a table
For $y=2^x$ at $x=0,1,2,3$, the values are $1,2,4,8$. At the last point,
\[\nabla y_3=4,\qquad \nabla^2y_3=2,\qquad \nabla^3y_3=1.\]To estimate $y(2.5)$, take $h=1$ and
\[q=\frac{2.5-3}{1}=-\frac12.\]Therefore
\[\begin{aligned} y(2.5)&\approx8+q(4) +\frac{q(q+1)}{2}(2) +\frac{q(q+1)(q+2)}{6}(1)\\ &=8-2-\frac14-\frac1{16}\\ &=\boxed{\frac{91}{16}=5.6875}. \end{aligned}\]The exact value is $2^{5/2}=4\sqrt2\approx5.65685$, so the interpolation error is about $3.06\times10^{-2}$. Unlike the quadratic example, this finite table truncates an infinite difference expansion.
Descriptive Questions
- Define forward and backward difference operators and prove $\nabla^r y_n=\Delta^r y_{n-r}$.
- Derive Newton’s forward interpolation formula from the shift operator.
- Derive Newton’s backward interpolation formula and explain why it is preferred near the end of a table.
- State the interpolation remainder and explain how node spacing and evaluation position affect it.
Numerical Problems
-
Use forward interpolation on $y=0,1,4,9$ at $x=0,1,2,3$ to find $y(1.5)$. Answer: $p=1.5$, $\Delta y_0=1$, $\Delta^2y_0=2$; $y(1.5)=9/4=2.25$.
-
The values of $x^3$ at $x=1,2,3,4$ are $1,8,27,64$. Use the backward formula to find the value at $x=3.5$. Answer: $q=-1/2$; $y(3.5)=343/8=42.875$.
-
A difference table begins with $2,5,10,17,26$. Determine the polynomial degree represented by the data. Answer: first differences are $3,5,7,9$ and second differences are constant at $2$; the degree is $2$.
-
For quadratic interpolation of $e^x$ through $x=0,0.5,1$, bound the error at $x=0.25$ using $\max_{[0,1]}e^x=e$. Answer: $\lvert R_2(0.25)\rvert\le e/128\approx2.1237\times10^{-2}$.
The new finite-difference tables, values, and error bound are checked in the Unit I Maxima worksheet; every displayed residual is zero.
References
- Newton polynomial — Wikipedia.
- Richard L. Burden, J. Douglas Faires, and Annette M. Burden, Numerical Analysis, 10th ed., Chapter 3, “Interpolation and Polynomial Approximation.”
- Steven C. Chapra and Raymond P. Canale, Numerical Methods for Engineers, 8th ed., Chapter 18, “Interpolation.”
Discussion