Cubic Splines

One polynomial through many points can wiggle badly (see Runge's Phenomenon and Chebyshev Nodes). A spline uses a separate low-degree polynomial on each interval between data points, like interpolation done locally, and joins the pieces smoothly. Cubic pieces are the standard choice.

Given knots $x_0 < x_1 < \cdots < x_n$ and values $y_i$, a cubic spline $s$ is a cubic polynomial on each $[x_i, x_{i+1}]$, passes through every $(x_i, y_i)$, and has $s$, $s'$ and $s''$ continuous at every inside knot. A natural spline also has $s''(x_0) = s''(x_n) = 0$.

Key idea

$n$ cubic pieces have $4n$ coefficients. Interpolation gives $2n$ conditions and smoothness of $s'$ and $s''$ at the $n - 1$ inside knots gives $2(n - 1)$ more, leaving $2$: the end conditions. Writing $M_i = s''(x_i)$, equal spacing $h$ leads to the tridiagonal system $$M_{i-1} + 4M_i + M_{i+1} = \frac{6}{h^{2}}(y_{i-1} - 2y_i + y_{i+1}).$$

Why it works

On each interval $s$ is cubic, so $s''$ is linear: it is the straight line from $M_i$ to $M_{i+1}$, which makes $s''$ continuous automatically. Integrating twice and choosing the two constants so that $s(x_i) = y_i$ and $s(x_{i+1}) = y_{i+1}$ gives, with $h = x_{i+1} - x_i$, $$s(x) = M_i\frac{(x_{i+1} - x)^{3}}{6h} + M_{i+1}\frac{(x - x_i)^{3}}{6h} + \left(\frac{y_i}{h} - \frac{M_ih}{6}\right)(x_{i+1} - x) + \left(\frac{y_{i+1}}{h} - \frac{M_{i+1}h}{6}\right)(x - x_i).$$ Requiring $s'$ to match at each inside knot gives one equation per knot, the system above. It is diagonally dominant ($4 > 1 + 1$), so it can be solved by LU without pivoting in about $8n$ operations.

Worked example: A natural spline through three points

Find the natural cubic spline through $(0, 0)$, $(1, 1)$, $(2, 0)$, and evaluate it at $x = 0.5$.

Natural: $M_0 = M_2 = 0$. The one inside equation: $0 + 4M_1 + 0 = \frac{6}{1}(0 - 2 + 0)$, so $M_1 = -3$.
On $[0, 1]$ the formula gives $s(x) = -3\frac{x^{3}}{6} + (1 + \frac{3}{6})x = -\frac{x^{3}}{2} + \frac{3}{2}x$.
Checks: $s(1) = 1$; $s'(x) = -\frac{3}{2}x^{2} + \frac{3}{2}$, so $s'(1) = 0$, as symmetry demands; $s''(0) = 0$.
$s(0.5) = -0.0625 + 0.75 = 0.6875$.

Answer: $s(0.5) = 0.6875$

Worked example: Counting conditions

A cubic spline passes through 5 points. Count unknowns and conditions.

4 intervals, 4 cubics: $16$ unknown coefficients.
Each piece matches the data at both ends: $8$ conditions. At the 3 inside knots, $s'$ and $s''$ must agree: $6$ more.
$14$ conditions for $16$ unknowns: 2 end conditions are needed (natural, clamped slopes, or "not-a-knot").

Answer: 16 unknowns, 14 + 2 conditions

Worked example: Is it a spline?

$s(x) = x^{3}$ on $[0, 1]$ and $s(x) = 1 + 3(x - 1) + 2(x - 1)^{2}$ on $[1, 2]$. Is $s$ a cubic spline?

Values at 1: $1$ and $1$. ✓ Slopes: $3x^{2} = 3$ and $3$. ✓
Second derivatives: $6x = 6$ on the left, $2 \cdot 2 = 4$ on the right. ✗
Not a spline: the curvature jumps at $x = 1$. With $3(x - 1)^{2}$ instead of $2(x - 1)^{2}$ it would be.

Answer: No

Blue: the natural cubic spline; its second derivative (below) is continuous. Orange dashed: cubic pieces that match only values and slopes; their second derivative jumps.

Common mistake

Matching only values and slopes at the knots. That leaves the second derivative, the curvature, jumping at every knot, which the eye notices as a kink in the bend. Also, do not forget the two end conditions; without them the system has two equations too few.

Cubic Splines

Practice

Builds on

Leads to

Sources and further reading