Uniform approximation of $x^n$ by a degree $d$ polynomial: estimating the error

The answer to this question should be well known, but it's a hard question to search for online.

Suppose we want to approximate the function $x^n$ by a polynomial of degree $d$ in the $L_\infty$ norm on $[-1,1]$. What is a good estimate of the error of the best approximator, in terms of $n$ and $d$?

I know this question was solved exactly by Chebyshev for $d = n-1$ (the error is $2^{-d}$ I think). The range of interest for me is $\sqrt{n} \leq d \leq n$ and I don't mind log factors in the estimate. Thus I would be happy to have an estimate for the error of the Chebyshev expansion truncated to degree $d$.

(A bonus would be an answer to the same question for $(1-x^2)^d$.)

Thanks!

-
The best approximation satisfies $f(-x) = (-1)^n f(x)$, so it is enough to approximate $t^{n/2}$ on $[0,1]$ by a linear combination of the first few integral or half-integral powers of $t=x^2$. The $L^2(0,1)$ norm of the distance from $t^d$ to the span of $t^{d_i}$ can be computed exactly for any $d$ and $d_i$ for which the integrals converge (that's the key to one proof of Müntz's theorem); while that's not the $L^\infty$ norm you ask for, it should give some sense of the size of the answer. Likewise for $(1-x^2)^d = (1-t)^d$. –  Noam D. Elkies Jul 15 '11 at 15:27
Hmm. Unfortunately this doesn't quite help me... The thing is, it's well known that with $d = O(\sqrt{n})$ one can get an $L^\infty$ error of $.01$ on $[0, 1-1/n] \cup \{1\}$. What I'm really interested in is whether you can also get such small $L^\infty$ error on $[1-1/n, 1]$ too, while keeping $d$ comparable to $\sqrt{n}$. Unfortunately, the narrowness of the interval $[1-1/n,1]$ means that looking at $L^2$ error won't tell you anything. :( –  Ryan O'Donnell Jul 16 '11 at 0:28
I should mention that I actually only care about the interval $[0,1]$; I just wrote $[-1,1]$ in the question because it seems to be more standard to use this interval in approximation theory. –  Ryan O'Donnell Jul 16 '11 at 0:29
Sure. Probably I shouldn't have said 'well-known'; it's somewhat well-known in theoretical computer science, let's say :) In Example 3.11 of this paper of Nisan and Szegedy -- springerlink.com/content/p1711275700w5264 -- they slightly manipulate the degree-$2\sqrt{n}$ Chebyshev polynomial to get a polynomial $p$ satisfying $|p(x) - 0| \leq 1/3$ for all $x \in \{0, 1/n, 2/n, \dots, 1-1/n\}$ and $|p(x) - 1| \leq 1/3$ for $x = 1$. It's also known and not too hard that with a little more manipulation you can replace the $1/3$ by $\epsilon$ at the expense of multiplying the degree by –  Ryan O'Donnell Jul 16 '11 at 13:02
the small factor $O(\log(1/\epsilon))$. Further, I'm pretty sure that if you're a little careful you can ensure $p(1) = 1$ and $|p(x)| \leq \epsilon$ for all $x \in [0, 1-1/n]$; this is with a polynomial of degree $O(\sqrt{n} \log(1/\epsilon))$. My question is, what if you want $\epsilon$ error (in $L^\infty$) even for this last interval $[1-1/n, 1]$? Can you get it with degree $C_\epsilon \sqrt{n}$? Or does one require degree proportional to $n$ for $\epsilon = .01$? Or is the tradeoff something in between? thanks for your help! –  Ryan O'Donnell Jul 16 '11 at 13:05

For large $n$ and fixed $\epsilon > 0$ there is a polynomial of degree $d = O_\epsilon(\sqrt{n})$ that uniformly approximates $x^n$ to within $\epsilon$ on all of $[-1,+1]$. The polynomial can be taken to be the truncated Čebyšev expansion of $x^n$, as the original proposer (OP) suggested. As $\epsilon \rightarrow 0$, the $O_\epsilon$ constant grows only as $(\log(\epsilon^{-1}))^{1/2}$; for example, $d = 2.576 \sqrt{n}$ suffices to get $\epsilon = .01$ if I computed correctly.

The OP wrote that truncating the Čebyšev expansion will give the correct $L^\infty$ distance to within a log factor. I don't see a priori why this should be, but fortunately the coefficients of the expansion of $x^n$ in Čebyšev polynomials turn out to be elementary and familiar enough to work with explicitly.

It will be convenient to define $T_k(x)$ for all $k \in \bf Z$ as the polynomial such that $T_k(\cos u) = \cos ku$. Then $T_{-k} = T_k$ is a polynomial of degree $|k|$ satisfying $|T_k(x)| \leq 1$ for all $x\in [-1,+1]$. Now the Čebyšev expansion of $x^n$ is simply $$x^n = \frac1{2^n} \sum_{m=0}^n {n \choose m} T_{2m-n}(x),$$ which can be checked by writing $x = \cos u = \frac12(e^{iu}+e^{-iu})$ and $T_k(x) = \frac12(e^{iku}+e^{-iku})$. So the coefficients form a binomial distribution, and truncating at degree $d$ eliminates only the tail of the distribution past $d^2/n$ standard deviations. Since each $|T_{2m-n}(x)| \leq 1$, this tail also bounds the truncation error for all $x \in [-1,+1]$, and we conclude that this error can be brought below any positive $\epsilon$ by making $d$ a large enough multiple of $\sqrt{n}$, as claimed.

This might not be the optimal $L^\infty$ approximation (except for $d=n-1$, when its optimality is the result of Čebyšev that you quoted), but it's not too far, because it is the best $L^2$ approximation with respect to the Čebyšev measure $\pi^{-1} dx/ \sqrt{1-x^2}$, and the $L^\infty$ distance is at least as large as the $L^2$ distance. The $L^2$ distance can be computed from the sums of the squares of the coefficients in the tail.

Much the same technique should work for $(1-x^2)^n$; indeed I see that while I was writing this Andrew posted an answer for $(1-x^2)^n$ that looks very similar to what I did for $x^n$.

-
Thanks Noam! The fact that the Chebyshev truncation gives best error up to a log factor is a theorem I read somewhere (maybe Rivlin's book?). –  Ryan O'Donnell Jul 17 '11 at 12:14

For $P_n(x)=(1-x^2)^n$, large $n$ and $a>0$ it's possible to produce a polinomial of degree $a\sqrt{2n}$ with difference in $L_\infty$ less than $C(1-\mathrm{erf}\;a)$, where $C$ is an absolute constant. Taking any positive sequence $a(n)\to+\infty$ as $n\to\infty$ leads to $L_\infty$ norm converging to zero. For large $a$ we have $1-\mathrm{erf}\;a \sim e^{-a^2}/(a\sqrt{\pi})\;$. So to obtain the uniform $\varepsilon$ estimate on $[0,1]$ the degree $\sim C(\log \varepsilon^{-1})^{1/2}\sqrt n\$ is enough.

Namely, consider $P_n$ on the segment $[-1,1]$. Let $x=\sin y$. Now it is enough to approximate the function $$\sin^{2n}y =\sum_{k=0}^n c_n^k\cos 2ky$$ on $[0,2\pi]$ by suitable trigonometric polynomials. Here $c_n^0=\frac1{4^{n}}{2n\choose n}$, $c_n^k =(-1)^{n-k}\frac1{2^{2n-1}}{2n\choose n+k}$, $k=1,\ldots,n$. For degree $2m<2n$ we'll take the polynomial $$Q_{2m}(x)=\sum_{k=0}^m c_n^k\cos 2ky.$$ Then the $L_\infty$ norm $$\|P_{2n}-Q_{2m}\| {} \le \sum_{k=m+1}^{n} |c_n^k|=\frac1{2^{2n-1}}\sum_{k=m+1}^{n}{2n\choose n+k}.$$

The last sum can be easily estimated since it is exactly the sum of the tails in the Bernoulli distribution with probability $p=1/2$ and $2n$ independent trials. For $m=[ a\sqrt{2n}]$ and large $n$ by the central limit theorem it is equal approximately to $2(1-\mathrm{erf}\;a)$. From here the above estimates follow.

-
Very nice answer, but is there any reference for any of this? –  Igor Rivin Jul 16 '11 at 22:32
This looks like the kind of thing that's easier to derive from scratch (now that the method is known) than to find in the literature... –  Noam D. Elkies Jul 16 '11 at 22:41
@Igor It's all straightforward calculations here. –  Andrew Jul 16 '11 at 22:43
Erm, the sum in the last displayed formula is the bulk, not the tail, so it doesn't even tend to $0$... –  fedja Jul 17 '11 at 1:20
OK, makes sense now :) –  fedja Jul 17 '11 at 11:57

Only a comment, but too long to fit in the comments section:

You sound unsure of the result for $d=n-1$. See the end of the page http://mathworld.wolfram.com/ChebyshevPolynomialoftheFirstKind.html. This gives the result, but there is a nice explanation in Acton's book Numerical Methods That Work: The Chebyshev polynomial

$T_n(x)=2^{n-1}x^n+$terms in $x^{n-2}$ and lower

is known to have $Int(n/2)$ minima of $-1$ and $Int((n-1)/2)$ maxima of $+1$ in the range $[-1,1]$. So, rearrange:

$x^n = 2^{-(n-1)}[T_n(x)-($terms in $x^{n-2}$ and lower$)]$

and you have an $(n-2)$-order polynomial approximation of $x^n$, with an error that oscillates between $\pm2^{-(n-1)}$ the correct number of times, which is therefore optimal.

Acton's book is a pleasure to read in any case, and will also lead you through Remes's algorithm if you want to generate minimax approximations for reasonably small $n$. You might want to search for this algorithm (if you don't know it already). For approximating polynomials (or just powers), search for "economization of series". I think there's actually pseudocode of an algorithm for it in the first edition of Oldham and Spanier's An Atlas of Functions. This is another lovely book, so long as you check the errata -- see http://www.trentu.ca/chemistry/oldham/AAOF.html. The second edition is better in some ways, but much less useful for algorithms.

-