Medium carolinum logo.svg
Medium dscf5623 edit 2bwa small

Viktor Futó

My goal is to simplify the way how we perceive informations and comprehend the knowledge. Say hello if you believe there is easier way to learn and understand!

Thumb carolinum logo.svg Charles University
Thumb mff logo Faculty of Mathematics and Physics
Thumb dscf5623 edit 2bwa small Viktor Futó
Lagrange Interpolation

interpolation is a method of constructing new data points within the range of a discrete set of known data points.

Thumb dscf5623 edit 2bwa small Viktor Futó

Construction of 'Natural' Cubic Spline

220px spline %28psf%29
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]$
Umkklia
$$ \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
$$ \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) $$
Construction of 'Natural' Cubic Spline