Construction of 'Natural' Cubic Spline

Notation
Thumb dscf5623 edit 2bwa small
$$ \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 $$
Eye
Thumb dscf5623 edit 2bwa small
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.
Eye
Thumb dscf5623 edit 2bwa small
$$ \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} $$
Eye
Thumb dscf5623 edit 2bwa small
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'.
Eye
Thumb dscf5623 edit 2bwa small
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':
Eye
Thumb dscf5623 edit 2bwa small
$$ M_i := \varphi^{\prime\prime}\left(x_i\right) \ \ \ \left(i=0,\dots,n\right) $$
Eye
Thumb dscf5623 edit 2bwa small
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} $$
Eye
Thumb dscf5623 edit 2bwa small
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) $$
Eye
Thumb dscf5623 edit 2bwa small
$\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]$
Eye
Thumb dscf5623 edit 2bwa small
$$ \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)$$
Eye
Thumb dscf5623 edit 2bwa small
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 $$
Eye
Thumb dscf5623 edit 2bwa small
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) $$
Eye
Thumb dscf5623 edit 2bwa small
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$$
Eye
Thumb dscf5623 edit 2bwa small
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) $$
Eye
Thumb dscf5623 edit 2bwa small
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} $$ $$ $$
Eye
Thumb dscf5623 edit 2bwa small
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) $$
Eye
Thumb dscf5623 edit 2bwa small
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
Thumb photo on 21 03 14 at 17.05

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

Thumb photo on 21 03 14 at 17.05

Human Being #10 that's not an excuse

Thumb photo on 21 03 14 at 17.05

Human Being #10 it's a cirsumstance

Thumb photo on 21 03 14 at 17.05

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

Eye
Thumb dscf5623 edit 2bwa small
$$ \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 $$
Eye
Thumb dscf5623 edit 2bwa small
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) $$
Eye