Approximating continuous functions with polynomials

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.)