3
$\begingroup$

There is a well-known theorem that states that on a closed interval $[a,b]$ any continuous function is the limit of a uniformly convergent sequence of polynomials.

Proofs for this theorem usually resort to Bernstein polynomials.

What about if we try with Lagrange polynomials ?

WLOG we may assume $[a,b]=[0,1]$

For a given $n \in \mathbb N$, let $x_1,...,x_n \in [0,1]$ be arbitrary and consider $$L_n(x)=\sum_{k=1}^n f(x_k)\prod_{i=1,i\neq k}\frac{x-x_i}{x_k-x_i}$$ which is known as the interpolating Lagrange polynomial for points $\{(x_1,f(x_1)),...,(x_n,f(x_n)) \}$.

  • Does the sequence of polynomials $(L_n)$ converge uniformly to $f$ ?

  • If not, does choosing points smartly instead of randomly leads to uniform convergence ?


$\endgroup$
  • $\begingroup$ Note that $x_i$ cannot be arbitrary. For example if for each $n$ you pick your $x_i$ to reside in $[0,1/2]$ then you're screwed on $[1/2,1]$. You could try for example to pick your $x_i$ in a dyadic fashion, by using intervals of the form $[\frac{i}{2^n},\frac{i+1}{2^n}]$. $\endgroup$ – Alex R. Apr 15 '14 at 17:51
  • $\begingroup$ @AlexR. I don't know about that. Is seems reasonable to consider $x_i=\frac{i}{n}$. I'm rather concerned about how Lagrange polynomials behave in between interpolation points, since the more points, the more degree, the more power ! $\endgroup$ – Gabriel Romon Apr 15 '14 at 17:55
  • $\begingroup$ My impression was that Lagrange polynomials behaved worse as the degree increased. From Wolfram: "When constructing interpolating polynomials, there is a tradeoff between having a better fit and having a smooth well-behaved fitting function. The more data points that are used in the interpolation, the higher the degree of the resulting polynomial, and therefore the greater oscillation it will exhibit between the data points. Therefore, a high-degree interpolation may be a poor predictor of the function between points, although the accuracy at the data points will be 'perfect.'" $\endgroup$ – Andrew Odesky Apr 15 '14 at 18:07
  • $\begingroup$ Maybe you should try plotting some and seeing what happens. $\endgroup$ – Andrew Odesky Apr 15 '14 at 18:08
  • $\begingroup$ @ntropy This is very interesting ! $\endgroup$ – Gabriel Romon Apr 15 '14 at 18:09
3
$\begingroup$

It depends on the function $f$ and I'll assume that the interpolation points are distinct. The closest result I know is the following:

Theorem: If $f:[0,1]\rightarrow\mathbb{C}$ is analytic and analytically continuable to a function that is analytic in a region containing the closed "stadium" of radius $1$ (consisting of all the points in the complex-plane that are at a distance $\leq1$ from $[0,1]$). Then, $L_n$ converges uniformly to $f$ as $n\rightarrow \infty$. The convergence is also geometrically fast.

(The proof uses the Hermite integral formula for $f - L_n$.) The result can be found on page 82 of the book Approximation Theory and Approximation Practice (ATAP) by L. N. Trefethen.

In particular, no assumption on the distribution of the interpolation points is made (only that they are distinct). They can all be on $[0,1/2]$ if you wish.

For functions that do not satisfy the above Theorem then I am not sure what can be said about the convergence of $L_n$ for general interpolation points.

For specific interpolation points, lots is known. For example:

  1. Chebyshev points: If $f$ is Lipschitz continuous, then $L_n$ converges to $f$ uniformly (also in ATAP). I think $f$ is Holder continuous with exponent $>0$ will also do.

  2. Leja points: If $f$ is analytic on $[0,1]$, then $L_n$ converges uniformly to $f$.

  3. Equally-spaced points: Runge function is an example of an analytic function where the equally-spaced interpolants diverge from $f$ as $n\rightarrow\infty$.

$\endgroup$
  • $\begingroup$ Thanks for your helpful answer. Can you give an example of a real function that is "analytic and analytically continuable to a function that is analytic in a region containing the closed "stadium" of radius 1" ? $\endgroup$ – Gabriel Romon Apr 15 '14 at 18:15
  • $\begingroup$ Any holomorphic function such as $e^x$ and $\cos(x)$ (they are analytic in the whole complex-plane). Also meromorphic functions such as $1/(10+x)$ and $1/(100+x^2)$, where the poles are outside of the stadium. $\endgroup$ – alext87 Apr 15 '14 at 18:19
0
$\begingroup$

Edit (rewritten):

If you assume $f$ is a smooth function, then one can show (see for example Theorem 4.3 here) that through Taylor series bounds:

$$f(x)=L_N(x)+e_N(x),$$

where,

$$e_N(x)=\frac{(x-x_1)(x-x_2)\cdots (x-x_N)f^{(N+1)}(c)}{(N+1)!}$$

for some fixed $c\in [0,1]$. So your error is bounded by $f^{(N+1)}(c)/(N+1)!$.

$\endgroup$
  • $\begingroup$ But the module of continuity of $L_n$ is (generally) unrelated to that of $f$. $\endgroup$ – Daniel Fischer Apr 15 '14 at 18:04
  • $\begingroup$ @DanielFischer: that's true but, it's also uniformly continuous right? So can't we pick the smaller module? $\endgroup$ – Alex R. Apr 15 '14 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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