In mathematics, a spline is a function defined piecewise by polynomials. In interpolating problems, spline interpolation is often preferred to polynomial interpolation because it yields similar results, even when using low degree polynomials, while avoiding Runge's phenomenon for higher degrees.

In the computer science subfields of computer-aided design and computer graphics, the term spline more frequently refers to a piecewise polynomial (parametric) curve. Splines are popular curves in these subfields because of the simplicity of their construction, their ease and accuracy of evaluation, and their capacity to approximate complex shapes through curve fitting and interactive curve design.

The term spline comes from the flexible spline devices used by shipbuilders and draftsmen to draw smooth shapes.

Introduction

The term "spline" is used to refer to a wide class of functions that are used in applications requiring data interpolation and/or smoothing. The data may be either one-dimensional or multi-dimensional. Spline functions for interpolation are normally determined as the minimizers of suitable measures of roughness (for example integral squared curvature) subject to the interpolation constraints. Smoothing splines may be viewed as generalizations of interpolation splines where the functions are determined to minimize a weighted combination of the average squared approximation error over observed data and the roughness measure. For a number of meaningful definitions of the roughness measure, the spline functions are found to be finite dimensional in nature, which is the primary reason for their utility in computations and representation. For the rest of this section, we focus entirely on one-dimensional, polynomial splines and use the term "spline" in this restricted sense.

Definition

We begin by limiting our discussion to polynomials in one variable. In this case, a spline is a piecewise polynomial function. This function, call it S, takes values from an interval [a,b] and maps them to ${\displaystyle \mathbb {R} ,}$ the set of real numbers,

$${\displaystyle S:[a,b]\to \mathbb {R} .}$$

$${\displaystyle {\begin{aligned}&[t_{i},t_{i+1}],\quad i=0,\ldots ,k-1\\[4pt]&[a,b]=[t_{0},t_{1})\cup [t_{1},t_{2})\cup \cdots \cup [t_{k-2},t_{k-1})\cup [t_{k-1},t_{k})\cup [t_{k}]\\[4pt]&a=t_{0}\leq t_{1}\leq \cdots \leq t_{k-1}\leq t_{k}=b\end{aligned))}$$

On each of these k "pieces" of [a,b], we want to define a polynomial, call it P_i.

$${\displaystyle P_{i}:[t_{i},t_{i+1}]\to \mathbb {R} .}$$

$${\displaystyle {\begin{aligned}S(t)&=P_{0}(t),&&t_{0}\leq t<t_{1},\\[2pt]S(t)&=P_{1}(t),&&t_{1}\leq t<t_{2},\\&\vdots \\S(t)&=P_{k-1}(t),&&t_{k-1}\leq t\leq t_{k}.\end{aligned))}$$

The given k + 1 points t_i are called knots. The vector t = (t₀, …, t_k) is called a knot vector for the spline. If the knots are equidistantly distributed in the interval [a,b] we say the spline is uniform, otherwise we say it is non-uniform.

If the polynomial pieces P_i each have degree at most n, then the spline is said to be of degree ≤ n (or of order n + 1).

If ${\displaystyle S\in C^{r_{i))}$ in a neighborhood of t_i, then the spline is said to be of smoothness (at least) ${\displaystyle C^{r_{i))}$ at t_i. That is, at t_i the two polynomial pieces P_i–1 and P_i share common derivative values from the derivative of order 0 (the function value) up through the derivative of order r_i (in other words, the two adjacent polynomial pieces connect with loss of smoothness of at most n – r_i)

$${\displaystyle {\begin{aligned}P_{i-1}^{(0)}(t_{i})&=P_{i}^{(0)}(t_{i}),\\[2pt]P_{i-1}^{(1)}(t_{i})&=P_{i}^{(1)}(t_{i}),\\\vdots &\\P_{i-1}^{(r_{i})}(t_{i})&=P_{i}^{(r_{i})}(t_{i}).\end{aligned))}$$

A vector r = (r₁, …, r_k–1) such that the spline has smoothness ${\displaystyle C^{r_{i))}$ at t_i for i = 1, …, k – 1 is called a smoothness vector for the spline.

Given a knot vector t, a degree n, and a smoothness vector r for t, one can consider the set of all splines of degree ≤ n having knot vector t and smoothness vector r. Equipped with the operation of adding two functions (pointwise addition) and taking real multiples of functions, this set becomes a real vector space. This spline space is commonly denoted by ${\displaystyle S_{n}^{\mathbf {r} }(\mathbf {t} ).}$

In the mathematical study of polynomial splines the question of what happens when two knots, say t_i and t_i+1, are taken to approach one another and become coincident has an easy answer. The polynomial piece P_i(t) disappears, and the pieces P_i−1(t) and P_i+1(t) join with the sum of the smoothness losses for t_i and t_i+1. That is,

$${\displaystyle S(t)\in C^{n-j_{i}-j_{i+1))[t_{i}=t_{i+1}],}$$

$${\displaystyle (t_{0},t_{1},\cdots ,t_{1},t_{2},\cdots ,t_{2},t_{3},\cdots ,t_{k-2},t_{k-1},\cdots ,t_{k-1},t_{k})}$$

where t_i is repeated j_i times for i = 1, …, k – 1.

A parametric curve on the interval [a,b]

$${\displaystyle G(t)={\bigl (}X(t),Y(t){\bigr )},\quad t\in [a,b]}$$

Examples

Suppose the interval [a, b] is [0, 3] and the subintervals are [0, 1], [1, 2], [2, 3]. Suppose the polynomial pieces are to be of degree 2, and the pieces on [0, 1] and [1, 2] must join in value and first derivative (at t = 1) while the pieces on [1, 2] and [2, 3] join simply in value (at t = 2). This would define a type of spline S(t) for which

$${\displaystyle {\begin{aligned}S(t)&=P_{0}(t)=-1+4t-t^{2},&&0\leq t<1\\[2pt]S(t)&=P_{1}(t)=2t,&&1\leq t<2\\[2pt]S(t)&=P_{2}(t)=2-t+t^{2},&&2\leq t\leq 3\end{aligned))}$$

would be a member of that type, and also

$${\displaystyle {\begin{aligned}S(t)&=P_{0}(t)=-2-2t^{2},&&0\leq t<1\\[2pt]S(t)&=P_{1}(t)=1-6t+t^{2},&&1\leq t<2\\[2pt]S(t)&=P_{2}(t)=-1+t-2t^{2},&&2\leq t\leq 3\end{aligned))}$$

would be a member of that type. (Note: while the polynomial piece 2t is not quadratic, the result is still called a quadratic spline. This demonstrates that the degree of a spline is the maximum degree of its polynomial parts.) The extended knot vector for this type of spline would be (0, 1, 2, 2, 3).

The simplest spline has degree 0. It is also called a step function. The next most simple spline has degree 1. It is also called a linear spline. A closed linear spline (i.e, the first knot and the last are the same) in the plane is just a polygon.

A common spline is the natural cubic spline. A cubic spline has degree 3 with continuity C², i.e. the values and first and second derivatives are continuous. Natural means that the second derivatives of the spline polynomials are zero at the endpoints of the interval of interpolation.

$${\displaystyle S''(a)\,=S''(b)=0.}$$

Thus, the graph of the spline is a straight line outside of the interval, but still smooth.

Algorithm for computing natural cubic splines

Cubic splines are of the form

$${\displaystyle S_{j}(x)=a_{j}+b_{j}(x-x_{j})+c_{j}(x-x_{j})^{2}+d_{j}(x-x_{j})^{3}.}$$

Given set of coordinates

$${\displaystyle C={\bigl [}(x_{0},y_{0}),(x_{1},y_{1}),...,(x_{n},y_{n}){\bigr ]},}$$

These must satisfy:

$${\displaystyle {\begin{aligned}S_{i}(x_{i})&=y_{i}=S_{i-1}(x_{i}),&&i=1,\ \ldots ,\ n-1,\\[4pt]S_{0}(x_{0})&=y_{0},\\[4pt]S_{n-1}(x_{n})&=y_{n},\\[4pt]S'_{i}(x_{i})&=S'_{i-1}(x_{i}),&&i=1,\ \ldots ,\ n-1,\\[4pt]S''_{i}(x_{i})&=S''_{i-1}(x_{i}),&&i=1,\ \ldots ,\ n-1,\\[4pt]S''_{0}(x_{0})&=S''_{n-1}(x_{n})=0.\end{aligned))}$$

Let us define one cubic spline S as a 5-tuple (a, b , c, d, x_t) where a, b, c, d correspond to coefficients in the form shown earlier and x_t is equal to x_j.

Algorithm for computing Natural Cubic Splines:
Input: set of coordinates C, with |C| = n + 1
Output: set splines which is composed of n 5-tuples.

1. Create new array a of size n + 1 and for i = 0, …, n set ${\displaystyle a_{i}=y_{i}\,}$
2. Create new arrays b and d, each of size n.
3. Create new array h of size n and for i = 0, …, n – 1 set ${\displaystyle h_{i}=x_{i+1}-x_{i}\,}$
4. Create new array α of size n and for i = 1, …, n – 1 set
   $${\displaystyle \alpha _{i}={\frac {3}{h_{i))}(a_{i+1}-a_{i})-{\frac {3}{h_{i-1))}(a_{i}-a_{i-1}).}$$

   
5. Create new arrays c, l, μ, z, each of size n + 1.
6. Set ${\displaystyle l_{0}=1,{\mu }_{0}=z_{0}=0\,}$
7. For i = 1, …, n – 1 set the following:
   $${\displaystyle {\begin{aligned}l_{i}&=2(x_{i+1}-x_{i-1})-h_{i-1}\mu _{i-1},\\\mu _{i}&={\frac {h_{i)){l_{i))},\\z_{i}&={\frac {\alpha _{i}-h_{i-1}z_{i-1)){l_{i))}.\end{aligned))}$$

   
8. Set ${\displaystyle l_{n}=1;z_{n}=c_{n}=0.\,}$
9. For j = n – 1, n – 2, …, 0, set the following:
   $${\displaystyle {\begin{aligned}c_{j}&=z_{j}-\mu _{j}c_{j+1},\\[4pt]b_{j}&={\frac {a_{j+1}-a_{j)){h_{j))}-{\frac {h_{j}(c_{j+1}+2c_{j})}{3)),\\[4pt]d_{j}&={\frac {c_{j+1}-c_{j)){3h_{j))}.\end{aligned))}$$

   
10. Create new set Splines and call it output_set. Populate it with n splines S.
11. For i = 0, …, n – 1 set the following:
    $${\displaystyle {\begin{aligned}S_{i,a}=a_{i},\\S_{i,b}=b_{i},\\S_{i,c}=c_{i},\\S_{i,d}=d_{i},\\S_{i,x}=x_{i}.\end{aligned))}$$

    
12. Output output_set

C++ implementation:

#include <array>
template<int n>
std::array<std::array<float, 5>, n> natural_cubic_splines_impl(
	const std::array<float, n + 1>& x, 
	const std::array<float, n + 1>& y)
{
	std::array<float, n + 1> a;
	for (int i = 0; i <= n; i++)
		a[i] = y[i];
	std::array<float, n> b, d, h;
	for (int i = 0; i <= n - 1; i++)
		h[i] = x[i + 1] - x[i];
	std::array<float, n> alpha;
	for (int i = 1; i <= n - 1; i++)
		alpha[i] = 3.0f / h[i] * (a[i + 1] - 
			a[i]) - 3.0f / h[i - 1] * (a[i] - a[i - 1]);
	std::array<float, n + 1> c, l, mu, z;
	l[0] = 1, mu[0] = z[0] = 0;
	for (int i = 1; i <= n - 1; i++)
	{
		l[i] = 2 * (x[i + 1] - x[i - 1]) - h[i - 1] * mu[i - 1];
		mu[i] = h[i] / l[i];
		z[i] = (alpha[i] - h[i - 1] * z[i - 1]) / l[i];
	}
	l[n] = 1, z[n] = c[n] = 0;
	for (int j = n - 1; j >= 0; j--)
	{
		c[j] = z[j] - mu[j] * c[j + 1];
		b[j] = (a[j + 1] - a[j]) / h[j] - 
				(h[j] * (c[j + 1] + 2 * c[j])) / 3.0f;
		d[j] = (c[j + 1] - c[j]) / (3.0f * h[j]);
	}
	std::array<std::array<float, 5>, n> output_set;
	for (int i = 0; i <= n - 1; i++)
	{
		output_set[i][0] = a[i];
		output_set[i][1] = b[i];
		output_set[i][2] = c[i];
		output_set[i][3] = d[i];
		output_set[i][4] = x[i];
	}
	return output_set;
}