# Do interpolation nodes have to be dense?

Let $f(x) = \exp(x)$ and $(\xi_i)_{i=0}^\infty, \, \xi_i \in (0,1)$ be a sequence of points from the unit interval.

For $n \in \mathbb{N}$ let $P_n$ be a polynomial of degree $n$ that interpolates $f$ at $\xi_0, \ldots, \xi_n$, i.e. $$f(\xi_i)-P_n(\xi_i) = 0, \text{ for all } i=0,\ldots,n,$$

Question: Does uniform convergence of the interpolation process on $(0,1)$, i.e. $$\lim_{n \rightarrow \infty} \|f - P_n\|_\infty =0$$ imply that the sequence $(\xi_i)_{i=0}^\infty$ is dense in $(0,1)$? My intuition says it is but I failed to proof it.

Thank you!

Unfortunately not. Just look at the (confluent) limit case when all $\xi_i=0$: in this case $P_n$ is just the $n$-th Taylor polynomial for $f$. which clearly converges to $f$ not only on $(0,1)$, but on the whole complex plane, but $\xi_i$ are all at the origin.

A less extreme argument is: if we consider the sequence $q_n$ of best polynomial approximants to $f$ on a subinterval $(\alpha, \beta)$ of $(0,1)$, then (i) $q_n$ actually interpolate $f$ on $(\alpha, \beta)$ (but not outside), and (ii) $(f-q_n) \to 0$ in the largest ellipse with foci at $\alpha$ and $\beta$ where $f$ has an analytic continuation. Since $f$ is entire, convergence holds on the whole $\mathbb{C}$, so on $(0,1)$.

EDIT after the comments of Dirk and Qiaochu Yuan:

I don't think that the fact that nodes are different or form a sequence makes any difference. Still, what about this argument: the Cauchy formula for the interpolation error at a point $t$ is $$(f-p_n)(t)=\frac{f^{(n+1)}(\theta)}{(n+1)!} \omega_n(t), \quad \omega_n(t)=\prod_{i=1}^{n+1}(t-\xi_i).$$ For $t\in (0,1)$, we have $\|\omega_n\|_\infty\leq 1$, and $f^{(n+1)}(\theta)\leq e$, REGARDLESS the distribution of $\xi_i$'s on $(0,1)$. In particular, they could live on $(0, 1/2)$ only, etc.

• I am not sure how this answers the question. First, the question specifically considers $f=\exp$ and second I am not sure if multiplicity of the interpolation points was allowed by the OP. – Dirk Nov 6 '13 at 22:16
• In the second argument, as far as I know you'll get a priori completely different sets of interpolation nodes at each step rather than adding one node at a time to a growing list of nodes. This affects how easy it is to adapt the first argument to the case where the $\xi_i$ are distinct as well. – Qiaochu Yuan Nov 6 '13 at 22:16
• Interesting, so it seems that $\exp(x)$ being analytic really does make all the difference. If $f$ is allowed to be a smooth bump function then the interpolation error can clearly stay bounded below if the interpolation points stay away from the support of the bump function, and we conclude that the derivatives somewhere have to grow about as fast as a factorial, as expected since smooth bump functions cannot be analytic. Nice! – Qiaochu Yuan Nov 6 '13 at 23:07
• The truth is that for any decent interpolation scheme you can think of there exists a domain containing the interval such that analyticity in this domain is almost equivalent to the convergence of the approximants to the function. Unfortunately, the comment field is too small to say much more. – fedja Nov 7 '13 at 1:15
• This answer relies on interpolating derivatives of the function. It is not clear that the OP is interested in that. The question seems to deal only with interpolation of function values. – David Ketcheson Nov 26 '13 at 7:02