## Construction of 'Natural' Cubic Spline

###### Notation
$$\forall i=0,\dots,n \ \ \ \ \ \ f_i := f\left(x_i\right)$$ $$\forall i=0,\dots,n-1 \ \ \ \ \varphi_i := \varphi\mid_{\left[x_i, x_{i+1}\right]}$$ $$\forall i=0,\dots,n-1 \ \ \ \ h_i := x_{i+1}-x_i$$
Cubic polynomial $\varphi_i$ on interval $\left[ x_i, x_{i+1} \right]$ is determined by 4 coefficients. The number of intervals is $n$. To determine $\varphi$ we have $4n$ degrees of freedom. For these degrees of freedom we construct corresponding equations.
$$\begin{matrix} \text{indexes} & \text{equations} & \left| \text{equations} \right| \\ \hline i=0,\dots,n & \varphi\left(x_i\right) = f\left(x_i\right) & n+1 \\ i=1,\dots,n-1 & \text{continuity of }\ \varphi\ \text{ in }\ x_i & n-1 \\ i=1,\dots,n-1 & \text{continuity of }\ \varphi\prime\ \text{ in }\ x_i & n-1 \\ i=1,\dots,n-1 & \text{continuity of }\ \varphi\prime\prime\ \text{ in }\ x_i & n-1 \\ \end{matrix}$$
The number of equations is 4 less than number of unknowns. We therefore add one of spline conditions. Let's consider a condition of null derivatives in endpoints. Such spline is called 'natural'.
To determine natural cubic spline we search $\varphi_i$ in convenient form. It emerges that efficient method is not based on expressing $\varphi_i$ as  $$\varphi_i\left(x\right) = a_ix^3 + b_ix^2 + c_ix + d_i$$  neither as  $$\varphi_i\left(x\right) = a_i(x-x_i)^3 + b_i(x-x_i)^2 + c_i(x-x_i) + d_i$$  but on expressing so called 'moments':
$$M_i := \varphi^{\prime\prime}\left(x_i\right) \ \ \ \left(i=0,\dots,n\right)$$
Assume we know these moments. We show later how to determine them. It holds:  $$\varphi_i \ - \ \text{cubic polynomial}$$ $$\varphi_i^\prime \ - \ \text{parabola}$$ $$\varphi_i^{\prime\prime} \ - \ \text{straight line}$$
From the assumption of second derivative continuity of $\varphi$ in $x_i$ we get  $$M_i = \varphi_i\prime\prime \left(x_i\right)$$ $$M_{i+1} = \varphi_i\prime\prime \left(x_{i+1}\right)$$
$\varphi_i\prime\prime$ is therefore a line passing through points $\left[x_i, M_i\right]$ and $\left[x_{i+1}, M_{i+1}\right]$
$$\varphi_i^{\prime\prime} \left(x\right) = \frac{\left(x-x_i\right)\cdot M_{i+1}}{x_{i+1}-x_i} + \frac{M_i\cdot\left(x-x_{i+1}\right)}{x_i-x_{i+1}}$$  $$\varphi_i^{\prime\prime}\left(x\right) = - \frac{M_i}{h_i}\cdot\left(x-x_{i+1}\right)+\frac{M_{i+1}}{h_i}\cdot\left(x-x_i\right)$$
With integration we obtain  $$\varphi_i^\prime\left(x\right) = - \frac{M_i}{2h_i}\cdot\left(x-x_{i+1}\right)^2 + \frac{M_{i+1}}{2h_i}\cdot\left(x-x_i\right)^2 + A_i$$  $$\varphi_i\left(x\right) = -\frac{M_i}{6h_i}\cdot\left(x-x_{i+1}\right)^3 + \frac{M_{i+1}}{6h_i}\cdot\left(x-x_i\right)^3 + A_i\left(x-x_i\right) + B_i$$
In last expression of $\varphi_i$ we first determine coefficients $A_i$, $B_i$ $\left(i=0,\dots,n-1\right)$ using moments and then we are going to construct equations for moments. For that we use conditions:  $$\varphi_i\left(x_i\right) = f_i$$  $$\varphi_i\left(x_{i+1}\right) = f_{i+1} \ \ \ \left(i=0,\cdots,n-1\right)$$
We obtain $$\varphi_i\left(x_i\right) = \frac{M_i}{6}\cdot h_i^2+B_i=f_i$$  $$\rightarrow \color{red}{B_i=}f_i-\frac{\color{red}{M_i}}{6}\cdot h_i^2$$  $$\varphi_i\left(x_{i+1}\right)=\frac{M_{i+1}}{6}\cdot h_i^2+A_ih_i+f_i - \frac{M_i}{6}\cdot h_i^2=f_{i+1}$$  $$\rightarrow \color{red}{A_i=}\frac{f_{i+1}-f_i}{h_i}+\frac{\color{red}{M_i}-\color{red}{M_{i+1}}}{6}\cdot h_i$$
We construct equations for moments using equivalent expression of continuity condition of cubic spline derivative in points:  $$\varphi_{i-1}^\prime\left(x_i\right)=\varphi_i^\prime\left(x_i\right) \ \ \left(i=1,\cdots,n\right)$$
Let's recall form $\varphi_i^\prime$  $$\varphi_i^\prime\left(x\right) = - \frac{M_i}{2h_i}\cdot\left(x-x_{i+1}\right)^2 + \frac{M_{i+1}}{2h_i}\cdot\left(x-x_i\right)^2 + A_i$$  $\varphi_{i-1}^\prime$ respectively:  $$\varphi_{i-1}^\prime\left(x\right) = - \frac{M_{i-1}}{2h_{i-1}}\cdot\left(x-x_i\right)^2 + \frac{M_i}{2h_{i-1}}\cdot\left(x-x_{i-1}\right)^2 + A_{i-1}$$ 
Using formulation of $A_i$, resp. $A_{i-1}$ via moments we get  $$\varphi_{i-1}^\prime\left(x_i\right)=0+\frac{M_i}{2h_{i-1}}\cdot h^2_{i-1} + \frac{f_i-f_{i-1}}{h_{i-1}}+\frac{M_{i-1}-M_i}{6}\cdot h_{i-1}$$  $$= - \frac{M_i}{2h_i}\cdot h_i^2 + 0 + \frac{f_{i+1}-f_i}{h_i} + \frac{M_i-M_{i+1}}{6}\cdot h_i = \varphi_i^\prime\left(x_i\right)$$
Because we construct natural cubic spline, it is valid that $M_0=\varphi^{\prime\prime}\left(x_0\right)=0=\varphi^{\prime\prime}\left(x_n\right)=M_n$ and therefore we have only $n-1$ equations $\left(i=1,\dots,n-1\right)$ for unknown moments $M_1, M_2,\dots,M_{n-1}$. These equations can be written in form

Human Being #10 you have to copy-paste we're pre beta folks

Human Being #10 that's not an excuse

Human Being #10 it's a cirsumstance

Human Being #10 so don't be shittin pants here fellas

$$\frac{h_{i-1}}{6}M_{i-1}+\left(\frac{h_{i-1}}{2}-\frac{h_{i-1}}{6}+\frac{h_i}{2}-\frac{h_i}{6}\right)\cdot M_i+\frac{h_i}{6}M_{i+1}= -\frac{f_i-f_{i-1}}{h_{i-1}}+\frac{f_{i+1}-f_i}{h_i}$$  $$\frac{h_{i-1}}{6}M_{i-1}+\frac{h_{i-1}+h_i}{3}\cdot M_i+\frac{h_i}{6}M_{i+1}= g_i$$
Matrix notation leads to a system with 3-diagonal matrix:  $$\left( \begin{matrix} \frac{h_0+h_1}{3} & \frac{h_1}{6} & & & & & \\ \ddots & \ddots & \ddots & & & & \\ & \ddots & \ddots & \ddots & & & \\ & & \frac{h_{i-1}}{6} & \frac{h_{i-1}+h_i}{3} & \frac{h_i}{6} & & \\ & & & \ddots & \ddots & \ddots & \\ & & & & \ddots & \ddots & \ddots \\ & & & & & \frac{h_{n-2}}{6} & \frac{h_{n-2}+h_{n-1}}{3} \\ \end{matrix} \right) \left(\begin{matrix} M_1 \\ \vdots \\ M_{i-1} \\ M_i \\ M_{i+1} \\ \vdots \\ M_{n-1} \end{matrix}\right) = \left(\begin{matrix} g_1 \\ \vdots \\ g_{i-1} \\ g_i \\ g_{i+1} \\ \vdots \\ g_{n-1} \end{matrix} \right)$$