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}
No comments:
Post a Comment