Wednesday 1 April 2020

Quadratic splines: Part I

Some basic properties of parabola in the context of the second-order Hermite interpolation equation. 

There is a one-dimensional dataset with $n$ points: $x = (x_0, \dots, x_{n-1})$ and $y = (y_0, \dots, y_{n-1})$, such that $x_{i} > x_{i-1}$ for any $i$. We introduce the following labels: $$h_{i-1} = x_i - x_{i-1}$$ $$\delta_{i-1} = \frac{y_i - y_{i-1}}{x_i - x_{i-1}}$$ $h$ is always positive, while $\delta$ can have any value. On each segment, we approximate the unknown function with a parabola. On the $[i-1, i]$ segment: \begin{equation}f(x) = a_0 + a_1 (x - x_{i-1}) + a_2 (x - x_{i-1})^2\end{equation} The first and the second derivative of the parabola are: \begin{equation}f'(x) = a_1 + 2 a_2 (x - x_{i-1})\end{equation} \begin{equation}f''(x) = 2 a_2 \end{equation} The Hermite interpolation theorem provides us with a tool to determine the $a$ coefficients on the $[i-1, i]$ segment if we know $y_{i-1}$, $y_i$ and one of the first derivative in the end points, either $y'_{i-1}$ or $y'_i$. Let's assume that we know ("know" in the sense "we can compute") $y'_{i-1}$. Then there are three equations that the parabola must obey: \begin{equation}f(x_{i-1}) = y_{i-1} = a_0\end{equation} \begin{equation}f'(x_{i-1}) = y'_{i-1} = a_1\end{equation} \begin{equation}f(x_{i}) = y_i = a_0 + a_1 h_{i-1} + a_2 h_{i-1}^2\end{equation} The solution is then trivial: \begin{equation}a_0 = y_{i-1}\end{equation} \begin{equation}a_1 = y'_{i-1}\end{equation} \begin{equation}a_2 = \frac{y_{i} - y_{i-1} - y'_{i-1} h_{i-1}}{h_{i-1}^2}\end{equation} Once the $a$ coefficients are known, the parabola is fully determined. That also means that the derivative in the point $i$ is fixed: $$f'(x_{i}) = y'_i = a_1 + 2 a_2 (x_i - x_{i-1}) = y'_{i-1} + 2 \frac{y_{i} - y_{i-1} - y'_{i-1} h_{i-1}}{h_{i-1}^2} h_{i-1}$$ $$y'_i = \frac{2(y_{i} - y_{i-1}) - y'_{i-1} h_{i-1}}{h_{i-1}} $$ \begin{equation}y'_i = 2\delta_{i-1} - y'_{i-1}\end{equation} Local extremum

The extremum of this parabola is located at $x_m$: $$f'(x_m) = 0 = a_1 + 2 a_2 (x_m - x_{i-1})$$ \begin{equation}x_m = x_{i-1} - \frac{a_1}{2a_2}\end{equation} Monotonicity

The function $f(x)$ is monotone on the $[i-1, i]$ segment if it does not have an extremum on it, i.e. if $$x_m < x_{i-1}\;\;\;\;\;\;\;\;\;\;\mathrm{or}\;\;\;\;\;\;\;\;\;\; x_m > x_i$$ The first condition readily translates into: $$x_{i-1} - \frac{a_1}{2a_2} < x_{i-1}$$ $$ \frac{a_1}{2a_2} > 0$$ or, when we substitute $a_1$ and $a_2$: $$ \frac{y'_{i-1} h_{i-1}^2}{2(y_{i} - y_{i-1} - y'_{i-1} h_{i-1})} > 0$$ $$ \frac{y'_{i-1} h_{i-1}}{2(\delta_{i-1} - y'_{i-1})} > 0$$ As by definition $h_{i-1} > 0$ $$ \frac{y'_{i-1}}{2(\delta_{i-1} - y'_{i-1})} > 0$$ If $y'_{i-1} > 0$ then $\delta_{i-1} - y'_{i-1} > 0$ and $\delta_{i-1} > y'_{i-1}$. If $y'_{i-1} < 0$, then $\delta_{i-1} < y'_{i-1}$. Therefore, the first condition ($x_m < x_{i-1}$) reduces to: \begin{equation}\boxed{|\delta_{i-1}| > |y'_{i-1}|}\end{equation} The second condition leads to: $$x_{i-1} - \frac{a_1}{2a_2} > x_{i}$$ $$-x_{i} + x_{i-1} - \frac{a_1}{2a_2} > 0$$ $$h_{i-1} + \frac{a_1}{2a_2} < 0$$ $$h_{i-1} + \frac{y'_{i-1} h_{i-1}}{2(\delta_{i-1} - y'_{i-1})} < 0$$ $$\frac{2\delta_{i-1} - y'_{i-1}}{2(\delta_{i-1} - y'_{i-1})} < 0$$ There are two cases. First, if $2\delta_{i-1} - y'_{i-1} > 0$, i.e. $2\delta_{i-1} > y'_{i-1}$. then it must be $\delta_{i-1} - y'_{i-1}< 0$, i.e.$\delta_{i-1} < y'_{i-1}$. Therefore, the first case leads to $2\delta_{i-1} > y'_{i-1} > \delta_{i-1}$. Secondly, if $2\delta_{i-1} - y'_{i-1} < 0$, i.e. $2\delta_{i-1} < y'_{i-1}$, it must be $\delta_{i-1} - y'_{i-1}> 0$, i.e. $\delta_{i-1} > y'_{i-1}$. So the second case leades to $\delta_{i-1} > y'_{i-1}> 2\delta_{i-1}$. The first case is possible only when both $\delta_{i-1}$ and $y'_{i-1}$ are positive and the second case is possible only when both are negative. Therefore, together, the two cases reduce the second condition ($x_m > x_{i}$) to: \begin{equation}\boxed{|2\delta_{i-1}| > |y'_{i-1}| > |\delta_{i-1}|}\end{equation} Together, the two conditions combine into \begin{equation}\boxed{|2\delta_{i-1}| > |y'_{i-1}|}\end{equation} A much faster way to reach the same result is to realize that the the derivatives $y'_{i-1}$ and $y'_{i}$ must be of the same sign if the function is monotone on the $[i-1, i]$ segment, i.e. $$y'_{i-1} \cdot (2\delta_{i-1} - y'_{i-1}) > 0$$ which obviously leads to $|2\delta_{i-1}| > |y'_{i-1}|$.

Therefore, for a Hermite parabola defined by $y_{i-1}$, $y_i$ and $y'_{i-1}$ to be monotone on the interval $(i-1, i)$, the derivative $y'_{i-1}$ must be of the same sign as the linear slope $\delta_{i-1}$ and smaller in magnitude than $2\delta_{i-1}$.

Convexity

For the function $f$ to be convex on $(i-1, i)$ (if parabola is convex on a segment, it's convex everywhere) the condition is $f''(x) > 0$. In the case of our parabola: $$f''(x) = 2a_2 > 0$$. $$\frac{y_{i} - y_{i-1} - y'_{i-1} h_{i-1}}{h_{i-1}^2} > 0$$ or $$y_{i} - y_{i-1} - y'_{i-1} h_{i-1} > 0$$ \begin{equation}\delta_{i-1} > y'_{i-1}\end{equation} This result is obvious $\delta_{i-1} = y'_{i-1}$ is the straight line going through the end-points of the segment. For the parabola to be concave, it must hold $f''(x) < 0$, i.e. \begin{equation}\delta_{i-1} < y'_{i-1}\end{equation}