Given $\epsilon \gt 0$ and $f \in C^{0}[0,1]$, Weierstrass says that I can find at least one (how many? probably a lot?) polynomial $P$ which approximates f uniformly: $$\sup_{x \in [0,1]} |f(x) - P(x)| \lt \epsilon$$

This means that, under the sup norm $||.||_{\infty}$, the polynomials are dense in $C^{0}[0,1]$. So, in analogy to approximating irrationals with the rationals, I would like to know:

  • What can we say about the order of $P$? Or, turning this around, given that $P$ is of order $n$, how small can $\epsilon$ get?

I'm betting this should depend in some way on the properties of $f$: the intuition is that smoother functions should be somehow "better" approximated by lower-order polynomials, and less-well-behaved functions should require higher-order polynomials. But I am not sure how to formalize this.

This is probably all well-understood, but I'm not well-read on approximation theory. Any guidance would be wonderful.

  • $\begingroup$ All of the answers have been very helpful, thank you to everyone! $\endgroup$ – AndrewG Jan 5 '13 at 19:58

According to Theorem 1.2 of this paper by Sukkrasanti and Lerdkasem, we have the following result (with impressively great generality, I might add):

Let $f: [0,1]^p \rightarrow \mathbb{R}^q$ be bounded. Then there exists $C$ such that $$ \| f - B_n(f) \|_{\infty} \le C \omega(1/\sqrt{n})$$ where $\omega(\delta) := \sup_{\|t_1 - t_2\| \le \delta} \|f(t_1) - f(t_2)\|$ and $B_n(f)$ is the $n$th Bernstein polynomial of $f$.

I do not claim to have read the paper myself. Notice that if $f$ is indeed continuous, then by uniform continuity, as $n \rightarrow \infty$, $\omega(1/\sqrt{n})$ must go to zero. So the convergence rate is related to how rapidly $f$ can vary, as intuition would already suggest.


Define, $B_i^n(x)=\binom{n}{i}x^i(1-x)^{n-i}$, nice fact,

  • Partition of the unity $\sum_{i=0}^{n}B_i^n(x)=1$ this is easy to see:

    See $1= x+(1-x)$ then, $$1=(x+(1-x))^n=\sum_{i=0}^{n}\binom{n}{i}x^i(1-x)^{n-i}=\sum_{i=0}^{n}B_i^n(x).$$

    Without loss of generality suppose $a=0$ and $b=1$. We need of the following estimative:

\begin{eqnarray*} \sum_{i=0}^{n}\left(x-\frac in\right)^{2}B_i^n(x)&=&x^2\sum_{i=0}^{n}B_i^n(x)-2x\sum_{i=0}^{n}\dfrac{i}{n}B_i^n(x)+\sum_{i=0}^{n}\left(\dfrac{i}{n}\right)^2 B_i^n(x)\\&=& x^2-2x^2+\dfrac{1}{n^2}\sum_{i=0}^{n}n(n-1)\dfrac{i^2-i +i}{n(n-1)} B_i^n(x)\\&=& -x^2+ \dfrac{1}{n}\sum_{i=0}^{n}\dfrac{i}{n}B_i^n(x)+\dfrac{n(n-1)}{n^2}\sum_{i=0}^{n}\dfrac{i(i-1)}{n(n-1)}B_i^n(x)\\&=& -x^2+\dfrac{x}{n}+\dfrac{n-1}{n}x^2\\&=& \dfrac{x-x^2}{n}\leqslant\dfrac{1}{4n}. \end{eqnarray*} Now, since $f$ is continuous we have that $f$ is uniformly continuous,because $[0,1]$ is compact. So for each $\epsilon$ exists $\delta>0$ such that for all $x,y\in [0.1]$ with $|x-y|<\delta$ implies $|f(x)-f(y)|<\epsilon$. Since $f$ have yours extreme extreme values in $[0,1]$ then exists a constant $M$ such that $|f(x)|\leqslant M$ for all $x\in[0,1].$

Consider the Berstein polynomial of $f$, $$P_n(x)=\sum_{i=0}^{n}f\left(\dfrac{i}{n}\right)B_i^n(x);$$ since $\displaystyle\sum_{i=0}^{n}B_i^n(x)=1$, we have $f(x)=\displaystyle\sum_{i=0}^{n}f(x)B_i^n(x)$ then,

\begin{eqnarray*} \left|f(x)-P_n(x)\right|&\leqslant& \sum_{i=0}^{n}\left|f(x)-f\left(\dfrac{i}{n}\right)\right|B_i^n(x)\\&=& \sum_{S_1}\left|f(x)-f\left(\dfrac{i}{n}\right)\right|B_i^n(x)+\sum_{S_2}\left|f(x)-f\left(\dfrac{i}{n}\right)\right|B_i^n(x) \end{eqnarray*}

where $S_1=\{0\leqslant i\leqslant n ~;~ |x-\frac{i}{n}|<\delta\}$ and $S_2=\{0\leqslant i\leqslant n~;~ |x-\frac{i}{n}|\geqslant \delta\}.$ analyzing each sum separately $$\sum_{S_1}\left|f(x)-f\left(\dfrac{i}{n}\right)\right|B_i^n(x)\leqslant \sum_{S_1}\epsilon|B_i^n(x)\leqslant \epsilon\sum_{i=0}^{n}B_i(x)=\epsilon$$

\begin{eqnarray*} \sum_{S_2}\left|f(x)-f\left(\dfrac{i}{n}\right)\right|B_i^n(x)&\leqslant& 2M\sum_{S_2}B_i^n(x)\leqslant \sum_{S_2}\dfrac{(x-\frac{i}{n})^2}{\delta^2}B_i^n(x)\\&\leqslant&\dfrac{2M}{\delta^2}\sum_{i=0}^{n}(x-\frac{i}{n})^2 B_i^n(x)\leqslant \dfrac{M}{2\delta^2 n} \end{eqnarray*}

since $\dfrac{M}{2\delta^2 n}<\epsilon$ for $n$ large, we demonstrate the desired.

  • 2
    $\begingroup$ Nice answer. By the way, what does "daí" mean? $\endgroup$ – Antonio Vargas Jan 5 '13 at 16:50
  • 1
    $\begingroup$ @AntonioVargas: I'm sorry, is the habit of writing in portuguese daí=so or then $\endgroup$ – user27456 Jan 5 '13 at 16:58
  • $\begingroup$ @EduardoSiva: Everything looks fine, except that you have not defined $ B_{i} $. I suppose that it denotes a Bernstein polynomial, am I right? $\endgroup$ – Haskell Curry Jan 5 '13 at 17:34
  • $\begingroup$ @HaskellCurry: I'll try to fix it $\endgroup$ – user27456 Jan 5 '13 at 17:43

A near minimax approximation to a continuous function, say, $f:[-1,1]\to\mathbb{R}$, can be obtained with Chebyshev polynomials. You may look up the details in this book chapter, of which theorem 3.10 says that if $p$ is a Chebyshev interpolation polynomial for such continuous $f:[-1,1]\to\mathbb{R}$ at $n+1$ points, then $\|f-p\|\sim C\,\omega(\frac1n)\log n$ as $n\to\infty$, where the norm is the maximum norm, $\omega(\cdot)$ denotes the modulus of continuity and $C$ is a constant.


Since you tagged your question by "reference-request" I will give only them (instead of copying a lot). Jackson inequality ("direct theorem"), and Bernstein theorem ("converse theorem"). See also the references therein. (My humble opinion they are good quality books. Typing into Google these keywords you will obtain a lot of links, including many free downloadable lecture notes, maybe books.)


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.