The lesson Runge taught us
By the time you reach this guide you have watched a single high-degree interpolating polynomial do something genuinely alarming. Sample a perfectly innocent function — the classic example is 1/(1 + 25 x^2) on [-1, 1] — at many equally spaced points, fit one polynomial through all of them, and the curve does not get better as you add points. It gets worse. Near the ends of the interval it sprouts violent oscillations that grow taller without bound as the degree rises. That is Runge's phenomenon, and the moral is blunt: forcing a single global polynomial to thread many points is the wrong tool. The previous guide offered one cure (move the points to Chebyshev nodes). This guide offers the other, and arguably the more practical one.
The key insight is to give up the idea of one curve. A polynomial of degree n has n wiggles available, and when n is large it will use them — that flexibility is exactly what lets the ends blow up. So instead of one stiff, twitchy, degree-n curve spanning everything, lay down many short curves, each of low and fixed degree, each responsible only for the little stretch between two neighbouring data points. Glue these short arcs together end to end. The result is a spline: a piecewise polynomial, low-degree on every piece, that passes through all the data and yet has no global wiggliness to run wild with. Each piece is too short and too gentle to misbehave.
From connect-the-dots to something smooth
The simplest spline is one you have drawn since childhood: connect each adjacent pair of points with a straight line. That is piecewise-linear interpolation — a spline of degree 1. It has wonderful properties. It never overshoots the data, it cannot oscillate, adding more points only ever makes it better, and it is dead simple to evaluate. For many jobs (a quick plot, a lookup table you read off densely) it is genuinely all you need, and it is immune to everything Runge throws at you. Its only flaw is that it is visibly kinked: at every data point the slope changes abruptly, so the curve has corners. The eye sees them, and any computation that needs a smooth derivative chokes on them.
To smooth out the corners we move up one notch in flexibility per piece. Suppose each piece is a cubic — a degree-3 polynomial — rather than a line. A cubic has four coefficients, which is exactly enough freedom to do four things at once: pass through the data point at its left end, pass through the data point at its right end, and match the slope and the curvature of its neighbour across the join. When we demand that adjacent cubics agree not just in value but in first derivative f'(x) and second derivative f''(x) at every interior knot, the corners vanish entirely. The joins become invisible: the curve and its first two derivatives are continuous everywhere. That is the famous cubic spline, and it is the workhorse of smooth interpolation.
How a cubic spline is actually built
Here is the part that makes the cubic spline both clever and cheap. With m intervals there are m cubics and so 4m unknown coefficients — that sounds like a big tangle. But the conditions line up beautifully. Each cubic must hit its two endpoints (that is 2m conditions), and at each of the m-1 interior knots the slope must match and the curvature must match (that is 2(m-1) more). Count them and you are exactly two conditions short of pinning everything down. Those last two are the boundary conditions you supply at the very ends — and that small freedom is real, so a spline is not uniquely determined by the data alone until you choose how to close it off.
- Treat the unknown second derivatives at the knots (call them M_0, M_1, ..., M_m) as the real unknowns; on each interval the cubic is then determined by the two M values at its ends plus the two data heights.
- Impose 'slope must match across each interior knot'. Each such condition links only a knot to its immediate left and right neighbours, giving one equation in M_{n-1}, M_n, M_{n+1}.
- Pick two boundary conditions to close the system: 'natural' (set M_0 = M_m = 0, the strip relaxed flat at the ends), or 'clamped' (fix the end slopes to known values), or 'not-a-knot'.
- Solve the resulting system for all the M values, then read off each cubic's coefficients from its two M endpoints and two data heights.
The beautiful payoff is the shape of that linear system. Because each slope-matching equation touches only a knot and its two immediate neighbours, the matrix is tridiagonal — non-zero only on the main diagonal and the two next to it, zero everywhere else. A tridiagonal system does not need general Gaussian elimination at O(n^3) cost; the Thomas algorithm sweeps it forward and back in O(n) time, linear in the number of points. So a cubic spline through a thousand points is built almost instantly. Contrast that with the global polynomial whose Vandermonde system is dense and notoriously ill-conditioned. Cheap, stable, smooth: the spline wins on every axis that mattered when Runge's curve was thrashing.
B-splines: the same curve, a better basis
There is a second way to describe exactly the same family of piecewise cubics that has taken over computer graphics, CAD, and font design. Instead of storing each piece's polynomial coefficients, build the spline as a weighted sum of special bump-shaped building blocks called B-splines (the 'B' is for 'basis'). Each B-spline is itself a small piecewise polynomial that is non-zero only over a handful of neighbouring intervals and zero everywhere else — it is a localized bump. Any spline you could write the coefficient way, you can equally write as a sum of these bumps, each scaled by one control coefficient. The B-spline basis is just a smarter set of coordinates for the very same space of curves.
Why bother with a new basis for the same curves? Locality. Because each B-spline bump touches only a few intervals, changing one control coefficient nudges the curve only in that small neighbourhood and leaves the rest untouched. A designer dragging one control point of a font outline does not want the far end of the letter to ripple — and with B-splines it does not. This is the exact opposite of a global polynomial, where moving a single data point reshapes the entire curve from end to end. Locality also means numerical stability (no catastrophic cancellation from huge opposing terms) and sparse, banded systems again. The graphics world's NURBS curves are B-splines with one more twist (weights), and they sit underneath essentially every smooth shape on your screen.
Honest limits: what splines do and do not promise
Splines are wonderful, but let us be straight about their boundaries. First, an interpolating spline still passes through every data point exactly — so if your samples are noisy, the spline faithfully reproduces the noise, wiggling through each errant point. When data is noisy you usually do not want to interpolate at all; you want to fit a smoothing spline or a least-squares model that is allowed to miss the points. Second, a cubic spline's accuracy is O(h^4) in the spacing h between points: excellent and steadily improving as you add points, but it is a fixed polynomial order, not the rocket-like exponential accuracy a Chebyshev approximation can reach for a truly smooth function. Splines trade a little peak accuracy for robustness and locality.
Third, the boundary conditions genuinely matter and are not free of consequences. A 'natural' spline forces zero curvature at the two ends, which is often wrong for the underlying function and can degrade accuracy near the boundary; 'not-a-knot' or 'clamped' (if you know the true end slopes) usually behave better. And every spline value you compute is still a floating-point approximation — the Thomas solve, though stable for the diagonally dominant systems splines produce, accumulates the usual rounding, so the curve that passes 'exactly' through your points does so only to about machine precision. None of this dents the headline: for fitting a smooth curve through reasonably clean data, a low-degree piecewise spline is almost always the right answer, and a single high-degree polynomial almost never is.