- Define Interpolation vs. Extrapolation and construct Forward, Backward, and Divided Difference Tables.
- Master Finite Difference Operator Algebra and prove relationships: $E = 1 + \Delta$, $\Delta = E\nabla$, and $E = e^{hD}$.
- State and prove the Fundamental Theorem of Finite Differences ($n$-th difference of a degree $n$ polynomial is constant).
- Derive Newton-Gregory Forward ($p = \frac{x - x_0}{h}$) and Backward ($p = \frac{x - x_n}{h}$) formulas and apply them to exam data.
- Derive Lagrange's Interpolation Formula for unequal intervals and evaluate its computational tradeoffs.
- Construct Newton's Divided Difference Table and derive the interpolating polynomial.
Suppose a weather station records temperatures every 4 hours: $12:00\text{ AM} \to 18^\circ\text{C}$, $4:00\text{ AM} \to 15^\circ\text{C}$, $8:00\text{ AM} \to 22^\circ\text{C}$, $12:00\text{ PM} \to 30^\circ\text{C}$.
If an engineer asks: "What was the exact temperature at 6:30 AM?", we have no physical reading! **Interpolation** is the mathematical art of finding a smooth polynomial $P(x)$ that passes exactly through all known data points, allowing us to estimate any in-between value with rigorous precision!
Given a discrete set of equidistant values $x_0, x_1 = x_0 + h, \dots, x_n = x_0 + nh$ with step size $h$, finite difference calculus operates on the following symbolic operators:
| Operator | Symbol | Mathematical Definition | Interpretation |
|---|---|---|---|
| Forward Difference | $\Delta$ | $\Delta f(x) = f(x + h) - f(x)$ | Subtracts current value from next forward value. |
| Backward Difference | $\nabla$ | $\nabla f(x) = f(x) - f(x - h)$ | Subtracts previous value from current value. |
| Shift (Displacement) | $E$ | $E f(x) = f(x + h)$, $E^n f(x) = f(x + nh)$ | Advances the argument by $n$ steps of $h$. |
| Central Difference | $\delta$ | $\delta f(x) = f\left(x + \frac{h}{2}\right) - f\left(x - \frac{h}{2}\right)$ | Symmetric difference about the midpoint. |
| Averaging | $\mu$ | $\mu f(x) = \frac{1}{2}\left[f\left(x + \frac{h}{2}\right) + f\left(x - \frac{h}{2}\right)\right]$ | Calculates average of forward and backward half-steps. |
| Differential Operator | $D$ | $D f(x) = \frac{d}{dx}f(x) = f'(x)$ | Continuous differential derivative. |
Core Operator Proofs (Standard University Exam Questions):
Proof 1: Prove that $E = 1 + \Delta$
$$\Delta f(x) = f(x + h) - f(x) = E f(x) - f(x) = (E - 1) f(x)$$ $$\implies \Delta = E - 1 \implies \mathbf{E = 1 + \Delta}$$Proof 2: Prove that $\nabla = 1 - E^{-1} = \frac{\Delta}{E}$
$$\nabla f(x) = f(x) - f(x - h) = f(x) - E^{-1} f(x) = (1 - E^{-1}) f(x) \implies \nabla = 1 - E^{-1}$$ $$\nabla = 1 - \frac{1}{E} = \frac{E - 1}{E} = \mathbf{\frac{\Delta}{E}} \implies \mathbf{\Delta = E \nabla = \nabla E}$$Proof 3: Prove that $E = e^{hD}$ (Relation between Shift and Derivative)
Expanding $f(x + h)$ using Taylor series about $x$:
$$E f(x) = f(x + h) = f(x) + h f'(x) + \frac{h^2}{2!} f''(x) + \frac{h^3}{3!} f'''(x) + \dots$$ $$E f(x) = f(x) + h D f(x) + \frac{h^2 D^2}{2!} f(x) + \frac{h^3 D^3}{3!} f(x) + \dots = \left[1 + hD + \frac{(hD)^2}{2!} + \frac{(hD)^3}{3!} + \dots\right] f(x)$$By the exponential series expansion $e^z = 1 + z + \frac{z^2}{2!} + \dots$, we obtain:
$$\mathbf{E = e^{hD}} \implies hD = \ln(E) = \ln(1 + \Delta) = \mathbf{\Delta - \frac{\Delta^2}{2} + \frac{\Delta^3}{3} - \frac{\Delta^4}{4} + \dots}$$If $f(x)$ is a polynomial of degree $n$ in $x$ with equal spacing $h$, then the $n$-th forward difference $\Delta^n f(x)$ is a constant, and all higher differences are strictly zero: $$\mathbf{\Delta^n [a_n x^n + a_{n-1} x^{n-1} + \dots + a_0] = a_n \cdot n! \cdot h^n = \text{Constant}}$$ $$\mathbf{\Delta^{n+1} f(x) = 0, \quad \Delta^{n+2} f(x) = 0, \quad \dots}$$
Step-by-Step Proof:
Let $f(x) = x^n$. Then the first forward difference is:
$$\Delta(x^n) = (x + h)^n - x^n = \left[x^n + n h x^{n-1} + \frac{n(n-1)}{2} h^2 x^{n-2} + \dots + h^n\right] - x^n$$ $$\Delta(x^n) = n h x^{n-1} + \text{terms of degree } \le n - 2$$Notice that taking the first difference $\Delta$ reduces the degree of the polynomial by exactly 1 and multiplies the leading coefficient by $n \cdot h$!
Repeating this operation $n$ times systematically drops the degree by 1 at each step:
$$\Delta^2(x^n) = n(n - 1) h^2 x^{n-2} + \dots$$ $$\Delta^n(x^n) = n(n - 1)(n - 2)\dots (1) h^n x^0 = \mathbf{n! \, h^n = \text{Constant}}$$Since the derivative of a constant is zero, any subsequent difference vanishes identically: $\mathbf{\Delta^{n+1} f(x) = 0}$.
1. Newton's Forward Interpolation Formula (Near Table Beginning)
Let $y = f(x)$ be given at equidistant arguments $x_0, x_1, \dots, x_n$ with step $h$. To evaluate $f(x)$ for an argument $x = x_0 + ph$ (where $p = \frac{x - x_0}{h}$):
$$f(x_0 + ph) = E^p f_0 = (1 + \Delta)^p f_0$$Expanding $(1 + \Delta)^p$ via Newton's Binomial Theorem:
$$\mathbf{y(x) = y_0 + p \Delta y_0 + \frac{p(p-1)}{2!} \Delta^2 y_0 + \frac{p(p-1)(p-2)}{3!} \Delta^3 y_0 + \dots}$$2. Newton's Backward Interpolation Formula (Near Table End)
When the target argument $x$ lies near the end of the table, using forward differences requires values outside the table. Instead, we expand using backward differences with origin at $x_n$, where $x = x_n + ph \implies p = \frac{x - x_n}{h}$ (note: $p$ is typically negative or between $-1$ and $0$):
$$f(x_n + ph) = E^p f_n = (1 - \nabla)^{-p} f_n$$ $$\mathbf{y(x) = y_n + p \nabla y_n + \frac{p(p+1)}{2!} \nabla^2 y_n + \frac{p(p+1)(p+2)}{3!} \nabla^3 y_n + \dots}$$β’ Forward ($p = \frac{x - x_0}{h}$): Factors have subtraction: $p, \frac{p(p-1)}{2!}, \frac{p(p-1)(p-2)}{3!}$. Uses the top diagonal row of the difference table ($\Delta y_0, \Delta^2 y_0, \dots$).
β’ Backward ($p = \frac{x - x_n}{h}$): Factors have addition: $p, \frac{p(p+1)}{2!}, \frac{p(p+1)(p+2)}{3!}$. Uses the bottom diagonal row of the difference table ($\nabla y_n, \nabla^2 y_n, \dots$).
Step-by-Step Solved Problem 1: Newton Forward (CSJMU 2023β24)
Problem: From the following table of values, estimate $f(1.5)$ using Newton's Forward formula:
| $x$ | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $y = f(x)$ | 10 | 26 | 58 | 112 |
Step 1: Construct the Forward Difference Table:
| $x$ | $y$ | $\Delta y$ | $\Delta^2 y$ | $\Delta^3 y$ |
|---|---|---|---|---|
| $x_0 = 1$ | $\mathbf{10} = y_0$ | |||
| $\mathbf{16} = \Delta y_0$ | ||||
| $2$ | $26$ | $\mathbf{16} = \Delta^2 y_0$ | ||
| $32$ | $\mathbf{6} = \Delta^3 y_0$ | |||
| $3$ | $58$ | $22$ | ||
| $54$ | ||||
| $4$ | $112$ |
Step 2: Calculate $p$: Here $x = 1.5$, $x_0 = 1$, and $h = 2 - 1 = 1$:
$$p = \frac{x - x_0}{h} = \frac{1.5 - 1}{1} = \mathbf{0.5}$$Step 3: Substitute into Newton's Forward Formula:
$$y(1.5) = y_0 + p \Delta y_0 + \frac{p(p-1)}{2} \Delta^2 y_0 + \frac{p(p-1)(p-2)}{6} \Delta^3 y_0$$ $$y(1.5) = 10 + (0.5)(16) + \frac{(0.5)(0.5 - 1)}{2} (16) + \frac{(0.5)(0.5 - 1)(0.5 - 2)}{6} (6)$$ $$y(1.5) = 10 + 8.0 + \frac{(0.5)(-0.5)}{2}(16) + \frac{(0.5)(-0.5)(-1.5)}{6}(6)$$ $$y(1.5) = 10 + 8.0 - 2.0 + 0.375 = \mathbf{16.375}$$Step-by-Step Solved Problem 2: Newton Backward (CSJMU 2024β25)
Problem: Using the same table above, estimate $f(3.8)$ using Newton's Backward formula.
β’ Since $x = 3.8$ is near the end of the table ($x_n = 4$), we use Newton's Backward formula.
β’ $x_n = 4$, $y_n = 112$, $h = 1$. The bottom-row differences are:
$\nabla y_n = 54, \quad \nabla^2 y_n = 22, \quad \nabla^3 y_n = 6$.
β’ $p = \frac{x - x_n}{h} = \frac{3.8 - 4}{1} = \mathbf{-0.2}$.
Substitute into Newton's Backward formula:
$$y(3.8) = y_n + p \nabla y_n + \frac{p(p+1)}{2!} \nabla^2 y_n + \frac{p(p+1)(p+2)}{3!} \nabla^3 y_n$$ $$y(3.8) = 112 + (-0.2)(54) + \frac{(-0.2)(-0.2 + 1)}{2} (22) + \frac{(-0.2)(-0.2 + 1)(-0.2 + 2)}{6} (6)$$ $$y(3.8) = 112 - 10.8 + \frac{(-0.2)(0.8)}{2}(22) + \frac{(-0.2)(0.8)(1.8)}{6}(6)$$ $$y(3.8) = 112 - 10.8 - 1.76 - 0.288 = \mathbf{99.152}$$High-Yield Technique: Missing Term Determination (CSJMU 2022β23)
If $n$ values of $y$ are given in a table corresponding to equally spaced arguments, the data can be represented by a polynomial of degree at most $n - 1$. By the Fundamental Theorem of Finite Differences, the $n$-th forward difference must be identically zero: $$\mathbf{\Delta^n y_0 = (E - 1)^n y_0 = 0}$$ Expanding $(E - 1)^n$ via Binomial Theorem gives a linear algebraic equation in terms of the given and unknown values!
Exam Problem: Find the missing term in the table: $x = [0, 1, 2, 3, 4]$, $y = [1, 3, 9, ?, 81]$.
Here 4 values are known ($y_0=1, y_1=3, y_2=9, y_4=81$). The missing value is $y_3$.
Since 4 values are known, degree of polynomial is 3, so $\Delta^4 y_0 = 0 \implies (E - 1)^4 y_0 = 0$.
$$(E^4 - 4E^3 + 6E^2 - 4E + 1) y_0 = 0$$
$$y_4 - 4y_3 + 6y_2 - 4y_1 + y_0 = 0$$
Substitute known values:
$$81 - 4y_3 + 6(9) - 4(3) + 1 = 0 \implies 81 - 4y_3 + 54 - 12 + 1 = 0$$
$$124 - 4y_3 = 0 \implies 4y_3 = 124 \implies \mathbf{y_3 = 31}$$
When the independent data points $x_0, x_1, \dots, x_n$ are unequally spaced (e.g. $x = 0, 1, 4, 7$), Newton's forward/backward formulas fail completely. In such cases, we apply Lagrange's Interpolation Formula.
For $n+1$ distinct points $(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)$: $$\mathbf{y(x) = \sum_{i=0}^n y_i \cdot L_i(x)}$$ where the $i$-th Lagrange basis polynomial $L_i(x)$ is given by: $$\mathbf{L_i(x) = \prod_{j \ne i} \frac{x - x_j}{x_i - x_j} = \frac{(x - x_0)\dots(x - x_{i-1})(x - x_{i+1})\dots(x - x_n)}{(x_i - x_0)\dots(x_i - x_{i-1})(x_i - x_{i+1})\dots(x_i - x_n)}}$$
Step-by-Step Solved University Numerical
Problem (CSJMU 2024β25): Given the unequal data points $(x_0=0, y_0=-12)$, $(x_1=1, y_1=0)$, $(x_2=3, y_2=6)$, $(x_3=4, y_3=12)$. Find $y(2)$.
Target $x = 2$. Applying Lagrange's 4-point formula:
$$y(2) = \frac{(2-1)(2-3)(2-4)}{(0-1)(0-3)(0-4)} (-12) + \frac{(2-0)(2-3)(2-4)}{(1-0)(1-3)(1-4)} (0) + \frac{(2-0)(2-1)(2-4)}{(3-0)(3-1)(3-4)} (6) + \frac{(2-0)(2-1)(2-3)}{(4-0)(4-1)(4-3)} (12)$$Evaluating each term:
β’ Term 1: $\frac{(1)(-1)(-2)}{(-1)(-3)(-4)} (-12) = \frac{2}{-12} (-12) = \mathbf{2}$
β’ Term 2: Evaluates to $\mathbf{0}$ (since $y_1 = 0$)
β’ Term 3: $\frac{(2)(1)(-2)}{(3)(2)(-1)} (6) = \frac{-4}{-6} (6) = \mathbf{4}$
β’ Term 4: $\frac{(2)(1)(-1)}{(4)(3)(1)} (12) = \frac{-2}{12} (12) = \mathbf{-2}$
$$\mathbf{y(2) = 2 + 0 + 4 - 2 = 4}$$Lagrange's Inverse Interpolation Formula (CSJMU 2021)
When $y$ is known and we must determine the unknown $x$ such that $f(x) = y$, ordinary polynomial root finding can be tedious. Instead, we interchange the roles of $x$ and $y$, expressing $x$ as a polynomial in $y$:
$$\mathbf{x(y) = \sum_{i=0}^n x_i \prod_{j \ne i} \frac{y - y_j}{y_i - y_j}}$$$$x(0.2) = 10 \frac{(0.2-0.2079)(0.2-0.2419)}{(0.1736-0.2079)(0.1736-0.2419)} + 12 \frac{(0.2-0.1736)(0.2-0.2419)}{(0.2079-0.1736)(0.2079-0.2419)} + 14 \frac{(0.2-0.1736)(0.2-0.2079)}{(0.2419-0.1736)(0.2419-0.2079)}$$ Evaluating the terms yields $\mathbf{x \approx 11.54^\circ}$.
An alternative to Lagrange for unequal intervals is Newton's Divided Difference Formula, which allows adding new data points incrementally without recalculating the entire polynomial from scratch.
β’ First Divided Difference: $f[x_0, x_1] = \frac{f(x_1) - f(x_0)}{x_1 - x_0}$
β’ Second Divided Difference: $f[x_0, x_1, x_2] = \frac{f[x_1, x_2] - f[x_0, x_1]}{x_2 - x_0}$
β’ $n$-th Divided Difference: $f[x_0, x_1, \dots, x_n] = \frac{f[x_1, \dots, x_n] - f[x_0, \dots, x_{n-1}]}{x_n - x_0}$
Newton's Divided Difference Polynomial Formula:
$$\mathbf{f(x) = f(x_0) + (x - x_0)f[x_0, x_1] + (x - x_0)(x - x_1)f[x_0, x_1, x_2] + (x - x_0)(x - x_1)(x - x_2)f[x_0, x_1, x_2, x_3] + \dots}$$Step-by-Step Solved Problem: Divided Difference Table
Problem: Given the data points $(1, 2), (2, 5), (4, 17), (7, 50)$, construct the divided difference table and estimate $f(5)$.
| $x$ | $f(x)$ | First Divided Diff | Second Divided Diff | Third Divided Diff |
|---|---|---|---|---|
| $1$ | $\mathbf{2}$ | |||
| $\mathbf{3} = \frac{5 - 2}{2 - 1}$ | ||||
| $2$ | $5$ | $\mathbf{1} = \frac{6 - 3}{4 - 1}$ | ||
| $6 = \frac{17 - 5}{4 - 2}$ | $\mathbf{0} = \frac{1 - 1}{7 - 1}$ | |||
| $4$ | $17$ | $1 = \frac{11 - 6}{7 - 2}$ | ||
| $11 = \frac{50 - 17}{7 - 4}$ | ||||
| $7$ | $50$ |
Using the top diagonal entries ($f[x_0]=2, f[x_0,x_1]=3, f[x_0,x_1,x_2]=1, f[x_0,x_1,x_2,x_3]=0$):
$$f(x) = 2 + (x - 1)(3) + (x - 1)(x - 2)(1) + 0$$ $$f(x) = 2 + 3x - 3 + x^2 - 3x + 2 = \mathbf{x^2 + 1}$$Substituting $x = 5$ gives: $\mathbf{f(5) = 5^2 + 1 = 26}$. Notice how Newton's divided difference naturally recovers the exact polynomial!
When the target interpolation point $x$ lies near the middle of an equally spaced table, both Newton's Forward and Newton's Backward formulas give poor results because they pull data points predominantly from one side. Central Difference Formulas maintain optimal numerical stability by choosing an origin $x_0$ near the center and expanding symmetrically.
| Method | Applicable $p = \frac{x - x_0}{h}$ Range | Mathematical Formula |
|---|---|---|
| Gauss Forward | $0 \le p \le 0.5$ | $y_p = y_0 + p \Delta y_0 + \frac{p(p-1)}{2!} \Delta^2 y_{-1} + \frac{(p+1)p(p-1)}{3!} \Delta^3 y_{-1} + \dots$ |
| Gauss Backward | $-0.5 \le p \le 0$ | $y_p = y_0 + p \Delta y_{-1} + \frac{(p+1)p}{2!} \Delta^2 y_{-1} + \frac{(p+1)p(p-1)}{3!} \Delta^3 y_{-2} + \dots$ |
| Stirling's Formula | $-0.25 \le p \le 0.25$ (Mean of Gauss Fwd & Bkwd) | $\mathbf{y_p = y_0 + p \left(\frac{\Delta y_0 + \Delta y_{-1}}{2}\right) + \frac{p^2}{2!} \Delta^2 y_{-1} + \frac{p(p^2 - 1)}{3!} \left(\frac{\Delta^3 y_{-1} + \Delta^3 y_{-2}}{2}\right) + \frac{p^2(p^2 - 1)}{4!} \Delta^4 y_{-2} + \dots}$ |
| Bessel's Formula | $0.25 \le p \le 0.75$ | $\mathbf{y_p = \frac{y_0 + y_1}{2} + \left(p - \frac{1}{2}\right)\Delta y_0 + \frac{p(p-1)}{2!} \left(\frac{\Delta^2 y_{-1} + \Delta^2 y_0}{2}\right) + \frac{(p-\frac{1}{2})p(p-1)}{3!} \Delta^3 y_{-1} + \dots}$ |
Rule of Thumb for Exams: If $x$ is near the beginning $\to$ Newton Forward. Near the end $\to$ Newton Backward. Near the center with $|p| < 0.25 \to$ Stirling. Near the center with $0.25 < p < 0.75 \to$ Bessel.
- Distinction between Equal vs. Unequal Spacing (2 Marks): Newton's forward/backward requires strictly constant step $h$. Lagrange works on any arbitrary unequal spacing.
- Formulas (3 Marks): Write both Newton-Gregory Forward formula and Lagrange basis polynomial formula $L_i(x) = \prod_{j \ne i} \frac{x - x_j}{x_i - x_j}$.
- Pros and Cons of Lagrange (3 Marks): Pro: no difference table needed, works on unequal points; Con: highly computationally expensiveβif one new point is added, every single term must be recalculated from scratch!
- Numerical Solution (2 Marks): Neatly show the arithmetic substitutions.
β’ Confusing Forward and Backward $p$: In Forward, $p = \frac{x - x_0}{h}$ and signs in formula alternate ($p(p-1)$). In Backward, $p = \frac{x - x_n}{h}$ and signs are all positive ($p(p+1)$)!
β’ Sign Errors in Lagrange Denominator: In the $i$-th term denominator, $(x_i - x_j)$ is subtracted. Forgetting negative signs is the #1 reason students lose 8 marks on Lagrange numericals!
Verify your conceptual mastery across finite difference operators, difference tables, Newton forward/backward, and Lagrange interpolation with this 10-question quiz.