Question

Some time ago, I asked about inite interpolation by a nondecreasing polynomial here at http://mathoverflow.net/questions/16673/finite-interpolation-by-a-nondecreasing-polynomial. This turned out to be an already solved problem; it also turned out that the degree of the solution could not be bounded in terms of the number of interpolation points alone.

My new question is: if we are willing to replace polynomials by another vector space V of indefinitely differentiable functions, then we can we achieve something better than with polynomials, in the sense that V is finite-dimensional?

Formally, fix $x_1 \lt x_2 \lt \ldots \lt x_n$ and let $y_1 \leq y_2\leq \ldots \leq y_n$ vary. We consider the system $(S)$ made of the $n$ interpolation constraints $f(x_i)=y_i$ for $i$ between $1$ and $n$. Is there a finite-dimensional subspace $V$ of ${\cal C}^{\infty}([x_1,x_n],{\mathbb R})$ such that for any $y_1 \leq y_2\leq \ldots \leq y_n$, there is a solution to $(S)$ which is nondecreasing and also in $V$?

Answer 1

This is to expand Qiaochu Yuan's comment. For $1\le i < n$ let $b_i:=(x_{i+1}+x_i)/2$ be the mid-point of the $i$-th interval, and let $0 < \epsilon \leq \min_{1\le i < n} (x_{i+1}+x_i)/2\ .$ Start with the linear space $V_0$ of all continuous functions on $\mathbb{R}$ that are affine on each component interval of $\mathbb{R}\setminus \{b _i\ : \ 1\leq i < n \}$ and take $V$ to be the image of $V_0$ via the (linear) convolution operator $u\mapsto u*\phi$, with a symmetric kernel $\phi\ge0$, $C^\infty_c(\ ]-\epsilon,+\epsilon[\ )\ $ and $\int_\mathbb{R} \phi = 1 .$ The convolution with $\phi$ preserve monotonicity and the values at the nodes $x_i$, so that the interpolation function in $V$ is just the mollification of the interpolation function on $V_0.$

Answer 2

From a more pedestrian point of view: If what you want is possible at all (and it is) then in particular there is some non-decresing $f_3 \in {\cal C}^{\infty}([x_1,x_n],{\mathbb R})$ with $f_3(x_1)=f_3(x_2)=0$ and$f_3(x_3)=f_3(x_4)=\cdots=f_3(x_n)=1$. i.e. a ${\cal C}^{\infty}$ function on $\mathbb R$ which is $0$ up to $x_2$ then increases to $1$ and then is $1$ from $x_3$ on. If so, then one can have $n$ similar functions $f_k$ with $f_k(x_j)=$ $0$ or $1$ according as $j < k$ or $k \le j$. They span a degree $n$ space $V$ and the non-negative linear combinations of the $f_k$ do what you want.

It remains only to show how to build the $f_k$. Here's one way, maybe not the most elegant: First consider ${\cal C}^{\infty}$ function $g_3$ which is $0$ except on the open interval $(x_2,x_3)$ where it is $$e^{-1/(x-x_2)^2}e^{-1/(x-x_3)^2}$$ Then let $f_3(x)=c\int_{-\infty}^{x}g_3(t)\ dt$ where the constant $c>0$ is chosen to make $f_3(x)=1$ for $x \ge x_3$.