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.

Polynomial Interpolation

Linear

Quadratic

n-th order

Spline Interpolation

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 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

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.

Constraints:

  1. Spline must pass through each knot: $s(x_i) = y_i$. [2*(n-1)]
  2. Spline twice continuously differentiable at internal knots: $s^{(k)}(x_i^-) = s^{(k)}(x_i^+), k = 1, 2$. [2*(n-2)]
  3. Boundary conditions are needed to guarantee solution uniqueness: (Either of the following suffices.) [2]
    • 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$.

Hermite basis functions:

  1. $h_{00}(t) = (1 + 2 t) (1 - t)^2$
  2. $h_{01}(t) = t (1 - t)^2$
  3. $h_{10}(t) = t^2 (3 - 2 t)$
  4. $h_{11}(t) = t^2 (t - 1)$

Given function and tangent values at the endpoints, the Hermite interpolation polynomial on the unit interval is their linear combination with the corresponding Hermite basis functions.

$$H(t) = h_{00}(t) p_0 + h_{10}(t) m_0 + h_{01}(t) p_1 + h_{11}(t) m_1$$

For an arbitrary interval $(x_i, x_{i+1})$, simply substitute $t = (x - x_i) / (x_{i+1} - x_i)$.

Solution process:

  1. 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;
  2. 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

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.

🏷 Category=Computation