← 2021 Paper 2

UPSC 2021 Maths Optional Paper 2 Q8b — Step-by-Step Solution

15 marks · Section B

Newton's Backward Difference Interpolation · Numerical Analysis · Read the full method →

Question

Derive Newton’s backward difference interpolation formula; do error analysis.

Technique

Operator algebra $\nabla=1-E^{-1}$; binomial expansion of $E^p=(1-\nabla)^{-p}$; standard error formula for polynomial interpolation.

Solution

Setup. Given data points $(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n)$ with $x_i=x_0+ih$ (equally spaced).

Backward difference operator: $\nabla y_i=y_i-y_{i-1}$.

Higher orders: $\nabla^2 y_i=\nabla y_i-\nabla y_{i-1}=y_i-2y_{i-1}+y_{i-2}$, etc.

Step 1 — Newton’s backward difference formula

For interpolation near $x_n$ (the last point), write $x=x_n+ph$, so $p=(x-x_n)/h$ (note $p\le 0$ for $x\le x_n$).

Newton’s backward difference formula:

Step 2 — Derivation

Using the relationship between $E$ (shift operator: $Ey_i=y_{i+1}$) and $\nabla$: $\nabla=1-E^{-1}$, so $E^{-1}=1-\nabla$, $E=1/(1-\nabla)$.

For interpolation at $x=x_n+ph$: $y(x_n+ph)=E^p y_n=(1-\nabla)^{-p}y_n$.

Expand binomially: $(1-\nabla)^{-p}=\sum_{k=0}^\infty\binom{-p}{k}(-\nabla)^k=\sum_{k=0}^\infty\binom{p+k-1}{k}\nabla^k$.

(Using $\binom{-p}{k}=(-1)^k\binom{p+k-1}{k}$.)

So $y(x_n+ph)=\sum_{k=0}^n\dfrac{p(p+1)\cdots(p+k-1)}{k!}\nabla^k y_n$,

which is the Newton’s backward formula stated above.

Step 3 — Error analysis

For a function $y(x)$ that is $(n+1)$-times differentiable on the interval containing the data points, the error in Newton’s backward formula is:

for some $\xi$ in the interval $[x_0,x_n]$.

Derivation: Standard result from polynomial interpolation theory. The error in any interpolation polynomial of degree $\le n$ through $n+1$ points is

$E(x)=\dfrac{(x-x_0)(x-x_1)\cdots(x-x_n)}{(n+1)!}y^{(n+1)}(\xi)$.

In terms of $p$ (with $x=x_n+ph$): $(x-x_i)=(x_n+ph-x_i)=h(p+(n-i))$.

So $(x-x_0)(x-x_1)\cdots(x-x_n)=h^{n+1}p(p+1)(p+2)\cdots(p+n)$.

Hence error formula as above.

Step 4 — Summary

Answer