Approximating continuous functions with polynomials 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.
 A: 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.
A: 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.)
A: 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.
A: 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.
