Calculus · Applications of derivatives
A table gives you \(\sin 0.5\) and \(\sin 1.0\), but you need \(\sin 0.7\). A measurement gives values every hour, but you need one at 2:20. Interpolation fills such gaps: it passes a polynomial through the known points and evaluates it in between. This post presents the two classical formulas, Newton's and Lagrange's, explains how accurate they are, and warns about the one way interpolation can go badly wrong.
We know the values \( y_0, y_1, \dots, y_n \) of a function \(y = f(x)\) at the points (nodes) \( x_0, x_1, \dots, x_n \). We want an approximate value at some other point \(x\). The natural idea is to find a simple function that passes through all the known points, and evaluate it instead. Polynomials are the simplest choice.
Why exactly one? If two such polynomials \(P\) and \(Q\) existed, their difference \(P - Q\) would be a polynomial of degree at most \(n\) with \(n + 1\) zeros (all the nodes). A nonzero polynomial of degree \(n\) has at most \(n\) zeros, so \(P - Q = 0\).
Using the polynomial between the nodes is interpolation; using it outside the range of the nodes is extrapolation, which is much less reliable.
When the nodes are equally spaced, \( x_{i+1} - x_i = h \), the polynomial can be built from simple subtractions arranged in a table.
Differences are the discrete version of derivatives. Since \( \frac{\Delta y}{h} \approx f'(x) \), we have \( \Delta^ky_0 \approx h^kf^{(k)}(x_0) \). In particular, for a polynomial of degree \(n\), the \(n\)-th differences are constant and the \((n + 1)\)-th are zero, just as its \(n\)-th derivative is constant. Rapidly shrinking differences tell you that a low-degree polynomial will fit the data well.
| \(x\) | \(y = \sin x\) | \(\Delta y\) | \(\Delta^2y\) | \(\Delta^3y\) |
|---|---|---|---|---|
| 0.0 | 0.00000 | 0.47943 | −0.11738 | −0.08864 |
| 0.5 | 0.47943 | 0.36205 | −0.20602 | |
| 1.0 | 0.84147 | 0.15602 | ||
| 1.5 | 0.99749 |
The variable \(q\) measures the position of \(x\) in "steps": \(q = 0\) at \(x_0\), \(q = 1\) at \(x_1\), \(q = 1.4\) a little less than halfway between \(x_1\) and \(x_2\).
Why it works: the right side is a polynomial of degree \(n\) in \(q\) (and therefore in \(x\)). At \(q = 0\) it gives \(y_0\). At \(q = 1\) all terms after the second vanish (they contain the factor \(q - 1\)), leaving \( y_0 + \Delta y_0 = y_1 \). At \(q = 2\): \( y_0 + 2\Delta y_0 + \Delta^2y_0 = y_2 \), and so on. So it passes through all the nodes, and by uniqueness it is the interpolation polynomial.
The analogy with Taylor: compare with \( f(x) = f(x_0) + \frac{f'(x_0)}{1!}(x - x_0) + \frac{f''(x_0)}{2!}(x - x_0)^2 + \cdots \). Newton's formula is its discrete twin: derivatives become differences, and powers \((x - x_0)^k\) become "falling" products \(q(q - 1)\cdots(q - k + 1)\).
For \(n = 1\) the formula is \( y = y_0 + q\,\Delta y_0 \): linear interpolation, the straight line through two neighbouring points. It is what everyone does instinctively when reading a table.
| Degree | Added term | Approximation |
|---|---|---|
| 1 (linear) | \(1.4\cdot 0.47943\) | 0.67120 |
| 2 | \(\frac{1.4\cdot 0.4}{2}\cdot(-0.11738)\) | 0.63833 |
| 3 | \(\frac{1.4\cdot 0.4\cdot(-0.6)}{6}\cdot(-0.08864)\) | 0.64329 |
The structure is just like Lagrange's remainder in Taylor's formula (previous post): "the next term", with the derivative evaluated at an unknown point. The second form uses \( \Delta^{n+1}y_0 \approx h^{n+1}f^{(n+1)} \), so it can be computed from the table alone, which is handy when the data come from measurements and \(f\) is unknown.
The factor \( q(q - 1)\cdots(q - n) \) explains two practical rules:
Newton's formula (1) needs equal spacing. Lagrange's formula works for any nodes.
Compactly, \( P_n(x) = \sum_{k=0}^n y_k\,L_k(x) \), where
\[ L_k(x) = \prod_{i \ne k}\frac{x - x_i}{x_k - x_i}. \]The idea is beautifully simple. Each \(L_k\) is a polynomial of degree \(n\) built to be a "switch":
\[ L_k(x_k) = 1, \qquad L_k(x_i) = 0 \quad (i \ne k). \]The numerator vanishes at every node except \(x_k\); the denominator is the numerator evaluated at \(x_k\), so it normalizes the value there to \(1\). Then at the node \(x_i\), the sum \( \sum y_kL_k(x_i) \) keeps only the term \(y_i\cdot 1\). Each data point is "switched on" by its own basis polynomial.
(For equal spacing, \( x - x_i = h(q - i) \), and this becomes exactly the error of Newton's formula.)
By uniqueness (Section 1), Newton's and Lagrange's formulas give the same polynomial on the same nodes. They differ only in how the polynomial is written, and that matters in practice:
| Newton (forward differences) | Lagrange | |
|---|---|---|
| Nodes | equally spaced | arbitrary |
| Adding a node | easy: one more term, earlier terms unchanged | every basis polynomial changes |
| Choosing the degree | easy: watch the differences shrink | must be fixed in advance |
| Error estimate | from the next difference \(\Delta^{n+1}y_0\) | needs a bound on \(f^{(n+1)}\) |
| Theory, proofs | less transparent | very clear structure |
It seems obvious that more nodes, and so a higher degree, always give a better approximation. It is not true. In 1901 Carl Runge interpolated the innocent-looking function
\[ f(x) = \frac{1}{1 + 25x^2} \]on \([-1, 1]\) at equally spaced nodes. As the degree grows, the polynomial gets better in the middle but develops wild oscillations near the ends, and the maximum error tends to infinity.
The culprit is the factor \( (x - x_0)\cdots(x - x_n) \) in the error formula: for equally spaced nodes it is enormous near the ends of the interval, and the high derivatives of Runge's function grow fast enough that nothing compensates. The remedies used in practice:
| Concept | Formula |
|---|---|
| Finite differences | \( \Delta y_0 = y_1 - y_0,\ \Delta^ky_0 = \Delta^{k-1}y_1 - \Delta^{k-1}y_0 \) |
| Newton's formula | \( y = y_0 + q\Delta y_0 + \frac{q(q-1)}{2!}\Delta^2y_0 + \cdots,\ \ q = \frac{x - x_0}{h} \) |
| Newton's error | \( R_n = \frac{h^{n+1}f^{(n+1)}(\xi)}{(n+1)!}q(q-1)\cdots(q-n) \approx \frac{\Delta^{n+1}y_0}{(n+1)!}q(q-1)\cdots(q-n) \) |
| Lagrange's polynomial | \( P_n(x) = \sum y_kL_k(x),\ \ L_k(x) = \prod_{i\ne k}\frac{x - x_i}{x_k - x_i} \) |
| Lagrange's error | \( R_n = \frac{f^{(n+1)}(\xi)}{(n+1)!}(x - x_0)\cdots(x - x_n) \) |
| Uniqueness | one polynomial of degree \(\le n\) through \(n + 1\) points |
Try each one before opening the solution. More solved problems from this topic are in Differential Calculus.
\(y\): \(0, 1, 8, 27, 64\); \(\Delta\): \(1, 7, 19, 37\); \(\Delta^2\): \(6, 12, 18\); \(\Delta^3\): \(6, 6\); \(\Delta^4\): \(0\). The third differences are constant, \( 6 = 3!\,h^3 \), as expected for a cubic.
\( 0.6931 + 0.5\cdot 0.4055 = 0.8959 \). Error bound: \( |f''| = \frac1{x^2} \le \frac14 \), so \( |R_1| \le \frac{1/4}{2}\cdot|0.5\cdot(-0.5)| = 0.03125 \). Actual: \( \ln 2.5 = 0.9163 \), error \(0.0204\).
\( 2\cdot\frac{x(x - 1)}{2} + 1\cdot\frac{(x + 1)(x - 1)}{-1} + 2\cdot\frac{(x + 1)x}{2} = x^2 - x - x^2 + 1 + x^2 + x = x^2 + 1 \).
\(\Delta\): \(1, 3, 5\); \(\Delta^2\): \(2, 2\); \(\Delta^3\): \(0\). With \(h = 1\), \(q = x\): \( y = 1 + x + \frac{x(x - 1)}{2}\cdot 2 = x^2 + 1 \). The zero third difference shows the data lie on a parabola.
Interpolate the constant function \(f(x) = 1\): all \(y_k = 1\), so \( P_n = \sum L_k \). Since \(f^{(n+1)} = 0\), the error is zero: \( P_n(x) = 1 \) exactly.
The error contains \( (x - x_0)(x - x_1)\cdots(x - x_n) \), which is small between the nodes but grows like \(|x|^{n+1}\) outside them. A polynomial fitted to a few points can shoot off in any direction once it leaves their range.
Interpolation answers a very practical question: what happens between the points we know? Newton's formula builds the answer from a table of differences, a discrete Taylor formula; Lagrange's formula builds it from switch-like basis polynomials, one per data point. Both produce the same unique polynomial, and both come with an error term that looks just like Taylor's remainder. Used with a few nearby points, interpolation is remarkably accurate; pushed to high degrees on equally spaced points, it can fail spectacularly. Knowing both sides is what makes it a reliable tool.
Related posts: Taylor's formula (the continuous analogue, and the form of the error) and finding roots numerically.