# Interpolation by a function whose second derivative is bounded

I don't know if this is an easy question for specialists in the field. Consider the following interpolation problem : let $\varepsilon >0$, $X$ be a finite set of real numbers and $g$ be a real-valued function on $X$. The goal is to find a function $f$, defined on an interval containing $X$, that coincides with $g$ on $X$, and admits a continuous second derivative $f''$ bounded by $\varepsilon$ : $|f''|< \varepsilon$.

A necessary condition is that, for any $x< y < z$ in $X$,
$(*) |\frac{(y-x)g(z)-(z-x)g(y)+(z-y)g(x)}{(z-x)(z-y)(y-x)}| < \frac{\varepsilon}{2}$.

Is that condition also sufficient ? If $X$ has just three elements then (*) says precisely that the Lagrange interpolating polynomial $f$ satisfies $|f''|< \varepsilon$, so that equivalence holds in this case.

-

It isn't sufficient. Suppose that the elements of $X$ are $$x_1 < x_2 < \cdots < x_n,$$ and suppose for simplicity that $\epsilon = 1$. Then the values $f(x_k)$ carry the same information as the integrals $$\langle p, f'' \rangle = \int_{x_1}^{x_n} p(x) f''(x) dx,$$ where $p(x)$ is a continuous, piecewise-linear function with $p(x_1) = p(x_n) = 0$. You can convert between such an integral and linear combinations of values of $f(x)$ by integrating by parts twice. For any such test function $p$, the inequality $$|\langle p, f'' \rangle| \le \int_{x_1}^{x_n} |p(x)| dx \qquad \qquad$$ holds. Moreover, many of these inequalities are logically independent. More precisely, the extremal choices of $p(x)$ are those for which $p(x_k)$ alternate in sign for $i \le k \le j$, and $p(x_k) = 0$ when $k < i$ or $k > j$. The idea to show that such as $p$ is extremal is to make a dual choice of $f''$ that switches between $1$ and $-1$ when $p$ crosses the $x$ axis. (I apologize for skipping some of the logic in the extremality calculation, but I think that this is correct.) The resulting set of values for $f(\vec{x})$ is not a polytope, but a certain convex region with both flat and curved boundary.
For example, consider your statistic, $$f_k = \frac{(x_{k+1}-x_k)f(x_{k+1})-(x_{k+1}-x_{k-1})f(x_k)+(x_k-x_{k+1})f(x_{k-1})}{(x_{k+1}-x_k)(x_{k+1}-x_{k-1})(x_k-x_{k-1})},$$ for consecutive triples of points, and suppose that $n=4$. Then the pair $(f_2,f_3)$ must lie inside the square $[-\frac12,\frac12]^2$; you identified two other pairs of inequalities, but they do not clip the square further. What actually happens is that two of the corners of the square are rounded by parabolas. The supporting lines of the parabolas come from the test function $p$ that is a piecewise-linear interpolation of $(0,-1,a,0)$ with $a > 0$.
The question asks for a continuous $f''$ and, as edited, strict inequalities. However, you might as well take the closure in the relevant topology ($f'' \in L^\infty$) and use non-strict inequalities. This doesn't really change the problem, and in my view clarifies it. – Greg Kuperberg Dec 16 '09 at 8:55
Your comment is absolutely right Greg. When I have time I'll check your answer in more detail, but could you please just what you mean by "interpolation of (0,-1,a,0)" : do you mean an interpolation system of the form $f(x_1)=0,f(x_2)=-1,f(x_3)=a,f(x_4)=0$ where $x_1,x_2,x_3,x_4$ may be arbitrary ? – Ewan Delanoy Dec 16 '09 at 11:17
I meant $(p(x_1),p(x_2),p(x_3),p(x_4)) = (0,-1,a,0)$, and $p$ is the piecewise-linear function connecting these values. For each $a > 0$, my third equation then gives you a different inequality for the four values $(f(x_1),f(x_2),f(x_3),f(x_4))$. – Greg Kuperberg Dec 16 '09 at 15:22
How do you know that the intersection of the halfplanes defined by (0,-1,a,0) eventually yields a parabola ? What degree 2 inequality in $f(x_1),f(x_2),f(x_3),f(x_4)$ would express it? – Ewan Delanoy Dec 16 '09 at 18:22