Natural Cubic Spline Function Interpolation

# Natural Cubic Spline Function Interpolation

We will now look at another way to interpolate data points with a function. Now, suppose that we have a finite number of data points to plot. Then we can create a function that represents this data by simply connected each point with a straight line: While these sort of piecewise linear functions pass through all of the data points, the one real disadvantage they have is that often times these functions are not smooth and so differentiating at these points in analyzing this data is meaningless.

Intuitively, the next approach we could take is connecting the data points with quadratic polynomials: Once again, these piecewise quadratic functions pass through all of the data points but they are not necessarily smooth.

Now suppose that we want to interpolate the $n$ distinct points $(x_1, y_1)$, $(x_2, y_2)$, …, $(x_n, y_n)$ in $\mathbb{R}^2$ and assume without loss of generality that $x_1 < x_2 < ... < x_n$. We want to find a function $y = s(x)$ that is continuous on the interval $[x_1, x_n]$ and such that the first and second derivatives of $s$ are continuous on this interval as well to ensure the smoothness of $s$.

Fortunately such functions can be constructed. We will not prove this here, but we will see that there exists a function $s(x)$ known as a Natural Cubic Spline Function such that for each subinterval $[x_{j-1}, x_j]$ for $j = 2, 3, ... n$ there exists a cubic polynomial for which the piecewise function of these cubic polynomials is $s(x)$, and the first and second derivatives $s'(x)$ and $s''(x)$ are continuous for all $x \in [a, b]$ and such that $s''(x_1) = 0 = s''(x_n)$.

We will now derive a formula for this natural cubic spline function.

We first note that since $s(x)$ is a cubic piecewise function, then $s'(x)$ will be a quadratic piecewise function and $s''(x)$ will be a linear piecewise function. Now since $s(x)$ is linear for each subinterval $[x_{j-1}, x_j]$, then we can easily construct $s''(x)$ by letting $s''(x_i) = M_i$ for each $i = 1, 2, ..., n$ and for all $x \in [ x_{j-1}, x_j]$, $j = 2, 3, ..., n$ we'll have that:

(1)
\begin{align} \quad s''(x) = \frac{(x_j - x)M_{j-1} + (x - x_{j-1}M_j}{x_j - x_{j-1}} \end{align}

We can then anti-differentiate this function twice (because $s''(x)$ and $s'(x)$ are continuous for $x \in [ x_{j-1}, x_j]$ to eventually get the following formula for our natural cubic spline function for all $x \in [x_{j-1}, x_j]$:

(2)
\begin{align} \quad s(x) = \frac{(x_j - x)^3 M_{j-1} + (x - x_{j-1})^3 M_j}{6(x_j - x_{j-1})} + \frac{(x_j - x)y_{j-1} + (x - x_{j-1})y_j}{x_j - x_{j-1}} - \frac{1}{6} (x_j - x_{j-1})\left ( (x_j - x)M_{j-1} + (x - x_{j-1})M_j \right ) \end{align}

To then determine the functions $s(x)$ - we need to know the values of the $M$'s It can be shown that the $M$'s must satisfy the following system of equations:

(3)
\begin{align} \quad \left\{\begin{matrix} M_1 = M_n = 0\\ \frac{1}{6}(x_j - x_{j-1})M_{j-1} + \frac{1}{3}(x_{j+1}-x_{j-1})M_j + \frac{1}{6}(x_{j+1} -x_j)M_{j+1} = \frac{y_{j+1}-y_j}{x_{j+1}-x_j} - \frac{y_j - y_{j-1}}{x_j - x_{j-1}} & j = 2, 3, ..., n-1 \end{matrix}\right. \end{align}

This system of equations can easily be solved for $M_2$ when $n = 3$ or for $M_2$ and $M_3$ when $n = 4$. When $n$ is large though, this system becomes increasingly difficult to solve for the intermediary $M$'s.

## Error in Natural Cubic Spline Function Interpolation

Suppose that we interpolate a function $f$ at $x_1$, $x_2$, …, $x_n$ where $x_i = a (i - 1)h$ for $h = \frac{b - a}{n - 1}$ and for $i = 1, 2, ..., n$. It can be shown that for some constant $C$ dependent on $f''(a)$, $f''(b)$, and $\max_{a ≤ x ≤ b} \mid f^{(4)}(x) \mid$ that:

(4)
\begin{align} \quad \max_{a≤x≤b} \mid f(x) - s_n(x) \mid ≤ Ch^2 \end{align}