Let $f:[0,1] \to \mathbb{R}$ be continuous. The Stone–Weierstrass theorem tells us that there is a sequence $p_n$ of polynomials defined on $[0,1]$ such that $$\lim_{n \to +\infty} ||p_n - f||_{\infty} = 0$$

A consequence of this theorem is that

$$\lim_{n \to +\infty} \inf \{||p-f||_{\infty} : p \ \text{is a polynomial of degree} \leq n\} =0$$

This is the quantity I'm interested in. Namely, $$\epsilon(n) \stackrel{\rm def}{=}\inf \{||p-f||_{\infty} : p \ \text{is a polynomial of degree} \leq n\}$$

This roughly tells us the following: if we want to uniformly approximate $f$ by a polynomial of degree $\leq n$, then we should expect an error of at least $\epsilon(n)$.

Is there an explicit upper bound on $\epsilon(n)$ (e.g., something like $\epsilon(n) \leq \frac{15}{\log n})$? Is there an asymptotic bound on $\epsilon(n)$ (e.g., $\epsilon(n) = O(n^{-2})$?

The bounds should be as tight as possible.

  • $\begingroup$ This kind of questions is core for the branch of mathematics called "approximation theory". This site is one of its headquarters. (Look also here). Your question is surely well-known to them. $\endgroup$ – Giuseppe Negro May 25 '17 at 9:03
  • $\begingroup$ Grazie per i miravigliosi riferimenti ai due siti Internet, caro @Giuseppe! $\endgroup$ – Georges Elencwajg May 25 '17 at 10:23
  • $\begingroup$ @GeorgesElencwajg: Prego, mi fa piacere essere stato utile, caro Georges. $\endgroup$ – Giuseppe Negro May 25 '17 at 11:05
  • $\begingroup$ This is a question of similar type: math.stackexchange.com/questions/271013/… $\endgroup$ – ploosu2 May 25 '17 at 11:09
  • $\begingroup$ In a paper that was linked in the other question's answer (m-hikari.com/imf-password2008/29-32-2008/…) the following (Theorem 1.2) is achieved: The Berstein polynomials of $f$ give the bound $\epsilon(n) = O(\omega(1/\sqrt n))$, where $\omega$ is the modulus of $f$, (see the paper how it's defined). I don't think you can get rid of the dependence on $f$, since $f$ can be rapidly oscillating and you need to have bigger $n$ depending on $f$. $\endgroup$ – ploosu2 May 25 '17 at 11:20

There's no reasonable answer without restricting the class of functions $f$ you're considering. The error may be $O(r^{-n})$ if $f$ has an analytic continuation to an ellipse with foci $0, 1$ in the complex plain, it may be just $O(1/n)$ if you only know it's differentiable (with bounded derivative) on $[0,1]$, or it can be still worse, if $f$ is just continuous, but not smooth.

  • $\begingroup$ Can you please give a reference/name the theorem that gives the error rate $O(r^{-n})$ for the first class of functions presented in your answer? $\endgroup$ – Lyuka Nov 13 '20 at 14:15

First of all, the quantity $\epsilon(n)$ is given by a certain polinomial $\tilde p$, so that $$\epsilon(n)=||f-\tilde p||_{\infty}$$ A bound of the error is given by Jackson's theorems. If $f$ is only continuous you can tell that $$ \epsilon(n) \le M \omega(f, \frac{b-a}{n}) $$ where the modulus of continuity is defined as $$ \omega(f,\delta) := \sup \{|f(x)-f(y)| : x,y \in [a,b],|x-y|\le \delta \}$$ and $M$ is a real constant (in your case the domain is $[a,b]=[0,1] $). If $f$ is increasingly regual, like lipschitz continuous, $C^p$, $C^{\infty}$ analytic and analytic on all the complex plane, the bounds become more severe and the approximation is much better.


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.