Skip to content

Finite Differences and Interpolation

CSIR NET numerical analysis: difference operators, Newton forward and backward, divided differences, Lagrange, Hermite and cubic spline interpolation.

  • 22 min read
  • Updated
On this page · 15 sections
  1. Prerequisites
  2. The Hook: More Points, Worse Fit
  3. Finite Difference Operators
  4. Interpolation with Equal Spacing: Newton’s Formulas
  5. Divided Differences: Unequal Spacing
  6. Lagrange Interpolation
  7. Hermite Interpolation
  8. Spline Interpolation
  9. Memory Tricks
  10. Don’t Confuse
  11. Common Mistakes
  12. Practice
  13. Quick Revision Table
  14. Key Takeaways
  15. What’s Next

Prerequisites

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) \).

OperatorDefinition
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 \)
01166
127126
2919186
3283724
46561
5126

(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$$
FormulaUse nearDifferences used
Newton forwardthe start of the tabletop diagonal \( \Delta^k f_0 \)
Newton backwardthe end of the tablebottom diagonal \( \nabla^k f_n \)
Gauss, Stirling, Bessel (central)the middle of the tablecentral 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 functionValue 1 forFormula
\( 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

ItemCount
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 conditionsName
\( 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

ThisvsThat
\( \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 \) pointsspline: piecewise cubics, \( C^2 \), degree 3 regardless of \( n \)
Hermite: matches values and derivativescubic spline: matches values only; derivatives are whatever continuity forces
Natural spline: \( S'' = 0 \) at endsclamped 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

  1. Express \( \nabla \) and \( \delta \) in terms of \( E \).
  2. What is \( \Delta^4 \) of \( f(x) = 3x^4 - x^2 + 7 \) with step \( h = 1 \)?
  3. How many conditions determine a cubic spline on \( n \) intervals, and how many come from interpolation and continuity?
Answers
  1. \( \nabla = 1 - E^{-1} \), \( \delta = E^{1/2} - E^{-1/2} \).
  2. \( a_4\,4!\,h^4 = 3 \times 24 = 72 \) (constant).
  3. \( 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

IdeaFact
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) \)
Polynomialdegree \( n \): \( \Delta^n f = a_n\,n!\,h^n \), \( \Delta^{n+1} f = 0 \)
Error in tablespreads 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 differencessymmetric; \( = \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