Given n observations, **interpolation** refers to techniques
that construct a smooth function passing through the observations
so that values at intermediate points can be estimated.
A complementary group of techniques is Fitting.

This is article is based on the original note on interpolation and numerical differentiation. Hermite and piecewise interpolation are also covered in the note, but omited here due to lack of application.

**Splines** are piecewise k-th order polynomials with (k-1)-th continuous derivative at knots.
**Knots** are points where constraints and continuous conditions are held.
The **order of a spline** is the highest order of the polynomials.

The technique and terminology are directly inspired by the practice of splines in engineering design, esp. shipbuilding.

Spline interpolation does not have the strong oscillation
observed in high order polynomial interpolation, aka **Runge's phenomenon**.

**Smoothing spline** treats the observations as noisy, which is a method of Fitting.

**Cubic spline** is a piecewise-cubic, twice continuously differentiable function.
It is sometimes referred to as **cubic Hermite spline**,
where cubic Hermite basis functions are used.
For n observations, n-1 cubic polynomials are needed, with 4*(n-1) degrees of freedom.

**Hermite interpolation polynomial** H(t) on the unit interval
is the linear combination of function and derivative values $(y_i, m_i)$ at the endpoints (i = 0, 1)
with the corresponding Hermite basis functions:
$H(t) = h_{00}(t) y_0 + h_{10}(t) m_0 + h_{01}(t) y_1 + h_{11}(t) m_1$.
Here the **cubic Hermite basis functions** are:
$h_{00}(t) = (1 + 2 t) (1 - t)^2$, $h_{01}(t) = t (1 - t)^2$,
$h_{10}(t) = t^2 (3 - 2 t)$, and $h_{11}(t) = t^2 (t - 1)$.
For an arbitrary interval $(x_i, x_{i+1})$, simply substitute $t = (x - x_i) / (x_{i+1} - x_i)$.

Constraints:

- Spline must pass through each knot: $s(x_i) = y_i$; 2(n-1) equations.
- Spline twice continuously differentiable at internal knots: $s^{(k)}(x_i^-) = s^{(k)}(x_i^+), k = 1, 2$; 2(n-2) equations
- Boundary conditions are needed to guarantee solution uniqueness:
either of the following suffices; 2 equations.
- Natural boundary condition: No torque exerted at the boundaries, $s''(x_i^-) = s''(x_i^+), i = 1, n$.
- Periodic boundary condition: $s^{(k)}(x_n^-) = s^{(k)}(x_0^+), k = 1, 2$.

Solution process:

- Initiate the cubic Hermite spline as $s(x) = \sum_{i = 1}^{n} [h_{00}(t_i) y_i + h_{10}(t_i) m_i]$, which automatically satisfies the first condition and the continuous differentiability condition;
- The twice continuous differentiability condition and the boundary condition lead to a system of linear equations of $m_i$, with a tri-diagonal matrix which has efficient solvers.

**B-spline**, or **basis spline**

Theorem: Every spline function of a given degree, smoothness, and domain partition, can be uniquely represented as a linear combination of B-splines of that same degree and smoothness, and over that same partition.