In the question below, I would have to solve for an upper estimate using Weierstrass Approximation Theorem, however I am not familiar with the theorem, how do I go about solving it?

For any $\epsilon\in [0,1]$, find an upper estimate on the integer $n$ such that there exists an approximation of $f(x)=|x|$ on $[-1,1]$ by a polynomial $P(x)$ of degree $n$ such that $$\sup_{x\in[-1,1]}|P(x)-|x||\leq \epsilon.$$

  • 1
    $\begingroup$ The statement of the theorem only helps you know that there is a solution to your problem. To find it you either need to apply knowledge about some of its proofs, or about Chebyshev polynomials. Or work it out form scratch by studying particular cases. $\endgroup$ – user647486 Mar 15 at 20:26
  • $\begingroup$ A tool to prove Weierstrass approximation theorem is the convolution with $(1-x^2)^n$. Using this, you should be able to find your degree of approximation in terms of $n$ $\endgroup$ – Gabriele Cassese Mar 15 at 20:26

One path for proving the Weierstrass theorem, that comes with a specific estimate, is to use the Bernstein polynomials $$B_n(f)(x) = 2^{-n}\sum_{k=0}^n f\left(\frac {2k-n}n\right)\cdot \binom{n}{k}(1+x)^k(1-x)^{n-k}$$ For uniformly continuous $f$ on $[-1,1]$, these converge uniformly to $f$ as $n\to\infty$. It's a probabilistic estimate; given a uniform continuity estimate $|f(x)-f(y)|\le g(t)$ whenever $|x-y|\le t$, we estimate \begin{align*}\left|B_n(f)(x)-f(x)\right| &= 2^{-n}\left|\sum_{k=0}^n \left(f\left(\frac {2k-n}n\right)-f(x)\right)\cdot \binom{n}{k}(1+x)^k(1-x)^{n-k}\right|\\ &=\sum_{k=0}^n\left|f\left(\frac {2k-n}n\right)-f(x)\right|\cdot 2^{-n}\binom{n}{k}(1+x)^k(1-x)^{n-k}\\ &\le \sum_{|(2k-n)/n-x|\le t}g(t)\cdot (*) + \sum_{|(2k-n)/n-x|> t}g(2)\cdot (*)\\ &\le g(t)\cdot P(X-x\le t) + g(2)\cdot P(X-x > t)\\ \left|B_n(f)(x)-f(x)\right| &\le g(t)\cdot 1 + \frac1{nt^2}g(2)\end{align*} In this, the random variable $X$ is the scaled binomial distribution with probability mass function $2^{-n}\binom{n}{k}(1+x)^k(1-x)^{n-k}$. That expression is also abbreviated with $(*)$ in the third line, for typographic reasons. This $X$ has mean $x$ and variance $\frac{(1+x)(1-x)}{4n}\le \frac1n$. For the final inequality, we estimate that the first probability is $\le 1$, and that the second probability is $\le \frac1{nt^2}$ by Chebyshev's inequality.

For the function $f(x)=|x|$ we're dealing with, we can take $g(t)=t$. The error estimate we get is then $$|B_n(f)(x)-f(x)|\le \inf_t\left(t+\frac{2}{nt^2}\right) = \left(\frac4n\right)^{\frac13} + \frac{2}{n\left(\frac4n\right)^{\frac23}} = \frac{3}{\sqrt[3]{2n}}$$ To make that less than $\epsilon$, we take $n>\frac12\cdot\left(\frac{3}{\epsilon}\right)^3$.

This is a theoretical estimate, that gives away more than it has to. It's also not the only way to find approximating polynomials. So, then, some follow-up questions:

  • How accurate are the Bernstein polynomials, really?
  • Can you find a sequence of polynomials that converge significantly faster than that?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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