Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
All of the answers have been very helpful, thank you to everyone! –  AndrewG Jan 5 '13 at 19:58
add comment

4 Answers 4

up vote 7 down vote accepted

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.

share|improve this answer
add comment

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.

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

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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