Cubic Interpolation

The cubic Hermite spline

A spline is a set of curved lines constructed from a set of points.

Cubic interpolation consists of inserting new points along a cubic spline.

For example, consider the following spline, constructed with 3 points:

\[ p_1 = (1,3) \quad p_2 = (2,1) \quad p_3 = (3,2) \]

This spline is made up of two curved lines. The first one created with \(p_1\) and \(p_2\), and the second one created with \(p_2\) and \(p_3\):

Each of these curved lines is created using a third-degree polynomial in this form:

\[ \begin{align} &f(x) = ax^3 + bx^2 + cx + d\\\\ &f'(x) = 3ax^2 + 2bx + c \end{align} \]

Only on the interval from \(x=0\) to \(x=1\). So we have:

\[ \begin{align} &f(0) = d \quad f(1) = a+b+c+d\\\\ &f'(0) = c \quad f'(1) = 3a+2b+c \end{align} \]

We solve for \(a\), \(b\), \(c\) and \(d\) with a system of equations, which results in:

\[ \begin{align} &a = 2f(0) - 2f(1) + f'(0) + f'(1)\\ &b = -3f(0) + 3f(1) - 2f'(0) - f'(1)\\ &c = f'(0)\\ &d = f(0) \end{align} \]

\(f(0)\) and \(f(1)\) are the \(y\)-coordinates of the endpoints of the curved line.

For example, the endpoints of the first curved line of our spline are \(p_1\) and \(p_2\):

So in this case we have:

\[ \begin{align} &p_1 = (1,3) \quad p_2 = (2,1)\\\\ &f(0) = 3 \quad f(1) = 1 \end{align} \]

\(f'(0)\) and \(f'(1)\) are the derivatives at the endpoints of the curved line:

We use the slope of the line between the previous and the next point as the derivative at a point.

For example the derivative at \(p_2\) is the slope of the line formed by \(p_1\) and \(p_3\).

If the point doesn't have a previous or a next point, then repeat the corresponding endpoint. For example, \(p_1\) doesn't have a previous point. An extra point \(p_0\) is created:

\[ p_1 = (1, 3) \quad p_0 = (0, 3) \]

So we have:

\[ \begin{align} &f'(0) = \frac{p_{2y} - p_{0y}}{p_{2x} - p_{0x}} = -1\\\\ &f'(1) = \frac{p_{3y} - p_{1y}}{p_{3x} - p_{1x}} = -0.5 \end{align} \]

If we plug these values into these equations, we'll get:

\[ \begin{align} &f(0) = 3 \quad f(1) = 1\\ &f'(0) = -1 \quad f'(1) = -0.5\\ &a=2.5, \quad b=-3.5 \quad c=-1 \quad d=3 \end{align} \]

\[ \begin{align} &f(x) = ax^3 + bx^2 + cx + d\\\\ &f(x) = \frac{5}{2}x^3 - \frac{7}{2}x^2 - x + 3\\\\ \end{align} \]

Now we can interpolate values between \(p_1\) and \(p_2\), on the interval \([0,1]\).

For example, the interpolated point at \(x=0.25\) is:

\[ \begin{align} &z = (1+x, f(x))\\\\ &z = (1.25, 2.57) \end{align} \]

We add \(1\) to the \(x\)-coordinate because that's the starting point of the curved line.

We do the same procedure with the second curved line, and the spline will be constructed.

Python code:

import numpy as np

# ys: y-coordinates
# x:  any value between 0 and len(ys) - 1
def cubic_query(ys, x):
    n = ys.shape[0]

    if x < 0 or x > n-1:
        raise ValueError('value x must be between 0 and n-1')

    if x == 0.0: return ys[0]
    elif x == float(n-1): return ys[-1]

    start = np.floor(x)
    x -= start

    prev = int(start) - 1
    follow = int(start) + 2

    p0 = ys[prev if prev >= 0 else 0]
    p1 = ys[int(start)]
    p2 = ys[int(start)+1]
    p3 = ys[follow if follow < n else n-1]

    f0 = p1
    f1 = p2
    df0 = (p2 - p0) / 2
    df1 = (p3 - p1) / 2

    a = 2*f0 - 2*f1 + df0 + df1
    b = -3*f0 + 3*f1 - 2*df0 - df1
    c = df0
    d = f0

    return a*x**3 + b*x**2 + c*x + d

Watch the video: