%%  cheb-numerical.tex
%%  Approximation Theory: 
%%  Simple applications of Chebyshev 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 = {Chebyshev Polynomials in Practice}

\centerline{\hfil\tf Chebyshev Polynomials in Practice\hfil}
\vskip-\baselineskip
\line{\sc Math 680 \hfil 7/11/94}

\noindent
The following examples are cribbed from the book
{\it Chebyshev Polynomials}, by L.\ Fox and 
I.\ B.\ Parker (Oxford University Press, 1968).

\noindent
As we've seen, the Chebyshev polynomals 
can be generated by a recurrence relation.  
By reversing the procedure, we could solve for  
$x^n$  in terms of  $T_0, T_1,\ldots, T_n$
(we'll do this calculation in class). 
Here are the first few terms in each of these
relations:

\setbox1 = \vbox{\hsize = 2.5 true in\parindent = 0pt%
$$\eqalign{%
	T_0(x)&=1\cr
	T_1(x)&=x\cr
	T_2(x)&=2x^2-1\cr
	T_3(x)&=4x^3-3x\cr
	T_4(x)&=8x^4-8x^2+1\cr
	T_5(x)&=16x^5-20x^3+5x\cr
}$$}

\setbox2 = \vbox{\hsize = 2.8 true in\parindent = 0pt%
$$\eqalign{%
	1&=T_0(x)\cr
	x&=T_1(x)\cr
	x^2&=(T_0(x)+T_1(x))/2\cr
	x^3&=(3\,T_1(x)+T_3(x))/4\cr
	x^4&=(3\,T_0(x)+4\,T_2(x)+T_4(x))/8\cr
	x^5&=(10\,T_1(x)+5\,T_3(x)+T_5(x))/16\cr
}$$}

\line{\hfill\box1\qquad\qquad\box2\hfill}

\vskip-\baselineskip

\noindent
Note the separation of even and odd terms in each
case.  Writing ordinary, garden variety
polynomials in their equivalent Chebyshev form has
some distinct advantages for numerical
computations.  Here's why:
$$1 - x + x^2 - x^3 + x^4  =  
	{15\over6}\,T_0(x)-{7\over4}\,T_1(x)+T_2(x)
	-{1\over4}\,T_3(x)+{1\over8}\,T_4(x)$$
(after some simplification).  Now we see at once
that we can get a cubic approximation to 
$1 - x + x^2 - x^3 + x^4$ on $[-1,1\,]$ 
with error at most  $1/8$  by simply dropping the
$T_4$ term on the right-hand side (since $|T_4(x)|\le 1$), 
whereas simply using $1 - x + x^2 - x^3$ 
as our cubic approximation could cause an error as big as  $1$!  
Pretty slick!  This gimmick of truncating the equivalent
Chebyshev form is called {\sl economization}.

\noindent
As a second example we note that a polynomial with
small norm on  $[-1,1\,]$  may have
annoyingly large coefficients:
$$\eqalign{%
(1 - x^2)^{10} &= 1 - 10 x^2 + 45Êx^4 - 120Êx^6 + 210Êx^8 - 252Êx^{10}\cr
	&\qquad\qquad\qquad
	{} + 210Êx^{12} - 120Êx^{14} + 45Êx^{16} - 10Êx^{18} + x^{20}\cr
}$$
but in Chebyshev form (look out!):
$$\eqalign{%
(1 - x^2)^{10} &=  {1\over 524{,}288} \,
	\bigl\{ 92{,}378 \,T_0(x) - 167{,}960 \,T_2(x) +
	125{,}970 \,T_4(x) - 77{,}520 \,T_6(x)\cr
	&\qquad\qquad
	{}  +ÊÊÊÊ38{,}760 \,T_8(x) - 15{,}504 \,T_{10}(x) 
	+ 4{,}845\, T_{12}(x) - 1{,}140\, T_{14}(x)\cr
	&\qquad\qquad\qquad
	{}+ 190 \,T_{16}(x) - 20 \,T_{18(x)} + T_{20}(x) 
	\bigr\}\cr
}$$
The largest coefficient is now only about  0.3, 
and the omission of the last three terms 
produces a maximum error of about  0.0004.  Not
bad.  

\noindent
As a last example, consider the Taylor
polynomial 
$e^x=\sum_{k=0}^nx^k/k!+x^{n+1}e^\xi/(n+1)!$
(with remainder), 
where $-1\le x$, $\xi\le1$.  Taking  $n = 6$, the truncated 
series has error no greater than  $e/7!\approx  0.0005$.  
But if we ``economize'' the first six terms, then:
$$\eqalign{%
\sum_{k=0}^6x^k/k  &=  1.26606 \,T_0(x) + 1.13021 \,T_1(x) + 
	0.27148 \,T_2(x) + 0.04427 \,T_3(x)\cr
	&\qquad\qquad{}
    + 0.00547 \,T_4(x) + 0.00052 \,T_5(x) + 0.00004 \,T_6(x).\cr
}$$
The initial approximation already has an error of
about  $0.0005$, so we can certainly drop the  $T_6$
term without any additional error.  Even dropping
the  $T_5$  term causes an error of no more than  $0.001$
(or thereabouts).  The resulting approximation has a far smaller
error than the corresponding truncated Taylor series: 
$e/5!\approx 0.023$.

\noindent
The approach used in our last example has the
decided disadvantage that we must first decide
where to truncate the Taylor series---which might
converge very slowly.  A better approach would be
to write  $e^x$  as a series involving Chebyshev
polynomials directly.  That is, if possible, we
want to write $e^x=\sum_{k=0}^\infty a_kT_k(x)$.  
If the  $a_k$'s  are absolutely summable, it will be very
easy to estimate any truncation error.  We'll get
some idea on how to go about this when we talk
about ``least-squares'' approximation.  As it
happens, such a series is easy to find (it's
rather like a Fourier series), and its partial
sums are remarkably good uniform approximations. 

\bye 

In fact, for  continuous $f$ and any  $n< 400$,
we can never hope for more than one extra
decimal place of accuracy by using the best
polynomial of degree  $n$  in place the the  $n$-th 
partial sum of this Chebyshev series!


%%  end of cheb-numerical.tex