Natural Cubic Spline interpolation (Theory)

I believe many would be very familiar with linear interpolation where we fix 2 points and we draw a line in between these 2 point. So the points in between are defined by a linear equation. Not many would come across and use cubic interpolation. Here is a quick guide on how it works.

In cubic spline, the idea is the same, we have 2 points and we want to find a cubic equation to describe the points in between such that we can use it to estimate the intermediate values. Now let us consider 4 points as shown below.

In this case, we have 4 points and we will need to model 3 equations; if we have n+1 points we will need n such equations  Each of these equation will look like this:

$f_i (x) = a_i (x-x_i)^3 + b_i (x-x_i)^2 + c_i (x-x_i) + d_i$

Thus there are 4n unknown we need to find. Here are the 4n equations that will help us determine these unknowns:

We know that at each equation has to fix the points hence we have the following:

$f_i (x_i) = a_i (x-x_i)_i^3 + b_i(x-x_i)_i^2 + c_i (x-x_i)_i + d_i$

where i = [0,...,n-1]

This implies that we have, 

$d_i = y_i$           ---(1a)

$f_0 (x_0) = y_0$    ---(1b)

This will give us n+1 equations.

To ensure that the equations are continuous/connecting, we need to ensure the end of the one equation will match the start of the next equation. Hence,

$f_i (x_i) = f_{i+1}(x_i)$ ; ---(2)

This will give us n-1 equations.

We also would want the slope, first derivative,  at the connecting points to be continuous or the same hence,

$f_i '(x_i) = f_{i+1}'(x_i)=c_i$ ---(3)

where i = [1,...,n-1]

This will give us n-1 equations.

We also want the second derivative  to be continuous or the same at connecting points, hence,

$f_i''(x_i) = 2b_i$

$f_i ''(x_i) = f_{i+1}''(x_i)=2b_i$ -- (4)

This will give us another n-1 equations.

Hence, now we have in total 4n-2 equations and we still need 2 more.

There are a few types of cubic spline and one of the most commonly seen is the natural cubic spline. For this we specify the final 2 equations:

$f_0''(x_0) = 0$ -- (5)

$f_{n-1}''(x_{n-1}) = 0$ -- (6)

Now we have 4n equations and we can go ahead to solve those variables. With those variables,we can now do interpolation with the equations:

$f_i (x) = a_i (x-x_i)^3 + b_i(x-x_i)^2 + c_i (x-x_i) + d_i$

Next, hang on to this theory first while I place all these into a system of linear equations.
And solve them using Matrix Algebra.