## Monday, March 17, 2008

### Bernstein Polynomial

Recently in Analysis we learned about a famous theorem due to Weierstrass. This theorem asserts that ANY continuous function on a closed interval can be approximated by a polynomial. The proof in Rudin's Principles of Mathematical Analysis was kind of easy to follow but really required that you fill in many gaps, as is usual with many of his proofs. However, over spring break I was reading A First Course in Numerical Analysis by Ralston and Rabinowitz and they provided a proof that was not only much easier to follow but seemed more natural to some extent. It should be noted however, that some of the steps in their proof assumed that you have some background in analysis in order to justify some of their claims. Anyway what follows is their statement of the theorem and its proof.

Theorem:
If $f(x)$ is continuous on a finite interval $[a,b]$, then given any $\epsilon>0$, there exist and $n$ and a polynomial $P_n(x)$ of degree $n$ such that $|f(x)-P_n(x)|<\epsilon$, for all $x$ in $[a,b]$.

Lemmas: The following lemmas are easily proven by the binomial theorem, and thus left to be done so by the reader. (Don't you just hate when books do this to you)
1: $\displaystyle\sum_{k=0}^{n}{n\choose k}x^k(1-x)^{n-k}=1$

2: $\displaystyle\sum_{k=0}^{n}\frac{k}{n}{n\choose k}x^k(1-x)^{n-k}=x$

3: $\displaystyle\sum_{k=0}^{n}\frac{k^2}{n^2}{n\choose k}x^k(1-x)^{n-k}=\left(1-\frac{1}{n}\right)x^2+\frac{1}{n}x$

Proof:
Define the polynomial $\displaystyle B_n(x)=\sum_{k=0}^{n}{n\choose k}x^k(1-x)^{n-k}f\left(\frac{k}{n}\right)$. From the lemmas we have that

$\displaystyle\sum_{k=0}^{n}\left(\frac{k}{n}-x\right)^2{n\choose k}x^k(1-x)^{n-k}=\frac{x(1-x)}{n}$, from this we have that

$\displaystyle f(x)-B_n(x)=\sum_{k=0}^{n}\left[f(x)-f\left(\frac{k}{n}\right)\right]{n\choose k}x^k(1-x)^{n-k}$. Let $M=\sup{|f(x)|}$ on $[0,1]$ (we can turn any finite interval into $[0,1]$ by a simple rescaling). Now $|f(x_1)-f(x_2)|<\epsilon$ if $|x_1-x_2|<\delta$. We

next proceed to define two sets, $A=\left\{\frac kn: \left|\frac kn -x\right|<\delta\right\}$ for any x in the interval and $k=0,1,\dots, n$, and $B$ is the set of remaining points.

Using the above identities we have that $\displaystyle\left|\sum_A\left[f(x)-f\left(\frac kn\right)\right]{n\choose k}x^k(1-x)^{n-k}\right|<\epsilon\sum_a{n\choose k}x^k(1-x)^{n-k}\leq\epsilon$.

For the set $B$ we have $\begin{eqnarray*}
\left|\sum_B\left[f(x)-f\left(\frac kn\right)\right]{n\choose k}x^k(1-x)^{n-k}\right|&\leq & 2M\sum_B{n\choose k}x^k(1-x)^{n-k}\\
&=&2M\sum_B\frac{(k/n-x)^2}{(k/n-x)^2}{n\choose k}x^k(1-x)^{n-k}\\
&\leq&\frac{M}{2n\delta^2}\\
&<& \epsilon
\end{eqnarray*}$

for $n$ large enough. (note that $x(1-x)\leq \frac 14$ on $[0,1]$)

Thus $|f(x)-B_n(x)|<2\epsilon$.
$\mathbb{Q.E.D.}$

Compared to Rudin's proof this one is much easier to follow if you actually prove the lemmas. The above proof was given by Bernstein in 1912, it should be mentioned that I might have left out a few details but the general idea is there. In case you didn't do it, the rescaling done with the interval is just $f(x)\mapsto f\left(\frac{x}{b-a}-\frac{a}{b-a}\right)$, so $f(a)\mapsto f(0)$ and $f(b)\mapsto f(1)$ and anything in between $a$ and $b$ maps to $f(\alpha)$ with $\alpha\in(0,1)$.

Challenge Problem:
If $F(t)$ is a periodic continuous function of period $2\pi$ prove that for any $\epsilon>0$ there exist $n$ such that $|F(t)-S_n(t)|<\epsilon$. Where $S_n(t)=a_0+\sum_{k=1}^{n} \left[a_k\cos(kt)+b_k\sin(kt)\right]$.