1
$\begingroup$

Some time ago, I asked about inite interpolation by a nondecreasing polynomial here at 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$?

$\endgroup$
4
  • $\begingroup$ The most obvious answer is the space of all continuous functions which are affine on each interval of the subdivision (or other similar variations on these lines). Is this what you want? $\endgroup$ Nov 16, 2010 at 17:22
  • $\begingroup$ Sorry, I misstated my problem. I've corrected it just now $\endgroup$ Nov 16, 2010 at 17:29
  • $\begingroup$ A modification of Pietro Majer's answer still works, right? You just need to smooth everything out in a neighborhood of each x_i. $\endgroup$ Nov 16, 2010 at 17:36
  • $\begingroup$ @ Qiaochu : I think not. The more "smoothings" you need to do, the bigger V becomes (in terms of dimensionality). Subproblem : what is the minimal dimensionality of V, if we replace indefinitely derivable functions by functions derivable k times? $\endgroup$ Nov 16, 2010 at 18:22

2 Answers 2

2
$\begingroup$

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.$

$\endgroup$
2
  • $\begingroup$ I don't understand why the values at the nodes $x_i$ are preserved. $\endgroup$ Nov 16, 2010 at 20:50
  • $\begingroup$ For any $u\in V_0$ we have $(u*\phi)(x_i)=u(x_i)$ just because $\phi$ is symmetric with support in $[-\epsilon,\epsilon]$ and $u$ is affine on $[x_i-\epsilon,x_i+\epsilon]$. $\endgroup$ Nov 16, 2010 at 22:17
1
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Thanks Aaron. Your solution is more "pedestrian" indeed, but it helped me understand better Qiaochu's and Pietro's "magical" solution. $\endgroup$ Nov 17, 2010 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.