Natural Cubic Spline interpolation (Application)

It has been a long journey from Theory to Derivation and now we are onto application. With all the theories and equations we obtained, we will now apply them and conduct interpolation.
For (n+1) points we now have 3 generic equations
$\frac{3(y_{i+2}-y_{i+1})}{(x_{i+2}-x_{i+1})^2} +\frac{3(y_{i+1}-y_i)}{(x_{i+1}-x_i)^2} = \frac{k_i}{x_{i+1}-x_i }+k_{i+1}[\frac{2}{x_{i+1}-x_i} +\frac{2}{x_{i+2}-x_{i+1}}]+\frac{k_{i+2}}{x_{i+2}-x_{i+1}}$           —(1)
$3\frac{y_{n+1}-y_n}{(x_{n+1}-x_n)^2}= \frac{2k_{n+1}}{x_{n+1}-x_n}+ \frac{k_n}{(x_{n+1}-x_n)}$ —(2)
$3\frac{y_1-y_0}{(x_1-x_0)^2} = \frac{2k_0}{x_1-x_0}+\frac{k_1}{x_1-x_0}$  —(3)
For i=[0,n-2]

The unknow here is k which is $f_i'(x_i)=c_i$, we have also seen that the rest of $a_i,b_i, d_i$ are all known as follows:
$a_i=\frac{1}{3}[\frac{(k_{i+1}-k_i)}{(x_{i+1}-x_i)^2}-\frac{2b_i}{(x_{i+1}-x_i )}]$ ---(4)
$b_i= \frac{3(y_{i+1}-y_i )}{(x_{i+1}-x_i)^2} - \frac{k_{i+1}+2k_i}{(x_{i+1}-x_i)}$    ---(5)
$c_i=k_i$    ---(6)
$d_i = y_i$    ---(7)

What is left now is to find k and it can be found by applying equation (1) - (3) and put them into matrix form and solve k using simple linear algebra.

$Wk = F$
$k_{(n+1)x1}=[k_0,k_1,...,k_n]^T$
$F_{(n+1)x1} =[ f_0,f_1,...,f_n]^T$
Where $f_i$ are the Left Hand sides of (1)-(3) and W is the (n+1)x(n+1) matrix formed by the Right Hand side of (1)-(3).

By obtaining the inverse of W,

$k = W^{-1} F$

we can solve for k.

To do interpolation for a value x, follow the following algorithm:

Step 1:
Find the interval $[x_i,x_{i+1}]$ by which x belongs.

Step 2:
Apply (4)-(7) to obtain the cubic equation coefficient.

Step 3:
Plug in the coefficients into the equation:
$y(x) = a_i(x-x_i)^3 + b_i(x-x_i)^2+c_i(x-x_i)+d_i$

Done! Now you got an estimated value of y(x)!

Natural Cubic Spline interpolation (Derivation)

Recap that in our previous post, we introduce how cubic spline interpolation can be applied to a n+1 points to produce a smooth curve. There will be a total of n curves each described by:
$f_i (x) = a_i(x-x_i)^3 + b_i(x-x_i)^2 + c_i (x-x_i) + d_i$

The conditions for a natural cubic spline is given by the following:

$f_i (x_i) = a_i(x-x_i)^3 + b_i(x-x_i)^2 + c_i (x-x_i)+d_i = y_i$    —(1)
$f_i (x_i) = f_{i+1}(x_i)$                                                                         —(2)
$f_i '(x_i) = f_{i+1}'(x_i)=c_i$                                                                —(3)
$f_i ''(x_{i+1}) = f_{i+1}''(x_{i+1})=2b_i$                                                      —(4)
$f_0''(x_0) = 0$                                                                                   —(5)
$f_{n-1}''(x_{n-1}) = 0$                                                                            —(6)

From here we will derive the solution to conduct cubic spline interpolation. The end results will be as specified in Wikipedia. The idea is the same as when you try to solve simultaneous equations and place them into systems of linear equations and solve them using simple linear algebra.

From (3) we are going to express everything in $f_i '(x_i) = f_{i+1} '(x_i) = k_{i+1}$. 
First we obtain $a_i$ in terms of $b_i$ and $k_i$

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

$c_{i+1}-c_i= 3a_i (x_(i+1)-x_i )^2+2b_i (x_(i+1)-x_i )$ 

$a_i=\frac{1}{3}[\frac{(k_{i+1}-k_i)}{(x_{i+1}-x_i)^2}-\frac{2b_i}{(x_{i+1}-x_i )}]$ —(7)

From (4) we will get,
$f_{i+1}''(x_{i+1})=2b_{i+1}=6a_i(x_{i+1}-x_i)+2b_i$
$b_{i+1}-b_i= 3a_i (x_{i+1}-x_i )$                                                                             —(8)

Next we will substitute (7) into (8) 
$b_{i+1}-b_i= 3*\frac{1}{3}[ \frac{k_(i+1)-k_i}{(x_{i+1}-x_i)^2} - \frac{2b_i}{(x_{i+1}-x_i )}]*(x_{i+1}-x_i ) $

$b_{i+1}-b_i= \frac{(k_{i+1}-k_i)}{(x_{i+1}-x_i )}-2b_i $
$b_{i+1}+b_i= \frac{(k_{i+1}-k_i)}{(x_{i+1}-x_i )}$                                                                    — (9)

Equation (9) will be used in one of the final substitution so let's just hang on to equation (9) first and we will come back to this later. Now we try to substitute (1) and (7) into (2) to express $b_i$ in terms of $k_i$:

$y_{i+1}= a_i (x_{i+1}-x_i )^3+b_i (x_{i+1}-x_i)^2+c_i (x_{i+1}-x_i )+d_i$

$y_{i+1}-y_i= \frac{1}{3}[ \frac{(k_{i+1}-k_i)}{(x_{i+1}-x_i)^2} -\frac{2b_i}{(x_{i+1}-x_i )}](x_{i+1}-x_i )^3+b_i (x_{i+1}-x_i)^2+k_i (x_{i+1}-x_i )$

$\frac{(y_{i+1}-y_i)}{(x_{i+1}-x_i)^2} = \frac{1}{3}[\frac{(k_{i+1}-k_i)}{(x_{i+1}-x_i}-2b_i ]+b_i+\frac{k_i}{(x_{i+1}-x_i )}$

$\frac{3(y_{i+1}-y_i )}{(x_{i+1}-x_i)^2} = [\frac{(k_{i+1}-k_i)}{(x_{i+1}-x_i)}-2b_i ]+3b_i+\frac{3k_i}{x_{i+1}-x_i } $

$b_i= \frac{3(y_{i+1}-y_i )}{(x_{i+1}-x_i)^2} -  \frac{(k_{i+1}-k_i)}{x_{i+1}-x_i}-\frac{3k_i}{(x_{i+1}-x_i )}$
$b_i= \frac{3(y_{i+1}-y_i )}{(x_{i+1}-x_i)^2} - \frac{k_{i+1}+2k_i}{(x_{i+1}-x_i)}$  —(10)

Finally substitute (10) into (9) to get a equation with only ks, ys and xs.
$\frac{3(y_{i+2}-y_{i+1} )}{(x_{i+2}-x_{i+1})^2} -  \frac{(k_{i+2}+2k_{i+1})}{(x_{i+2}-x_{i+1})}+\frac{3(y_{i+1}-y_i )}{(x_{i+1}-x_i)^2} - \frac{(k_{i+1}+2k_i)}{(x_{i+1}-x_i)}= \frac{k_{i+1}-k_i}{x_{i+1}-x_i}$

$\frac{3(y_{i+2}-y_{i+1})}{(x_{i+2}-x_{i+1})^2} +\frac{3(y_{i+1}-y_i )}{(x_{i+1}-x_i)^2} = \frac{k_{i+1}-k_i}{x_{i+1}-x_i}+ \frac{k_{i+2}+2k_{i+1}}{x_{i+2}-x_{i+1}}+ \frac{k_{i+1}+2k_i}{x_{i+1}-x_i}$

$\frac{3(y_{i+2}-y_{i+1})}{(x_{i+2}-x_{i+1})^2} +\frac{3(y_{i+1}-y_i}{(x_{i+1}-x_i)^2} = \frac{k_i}{x_{i+1}-x_i }+k_{i+1}[\frac{2}{x_{i+1}-x_i} +\frac{2}{x_{i+2}-x_{i+1}}]+\frac{k_{i+2}}{x_{i+2}-x_{i+1}}$ —(11)

With this equation we have exactly (n-1) such equations for i=[0,n-2] and we have (n+1) unknown. By using the 2 other equation (5) and (6), we will obtain the other 2 equations.

Therefore, subsitute i=n and (10 )into (4) 

$0= 6a_n (x_{n+1}-x_n )+2b_n$
$0= 2[\frac{(k_{n+1}-k_n)}{(x_{n+1}-x_n)^2} -\frac{2b_n}{x_{n+1}-x_n }](x_{n+1}-x_n )+2b_n$
$b_n   =\frac{k_{n+1}-k_n}{x_{n+1}-x_n }$
$3\frac{y_{n+1}-y_n }{(x_{n+1}-x_n)^2} = \frac{k_{n+1}-k_n}{x_{n+1}-x_n }+
\frac{k_{n+1}+2k_n}{x_{n+1}-x_n}$
$3\frac{y_{n+1}-y_n}{(x_{n+1}-x_n)^2}= \frac{2k_{n+1}}{x_{n+1}-x_n}+ \frac{k_n}{(x_{n+1}-x_n)}$ —(12)

Substitute i=0 into (10),

$b_0= \frac{3(y_1-y_0 )}{(x_1-x_0)^2} - \frac{k_1+2k_0}{(x_i-x_0)}=0$

$3\frac{y_1-y_0}{(x_1-x_0)^2} = \frac{k_1+2k_0}{x_1-x_0}$
$3\frac{y_1-y_0}{(x_1-x_0)^2} = \frac{2k_0}{x_1-x_0}+\frac{k_1}{x_1-x_0}$  —(13)

Equations 11-13 is the exact equations you will see in Wikipedia. Now the obvious question is "How are we going to use all these equations we derived to do Cubic Spline Interpolation?". This shall be reviewed in the upcoming post.

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.