%%  chapter-04.tex
%%  Approximation Theory: Chapter 4
%%  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 = {Best Approximation}

\centerline{\hfil\tf Characterization of Best Approximation\hfil}
\vskip-\baselineskip
\line{\sc Math 680 \hfil 7/6/94}

\noindent
We next discuss Chebyshev's solution to the problem of
best polynomial approximation from 1854.  Given that there 
was no reason to believe that the problem even had a solution,
let alone a unique solution, Chebyshev's accomplishment
should not be underestimated.  
Chebyshev might very well have been able to prove 
Weierstrass's result---30 years early---had the thought 
simply occurred to him!  Chebyshev's original papers are
apparently rather sketchy.  It wasn't until 1903 that full
details were given by Kirchberger.  Curiously, Kirchberger's
proofs foreshadow very modern techniques such as convexity and 
separation arguments.  The presentation we'll give owes much to 
Haar and to de la Vall\'ee Poussin (both from around 1918).

We begin with an easy observation:

\proclaim Lemma.
Let $f\in C[\,a,b\,]$ and let $p=p_n^*$ be a
best approximation to $f$ out of ${\cal P}_n$.
Then, there are at least two distinct points 
$x_1$, $x_2\in[\,a,b\,]$ such that 
$$f(x_1)-p(x_1)=-(f(x_2)-p(x_2))=\Vert f-p\Vert.$$
That is, $f-p$ attains both of the values
$\pm\Vert f-p\Vert$.

\proof
Let's write $E=E_n(f)=\Vert f-p\Vert
	=\Max_{\strut a\le x\le b}|f(x)-p(x)|$. 
If the conclusion of the Lemma is false, then we might as well
suppose that $f(x_1)-p(x_1)=E$, for some $x_1$, but that 
$$e=\Min_{\strut a\le x\le b}(f(x)-p(x))>-E.$$  
In particular, $E+e\ne0$ and so $q=p-(E+e)/2$ is
an element of ${\cal P}_n$ with $q\ne p$.  We claim 
that $q$ is a better approximation to $f$ than $p$.
Here's why:
$$E-\left({{E+e}\over2}\right) 
	\ \ge \ f(x)-p(x)-\left({{E+e}\over2}\right)
	 \ \ge \ e-\left({{E+e}\over2}\right),$$
or
$$\left({{E-e}\over2}\right) \ \ge \ f(x)-q(x) \ \ge \ 
	-\left({{E-e}\over2}\right).$$
That is,
$$\Vert f-q\Vert \ \le \ \left({{E-e}\over2}\right)
	\ < \ E \ = \ \Vert f-p\Vert,$$
a contradiction.~\qed

\proclaim Corollary.
The best approximating constant to $f\in C[\,a,b\,]$ is
$$p_0^* \ = \ {1\over2}\left[\Max_{\strut a\le x\le b}f(x)
	+\Min_{\strut a\le x\le b}f(x)\right],$$
and
$$E_0(f) \ = \ {1\over2}\left[\Max_{\strut a\le x\le b}f(x)
	-\Min_{\strut a\le x\le b}f(x)\right].$$

\proof
{\bf Exercise}.

Now all of this is meant as motivation for the general case,
which essentially repeats the observation of our first Lemma
inductively.  A little experimentation will convince you 
that a best linear approximation, for example, would imply
the existence of 
{\sl three\/} points (at least) at which $f-p_1^*$ alternates
between $\pm\Vert f-p_1^*\Vert$.

A bit of notation will help us set up the argument for the
general case: Given $g$ in $C[\,a,b\,]$, we'll say that 
$x\in[\,a,b\,]$ is a $(+)$ {\sl point\/} for $g$ (respectively,
a $(-)$ {\sl point\/} for $g$) if $g(x)=\Vert g\Vert$ (respectively,
$g(x)=-\Vert g\Vert$\/).  A set of distinct point
$a\le x_0<x_1<\cdots<x_n\le b$ will be called an
{\sl alternating set\/} for $g$ if the $x_i$'s are alternately
$(+)$ points and $(-)$ points; that is, if
$$|g(x_i)|=\Vert g\Vert,\qquad i=0,1,\ldots,n,$$
and 
$$g(x_i)=-g(x_{i-1}),\qquad i=1,2,\ldots,n.$$
Using this notation, we will be able to characterize
the polynomial of best approximation.  Since the
following three theorems are particularly important,
we will number them for future reference.  Our first
result is where all the fighting takes place:

\proclaim Theorem 1.
Let $f\in C[\,a,b\,]$, and suppose that $p=p_n^*$ is a
best approximation to $f$ out of ${\cal P}_n$.  
Then, there is an alternating set for $f-p$
consisting of at least $n+2$ points.  

\proof
If $f\in{\cal P}_n$, there's nothing to show.  (Why?)
Thus, we may suppose that $f\notin{\cal P}_n$ and,
hence, that $E=E_n(f)=\Vert f-p\Vert>0$.  

Now consider the (uniformly) continuous function
$\varphi=f-p$.  We may partition $[\,a,b\,]$ by way of
$a=t_0<t_1<\cdots<t_n=b$ into sufficiently small 
intervals so that
$$|\varphi(x)-\varphi(y)|<E/2\qquad\hbox{whenever}\qquad
	x,y\in[\,t_i,t_{i+1}\,].$$
Here's why we'd want to do such a thing: If $[\,t_i,t_{i+1}\,]$
contains a $(+)$ point for $\varphi=f-p$, then $\varphi$
is positive on all of $[\,t_i,t_{i+1}\,]$.  Indeed,
$$x,y\in[\,t_i,t_{i+1}\,]\ \hbox{ and }\ \varphi(x)=E
	\quad\implies\quad\varphi(y)>E/2>0.$$
Similarly, if $[\,t_i,t_{i+1}\,]$
contains a $(-)$ point for $\varphi$, then $\varphi$
is negative on all of $[\,t_i,t_{i+1}\,]$.  Consequently,
{\bf no interval $[\,t_i,t_{i+1}\,]$ can contain both $(+)$ 
points and $(-)$ points}.

Call $[\,t_i,t_{i+1}\,]$ a $(+)$ {\sl interval\/} (respectively,
a $(-)$ {\sl interval\/}) if it contains a $(+)$ point
(respectively, a $(-)$ point) for $\varphi=f-p$.  Notice that
{\bf no $(+)$ interval can even touch a $(-)$ interval}.  In
other words, a $(+)$ interval and a $(-)$ interval must be
strictly separated (by some interval containing a zero for
$\varphi$).

We now relabel the $(+)$ and $(-)$ intervals from left to right,
ignoring the ``neither'' intervals.  There's no harm in supposing
that the first ``signed'' interval is a $(+)$ interval.  Thus,
we suppose that our relabeled intervals are written
$$\displaylines{%
\qquad\qquad\qquad\qquad\qquad
	I_1,I_2,\ldots,I_{k_1}\hfill
	\qquad(+)\ \hbox{intervals},
	\qquad\qquad\qquad\qquad\qquad\cr
\qquad\qquad\qquad\qquad\qquad
	I_{k_1+1},I_{k_1+2},\ldots,I_{k_2}\hfill
	\qquad(-)\ \hbox{intervals},
	\qquad\qquad\qquad\qquad\qquad\cr
\qquad\qquad\qquad\qquad\qquad
	\hbox to 1.4 true in{~\dotfill~}\hfill
	\qquad\qquad\qquad\qquad\qquad\cr
\qquad\qquad\qquad\qquad\qquad
	I_{k_{m-1}+1},I_{k_1+2},\ldots,I_{k_m}\hfill
	\qquad(-1)^{m-1}\ \hbox{intervals},
	\qquad\qquad\qquad\qquad\cr
}$$
where $I_{k_1}$ is the last $(+)$ interval before we
reach the first $(-)$ interval, $I_{k_1+1}$.  And
so on.  
Our goal here is to show that $m\ge n+2$. (So far
we only know that $m\ge2$!)  Let's suppose that
$m<n+2$ and see what goes wrong.

Since any $(+)$ interval is strictly separated
from any $(-)$ interval, we can find points
$z_1,\ldots,z_{m-1}$ such that 
$$\displaylines{%
\max I_{k_1}<z_1<\min I_{k_1+1}\cr
\max I_{k_2}<z_2<\min I_{k_2+1}\cr
\hbox to 1.5 true in{\dotfill}\cr
\max I_{k_{m-1}}<z_{m-1}<\min I_{k_{m-1}+1}\cr
}$$
And now we construct the offending polynomial:
$$q(x)=(z_1-x)(z_2-x)\cdots(z_{m-1}-x).$$
Notice that $q\in{\cal P}_n$ since $m-1\le n$.  
(Here is the {\sl only\/} use we'll make of the
assumption $m<n+2$!)  We're going to show that
$p+\lambda q\in{\cal P}_n$ is a better approximation
to $f$ than $p$, for some suitable scalar $\lambda$.

We first claim that $q$ and $f-p$ have the 
same sign.  Indeed, $q$ has no zeros in any
of the $(\pm)$ intervals, hence is of constant sign
on any such interval.  Thus, $q>0$ on $I_1,\ldots,I_{k_1}$
because each $(z_j-x)>0$ on these intervals; $q<0$ on
$I_{k_1+1},\ldots,I_{k_2}$ because here $(z_1-x)<0$, while 
$(z_j-x)>0$ for $j>1$; and so on.  

We next find $\lambda$.  Let $e=\Max_{\strut x\in R}|f(x)-p(x)|$,
where $R$ is the union of all the subintervals $[\,t_i,t_{i+1}\,]$
which are neither $(+)$ intervals nor $(-)$ intervals.  
Then, $e<E$.  (Why?)  Now choose $\lambda>0$ so that 
$\lambda\Vert q\Vert<\min\{E-e,E/2\}$. 
We claim that $p+\lambda q$ is a better approximation to 
$f$ than $p$.  One case is easy: If $x\in R$, then
$$|f(x)-(p(x)+\lambda q(x))| \ \le \ 
	e+\lambda\Vert q\Vert \ < \ E.$$
On the other hand, if $x\notin R$, then $x$ is in either
a $(+)$ interval or a $(-)$ interval.  In particular, we
know that $|f(x)-p(x)|>E/2>\lambda\Vert q\Vert$ and that 
$f(x)-p(x)$ and $\lambda q(x)$ have the same sign.  Thus,
$$\eqalign{%
|f(x)-(p(x)+\lambda q(x))| \ &= \ |f(x)-p(x)|-\lambda |q(x)|\cr
	&\le \ E-\lambda\,\Min_{\strut x\notin R}|q(x)| \ < \ E,
}$$
since $q$ is nonzero off $R$.  This contradiction finishes
the proof.  (Phew!)~\qed

\noindent{\bf Remarks}

\item{1.}
It should be pointed out that the number $n+2$ here is
actually $1+{\rm dim}\,{\cal P}_n$.  

\item{2.}
Notice, too, that if $f-p_n^*$ alternates in sign $n+2$ times,
then $f-p_n^*$ must have at least $n+1$ zeros.  Thus, $p_n^*$ 
actually agrees with $f$ (or ``interpolates'' $f$\/)
at $n+1$ points.

\filbreak

We're now ready to establish the uniqueness of the
polynomial of best approximation.

\proclaim Theorem 2.
Let $f\in C[\,a,b\,]$.  Then, the polynomial of best 
approximation to $f$ out of ${\cal P}_n$ is unique.

\proof
Suppose that $p$, $q\in{\cal P}_n$ both satisfy
$\Vert f-p\Vert=\Vert f-q\Vert=E_n(f)=E$.  Then, as we've
seen, their average $r=(p+q)/2\in{\cal P}_n$ is also best:
$\Vert f-r\Vert=E$ since $f-r=(f-p)/2+(f-q)/2$.

By Theorem~1, $f-r$ has an alternating set $x_0,x_1,\ldots,x_{n+1}$,
containing $n+2$ points.  Thus, for each $i$,
$$(f-p)(x_i)+(f-q)(x_i)=\pm 2 E,$$
while 
$$-E\le(f-p)(x_i),\,(f-q)(x_i)\le E.$$
But this means that
$$(f-p)(x_i)=(f-q)(x_i)=\pm E$$
for each $i$.  (Why?)  That is, $x_0,x_1,\ldots,x_{n+1}$
is an alternating set for both $f-p$ and $f-q$.  
In particular, the polynomial $p-q=(f-p)-(f-q)$
has $n+2$ zeros!  Since $p-q\in{\cal P}_n$, we
must have $p=q$.~\qed

Finally, we come full circle: 

\proclaim Theorem 3.
Let $f\in C[\,a,b\,]$, and let $p\in{\cal P}_n$.
If $f-p$ has an alternating set containing $n+2$~ 
{\rm(}or more\/{\rm)} points, then $p$ is the best 
approximation to $f$ out of ${\cal P}_n$.

\proof
Let $x_0,x_1,\ldots,x_{n+1}$ be an alternating set for
$f-p$, and suppose that some $q\in{\cal P}_n$ is a better
approximation to $f$ than $p$; that is,
$\Vert f-q\Vert<\Vert f-p\Vert$.  In particular, then,
we must have
$$\Vert f-p\Vert=|f(x_i)-p(x_i)|>|f(x_i)-q(x_i)|\ge\Vert f-q\Vert$$ 
for each $i=0,1,\ldots,n+1$.  
Now the inequality $|a|>|b|$ implies that $a$ and $a-b$ have
the same sign (why?),\ hence  $q-p=(f-p)-(f-q)$ alternates in
sign $n+2$ times (because $f-p$ does).  But then, $q-p$ would
have at least $n+1$ zeros.  Since $q-p\in{\cal P}_n$, we must
have $q=p$, which is a contradiction.  Thus, $p$ is the best 
approximation to $f$ out of ${\cal P}_n$.~\qed

\noindent{\bf Example} (taken from Rivlin)

\noindent
While an alternating set for $f-p_n^*$ is supposed to have
at least $n+2$ points, it may well have more than 
$n+2$ points; thus, alternating sets need not be unique.  
For example, consider the function $f(x)=\sin 4x$ on
$[-\pi,\pi\,]$.  Since there are $8$ points where $f$
alternates between $\pm1$, it follows that
$p_0^*=0$ and that there are $4\times4=16$ different
alternating sets consisting of exactly $2$ points (not
to mention all those with more than $2$ points).
In addition, notice that we actually have
$p_1^*=\cdots=p_6^*=0$, but that $p_7^*\ne0$.  (Why?)

\noindent{\bf Exercise}

\noindent
Show that $y=x-1/8$ is the best linear approximation 
to $y=x^2$ on $[\,0,1\,]$.

Essentially repeating the proof given for Theorem~3 
yields a lower bound for $E_n(f)$.  

\proclaim Theorem.
Let $f\in C[\,a,b\,]$, and suppose that $q\in{\cal P}_n$
is such that $f(x_i)-q(x_i)$ alternates in sign at $n+2$
points $a\le x_0\le x_1\le\ldots\le x_{n+1}\le b$.  Then, 
$$E_n(f) \ \ge \ \Min_{\strut i=0,\ldots,n+1}|f(x_i)-q(x_i)|.$$

\proof
If the inequality fails, we could repeat (essentially) the
same argument as that used  
in the proof of Theorem 3 to arrive at a contradiction.~\qed

Even for relatively simple functions, the problem of
actually finding the polynomial of best approximation
is genuinely difficult (even computationally).  We
end this section by stating two important problems
that Chebyshev was able to solve.  

\noindent{\bf Problem}

\noindent
Find the polynomial $p_{n-1}^*\in{\cal P}_{n-1}^*$, of degree
at most $n-1$, that 
best approximates $f(x)=x^n$ on the interval $[-1,1\,]$.
(This particular choice of interval makes for a tidy solution; 
we'll discuss the general situation later.)

Since $p_{n-1}^*$ is to minimize 
$\Max_{\strut |x|\le1}|x^n-p_{n-1}^*(x)|$, our first
problem is equivalent to:

\noindent{\bf Problem}

\noindent
Find the monic polynomial of degree $n$ which deviates
least from $0$ on $[-1,1\,]$.  In other words, find the monic 
polynomial of degree $n$ which has smallest norm in $C[-1,1\,]$.

We'll give two solutions to this problem (which we know 
has a unique solution, of course).  First, let's simplify
our notation.  We write 
$$p(x)=x^n-p_{n-1}^*(x)\quad\hbox{(the solution)},$$ 
and 
$$M=\Vert p\Vert=E_{n-1}(x^n;[-1,1\,]).$$
All we know about $p$ is that it has an alternating set
$x_0,x_1,\ldots,x_n$ containing $(n-1)+2=n+1$ points;
that is, $|p(x_i)|=M$ and $p(x_{i+1})=-p(x_i)$ for all $i$.
Using this tiny bit of information, Chebyshev was led
to compare the polynomials $p^2$ and $p\,'$.  Watch closely!

\noindent{\bf Step 1}.
At any $x_i$ in $(-1,1)$, we must have $p\,'(x_i)=0$
(because $p(x_i)$ is a relative extreme value for $p$\/).
But, $p\,'$ is a polynomial of degree $n-1$ and so can
have at most $n-1$ zeros.  Thus, we must have
$$x_i\in(-1,1),\ \ p\,'(x_i)=0,\ \ \hbox{for}\ \ i=1,\ldots,n-1,$$
(in fact, $x_1,\ldots,x_{n-1}$ are {\sl all\/} the zeros of $p\,'$\/)
and
$$x_0=-1,\ \ p\,'(x_0)\ne0,\ \ x_{n-1}=1,\ \ p\,'(x_{n-1})\ne0.$$

\noindent{\bf Step 2}.
Now consider the polynomial $M^2-p^2\in{\cal P}_{2n}$.  We know
that $M^2-(p(x_i))^2=0$ for $i=0,1,\ldots,n$, and that $M^2-p^2\ge0$
on $[-1,1\,]$.  Thus, $x_1,\ldots,x_{n-1}$ must be double roots
(at least) of $M^2-p^2$.  But this makes for $2(n-1)+2=2n$ roots
already, so we must have them all.  Hence, $x_1,\ldots,x_{n-1}$ 
are double roots, $x_0$ and $x_n$ are simple roots, and these
are all the roots of $M^2-p^2$.

\noindent{\bf Step 3}.
Next consider $(p\,')^2\in{\cal P}_{2(n-1)}$.  We know that
$(p\,')^2$ has a double root at each of $x_1,\ldots,x_{n-1}$
(and no other roots), hence $(1-x^2)(p\,'(x))^2$ has a double
root at each $x_1,\ldots,x_{n-1}$, and a simple root at 
$x_0$ and $x_n$.  Since $(1-x^2)(p\,'(x))^2\in{\cal P}_{2n}$,
we've found all of its roots.  

Here's the point to all this rooting: 

\noindent{\bf Step 4}.
Since $M^2-(p(x))^2$ and $(1-x^2)(p\,'(x))^2$ are polynomials
of the same degree with the same roots, they are, up to a
constant multiple, the same polynomial!  It's easy to see
what constant, too:  The leading coefficient of $p$ is $1$
while the leading coefficient of $p\,'$ is $n$; thus,
$$M^2-(p(x))^2 \ = \ {{(1-x^2)(p\,'(x))^2}\over{n^2}}.$$
After tidying up,
$${{p\,'(x)}\over{\sqrt{\,M^2-(p(x))^2\,}}} \ = \ 
	{n\over\sqrt{\,1-x^2\,}}.$$
We really should have an extra $\pm$ here, but we know that
$p\,'$ is positive on {\sl some\/} interval.  We'll simply
assume that it's positive on $[-1,x_1\,]$.  Now, upon
integrating,
$$\arccos\left({{p(x)}\over M}\right) \ = \ n\arccos x + C,$$
or, $p(x) = M\cos(n\arccos x + C)$.  
But $p(-1)=-M$ (because $p\,'(-1)\ge0$\/), so
$$\eqalign{%
\cos(n\pi+C)=-1\ &\implies\ C=m\pi\ \ \hbox{(and}\ n+m\ \hbox{is odd)}\cr
	&\implies\ p(x) = \pm M\cos(n\arccos x)\cr
	&\implies\ p(\cos x) = \pm M\cos nx.\cr
}$$
Look familiar?  Since we know that the Chebyshev polynomial $T_n$
satisfies this equation (with $\pm M=1$) and has leading coefficient 
$2^{n-1}$, the solution to our problem must be
$$p(x) \ = \ 2^{-n+1}\,T_n(x),$$
and the minimum norm is $M=2^{-n+1}$.~\qed

Next we give a ``fancy'' solution, based on our characterization
of best approximations (Theorem 3) and a few simple properties
of the Chebyshev polynomials.

\proclaim Theorem.
For any $n\ge1$, the formula $p(x)=x^n-2^{-n+1}\,T_n(x)$ 
defines a polynomial $p\in{\cal P}_{n-1}$ satisfying
$$2^{-n+1} \ = \ \Max_{\strut |x|\le1}|x^n-p(x)| \ 
	< \ \Max_{\strut |x|\le1}|x^n-q(x)|$$
for any other $q\in{\cal P}_{n-1}$.

\proof
We know that $2^{-n+1}\,T_n(x)$ has leading coefficient $1$,
and so $p\in{\cal P}_{n-1}$.  
Now set $x_k=\cos((n-k)\pi/n)$ for $k=0,1,\ldots,n$.  Then,
$-1=x_0<x_1<\cdots<x_n=1$ and 
$$T_n(x_k)=T_n(\cos((n-k)\pi/n))=\cos((n-k)\pi)=(-1)^{n-k}.$$
Since $|T_n(x)|=|T_n(\cos\theta)|=|\cos n\theta|\le1$,
for $-1\le x\le1$, we've found an alternating set for
$T_n$ containing $n+1$ points.  

In other words, $x^n-p(x)=2^{-n+1}\,T_n(x)$ satisfies
$|x^n-p(x)|\le 2^{-n+1}$ and, for each $k=0,1,\ldots,n$, has
$x_k^n-p(x_k)=2^{-n+1}\,T_n(x_k)=(-1)^{n-k}2^{-n+1}$.
By our characterization of best approximations
(Theorem 3), $p$ must be the best approximation to $x^n$
out of ${\cal P}_{n-1}$.~\qed

\proclaim Corollary.
The monic polynomial of degree exactly $n$ having smallest
norm in $C[\,a,b\,]$ is
$${{(b-a)^n}\over{2^n2^{n-1}}}\cdot 
	T_n\left({{2x-b-a}\over{b-a}}\right).$$

\proof
{\bf Exercise}. [Hint: If $p(x)$ is a polynomial of degree $n$
with leading coefficient $1$, then $\tilde p(x)=p((2x-b-a)/(b-a))$ 
is a polynomial of degree $n$ with leading coefficient $2^n/(b-a)^n$.  
Moreover, 
$\Max_{\strut a\le x\le b}|p(x)|=\Max_{\strut -1\le x\le1}|\tilde p(x)|$.]

\noindent{\bf Properties of the Chebyshev Polynomials}

\noindent
As we've seen, the Chebyshev polynomial $T_n(x)$ is the
(unique, real) polynomial of degree $n$ (having leading
coefficient $1$ if $n=0$, and $2^{n-1}$ if $n\ge1$\/)
such that $T_n(\cos\theta)=\cos n\theta$ for all $\theta$.
The Chebyshev polynomials have dozens of interesting properties
and satisfy all sorts of curious equations.  We'll catalogue
just a few.  

\item{\bf 1.}
$T_n(x) = 2x\,T_{n-1}(x)-T_{n-2}(x)$ for $n\ge 2$.

\proof
It follows from the trig identity
$\cos n\theta=2\cos\theta\,\cos(n-1)\theta-\cos(n-2)\theta$
that 
$T_n(\cos\theta) = 2\cos\theta\,T_{n-1}(\cos\theta)-T_{n-2}(\cos\theta)$
for all $\theta$; that is, the equation
$T_n(x) = 2x\,T_{n-1}(x)-T_{n-2}(x)$ holds for all $-1\le x\le1$.
But since both sides are polynomials, equality must
hold for all $x$.~\qed

The next two properties are proved in essentially the same way:

\item{\bf 2.}
$T_m(x)+T_n(x)={1\over2}\bigl[T_{m+n}(x)+T_{m-n}(x)\bigr]$ for $m>n$.

\item{\bf 3.}
$T_m(T_n(x)) = T_{mn}(x)$.

\item{\bf 4.}
$T_n(x) = {1\over2}\bigl[(x+\sqrt{x^2-1}\,)^n+(x-\sqrt{x^2-1}\,)^n\bigr]$. 

\proof
First notice that the expression on the right-hand side
is actually a polynomial since, in combining the binomial expansions
of $(x+\sqrt{x^2-1}\,)^n$ and $(x-\sqrt{x^2-1}\,)^n$, the odd powers 
of $\sqrt{x^2-1}$ cancel.  Next, for $x=\cos\theta$, 
$$\eqalign{%
T_n(x)=T_n(\cos\theta)
	&=\cos n\theta = {1\over2}(e^{in\theta}+e^{-in\theta})\cr
	&={1\over2}\bigl[(\cos\theta+i\sin\theta)^n+(\cos\theta-i\sin\theta)^n\bigr]\cr
	&={1\over2}\bigl[\bigl(x+i\sqrt{1-x^2\,}\,\bigr)^n
		+\bigl(x-i\sqrt{1-x^2\,}\,\bigr)^n\bigr]\cr
	&={1\over2}\bigl[\bigl(x+\sqrt{x^2-1\,}\,\bigr)^n
		+\bigl(x-\sqrt{x^2-1\,}\,\bigr)^n\bigr].\cr
}$$
We've shown that these two polynomials agree for $|x|\le1$, hence
they must agree for all $x$ (real or complex, for that matter).~\qed

For real $x$ with $|x|\ge1$, the expression 
${1\over2}\bigl[(x+\sqrt{x^2-1}\,)^n+(x-\sqrt{x^2-1}\,)^n\bigr]$
equals $\cosh(n\cosh^{-1}x)$.  In other words,

\item{\bf 5.}
$T_n(\cosh x)=\cosh nx$ for all real $x$.

The next property also follows from {\bf 4}.

\item{\bf 6.}
$T_n(x) \le (|x|+\sqrt{x^2-1}\,)^n$ for $|x|\ge1$.

An approach similar to {\bf 4} allows us to write $x^n$ in
terms of the Chebyshev polynomials $T_0,T_1,\ldots,T_n$.

\item{\bf 7.}
For $n$ odd, 
$2^nx^n=\displaystyle{\sum_{k=0}^{[n/2]}{n\choose k}2\,T_{n-2k}(x)}$;
for $n$ even, $2\,T_0$ should be replaced by $T_0$.

\proof
For $-1\le x\le1$,
$$\openup1\jot\eqalignno{%
2^nx^n&=2^n(\cos\theta)^n=(e^{i\theta}+e^{-i\theta})^n\cr
	&=e^{in\theta}+{n\choose1}e^{i(n-2)\theta}+
		{n\choose2}e^{i(n-4)\theta}+\cdots\cr
	&\qquad\qquad\cdots+
		{n\choose{n-2}}e^{-i(n-4)\theta}+
		{n\choose{n-1}}e^{-i(n-2)\theta}+e^{-in\theta}\cr
	&=2\cos n\theta+{n\choose1}2\cos(n-2)\theta+
		{n\choose2}2\cos(n-4)\theta+\cdots\cr
	&=2\,T_n(x)+{n\choose1}2\,T_{n-2}(x)+{n\choose2}2\,T_{n-4}(x)+\cdots,\cr
}$$
where, if $n$ is even, the last term in this last sum
is ${n\choose{[n/2]}}T_0$ (since the central term in the binomial
expansion, namely ${n\choose{[n/2]}}={n\choose{[n/2]}}T_0$, 
isn't doubled in this case).~\qed

\item{\bf 8.}
The zeros of $T_n$ are $x_k^{(n)}=\cos((2k-1)\pi/2n)$,
$k=1,\ldots,n$.  They're real, simple, and lie in the
open interval $(-1,1)$.

\proof
Just check!  But notice, please, that the zeros are
listed here in {\sl decreasing\/} order (because
cosine decreases).~\qed

\item{\bf 9.}
Between two consecutive zeros of $T_n$, there is precisely
one root of $T_{n-1}$.

\proof
It's not hard to check that
$${{2k-1}\over{2n}}<{{2k-1}\over{2n-1}}<{{2k+1}\over{2n}},$$
which means that $x_k^{(n)}>x_k^{(n-1)}>x_{k+1}^{(n)}$ for
$k=1,\ldots,n-1$.~\qed

\item{\bf 10.}
$T_n$ and $T_{n-1}$ have no common zeros.

\proof
Although this is immediate from {\bf 9}, there's another
way to see it:  $T_n(x_0)=0=T_{n-1}(x_0)$ implies that
$T_{n-2}(x_0)=0$ by {\bf 1}.  Repeating this observation,
we would have $T_k(x_0)=0$ for every $k<n$, including $k=0$.
No good!  $T_0(x)=1$ has no zeros.~\qed

\item{\bf 11.}
The set $\{x_k^{(n)}\}_{k,n}$ is dense in $[-1,1\,]$.

\proof
Since $|\cos\alpha-\cos\beta|\le|\alpha-\beta|$, it's enough
to know that $\theta_k^{(n)}=(2k-1)\pi/2n$, $1\le k\le n$, 
$n=1,2,\ldots$, defines a dense sequence in $[\,0,\pi\,]$, and
for this it's enough to know that the set $\{(2k-1)/2n\}_{k,n}$ 
is dense in $[\,0,1\,]$.  (Why?)  But
$${{2k-1}\over{2n}}={k\over n}-{1\over{2n}}\approx{k\over n}$$
for $n$ large; that is, the set $\{(2k-1)/2n\}_{k,n}$ is dense
among the rationals in $[\,0,1\,]$.~\qed

It's interesting to note here that the {\sl distribution\/} of
the roots $\{x_k^{(n)}\}_{k,n}$ can be estimated (see
Natanson, {\it Constructive Function Theory}, Vol.\ I,
pp.\ 48--51).  For large $n$, the number of roots of $T_n$
that lie in an interval $[\,x,x+\Delta x\,]\subset[-1,1\,]$
is approximately 
$${{n\Delta x}\over{\pi\sqrt{1-x^2\,}}}\,.$$
In particular, for $n$ large, the roots of $T_n$ 
are ``thickest'' near the endpoints $\pm1$.

In probabilistic terms, this means that if we assign equal 
probability to each of the roots $x_0^{(n)},\ldots,x_n^{(n)}$ 
(that is, if we think of each root as the position of a point 
with mass $1/n$\/), then the {\sl density\/} of 
this probability distribution (or the density of the system of point 
masses) at a point $x$ is approximately $1/\pi\sqrt{1-x^2\,}$
for large $n$.
In still other words, this tells us that the probability that
a root of $T_n$ lies in the interval $[\,a,b\,]$ is approximately
$${1\over\pi}\int_a^b{1\over\sqrt{1-x^2\,}}\,dx\,.$$

\item{\bf 12.}
The Chebyshev polynomials are mutually {\sl orthogonal\/} 
relative to the weight $w(x)=(1-x^2)^{-1/2}$ on $[-1,1\,]$.

\proof
For $m\ne n$, the substitution $x=\cos\theta$ leads yields
$$\int_{-1}^1T_n(x)\,T_m(x)\,{{dx}\over{\sqrt{1-x^2}}} \ 
	=\int_0^{\pi}\cos m\theta\,\cos n\theta\,d\theta=0,$$
while for $m=n$,
$$\int_{-1}^1T_n^2(x)\,{{dx}\over{\sqrt{1-x^2}}} \ 
	=\int_0^{\pi}\cos^2 n\theta\,d\theta
	=\cases{\pi & if \ $n=0$\cr \pi/2 & if \ $n>0$.\cr}
	\eqno\qed$$

\item{\bf 13.}
$|T_n'(x)|\le n^2$ for $-1\le x\le1$, and $|T_n'(\pm 1)|=n^2$.

\proof
For $-1<x<1$ we have 
$${d\over{dx}}T_n(x) \ = \ 
	{{{d\over{d\theta}}\,T_n(\cos\theta)}\over{{d\over{d\theta}}\cos\theta}}
	\ = \ {{n\sin n\theta}\over{\sin\theta}}.$$
Thus, $|T_n'(x)|\le n^2$ because $|\sin n\theta|\le n|\sin\theta|$
(which can be easily checked by induction, for example).  At
$x=\pm1$, we interpret this derivative formula as a limit
(as $\theta\to0$ and $\theta\to\pi$\/) and find
that $|T_n'(\pm 1)|=n^2$.~\qed

As we'll see later, each $p\in{\cal P}_n$ satisfies
$|p\,'(x)|\le\Vert p\Vert n^2=\Vert p\Vert T_n'(1)$ for
$-1\le x\le1$, and this is, of course, best possible.
As it happens, $T_n(x)$ has the largest possible rate of
growth outside of $[-1,1\,]$ among all polynomials of
degree $n$. Specifically:

\proclaim Theorem.
Let $p\in{\cal P}_n$ and let 
$\Vert p\Vert=\Max_{\strut-1\le x\le1}|p(x)|$.
Then, for any $x_0$ with $|x_0|\ge1$ and any $k=0,1,\ldots,n$ we have
$$|p^{(k)}(x_0)|\le\Vert p\Vert\,|T_n^{(k)}(x_0)|,$$
where $p^{(k)}$ is the $k$-th derivative of $p$.

We'll prove only the case $k=0$.  In other words, we'll 
check that $|p(x_0)|\le\Vert p\Vert\,|T_n(x_0)|$.  The
more general case is in Rivlin, Theorem 1.10, p.\ 31.

\proof
Since all the zeros of $T_n$ lie in
$(-1,1)$, we know that $T_n(x_0)\ne0$.  Thus, we may
consider the polynomial
$$q(x) \ = \ {{p(x_0)}\over{T_n(x_0)}}\,T_n(x) \ - \ p(x)
	\in{\cal P}_n.$$
If the claim is {\sl false}, then 
$$\Vert p\Vert<\left|{{p(x_0)}\over{T_n(x_0)}}\right|.$$
Now at each of the points $y_k=\cos(k\pi/n)$, $k=0,1,\ldots,n$,
we have $T_n(y_k)=(-1)^k$ and, hence, 
$$q(y_k) \ = \ (-1)^k{{p(x_0)}\over{T_n(x_0)}} \ - \ p(x_k).$$
Since $|p(x_k)|\le\Vert p\Vert$, it follows that $q$ alternates 
in sign at these $n+1$ points.  In particular, $q$ must have
at least $n$ zeros in $(-1,1)$.  But $q(x_0)=0$, by design,
and $|x_0|\ge1$.  That is, we've found $n+1$ zeros for a 
polynomial of degree $n$.  So, $q\equiv0$; that is,
$$p(x) \ = \ {{p(x_0)}\over{T_n(x_0)}}\,T_n(x).$$
But then,
$$|p(1)|=\left|{{p(x_0)}\over{T_n(x_0)}}\right|>\Vert p\Vert,$$
since $T_n(1)=T_n(\cos0)=1$, which is a contradiction.~\qed

\proclaim Corollary.
Let $p\in{\cal P}_n$ and let 
$\Vert p\Vert=\Max_{\strut-1\le x\le1}|p(x)|$.
Then, for any $x_0$ with $|x_0|\ge1$, we have
$$|p(x_0)|\le\Vert p\Vert\left(|x_0|+\sqrt{x_0^2-1\,}\,\right)^n.$$

Rivlin's proof of our last result in the general case uses the 
following observation:

\item{\bf 14.}
For $x\ge1$ and $k=0,1,\ldots,n$, we have $T_n^{(k)}(x)>0$.

\proof
{\bf Exercise}.

\noindent{\bf Uniform Approximation by Trig Polynomials}

We end this section by summarizing (without proofs) the
analogues of Theorems 1--3 for uniform approximation by
trig polynomials.  Throughout, $f\in C^{2\pi}$ and 
${\cal T}_n$ denotes the collection of trig polynomials of 
degree at most $n$.

\item{\bf 1.}
$f$ has a best approximation $T^*\in{\cal T}_n$.

\item{\bf 2.}
$f-T^*$ has an alternating set containing $2n+2$
(or more) points in $[\,0,2\pi)$.

\item{\bf 3.}
$T^*$ is unique.

\item{\bf 4.}
If $T\in{\cal T}_n$ is such that $f-T$ has an
alternating set containing $2n+2$ or more points
in $[\,0,2\pi)$, then $T=T^*$.

The proofs of {\bf1}--{\bf4} are very similar to
the corresponding results for algebraic polynomials.
As you might imagine, {\bf2} is where all the
fighting takes place, and there are a few technical
difficulties to cope with.  Nevertheless, we'll
swallow these facts whole and apply them with a clear
conscience to a few examples.

\noindent{\bf Example}

\noindent
For $m>n$, the best approximation to 
$f(x)=A\cos mx+B\sin mx$ out of ${\cal T}_n$ is $0$!

\proof
We may write $f(x)=R\cos m(x-x_0)$ for some $R$ and
$x_0$.  (How?)  Now we need only display a sufficiently
large alternating set for $f$ (in some interval of
length $2\pi$\/).  

Setting $x_k=x_0+k\pi/m$, $k=1,2,\ldots,2m$, we get 
$f(x_k)=R\cos(-k\pi)=R(-1)^k$.  Since $m>n$,
it follows that $2m\ge 2n+2$.~\qed

\noindent{\bf Example}

\noindent
The best approximation to 
$$f(x)=a_0+\sum_{k=1}^{n+1}\bigl(a_k\cos kx+b_k\sin kx\bigr)$$
out of ${\cal T}_n$ is
$$T(x)=a_0+\sum_{k=1}^n\bigl(a_k\cos kx+b_k\sin kx\bigr),$$
and $\Vert f-T\Vert=\sqrt{a_{n+1}^2+b_{n+1}^2\,}$.

\proof
By our last example, the best approximation to $f-T$ out
of ${\cal T}_n$ is $0$, hence $T$ must be the best
approximation to $f$.  (Why?)  The last assertion is
easy to check:  Since we can always write 
$A\cos mx+B\sin mx=\sqrt{A^2+B^2\,}\cdot\cos m(x-x_0)$,
for some $x_0$, it follows that 
$\Vert f-T\Vert=\sqrt{a_{n+1}^2+b_{n+1}^2\,}$.~\qed

Finally, let's make a simple connection between the two
types of polynomial approximation:

\proclaim Theorem.
Let $f\in C[-1,1\,]$ and define $\varphi\in C^{2\pi}$
by $\varphi(\theta)=f(\cos\theta)$.  Then,
$$\Min_{\strut p\in{\cal P}_n}\Vert f-p\Vert
	= \Min_{\strut T\in{\cal T}_n}\Vert \varphi-T\Vert.$$

\proof
Suppose that $p^*(x)=\sum_{k=0}^na_kx^k$ is the best 
approximation to $f$ out of ${\cal P}_n$.  Then,
$\widehat T(\theta)=p^*(\cos\theta)$ is in ${\cal T}_n$ and, clearly, 
$$\max_{\strut-1\le x\le1}|f(x)-p^*(x)|
	= \max_{\strut 0\le\theta\le2\pi}|f(\cos\theta)-p^*(\cos\theta)|.$$
Thus, 
$\Vert f-p\Vert=\Vert\varphi-\widehat T\Vert
	\ge\Min_{\strut T\in{\cal T}_n}\Vert \varphi-T\Vert$.

On the other hand, since $\varphi$ is {\sl even}, we know that $T^*$,
its best approximation out of ${\cal T}_n$, is also even.  Thus,
$T^*(\theta)=q(\cos\theta)$ for some algebraic polynomial $q\in{\cal P}_n$.
Consequently, 
$\Vert\varphi-T^*\Vert=\Vert f-q\Vert
	\ge\Min_{\strut p\in{\cal P}_n}\Vert f-p\Vert$.~\qed

\noindent{\bf Remarks}

\item{1.}
Once we know that 
$\Min_{\strut p\in{\cal P}_n}\Vert f-p\Vert
	= \Min_{\strut T\in{\cal T}_n}\Vert \varphi-T\Vert$, it
follows that we must also have $T^*(\theta)=p^*(\cos\theta)$.

\item{2.}
Each {\sl even\/} $\varphi\in C^{2\pi}$ corresponds to an
$f\in C[-1,1\,]$ by $f(x)=\varphi(\arccos x)$ and, of course,
the conclusions of the Theorem and of Remark 1 hold in this 
case, too.  

\item{3.}
Whenever we speak of even trig polynomials, the 
Chebyshev polynomials are lurking somewhere in the background.
Indeed, let $T(\theta)$ be an even trig polynomial, write
$x=\cos\theta$, as usual, and consider the following cryptic
equation:
$$T(\theta)=\sum_{k=0}^na_k\cos kx=\sum_{k=0}^na_kT_k(\cos\theta)
	=\sum_{k=0}^na_kT_k(x)=\sum_{k=0}^nb_kx^k=p(x).$$




\bye


%%  end of chapter-04.tex


