%% 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_00$. Now consider the (uniformly) continuous function $\varphi=f-p$. We may partition $[\,a,b\,]$ by way of $a=t_0E/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 $m0$ 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, $e0$ 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_0n$. \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 $k0$.\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\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