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.