Finite Differences and Interpolation
CSIR NET numerical analysis: difference operators, Newton forward and backward, divided differences, Lagrange, Hermite and cubic spline interpolation.
- 22 min
On this page · 15 sections
- Prerequisites
- The Hook: More Points, Worse Fit
- Finite Difference Operators
- Interpolation with Equal Spacing: Newton’s Formulas
- Divided Differences: Unequal Spacing
- Lagrange Interpolation
- Hermite Interpolation
- Spline Interpolation
- Memory Tricks
- Don’t Confuse
- Common Mistakes
- Practice
- Quick Revision Table
- Key Takeaways
- What’s Next
Prerequisites
- Continuity, Differentiability and Bounded Variation: Rolle’s theorem, applied repeatedly, gives the interpolation error formula.
- Gauss Elimination and Gauss-Seidel: cubic splines reduce to a tridiagonal, diagonally dominant linear system.
- Polynomials: a non-zero polynomial of degree at most \( n \) has at most \( n \) roots.
- The chapter map is on Numerical Analysis.
The Hook: More Points, Worse Fit
Finite Difference Operators
Take equally spaced points \( x_k = x_0 + kh \) and write \( f_k = f(x_k) \).
| Operator | Definition |
|---|---|
| Forward difference \( \Delta \) | \( \Delta f(x) = f(x + h) - f(x) \) |
| Backward difference \( \nabla \) | \( \nabla f(x) = f(x) - f(x - h) \) |
| Central difference \( \delta \) | \( \delta f(x) = f(x + \tfrac{h}{2}) - f(x - \tfrac{h}{2}) \) |
| Shift \( E \) | \( E f(x) = f(x + h) \) |
| Average \( \mu \) | \( \mu f(x) = \frac{1}{2}\big(f(x + \tfrac{h}{2}) + f(x - \tfrac{h}{2})\big) \) |
| Differential \( D \) | \( Df(x) = f'(x) \) |
Operator identities
All of these follow by acting on \( f(x) \); they are formal identities, and the ones involving \( D \) assume \( f \) is analytic (Taylor’s series).
$$\Delta = E - 1, \qquad \nabla = 1 - E^{-1}, \qquad \delta = E^{1/2} - E^{-1/2}, \qquad \mu = \tfrac{1}{2}\left(E^{1/2} + E^{-1/2}\right)$$$$E = e^{hD}, \qquad hD = \log(1 + \Delta) = -\log(1 - \nabla) = 2\sinh^{-1}\tfrac{\delta}{2}$$$$\Delta\nabla = \nabla\Delta = \Delta - \nabla = \delta^2, \qquad \nabla = \Delta E^{-1}, \qquad \mu^2 = 1 + \tfrac{\delta^2}{4}, \qquad \Delta^n f_k = \nabla^n f_{k+n} = \delta^n f_{k + n/2}$$Expanding \( E^n \)
From \( E = 1 + \Delta \) and the binomial theorem:
$$f_n = E^n f_0 = \sum_{k=0}^{n}\binom{n}{k}\Delta^k f_0, \qquad \Delta^n f_0 = (E - 1)^n f_0 = \sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k} f_k.$$Differences of polynomials
The factorial polynomial \( x^{(n)} = x(x - h)(x - 2h)\cdots(x - (n - 1)h) \) behaves under \( \Delta \) as \( x^n \) does under \( D \): \( \Delta x^{(n)} = nh\, x^{(n-1)} \). Expressing a polynomial in factorial powers is the quickest way to compute its differences by hand.
The difference table and error detection
| \( x \) | \( f \) | \( \Delta f \) | \( \Delta^2 f \) | \( \Delta^3 f \) |
|---|---|---|---|---|
| 0 | 1 | 1 | 6 | 6 |
| 1 | 2 | 7 | 12 | 6 |
| 2 | 9 | 19 | 18 | 6 |
| 3 | 28 | 37 | 24 | |
| 4 | 65 | 61 | ||
| 5 | 126 |
(This is \( f(x) = x^3 + 1 \): third differences constant at \( 3! = 6 \).)
Error propagation. If one entry \( f_k \) carries an error \( \varepsilon \), the \( m \)-th differences around it carry errors \( \varepsilon \) times the binomial coefficients of \( (1 - 1)^m \) with alternating signs: \( \varepsilon, -\varepsilon \) in the first differences; \( \varepsilon, -2\varepsilon, \varepsilon \) in the second; \( \varepsilon, -3\varepsilon, 3\varepsilon, -\varepsilon \) in the third. The error grows and spreads in a fan. This is how Part C asks you to locate and correct a wrong entry (see Practice Q5).
Interpolation with Equal Spacing: Newton’s Formulas
Write \( x = x_0 + sh \). Since \( f(x_0 + sh) = E^s f_0 = (1 + \Delta)^s f_0 \), truncating the binomial series gives
$$\textbf{Newton forward:}\quad p(x_0 + sh) = f_0 + s\,\Delta f_0 + \frac{s(s-1)}{2!}\Delta^2 f_0 + \frac{s(s-1)(s-2)}{3!}\Delta^3 f_0 + \cdots$$Similarly, with \( x = x_n + sh \) (\( s \le 0 \) inside the table) and \( E^s = (1 - \nabla)^{-s} \):
$$\textbf{Newton backward:}\quad p(x_n + sh) = f_n + s\,\nabla f_n + \frac{s(s+1)}{2!}\nabla^2 f_n + \frac{s(s+1)(s+2)}{3!}\nabla^3 f_n + \cdots$$| Formula | Use near | Differences used |
|---|---|---|
| Newton forward | the start of the table | top diagonal \( \Delta^k f_0 \) |
| Newton backward | the end of the table | bottom diagonal \( \nabla^k f_n \) |
| Gauss, Stirling, Bessel (central) | the middle of the table | central differences along the middle row |
All these formulas, carried to the same set of points, give the same polynomial; only the order of terms differs (and so the error from truncating early).
Divided Differences: Unequal Spacing
$$f[x_i] = f_i, \qquad f[x_i, x_{i+1}] = \frac{f_{i+1} - f_i}{x_{i+1} - x_i}, \qquad f[x_0, \dots, x_k] = \frac{f[x_1, \dots, x_k] - f[x_0, \dots, x_{k-1}]}{x_k - x_0}.$$Properties.
- Symmetric: \( f[x_0, \dots, x_k] \) does not depend on the order of the points. Explicitly \( f[x_0, \dots, x_k] = \sum_i \frac{f_i}{\prod_{j \ne i}(x_i - x_j)} \).
- Mean value form: \( f[x_0, \dots, x_k] = \frac{f^{(k)}(\xi)}{k!} \) for some \( \xi \) between the smallest and largest node.
- Polynomials: for a polynomial of degree \( n \), the \( n \)-th divided difference is its leading coefficient and all higher ones vanish.
- Equal spacing: \( f[x_0, \dots, x_k] = \frac{\Delta^k f_0}{k!\,h^k} \).
- Repeated nodes: \( f[x_0, x_0] = f'(x_0) \) (the limit as two nodes merge). This is the bridge to Hermite interpolation.
Newton’s divided difference formula:
$$p(x) = f[x_0] + f[x_0, x_1](x - x_0) + f[x_0, x_1, x_2](x - x_0)(x - x_1) + \cdots + f[x_0, \dots, x_n]\prod_{i=0}^{n-1}(x - x_i).$$Its great advantage: adding a node adds one term; earlier work is kept.
Lagrange Interpolation
The Lagrange form:
$$p(x) = \sum_{i=0}^{n} f_i L_i(x), \qquad L_i(x) = \prod_{j \ne i}\frac{x - x_j}{x_i - x_j}, \qquad L_i(x_j) = \delta_{ij}.$$Basis identities (interpolate \( 1, x, \dots, x^n \), which are reproduced exactly):
$$\sum_{i=0}^n L_i(x) = 1, \qquad \sum_{i=0}^n x_i^k L_i(x) = x^k \quad (0 \le k \le n).$$For \( k = n + 1 \) the identity fails: \( \sum_i x_i^{n+1} L_i(x) = x^{n+1} - \omega(x) \), where \( \omega(x) = \prod_{i=0}^n (x - x_i) \).
The interpolation error
Proof idea: for fixed \( x \), the function \( g(t) = f(t) - p(t) - \frac{f(x) - p(x)}{\omega(x)}\omega(t) \) has \( n + 2 \) zeros; apply Rolle’s theorem \( n + 1 \) times.
Consequences:
- Linear interpolation on \( [x_0, x_0 + h] \): \( \lvert f - p \rvert \le \frac{h^2}{8}\max\lvert f'' \rvert \), since \( \max\lvert (x - x_0)(x - x_1) \rvert = \frac{h^2}{4} \).
- Polynomials of degree \( \le n \) are reproduced exactly (\( f^{(n+1)} = 0 \)).
- Example: interpolating \( e^x \) at \( 0, \frac{1}{2}, 1 \), the error at \( x = \frac{1}{4} \) is at most \( \frac{e}{6}\left\lvert \frac{1}{4}\cdot\left(-\frac{1}{4}\right)\cdot\left(-\frac{3}{4}\right) \right\rvert \approx 0.0212 \). (The actual error is about 0.0123.)
- Chebyshev nodes (zeros of \( T_{n+1} \) on \( [-1, 1] \)) minimise \( \max_{[-1, 1]}\lvert \omega(x) \rvert \); the minimum value is \( 2^{-n} \). With equally spaced nodes \( \lvert \omega \rvert \) is much larger near the ends, which is the source of Runge’s phenomenon.
Inverse interpolation. To solve \( f(x) = c \) from a table, swap the roles of \( x \) and \( f \) (when \( f \) is monotone on the range) and interpolate \( x \) as a function of \( f \).
Hermite Interpolation
Given distinct nodes \( x_0, \dots, x_n \) with values \( f_i \) and slopes \( f_i' \), there is a unique polynomial \( H \) of degree at most \( 2n + 1 \) with \( H(x_i) = f_i \) and \( H'(x_i) = f_i' \) (that is \( 2n + 2 \) conditions):
$$H(x) = \sum_{i=0}^n \big[1 - 2L_i'(x_i)(x - x_i)\big]L_i(x)^2 f_i + \sum_{i=0}^n (x - x_i)L_i(x)^2 f_i'.$$Error: \( f(x) - H(x) = \dfrac{f^{(2n+2)}(\xi)}{(2n + 2)!}\prod_{i=0}^n (x - x_i)^2 \).
In practice, build \( H \) with Newton’s divided differences on the doubled node list \( x_0, x_0, x_1, x_1, \dots \), using \( f[x_i, x_i] = f'(x_i) \).
Two-point cubic Hermite on \( [0, 1] \), \( t \in [0, 1] \):
| Basis function | Value 1 for | Formula |
|---|---|---|
| \( h_{00}(t) \) | \( H(0) \) | \( 2t^3 - 3t^2 + 1 \) |
| \( h_{10}(t) \) | \( H'(0) \) | \( t^3 - 2t^2 + t \) |
| \( h_{01}(t) \) | \( H(1) \) | \( -2t^3 + 3t^2 \) |
| \( h_{11}(t) \) | \( H'(1) \) | \( t^3 - t^2 \) |
So \( H(t) = f_0 h_{00} + f_0' h_{10} + f_1 h_{01} + f_1' h_{11} \). On an interval of length \( h \), multiply the slope terms by \( h \).
Spline Interpolation
Let \( a = x_0 < x_1 < \dots < x_n = b \) be knots. A spline of degree \( k \) is a function that is a polynomial of degree at most \( k \) on each \( [x_{i-1}, x_i] \) and is \( C^{k-1} \) on \( [a, b] \).
- Linear spline (\( k = 1 \)): join the dots; continuous, kinks at knots; error \( O(h^2) \).
- Cubic spline (\( k = 3 \)): cubic pieces, \( S, S', S'' \) continuous everywhere.
Counting conditions for a cubic spline
| Item | Count |
|---|---|
| Unknowns (4 coefficients on each of \( n \) intervals) | \( 4n \) |
| Interpolation at both ends of each interval | \( 2n \) |
| \( S' \) continuous at interior knots | \( n - 1 \) |
| \( S'' \) continuous at interior knots | \( n - 1 \) |
| Total so far | \( 4n - 2 \) |
Two more conditions are needed; the choice names the spline:
| End conditions | Name |
|---|---|
| \( S''(x_0) = S''(x_n) = 0 \) | natural (free) spline |
| \( S'(x_0) = f'(x_0) \), \( S'(x_n) = f'(x_n) \) | clamped (complete) spline |
| \( S''' \) continuous at \( x_1 \) and \( x_{n-1} \) | not-a-knot |
| \( S'(x_0) = S'(x_n) \), \( S''(x_0) = S''(x_n) \) (with \( f_0 = f_n \)) | periodic |
With either the natural or the clamped end conditions, the cubic spline interpolant exists and is unique.
Computing a cubic spline: the moment equations
Let \( M_i = S''(x_i) \). On \( [x_{i-1}, x_i] \), \( S'' \) is linear, interpolating \( M_{i-1} \) and \( M_i \). Integrating twice and imposing the data gives, for equal spacing \( h \),
$$M_{i-1} + 4M_i + M_{i+1} = \frac{6}{h^2}\left(f_{i-1} - 2f_i + f_{i+1}\right), \qquad i = 1, \dots, n - 1,$$and on \( [x_{i-1}, x_i] \):
$$S(x) = \frac{M_{i-1}(x_i - x)^3 + M_i(x - x_{i-1})^3}{6h} + \left(\frac{f_{i-1}}{h} - \frac{M_{i-1}h}{6}\right)(x_i - x) + \left(\frac{f_i}{h} - \frac{M_i h}{6}\right)(x - x_{i-1}).$$The system for \( M_1, \dots, M_{n-1} \) (natural: \( M_0 = M_n = 0 \)) is tridiagonal and strictly diagonally dominant (\( 4 > 1 + 1 \)), so it has a unique solution and Gauss-Seidel converges on it.
Minimum curvature property. Among all \( C^2 \) functions \( g \) interpolating the data, the natural cubic spline minimises \( \int_a^b (g'')^2\,dx \). This is why it looks like a drafting spline (a thin elastic strip).
Accuracy. For smooth \( f \), the clamped cubic spline has error \( O(h^4) \) as the knot spacing \( h \to 0 \), and refining the knots never produces Runge-type blow-up.
Memory Tricks
Don’t Confuse
| This | vs | That |
|---|---|---|
| \( \Delta f_k = f_{k+1} - f_k \) | \( \nabla f_k = f_k - f_{k-1} \) (so \( \nabla f_{k+1} = \Delta f_k \)) | |
| Lagrange: one polynomial, degree \( n \), through \( n + 1 \) points | spline: piecewise cubics, \( C^2 \), degree 3 regardless of \( n \) | |
| Hermite: matches values and derivatives | cubic spline: matches values only; derivatives are whatever continuity forces | |
| Natural spline: \( S'' = 0 \) at ends | clamped spline: \( S' \) prescribed at ends | |
| Divided difference \( f[x_0, \dots, x_k] \) | forward difference \( \Delta^k f_0 = k!\,h^k f[x_0, \dots, x_k] \) | |
| Interpolation (pass through the data) | least squares fitting (minimise the residual; need not pass through any point) |
Common Mistakes
Practice
All questions below are original practice questions written for this page. They are not from any CSIR NET paper. In Level 3, as in Part C, one or more options may be correct.
Level 1: Foundation
- Express \( \nabla \) and \( \delta \) in terms of \( E \).
- What is \( \Delta^4 \) of \( f(x) = 3x^4 - x^2 + 7 \) with step \( h = 1 \)?
- How many conditions determine a cubic spline on \( n \) intervals, and how many come from interpolation and continuity?
Answers
- \( \nabla = 1 - E^{-1} \), \( \delta = E^{1/2} - E^{-1/2} \).
- \( a_4\,4!\,h^4 = 3 \times 24 = 72 \) (constant).
- \( 4n \) unknowns; interpolation and \( C^1, C^2 \) continuity give \( 4n - 2 \); two end conditions complete the count.
Level 2: Part B Style
Practice Q1. The polynomial of degree at most 2 through \( (0, 1), (1, 2), (2, 8) \) takes at \( x = 1.5 \) the value
(a) 4.25 (b) 4.375 (c) 4.5 (d) 5.0
Answer: (b)
\( p(x) = \frac{5}{2}x^2 - \frac{3}{2}x + 1 \) (see the worked example), so \( p(1.5) = 5.625 - 2.25 + 1 = 4.375 \). Option (d) is linear interpolation between \( (1, 2) \) and \( (2, 8) \).
Practice Q2. For \( f(x) = 2x^3 - x + 5 \) tabulated with step \( h = 2 \), the third forward difference \( \Delta^3 f \) equals
(a) 12 (b) 48 (c) 96 (d) 0
Answer: (c)
\( \Delta^3 f = a_3\,3!\,h^3 = 2 \times 6 \times 8 = 96 \). Option (a) forgets \( h^3 \); option (b) forgets the leading coefficient.
Practice Q3. The cubic \( H \) with \( H(0) = 0 \), \( H'(0) = 1 \), \( H(1) = 1 \), \( H'(1) = 0 \) satisfies \( H(\frac{1}{2}) = \)
(a) \( \frac{1}{2} \) (b) \( \frac{9}{16} \) (c) \( \frac{5}{8} \) (d) \( \frac{3}{4} \)
Answer: (c)
\( H(t) = h_{10}(t) + h_{01}(t) = -t^3 + t^2 + t \), so \( H(\frac{1}{2}) = -\frac{1}{8} + \frac{1}{4} + \frac{1}{2} = \frac{5}{8} \).
Practice Q4. For the natural cubic spline \( S \) through \( (0, 0), (1, 1), (2, 0) \), the value \( S''(1) \) is
(a) 0 (b) \( -2 \) (c) \( -3 \) (d) \( -6 \)
Answer: (c)
Moment equation with \( h = 1 \), \( M_0 = M_2 = 0 \): \( 4M_1 = 6(0 - 2 \cdot 1 + 0) = -12 \), so \( M_1 = S''(1) = -3 \).
Level 3: Part C Style
Practice Q5. The following values of a cubic polynomial \( f \) at \( x = 0, 1, \dots, 6 \) contain exactly one wrong entry:
\( 1, \ 2, \ 9, \ 30, \ 65, \ 126, \ 217 \)
Which statements are true?
(a) The third differences of the table are \( 8, 0, 12, 4 \). (b) The wrong entry is \( f(3) \), and its correct value is 28. (c) The deviations of the third differences from their true common value are proportional to \( 1, -3, 3, -1 \). (d) The fourth differences of the table are all zero.
Answer: (a), (b) and (c)
First differences: \( 1, 7, 21, 35, 61, 91 \). Second: \( 6, 14, 14, 26, 30 \). Third: \( 8, 0, 12, 4 \).
- (a) True (computed above).
- (c) True. The true third differences of a cubic are constant; the four values average to \( \frac{8 + 0 + 12 + 4}{4} = 6 \) (the error terms \( \varepsilon(1 - 3 + 3 - 1) \) sum to zero), so the deviations are \( 2, -6, 6, -2 = 2 \times (1, -3, 3, -1) \).
- (b) True. The pattern \( \varepsilon(1, -3, 3, -1) \) in \( \Delta^3 f_0, \dots, \Delta^3 f_3 \) points to the entry \( f_3 \), with \( \varepsilon = 2 \). Corrected value \( 30 - 2 = 28 \). (The data are \( x^3 + 1 \).)
- (d) False. The fourth differences are \( -8, 12, -8 \).
Practice Q6. Let
$$S(x) = \begin{cases} x^3, & 0 \le x \le 1, \\ a(x - 1)^3 + b(x - 1)^2 + c(x - 1) + d, & 1 \le x \le 2. \end{cases}$$Suppose \( S \) is a natural cubic spline on \( [0, 2] \) with knots \( 0, 1, 2 \). Which statements are true?
(a) \( d = 1 \) and \( c = 3 \). (b) \( b = 3 \). (c) \( a = -1 \). (d) \( S(2) = 7 \).
Answer: (a), (b) and (c)
At \( x = 1 \): \( S \) continuous gives \( d = 1 \); \( S' \) continuous gives \( c = 3 \cdot 1^2 = 3 \); \( S'' \) continuous gives \( 2b = 6 \), so \( b = 3 \). Natural at \( x = 2 \): \( S''(2) = 6a + 2b = 0 \), so \( a = -1 \). (At \( x = 0 \), \( S''(0) = 0 \) already holds for \( x^3 \).)
- (a), (b), (c) True.
- (d) False. \( S(2) = -1 + 3 + 3 + 1 = 6 \).
Practice Q7. Let \( L_0, \dots, L_n \) be the Lagrange basis polynomials for distinct nodes \( x_0, \dots, x_n \) (\( n \ge 1 \)), and \( \omega(x) = \prod_i (x - x_i) \). Which statements are true?
(a) \( \sum_{i=0}^n L_i(x) = 1 \) for all \( x \). (b) \( \sum_{i=0}^n x_i^{n+1} L_i(x) = x^{n+1} \) for all \( x \). (c) For every continuous \( f \) on \( [-1, 1] \), the interpolants at \( n + 1 \) equally spaced nodes converge uniformly to \( f \) as \( n \to \infty \). (d) If \( p \) interpolates \( e^x \) at \( 0, \frac{1}{2}, 1 \), then \( \lvert e^{1/4} - p(\frac{1}{4}) \rvert \le 0.022 \).
Answer: (a) and (d)
- (a) True. It is the interpolant of the constant 1, which is reproduced exactly.
- (b) False. The interpolant of \( x^{n+1} \) is \( x^{n+1} - \omega(x) \): the difference \( x^{n+1} - \omega(x) \) has degree \( \le n \) and agrees with \( x^{n+1} \) at every node. Since \( \omega \not\equiv 0 \), the sum is not \( x^{n+1} \).
- (c) False. Runge’s function \( \frac{1}{1 + 25x^2} \) is a counter-example: the maximum error grows with \( n \).
- (d) True. The error is \( \frac{e^\xi}{3!}\lvert \omega(\frac{1}{4}) \rvert \le \frac{e}{6} \cdot \frac{1}{4}\cdot\frac{1}{4}\cdot\frac{3}{4} = \frac{3e}{384} \approx 0.0212 \).
Quick Revision Table
| Idea | Fact |
|---|---|
| Operators | \( \Delta = E - 1 \), \( \nabla = 1 - E^{-1} \), \( \delta = E^{1/2} - E^{-1/2} \), \( E = e^{hD} \) |
| Key identities | \( \Delta - \nabla = \Delta\nabla = \delta^2 \); \( \mu^2 = 1 + \frac{\delta^2}{4} \); \( hD = \log(1 + \Delta) \) |
| Polynomial | degree \( n \): \( \Delta^n f = a_n\,n!\,h^n \), \( \Delta^{n+1} f = 0 \) |
| Error in table | spreads as \( \varepsilon \binom{m}{j}(-1)^j \) in \( m \)-th differences |
| Newton forward / backward | \( (1 + \Delta)^s f_0 \) / \( (1 - \nabla)^{-s} f_n \) |
| Divided differences | symmetric; \( = \frac{f^{(k)}(\xi)}{k!} \); \( f[x_0, x_0] = f'(x_0) \) |
| Lagrange | \( L_i = \prod_{j \ne i}\frac{x - x_j}{x_i - x_j} \); \( \sum L_i = 1 \) |
| Error | \( \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod(x - x_i) \); linear: \( \le \frac{h^2}{8}\max\lvert f'' \rvert \) |
| Hermite | \( n + 1 \) nodes with slopes, degree \( \le 2n + 1 \); error with \( \prod(x - x_i)^2 \) |
| Cubic spline | \( C^2 \) piecewise cubic; \( 4n \) unknowns \( = 4n - 2 + 2 \) |
| Moments (equal \( h \)) | \( M_{i-1} + 4M_i + M_{i+1} = \frac{6}{h^2}(f_{i-1} - 2f_i + f_{i+1}) \) |
| Natural spline | \( M_0 = M_n = 0 \); minimises \( \int (g'')^2 \) |
Key Takeaways
What’s Next
- Numerical Differentiation and Integration: differentiate and integrate the interpolating polynomial to get difference formulas and the Newton-Cotes rules.
- Gauss Elimination and Gauss-Seidel: the solver behind the spline moment equations.
- Numerical Analysis: Quick Revision.