2
$\begingroup$

Question: Given $f\in C^2 [a,b]$, and $s$ its "natural cubic spline" interpolant on some grid/knots $a= t_0 < t_1<t_2 < \ldots < t_n = b$, is there a bound on the number of extremum points of $s$? This bound may depend on $n$ and/or the number of local extremum points of $f$. If not, are there stronger conditions by which this is true?

An easy condition on $f$ — If $f\in C^4$, then $|f'-s'|<C h^3$, where $h=\max\limits_{j=1,\ldots n} |t_j - t_{j-1}|$. So, if $|f'|>\alpha >0$ on $[a,b]$, then for sufficiently small $h$ we have that $|s'|>\frac{\alpha}{2} > 0$. So, to sharpen the original question: Can anything be said about such situations where $f'=0$ on finitely many points in $[a,b]$?

Intuition: The natural cubic spline minimizes the curvature $\|s''\|_2$, and so it seems that the arc-length of the graph of $s$ is small. Therefore, it might imply that $s$ doesn't oscillate "too much", i.e., no more than the function $f$ it interpolates. However, I could not find or prove anything of that sort myself, and a counter-example may as well exist.

$\endgroup$

2 Answers 2

3
$\begingroup$

Can we use the number of local extremum points of $f$ to bound the number of local extremum points of $s$?

No. See https://en.m.wikipedia.org/wiki/Monotone_cubic_interpolation for a counterexample and for examples of alternative conditions that give the kind of cubic interpolation you seek.

$\endgroup$
5
  • 1
    $\begingroup$ Thanks, I'll look into it. Does that mean we cannot even bound the number of extremum points? $\endgroup$
    – Amir Sagiv
    Commented Oct 15, 2017 at 6:42
  • $\begingroup$ Ah -- I took your question to mean "is the number of local extrema of the spline interpolant less than or equal to the number of local extrema of $f$". If you mean something different, I think you should edit the question to be more specific. $\endgroup$ Commented Oct 15, 2017 at 12:57
  • $\begingroup$ Sure. Does that last edit help? $\endgroup$
    – Amir Sagiv
    Commented Oct 15, 2017 at 17:52
  • $\begingroup$ does the last edit help? @David Ketcheson $\endgroup$
    – Amir Sagiv
    Commented Nov 17, 2017 at 15:22
  • $\begingroup$ Well, the wikipedia example shows that $s$ can oscillate more than $f$ in at least one rather important sense. $\endgroup$ Commented Nov 19, 2017 at 3:53
1
$\begingroup$

The number of local extremum points of $s(t)$ can be bound as a function of $n$ (where $n+1$ is the number of interpolation points). The final bound, which I will develop using B-Splines, is $n-1$. I'll also show that his bound is tight.

First, note that there is a naive bound of $2n$ extremum points since each segment of the spline between the knots is just a cubic polynomial which has at most two extremum points. However, as I said above, we can do better using the theory of B-Splines.

In the reference in the question each $[t_i, t_{i+1}]$ interval is of unit length, so we will represent $s(t)$ using the uniform B-Spline basis functions where $\{t_i\}$ are equally spaced knots placed a unit length apart. For simplicity (and without loss of generality) $t_i=i$, however the arguments below can probably be extended to non-uniform knot vectors as well.

The function representation is now (see for example Piegl, Les; Tiller, Wayne, The $NURBS$ books., Berlin: Springer. xiv, 646 p. (1997). ZBL0868.68106. or here) $$ s(t) = \sum_{k=0}^{n+2} P_k N_{k,3}(t) $$ Where $N_{k,3}(t)$ are the cubic B-Spline basis functions derived from the knot vector and $P_k$ are the control points (in this case control coefficients since they are scalars). The ordered control points compose the control polygon, which has geometric properties that we will be using. Note that the number of control points in the B-Spline representation is $n+3$.

(I'll be using the terms control points and control polygon a bit freely here. They can be formulated more formally using a parametric B-Spline curve $(x(t)=t, y(t)=s(t))$ of the graph of the function but I omit the details).

Solving the B-Spline interpolation problem is standard (see for example, Chapter 9 of The NURBS Book, or here). In order to compute the control points you evaluates the basis functions at the knots for $n+1$ linear constraints and the natural end conditions $s''(t_0)=s''(t_n)=0$ give you the additional two constraints.

Once we have the B-Spline representation, we have $n+3$ coefficients $P_k$ and we can use their geometric properties to give our bound. The first property we use is the simple form of the B-Spline derivative. The derivative of a cubic B-Spline function is itself a B-Spline function (of degree 2) and has a nice representation. For our uniform knots case the derivative function is just $$ s'(t) = \sum_{k=0}^{n+1} (P_{k+1}-P_k) N_{k,2}(t). $$

The second property we use is the variation diminishing property of B-Splines, which we apply to the derivative function. This means that the number of intersection points of any line with the function graph is smaller or equal to the number of intersections of this line with the control polygon. Applying it to our context means that the $x$-axis does not intersect the graph of the derivative function more than $n+1$ times (since there are $n+1$ segments in a control polygon with $n+2$ control points). Therefore, we have a bound of $n+1$ on the zero-crossing of the derivative. Thus, there cannot be more than $n+1$ extremum points to the original function $s(t)$.

For the natural spline, we can in fact do slightly better. The natural end-conditions imply that $P_1$ lies on the line between $P_0$ and $P_2$ (and similarly for the last end points). From this follows that $P_1-P_0$ and $P_2-P_1$, the first control points of the derivative, have the same sign (and similarly for the last points). Therefore, the first (and last) two segments of the derivative control polygon can only contribute at most one zero-crossing and therefore the maximal number of zero crossings is $n-1$. So (at last), our final bound is $n-1$ extremum points.

This bound is tight; for any $n$ we can construct the following $n+1$ configuration of points for which the natural spline will have $n-1$ extremum points.

An alternating $(n+1)$-sized point sequence of $\pm 1$ will have $n-1$ extremum points (see the figure for an example with $n=10$). This can be proved by explicitly solving the interpolation equations but a simpler proof comes from the mean value theorem. By the mean value theorem every alternating segment $(t_i,-1), (t_{i+1}, 1)$ has a positive derivative of value $s'(c_i)=2=\frac{1-(-1)}{t_{i+1}-t_i}$, and its consecutive segment will have a negative derivative of value $s'(c_{i+1})=-2=\frac{(-1)-1}{t_{i+2}-t_{i+1}}$. Thus, by the continuity of the derivative we have a zero derivative in the interval $(c_0,c_1)$ and another one in $(c_1,c_2)$ and so on.. until the last interval $(c_{n-2},c_{n-1})$, for a total of $n-1$ zero derivatives.

Lower Bound: A configuration of $n=11$ points that has $n-1=9$ extremum points on $s(t)$

Conclusion: From the theory of B-Splines and their geometric properties, it follows that the maximal number of extremum points of $s(t)$ is $n-1$ and this bound is tight since for any $n$ we can construct a configuration of interpolation points for which this bound is attained.

$\endgroup$
8
  • $\begingroup$ Thank you, this is a very eye-opening question. How do we relate it to an underlying function $f$? If our samples are the values of $f$, what properties does $f$ has to have so that the number of local extremum will be $\leq k$, for some $k\leq n-1$? $\endgroup$
    – Amir Sagiv
    Commented Apr 23, 2018 at 19:58
  • $\begingroup$ Also, at the paragraph of the $\pm 1$ example, I think you have a typo with the $(t_i ,-1)$. $\endgroup$
    – Amir Sagiv
    Commented Apr 23, 2018 at 19:59
  • $\begingroup$ As other answers have shown, even for the simple case of monoticity, a monotone $f$ does not guarantee a monotone $s$. The opposite is also true of course - you can have $f$ full of extremum points with $s$ having no extremum points at all (e.g., sampling $sin(\pi t)$ at integer values will result in $s(t)$ being a line). So I don't really have yet any good ideas on how to relate it to $f$. $\endgroup$ Commented Apr 24, 2018 at 14:41
  • 1
    $\begingroup$ Following your comment I had the following idea: If there is a finite number of points for which $f'=0$, then there is a minimal distance $\delta$ between two such zeros. So, for a sufficiently small $h$ (less than that $\delta$), any $h$-interval contains at most one zero-derivative point. Outside these intervals you will have $s'$ meet your condition so $s$ will be monotone there. For the intervals containing the zero-derivatives, if they contain an extremum point then their derivative will have opposite signs at the end points of the interval. $\endgroup$ Commented May 10, 2018 at 6:52
  • 1
    $\begingroup$ When the derivative at end points have opposite signs, the cubic polynomial inside this interval has only one extremum point (this can be shown e.g., from the fact that its derivative is a parabola). The problem is with inflection points - for inflection points you can either have zero or two extremum points for $s$ in the interval, and I don't see an easy way to verify the former. So to conclude, for a sufficiently small $h$ you may be able to bound the number of extremum points of $s$ by the number of extremum points of $f$ + twice the number of inflection points. Is that a helpful bound? $\endgroup$ Commented May 10, 2018 at 7:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .