%%  polynomials.tex
%%  Approximation Theory: 
%%  Exercises on Approximation by Polynomials
%%  Neal L. Carothers
%%  Bowling Green State University
%%  Bowling Green, Ohio  43403
%%  carother@math.bgsu.edu
%%  http://www.bgsu.edu/~carother/


\input 680-setup.tex

\chaptertitle = {Polynomials}

\centerline{\hfil\tf Uniform Approximation by Polynomials\hfil}
\vskip-\baselineskip
\line{\sc Math 680 \hfil 6/29/94}

\noindent
One of our first tasks will be to give a
constructive proof of {\sl Weierstrass's Theorem},
stating that each  $f\in C[\,a,b\,]$  is the uniform
limit of a sequence of polynomials.  As it happens, 
the choice of interval $[\,a,b\,]$ is inconsequential:
If Weierstrass's theorem is true for one, then it's true
for all.  

\prob{\cmark\gmark}{%
Define $\sigma:[\,0,1\,]\to[\,a,b\,]$ by $\sigma(t)=a+t(b-a)$
for $0\le t\le 1$, and define a transformation
$T_\sigma:C[\,a,b\,]\to C[\,0,1\,]$
by $(T_\sigma(f))(t)=f(\sigma(t))$.  Prove that  
$T_\sigma$ satisfies:
\itemitem{(a)}
$T_\sigma(f+g)=T_\sigma(f)+T_\sigma(g)$ and 
$T_\sigma(cf)=c\,T_\sigma(f)$ for $c\in\R$.
\itemitem{(b)}
$T_\sigma(fg)=T_\sigma(f)\,T_\sigma(g)$.  In particular,
$T_\sigma$ maps polynomials to polynomials.
\itemitem{(c)}
$T_\sigma(f)\le T_\sigma(g)$ if and only if $f\le g$.
\itemitem{(d)}
$\Vert T_\sigma(f)\Vert=\Vert f\Vert$.
\itemitem{(e)}
$T_\sigma$ is both one-to-one and onto. Moreover, 
$(T_\sigma)^{-1}=T_{\sigma^{-1}}$.
}

\noindent
The point to exercise {\bf 1} is that $C[\,a,b\,]$ and
$C[\,0,1\,]$ are {\sl identical\/} as vector spaces,
metric spaces, algebras, and lattices.  For all practical
purposes, they are one and the same space.
While Bernstein's proof of the Weierstrass theorem
(below) will prove most useful for our purposes,
there are {\sl many\/} others;  two of these (in the case
of  $C[\,0,1\,]$) are sketched below.

\prob{\gmark}{%
(Landau's proof):  For each  $n = 1, 2,\ldots$
and  $0\le\delta\le 1$, define
$I_n(\delta)=\int_\delta^1(1-x^2)^n\,dx$.
Show that  $I_n(\delta)/I_n(0) \to 0$  as 
$n \to\infty$  for any  $\delta>0$.
Now, given  $f\in C[\,0,1\,]$  with  
$f(0)= f(1) = 0$, show that the {\sl polynomial\/} 
$L_n(x) =Ê(2I_n(0))^{-1}\int_0^1Êf(t)(1-(t-x)^2)^n\,dt$
converges uniformly to $f(x)$ on $[\,0,1\,]$ 
as $n\to\infty$.  [Hint: You may assume that $f\equiv0$
outside of $[\,0,1\,]$.]  To get the result for general  
$f\in C[\,0,1\,]$, we simply need to subtract the 
{\sl linear\/} function  $f(0) + x(f(1)-f(0))$.
}

\prob{\gmark}{%
(Lebesgue's proof):  Given  $f\in C[\,0,1\,]$,
first show that  $f$  can be uniformly approximated
by a {\sl polygonal\/} function.  Specifically, given a
positive integer $N$, define  $L(x)$  by
the conditions  $L(k/N) = f(k/N)$  for 
$k = 0, 1,\ldots, N$, and  $L(x)$  is linear
for  $k/N\le x \le(k+1)/N$; show that  
$\Vert f-L\Vert$  is small provided that  $N$  is sufficiently
large.  The function $L(x)$  can be written 
(uniquely) as a linear combination of the ``angles''  
$\varphi_k(x) =|x - k/N| + x - k/N$ and $\varphi_N(x)=1$; the
equation $L(x) =  \sum_{k=0}^Nc_k\varphi_k(x)$ can
be solved since the system of equations 
$L(k/N)=\sum_{k=0}^Nc_k\varphi_k(k/N)$, $k=0,\ldots,N$,
can be solved (uniquely) for $c_0,\ldots,c_N$.  (How?)
To finish the proof, we need to show that 
$|x|$  can be approximated by polynomials
on any interval $[\,a,b\,]$.  (Why?)
}

\prob{\gmark}{%  
Here's an elementary proof that there is 
a sequence of polynomials $(P_n)$ converging uniformly 
to $|x|$ on $[\,-1,1\,]$. 
\itemitem{(a)} 
	Define $(P_n)$ recursively by 
	$P_{n+1}(x)=P_n(x)+[x-P_n(x)^2]/2$, where
	$P_0(x)=0$.  Clearly, each $P_n$ is a polynomial.
\itemitem{(b)} 
	Check that $0\le P_n(x)\le P_{n+1}(x)\le \sqrt{x}$
	for $0\le x\le 1$.  Use Dini's theorem to conclude
	that $P_n(x)\uniformto \sqrt{x}$ on $[\,0,1\,]$.
\itemitem{(c)} 
	$P_n(x^2)$ is also a polynomial, and 
	$P_n(x^2)\uniformto |x|$ on $[\,-1,1\,]$.\par
}

\prob{\cmark\gmark}{%
The result in problem {\bf 2} (or {\bf 3}) shows that the polynomials
are dense in $C[\,0,1\,]$.  Using the results in problem {\bf 1}, conclude 
that the polynomials are also dense in $C[\,a,b\,]$.
}

\prob{\cmark\gmark}{%
How do we know that there are non-polynomial elements in
$C[\,0,1\,]$\/?  In other words, is it possible that every element
of $C[\,0,1\,]$ agrees with some polynomial on $[\,0,1\,]$\/?
}

\prob{}{%
Let  $(Q_n)$  be a sequence of polynomials of degree
$m_n$, and suppose that  $(Q_n)$ converges uniformly to
$f$ on $[\,a,b\,]$, where  $f$  is {\sl not\/} a polynomial.  
Show that  $m_n \to \infty$.
}

\prob{}{%
If  $f\in C[-1,1\,]$  (or  $C^{2\pi}$) is an {\sl even\/}
function, show that $f$ may be uniformly approximated
by even polynomials (or even trig polynomials).
}

\prob{}{%
If $f\in C[\,0,1\,]$ and if $f(0)=f(1)=0$, show that the 
sequence of polynomials  
$\sum_{k=0}^n\left[{n\choose k}f(k/n)\right]x^k(1-x)^{n-k}$
with {\sl integer\/} coefficients converges uniformly to  $f$
(where $[x]$ denotes the greatest integer in $x$).
The same trick works for any  $f\in C[\,a,b\,]$ 
provided that  $0 < a < b < 1$.
}

\prob{}{%
If $p$ is a polynomial and $\eps>0$, prove that there is 
a polynomial $q$ with {\sl rational\/} coefficients such that 
$\Vert p-q\Vert<\eps$ on $[\,0,1\,]$.  Conclude that $C[\,0,1\,]$
is {\sl separable}.
}

\prob{}{%
Let $(x_i)$ be a sequence of numbers in $(0,1)$ such that
$\Limonn {1\over n}\sum_{i=1}^n x_i^k$ exists for every
$k=0,1,2,\ldots$.  Show that 
$\Limonn {1\over n}\sum_{i=1}^n f(x_i)$ exists for every
$f\in C[\,0,1\,]$.
}

\prob{}{%
If  $f \in CÊÊ[\,0,1\,]$  and if  $\int_0^1x^nf(x)\,dx=0$
for each  $n = 0, 1,2,\ldots$, show that  $f\equivÊ0$.  
[Hint: Using the Weierstrass theorem, show that $\int_0^1f^2=0$.] 
}

\noindent
The next proof of the Weierstrass theorem that 
we consider is quite explicit; we actually display a  
sequence of polynomials that converges uniformly
to a given $f\in C[\,0,1\,]$.  
Given $f\in C[\,0,1\,]$, we define the sequence
$\bigl(B_n(f)\bigr)_{n=1}^\infty$ of 
{\sl Bernstein polynomials\/} for $f$ by
$$\bigl(B_n(f)\bigr)(x) = \sum_{k=0}^n f\!\left({k\over n}\right)
	\cdot {n\choose k} x^k(1-x)^{n-k}.$$
Please note that $B_n(f)$ is a polynomial of degree
at most $n$.  Also, it's easy to see that 
$\bigl(B_n(f)\bigr)(0)=f(0)$ and
$\bigl(B_n(f)\bigr)(1)=f(1)$.  In general, 
$\bigl(B_n(f)\bigr)(x)$ is an {\sl average\/}
of the numbers $f(k/n)$, $k=0,\ldots,n$.
{\sl Bernstein's theorem\/} states that the sequence
$B_n(f)$ converges uniformly to $f$ for each
$f\in C[\,0,1\,]$; the proof is rather simple once
we have a few facts about the Bernstein polynomials
at our disposal.  For later reference, let's write 
$$f_0(x)=1,\quad f_1(x)=x,\quad \hbox{and}\quad f_2(x)=x^2.$$
Among other things, the following exercise establishes
Bernstein's theorem for these three polynomials.
Curiously, these few special cases will imply
the general result.

\prob{\cmark}{%
\vskip-\baselineskip
\vskip-\parskip
\itemitem{\rm(i)}
	$B_n(f_0)=f_0$ \ and \ $B_n(f_1)=f_1$.
	[Hint: Use the binomial theorem.]
\item{\rm(ii)} 
	$B_n(f_2)=
	\left(1-{1\over n}\right)f_2 + {1\over n}f_1$, \ 
	and hence $(B_n(f_2))$ converges uniformly to $f_2$.
\item{\rm(iii)} 
	$\sum_{k=0}^n \left({k\over n}-x\right)^2{n\choose k}\,x^k(1-x)^{n-k}
	= {{x(1-x)}\over n} \le {1\over{4n}}$, \ if \ $0\le x\le 1$.
\item{\rm(iv)} 
	Given $\delta>0$ and $0\le x\le 1$, let
	$F$ denote the set of $k$'s in $\{0,\ldots,n\}$ for which 
	$\left|{k\over n}-x\right|\ge \delta$.  Then
	$\sum_{k\in F}{n\choose k}\,x^k(1-x)^{n-k}
	\le {1\over{4n\delta^2}}$.\par
}

\prob{\cmark}{%
Show that $|B_n(f)|\le B_n(|f|)$, and
that $B_n(f)\ge 0$ whenever $f\ge 0$.  Conclude that
$\Vert B_n(f)\Vert\le\Vert f\Vert$.
}

\prob{}{%
If $f$ is a bounded function on $[\,0,1\,]$, 
show that $B_n(f)(x)\to f(x)$ at
each point of continuity of $f$.
}

\prob{}{%
(Bohman, Korovkin) \ Let $(T_n)$ be a sequence of monotone
linear operators on $C[\,0,1\,]$; that is, each $T_n$ is
a linear map from $C[\,0,1\,]$ into itself satisfying
$T_n(f)\le T_n(g)$ whenever $f\le g$.  Suppose also that
$T_n(f_0)\uniformto f_0$, $T_n(f_1)\uniformto f_1$, and
$T_n(f_2)\uniformto f_2$.  Prove that $T_n(f)\uniformto f$
for every $f\in C[\,0,1\,]$.  [Hint: Mimic the proof of 
Bernstein's theorem.]
}

\prob{}{%
Find  $B_n(f)$  for  $f(x)=x^3$.  [Hint: $k^2=(k-1)(k-2)+3(k-1)+1$.]  
The same method of calculation can be used to show that 
$B_n(f)\in {\cal P}_m$ whenever $f \in {\cal P}_m$ and $n > m$.
}

\prob{}{%
Let  $f$  be continuously differentiable on 
$[\,a,b\,]$, and let  $\eps > 0$.  Show that there is
a polynomial  $p$  such that  $\Vert f - p\Vert<\eps$
{\sl and\/} $\Vert f\,' - p'\Vert<\eps$.
}

\prob{}{%
Suppose that  $f \in C[\,a,b\,]$  is twice
continuously differentiable and has  $f\,{''} > 0$. 
Prove that the best linear approximation to  $f$  on 
$[\,a,b\,]$  is  $a_0+ a_1x$  where $a_0Ê=f\,'(c)$,  
$a_1= [f(a) +f(c) + f\,'(c) (a + c)]/2$, 
and where $c$  is the unique solution to  
$f\,'(c)= (f(b)-f(a))/(b-a)$.
}

\noindent
The next several exercises use the {\sl modulus of continuity}.
Given a bounded real-valued function $f$ defined on some interval $I$, 
we define $\omega_f$, the modulus of continuity of $f$, by 
$$\omega_f(I;\delta)=\omega_f(\delta)=
	\sup\bigl\{|f(x)-f(y)|:x,y\in I,\,|x-y|\le\delta\,\bigr\}
	\quad \delta\ge0.$$
Note, for example, that if $f$ is {\sl uniformly continuous}, 
then $\omega_f(\delta)\to 0$ as $\delta\to 0$.
Indeed, the statement that $|f(x)-f(y)|\le\eps$ whenever
$|x-y|\le\delta$ is equivalent to the statement that
$\omega_f(\delta)\le\eps$.  On the other hand, if the graph of
$f$ has a jump of magnitude $1$, say, then $\omega_f(\delta)\ge1$
for all $\delta>0$.

\prob{}{%
If $f$ satisfies the Lipschitz condition 
$|f(x)-f(y)|\le K|x-y|$, what can you say about
$\omega_f$?  Find $\omega_g$ for $g(x)=\sqrt{x}$ on $[\,0,1\,]$.
}

\prob{}{%
If $f\in C[\,a,b\,]$, show that 
$\omega_f(\delta_1+\delta_2)\le\omega_f(\delta_1)+\omega_f(\delta_2)$
and that $\omega_f(\delta)\downarrow0$ as $\delta\downarrow0$.
Use this to show that $\omega_f$ is continuous for $\delta\ge0$.
Finally, show that the modulus of continuity of $\omega_f$ is again
$\omega_f$.  
}

\prob{}{%
\vskip-\baselineskip
\vskip-\parskip
\itemitem{(a)}
If  $x = \cos\theta$,  where  $-1\le x\le1$, and if 
$g(\theta) = f(\cos\theta)$,  show that
$\omega_g([-\pi,\pi\,],\delta)=\omega_g([\,0,\pi\,],\delta)
	\le\omega_f([-1,1\,];\delta)$.
\itemitem{(b)}
If $g(x)=f(ax+b)$ for $c\le x\le d$, show that
$\omega_g([\,c,d\,];\delta)=\omega_f([\,ac+b,ad+b\,];a\delta)$.
}

\prob{}{%
Let  $f$  be continuously differentiable on 
$[\,0,1\,]$.  Show that  $(B_n(f)')$ converges
uniformly to $f\,'$ by showing that  
$\Vert B_n(f\,')-(B_{n+1}(f))'\,\Vert\le \omega_{f\,'}(1/(n+1))$.  
[In order to see why this is of interest, find 
a uniformly convergent sequence of {\sl polynomials\/} 
whose derivatives fail to converge uniformly. 
Compare this result with problem {\bf 18}.]
}

\bye


%%  end of polynomials.tex