It is well known that for any lipschitz function $f:[0,1]\rightarrow [0,1]$, we can approximate it by $\sum_{i=1}^n f(i/n) {n\choose i} x^i (1-x)^{n-i}$, and the $L_\infty$ error is $O(1/\sqrt{n})$. However, the best degree $n$ polynomial approximation could achieve an additive error of $O(1/n)$. Since $\{{n\choose i} x^i (1-x)^{n-i}\}_{i=0,...,n}$ is a basis of all polynomials of degree at most $n$, so it is possible to approximate $f$ with error $O(1/n)$ using $\sum_{i=1}^n c_i {n\choose i} x^i (1-x)^{n-i}$ for some $c_i$. However, the $c_i$s might be very large (exponential in $n$). Is there any result stating that whether we can achieve an error $O(1/n)$ while keeping $c_i$s small (hopefully polynomial in $n$) (or anything related to both the convergence and the coefficients of the approximation)? Thanks.
1 Answer
It is fairly classical though I cannot guarantee that the question has ever been formally considered in this form. The problem is that if $z=x+iy$ where $x\approx \frac 12$ and $y\le 2n^{-1/2}$, then $|z^p(1-z)^{n-p}|\le Cx^p(1-x)^{n-p}$, so if $|c_k|\le A$, then the corresponding Bernstein polynomial is bounded by $CA$ in the disk $D$ centered at $1/2$ of radius $2n^{-1/2}$. Now, let $E\in(0,n^{-1/2})$. Consider the seesaw function that is $2E$ at $1/2$ and goes up and down from $2E$ to $-2E$ and back. If we can approximate it with with the error $E$ keeping $|c_k|<A$, then the approximating polynomial $P$ has at least $n^{-1/2}(4E)^{-1}$ zeroes in $\frac 12D$ and is bounded by $CA$ in $D$, whence, by Jensen, we must have $E\le |P(1/2)|\le CAe^{-cn^{-1/2}E^{-1}}$, so $$ A\ge cEe^{cn^{-1/2}E^{-1}}\, $$ which for $E\approx 1/n$ gives about $e^{\sqrt n}$.
I hope this is discouraging enough, so I'll stop here for now.
