%% 3. Chebyshev polynomials and series ATAPformats %% % % Throughout applied mathematics, one encounters three closely analogous % canonical settings associated with the names of Fourier, Laurent, and % Chebyshev. In fact, if we impose certain symmetries in the Fourier and % Laurent cases, the analogies become equivalences. % The Chebyshev setting is the one of central interest in this book, % concerning a variable $x$ and a function $f$ defined on $[-1,1]$: % $$\hbox{\em Chebyshev:}\quad x\in [-1,1], \quad f(x)\approx \sum_{k=0}^n % a_kT_k(x). \eqno (3.1)$$ % Here $T_k$ is the $k$th Chebyshev polynomial, which we shall discuss in % a moment. % For the equivalent Laurent problem, let $z$ be a % variable that ranges over the unit circle in the complex plane. % Given $f(x)$, define a transplanted function $F(z)$ on the % unit circle by the condition $F(z)=f(x)$, where % $x = (z+z^{-1})/2$ as in (2.1). Note that this means that there are % two values of $z$ for each value of $x$, and $F$ satisfies the % symmetry property $F(z) = F(z^{-1})$. The series now involves a % polynomial in both $z$ and $z^{-1}$, known as a {\em Laurent polynomial:} % $$\hbox{\em Laurent:}\quad |z|=1, \quad F(z) = F(z^{-1}) \approx % {1\over 2} \sum_{k=0}^n % a_k(z^k + z^{-k}). \eqno (3.2)$$ % For the equivalent Fourier problem, let $\theta$ be a variable % that ranges over $[-\pi,\pi]$, which we regard as a $2\pi$-periodic domain. % Transplant $f$ and $F$ to a function ${\cal F}$ defined % on $[-\pi,\pi]$ by setting ${\cal F}(\theta) = F(e^{i\theta}) = % f(\cos(\theta))$ as in (2.2). Now we have a 1-to-1 correspondence % $z = e^{i\theta}$ between $\theta$ and $z$ and a 2-to-1 % correspondence between $\theta$ and $x$, with the symmetry % ${\cal F}(\theta) = {\cal F}(-\theta)$, and the series is a % trigonometric polynomial: % $$\hbox{\em Fourier:} \quad \theta\in[-\pi,\pi], \quad{\cal F}(\theta) = % {\cal F}(-\theta) \approx {1\over 2} \sum_{k=0}^n % a_k(e^{ik\theta} + e^{-ik\theta}). \eqno (3.3)$$ % One can carry (3.1)--(3.3) further by introducing canonical systems % of grid points in the three settings. We have already seen % the $(n+1)$-point Chebyshev grid, % $$\hbox{\em Chebyshev points:}\quad x_j = \cos(\kern .5pt j\pi/n), \quad 0\le j \le n, % \eqno (3.4)$$ % and we have interpreted these in terms of the $(2n)$th roots of % unity: % $$\hbox{\em Roots of unity:}\quad z_j = e^{ij\pi/n}, \quad -n+1\le j \le n. % \eqno (3.5)$$ % These grids are transplants of the set of % $2n$ equispaced points in $[-\pi,\pi]$: % $$\hbox{\em Equispaced points:}\quad \theta_j = j\pi/n, \quad -n+1\le j \le n. % \eqno (3.6)$$ % %% % All three of these settings are unassailably important. % Real analysts cannot do without Fourier, complex analysts cannot % do without Laurent, and numerical analysts cannot do without Chebyshev. % Moreover, the mathematics of the connections between the three frameworks is beautiful. % But all this symmetry presents an % expository problem. Without a doubt, a fully % logical treatment should consider $x$, $z$ and $\theta$ in parallel. % Each theorem should appear in three forms. Each application should be % one of a trio. %% % It was on this basis that I started to write a book in 2008. % The symmetries were elegant, but as the chapters accumulated, I came % to realize that this would be a very long book and not a lovable % one. The excellent logic was just a dead weight. The next year, I % started again with the decision that the book would focus on $x\in [-1,1]$. % This is the setting closest to much of approximation % theory and numerical analysis, and it has a further special feature: % it is the one least familiar to people. Nobody is surprised if % you compute a Fourier transform of a million points, but the % fact that you can compute a polynomial interpolant through a % million Chebyshev points surprises people indeed. %% % Here then is the mathematical plan for this book. Our central interest % will be the approximation of functions $f(x)$ on $[-1,1]$. When it % comes to deriving formulas and proving theorems, however, we shall % generally transplant to $F(z)$ on the unit circle so as to make the tools % of complex analysis most conveniently available. %% % Now let us turn to the definitions, already implicit in (3.1)--(3.3). % The $k\kern -3pt$ % th _Chebyshev polynomial_ can be defined as the real part of the function % $z^k$ on the unit circle: %% % \vskip -1em % $$x = \hbox{Re}(z) = {\textstyle{1\over 2}} (z+z^{-1}) % = \cos \theta, \quad \theta = \cos^{-1}x, \eqno (3.7)$$ % \vspace{-0.5em} % $$T_k(x) = \hbox{Re}(z^k) = {\textstyle{1\over 2}}(z^k + z^{-k}) % = \cos(k\theta). \eqno (3.8)$$ % \vspace{-1.5em} %% % (Chebyshev polynomials were introduced % by Chebyshev in the 1850s, though without the connection to the variables % $z$ and $\theta$ [Chebyshev 1854 & 1859]. The label $T$ was apparently % chosen by Bernstein, following French transliterations such as % Tchebischeff.'') The Chebyshev polynomials are a family of orthogonal % polynomials with respect to a certain weight function (Exercise 3.7), but % we shall not make much use of orthogonality until Chapters 17--19. %% % % It follows from (3.8) that $T_k$ satisfies $-1\le T_k(x) \le 1$ for % $x\in[-1,1]$ and takes alternating values $\pm 1$ at the $k+1$ Chebyshev % points. What is not obvious is that $T_k$ is a polynomial. We % can verify this property by the computation % $${\textstyle{1\over 2}}(z+z^{-1})(z^k + z^{-k}) % = {\textstyle{1\over 2}}(z^{k+1}+z^{-k-1}) % + {\textstyle{1\over 2}}(z^{k-1}+z^{-k+1})$$ % for any $k\ge 1$, that is, % $$2xT_k(x) = T_{k+1}(x) + T_{k-1}(x), \eqno (3.9)$$ % or in other words % $$T_{k+1}(x) = 2xT_k(x) - T_{k-1}(x). \eqno (3.10)$$ % \vspace{-1.5em} %% % By induction, this three-term recurrence relation implies that for each % $k\ge 1$, $T_k$ is a polynomial of degree exactly $k$ with leading % coefficient $2^{k-1}$. In Chapters 18 and 19 the coefficients of this recurrence % will be taken as the entries of a colleague matrix,'' whose eigenvalues % can be computed to find roots of polynomials or quadrature nodes. %% % % The Chebfun command \verb|chebpoly(n)| returns the chebfun corresponding % to $T_n$.\footnote{The name of the software system is Chebfun, with a % capital C. A representation of a particular function in Chebfun is % called a chebfun, with a lower-case c.} Here for example are % $T_1,\dots,T_6$: % %% % \vskip -2em FS = 'fontsize'; for n = 1:6 T{n} = chebpoly(n); subplot(3,2,n), plot(T{n}), axis([-1 1 -1 1]) text(.7,.41,'T',FS,10), text(.78,.24,int2str(n),FS,7) end %% % \vskip 1pt %% % These plots do not show the Chebyshev points, which are the extremes of % each curve: thus the numbers of Chebyshev points in the six plots are 2, % 3, 4, 5, 6, and 7. %% % % Here are the coefficients of these polynomials with respect to the % monomial basis $1,x,x^2,\dots.$\ \ As usual, Matlab orders coefficients % from highest degree down to degree zero. % %% % \vskip -2em for n = 1:6, disp(poly(T{n})), end %% % So, for example, $$T_5(x) = 16x^5 - 20 x^3 + 5x.$$ The monomial basis % is familiar and comfortable, but you should never use it for numerical % work with functions on an interval. Use the Chebyshev basis instead % (Exercise 3.8). (If the domain is $[a,b]$ rather than $[-1,1]$, the % Chebyshev polynomials must be scaled accordingly, and Chebfun does this % automatically when it works on other intervals.) For example, $x^5$ has % the Chebyshev expansion $$x^5 = {5\over 80}T_5(x) + {5\over 16} T_3(x) % + {5\over 8} T_1(x).$$ We can calculate such expansion coefficients by % using the command |chebpoly(p)|, where $p$ is the chebfun whose % coefficients we want to know: %% % \vskip -2em format short, x = chebfun('x'); chebpoly(x.^5) %% % Any polynomial $p$ can be written uniquely like this as a finite % Chebyshev series: the functions $T_0(x), T_1(x), \dots , T_n(x)$ form a % basis for ${\cal P}_n$. Since $p$ is determined by its values at % Chebyshev points, it follows that there is a one-to-one linear mapping % between values at Chebyshev points and Chebyshev expansion coefficients. % This mapping can be % applied in $O(n\log n)$ operations with the aid of the Fast Fourier % Transform (FFT) or the Fast Cosine Transform, a crucial observation % for practical work that was perhaps % first made by Ahmed and Fisher and Orzsag around 1970 [Ahmed & Fisher % 1970, Orszag 1971a and 1971b, Gentleman 1972b, Geddes 1978]. This is % what Chebfun does every time it constructs a chebfun. We shall not give % details. %% % Just as a polynomial $p$ has a finite Chebyshev series, a more general % function $f$ has an infinite Chebyshev series. Exactly what kind of % more general function'' can we allow? For an example like $f(x) = e^x$ % with a rapidly converging Taylor series, everything will surely be % straightforward, but what if $f$ is merely differentiable rather than % analytic? Or what if it is continuous but not differentiable? Analysts % have studied such cases carefully, identifying exactly what degrees of % smoothness correspond to what kinds of convergence of Chebyshev series. % We shall not concern ourselves with trying to state the sharpest possible % result but will just make a particular assumption that covers most % applications. We shall assume that $f$ is _Lipschitz continuous_ on % $[-1,1]$. Recall that this means that there is a constant $C$ such that % $|f(x) - f(y)| \le C |x-y|$ for all $x,y \in [-1,1]$. Recall also that a % series is _absolutely convergent_ if it remains convergent if each term % is replaced by its absolute value, and that this implies that one can % reorder the terms arbitrarily without changing the result. Such matters % are discussed in analysis textbooks such as [Rudin 1976]. %% % Here is our basic theorem about Chebyshev series and their coefficients. %% % *Theorem 3.1. Chebyshev series.* _If $f$ is Lipschitz continuous on % $[-1,1]$, it has a unique representation as a Chebyshev series,_ %% % \em \vspace{-1.5em} % $$f(x) = \sum_{k=0}^\infty a_k T_k(x), \eqno (3.11)$$ % which is absolutely and uniformly convergent, % and the coefficients are given for $k\ge 1$ by the formula % $$a_k = {2\over\pi} \int_{-1}^1 {f(x) T_k(x)\over \sqrt{1-x^2}} dx, % \eqno (3.12)$$ % and for $k=0$ by the same formula with the factor $2/\pi$ changed to $1/\pi$. % \vspace{-.5em} %% % _Proof._ % Formula (3.12) will come from the Cauchy integral formula, and to make % this happen, we begin by transplanting $f$ to $F$ on the unit circle as described above: % $F(z) = F(z^{-1}) = f(x)$ with $x = \hbox{Re}\,z = (z+z^{-1})/2$. % To convert between integrals in $x$ and $z$, we have to % convert between $dx$ and $dz$: % $$dx = \textstyle{1\over 2} (1-z^{-2}) \, dz = % \textstyle{1\over 2} z^{-1}(z-z^{-1}) \, dz.$$ % Since % $${\textstyle{1\over 2}} (z-z^{-1}) = i\kern .7pt\hbox{Im}\, z % = \pm i \sqrt{1-x^2},$$ % this implies % $$dx = \pm i\kern .7pt z^{-1}\sqrt{1-x^2} \, dz.$$ % In these equations % the plus sign applies for $\hbox{Im}\, z\ge 0$ and % the minus sign for $\hbox{Im}\, z\le 0$. %% % These formulas have implications for smoothness. Since $\sqrt{1-x^2} \le % 1$ for all $x \in [-1,1]$, they imply that if $f(x)$ is Lipschitz % continuous, then so is $F(z)$. By a standard result in Fourier analysis, % this implies that $F$ has a unique representation as an absolutely and % uniformly convergent Laurent series on the unit circle, % $$F(z) = {1\over 2} \sum_{k=0}^\infty a_k (z^k + z^{-k}) % = \sum_{k=0}^\infty a_k T_k(x).$$ % Recall that a _Laurent series_ is an infinite series in both positive and % negative powers of $z$, and that if $F$ is analytic, such a series % converges in the % interior of an annulus. A good treatment of Laurent series for % analytic functions can be found % in [Markushevich 1985]; see also other complex variables texts such as % [Hille 1973, Priestley 2003, Saff & Snider 2003]. %% % % The $k$th Laurent coefficient of a Lipschitz continuous function $G(z) = % \sum_{k=-\infty}^\infty b_k z^k$ on the unit circle can be computed by % the Cauchy integral formula, % $$b_k={1\over 2\pi i}\int_{|z|=1}z^{-1-k}G(z)\,dz.$$ % (We shall make more substantial use of the Cauchy integral formula in % Chapters 11--12.) The notation $|z|=1$ indicates that the contour % consists of the unit circle traversed once in the positive % (counterclockwise) direction. Here we have a function $F$ with the % special symmetry property $F(z) = F(z^{-1})$, and we have also introduced % a factor $1/2$ in front of the series. Accordingly, we % can compute the coefficients $a_k$ from either of two contour integrals, % $$a_k={1\over\pi i}\int_{|z|=1}z^{-1+k}F(z)\,dz % ={1\over\pi i}\int_{|z|=1}z^{-1-k}F(z)\,dz, \eqno (3.13)$$ % with $\pi i$ replaced by $2\pi i$ for $k=0$. % %% % % In particular, we can get a formula for $a_k$ that is symmetric % in $k$ and $-k$ by combining the two integrals like this: % $$a_k={1\over 2\pi i}\int_{|z|=1}(z^{-1+k}+z^{-1-k})F(z)\,dz = {1\over \pi i} % \int_{|z|=1} z^{-1}\,T_k(x) F(z) \,dz, \eqno (3.14)$$ % with $\pi i$ replaced by $2\pi i$ for $k=0$. Replacing $F(z)$ by $f(x)$ % and $z^{-1} dz$ by $-i\,dx/(\pm \sqrt{1-x^2})$ gives % $$a_k = -{1\over \pi} \int_{|z|=1} % {f(x) T_k(x)\over \pm \sqrt{1-x^2}} \,dx,$$ with $\pi$ replaced by % $2\pi$ for $k=0$. We have now almost entirely converted to the $x$ % variable, except that the contour of integration is still the circle % $|z|=1$. When $z$ traverses the circle all the way around in the % positive direction, $x$ decreases from $1$ to $-1$ and then increases % back to $1$ again. At the turning point $z=x=-1$, the $\pm$ sign attached % to the square root switches from $+$ to $-$. Thus instead of cancelling, % the two traverses of $x\in[-1,1]$ contribute equal halves to $a_k$. % Converting to a single integration from $-1$ to $1$ in the $x$ variable % multiplies the integral by $-1/2$, hence multiplies the formula for $a_k$ % by $-2$, giving (3.12). % $~\hbox{\vrule width 2.5pt depth 2.5 pt height 3.5 pt}$ % %% % We now know that any function $f$, so long as it is Lipschitz % continous, has a Chebyshev series. % Chebfun represents a function as a finite series of some degree $n$, % storing both its values at Chebyshev % points and also, equivalently, their Chebyshev coefficients. How does it % figure out the right value of $n$? Given a set of $n+1$ samples, it % converts the data to a Chebyshev expansion of degree $n$ and examines the % resulting Chebyshev coefficients. If several of these in a row fall % below a relative level of approximately $10^{-15}$, then the grid is % judged to be fine enough. For example, here are the Chebyshev % coefficients of the chebfun corresponding to $e^x$: %% % \vskip -2em f = exp(x); a = chebpoly(f); format long, a(end:-1:1)' %% % Notice that the last coefficient is about at the level of machine precision. %% % For complicated functions it is often more interesting to plot the % coefficients than to list them. For example, here is a function with a % number of wiggles: %% % \vskip -2em f = sin(6*x) + sin(60*exp(x)); clf, plot(f), title('A function with wiggles',FS,9) %% % \vskip 1pt %% % If we plot the absolute values of the Chebyshev coefficients, % here is what we find: %% % \vskip -2em a = chebpoly(f); semilogy(abs(a(end:-1:1)),'m') grid on, title('Absolute values of Chebyshev coefficients',FS,9) %% % \vskip 1pt %% % One can explain this plot as follows. Up to degree about $k=80$, a % Chebyshev series cannot resolve $f$ much at all, for the oscillations % occur on too short wavelengths. After that, the series begins to % converge rapidly. By the time we reach $k=150$, the accuracy is about 15 % digits, and the computed Chebyshev series is truncated there. We can find % out exactly where the truncation took place with the command |length(f)|: %% % \vskip -2em length(f) %% % This tells us that the chebfun is a polynomial interpolant % through 151 points, that is, of degree 150. %% % Without giving all the engineering details, here is a fuller % description of how Chebfun constructs its approximation. First it % calculates the polynomial interpolant through the function sampled at 9 % Chebyshev points, i.e., a polynomial of degree 8, and checks whether the % Chebyshev coefficients appear to be small enough. For the example just % given, the answer is no. Then it tries 17 points, then 33, then 65, and % so on. In this case Chebfun judges at 257 points that the Chebyshev % coefficients have fallen to the level of rounding error. At this % point it truncates the tail of terms deemed to be negligible, leaving a % series of 151 terms (Exercise 3.13). The corresponding degree 150 % polynomial is then evaluated at 151 Chebyshev points via FFT, and these % 151 numbers become the data defining this particular chebfun. Engineers % would say that the signal has been {\em downsampled\/} from 257 points to % 151. %% % For another example we consider a function with two spikes: %% % \vspace{-2em} f = 1./(1+1000*(x+.5).^2) + 1./sqrt(1+1000*(x-.5).^2); clf, plot(f), title('A function with two spikes',FS,9) %% % \vskip 1pt %% % Here are the Chebyshev coefficients of the chebfun. This time, instead % of |chebpoly| and |semilogy|, we execute the special command % |chebpolyplot|, which has the same effect. %% % \vskip -2em chebpolyplot(f,'m'), grid on title('Absolute values of Chebyshev coefficients',FS,9) %% % \vskip 1pt %% % Note that although it is far less wiggly, this function needs six times % as many points to resolve as the previous one (Exercise 3.13). % We shall explain these polynomial degrees in Chapter 8. %% % Chebyshev interpolants are effective for complex functions (still defined % on a real interval) as well as real ones. Here, for example, is a % complex function that happens to be periodic, though the Chebyshev % representation does not take advantage of this fact. %% % \vskip -2em f = (3+sin(10*pi*x)+sin(61*exp(.8*sin(pi*x)+.7))).*exp(1i*pi*x); %% % A plot shows the image of $[-1,1]$ under $f$, which appears complicated: %% % \vskip -2em plot(f,'linewidth',0.6,'color',[0 .8 0]), axis equal off %% % \vskip 1pt %% % Yet the degree of the polynomial is not so high: %% % \vskip -2em length(f) %% % People often ask, is there anything special about Chebyshev points and % Chebyshev polynomials? Could we equally well interpolate in other points % and expand in other sets of polynomials? From an approximation point of % view, the answer is yes, and in particular, Legendre points and Legendre % polynomials have much the same power for representing a general function % $f$, as we shall see in Chapters 17--19. Legendre points and polynomials % are neither much better than Chebyshev for approximating functions, nor % much worse; they are essentially the same. One can improve upon both % Legendre and Chebyshev, shrinking the number of sample points needed to % represent a given function by a factor of up to $\pi/2$, but to do so one % must leave the class of polynomials. See Chapter 22. %% % Nevertheless, there is a big advantage of Chebyshev over Legendre points, % and this is that one can use the FFT to go from point values to % coefficients and back again. There are algorithms that make such % computations practicable for Legendre interpolants too [Piessens 1974, % Alpert & Rokhlin 1991, Dutt, Gu & Rokhlin 1996, Potts, % Steidl & Tasche 1998, Iserles 2011]---see also Theorem 19.6 of % this book---but Chebyshev remains the easy case. %% % % \begin{displaymath} % \framebox[4.7in][c]{\parbox{4.5in}{\vspace{2pt}\sl % {\sc Summary of Chapter 3.} % The Chebyshev polynomial $T_k(x)$ is an analogue for % $[-1,1]$ of the monomial $z^k$ on the unit circle. % Each Lipschitz continuous function $f$ on $[-1,1]$ has % an absolutely and uniformly convergent % Chebyshev series, that is, an expansion % $f(x) = a_0T_0(x) + a_1T_1(x) + \dots .$\vspace{2pt}}} % \end{displaymath} % %% % \smallskip\small\parskip=2pt % {\bf Exercise 3.1. Monomial and Chebyshev coefficients.} Let $p\in {\cal % P}_n$ have coefficient vectors $a = (a_0, a_1,\dots , a_n)^T$ for a % Chebyshev series and $b = (b_0, b_1,\dots , b_n)^T$ for a series in the % monomials $1, x, \dots , x^n$. Show that $a$ and $b$ are related by $Aa % = b$, where $A$ is an upper-triangular matrix, whose entries you should % describe precisely, though you don't have to give % explicit formulas for them. % Prove that any $p\in {\cal P}_n$ has uniquely defined % coefficient vectors $a$ and $b$ for both representations. % \par % {\bf Exercise 3.2. A Chebyshev coefficient.} Use Chebfun to determine % numerically the coefficient of $T_5$ in the Chebyshev expansion of % $\tan^{-1}(x)$ on $[-1,1]$. % \par % {\bf Exercise 3.3. Chebyshev coefficients and rat''.} (a) Use Chebfun % to determine numerically the coefficients of the Chebyshev series for $1 % + x^3 + x^4$. By inspection, identify these rational numbers. Use the % Matlab command {\tt [n,d] = rat(c)} to confirm this. (b) Use Chebfun and % {\tt rat} to make good guesses as to the Chebyshev coefficients of $x^7/7 % + x^9/9$. (Of course it is not hard to figure them out analytically.) % \par % {\bf Exercise 3.4. Dependence on wave number.} % (a) Calculate the length % $L(k)$ of the chebfun corresponding to % $f(x) = \sin(kx)$ on $[-1,1]$ for $k = 1,2,4,8,\dots,2^{10}$. % (You can do this elegantly by defining a Matlab % anonymous function {\tt f = @(k)}....) % Make a loglog plot of $L(k)$ as a function of $k$ and comment % on the result. % (b) Do the same for $g(x) = 1/(1+(kx)^2)$. % \par % {\bf Exercise 3.5. Chebyshev series of a complicated function.} % (a) Make chebfuns of the three functions % $f(x) = \tanh(x)$, % $g(x) = 10^{-5}\tanh(10x)$, % $h(x) = 10^{-10}\tanh(100x)$ on $[-1,1]$, and call {\tt chebpolyplot} % to show their Chebyshev coefficients. Comment on the results. % (b) Now define $s = f+g+h$ and comment on the result of % {\tt chebpolyplot} applied to $s$. Chebfun does not automatically % chop the tail of a Chebyshev series obtained by summation, but applying the {\tt simplify} % command will do this. What happens with % {\tt chebpolyplot(simplify(s))}? % \par % {\bf Exercise 3.6. Chebyshev series of \boldmath $\hbox{\bf sign}(x)$ and $|x|$} [Bernstein 1914]. % Derive the following Chebyshev series coefficients by using the first equality in (3.14). % (a) For $f(x) = \hbox{sign}(x)$, $a_k = 0$ for $k$ even and % $a_k = (4/\pi)(-1)^{k-1}/k$ for $k$ odd. % (b) For $f(x) = |x|$, $a_k = 0$ for $k$ odd, $a_0 = 2/\pi$, and % $a_k = (4/\pi)(-1)^{(k/2)}/(1-k^2)$ for $k\ge 2$ even. % \par % {\bf Exercise 3.7. Orthogonality of Chebyshev polynomials.} Equation % (3.12) gives the Chebyshev coefficient $a_k$ of $f$ by integration of $f$ % against just the single Chebyshev polynomial $T_k$. This formula implies % an orthogonality property for $\{T_j\}$ involving a weighted integral. % State exactly what this orthogonality property is and show carefully how % it follows from the equations of this chapter. % \par % {\bf Exercise 3.8. Conditioning of the Chebyshev basis.} Although the % Chebyshev polynomials are not orthogonal with respect to the standard % unweighted inner product, they are close enough to orthogonal % to provide a well-behaved % basis. Set {\tt T = chebpoly(0:10)} and explore the Chebfun % quasimatrix'' that results with commands like {\tt size(T)}, {\tt % spy(T)}, {\tt plot(T)}, {\tt svd(T)}. Explain the meaning of {\tt T} (you % may find Chapter 6 of the Chebfun Guide helpful) and determine the % condition number of this basis with {\tt cond(T)}. (b) Now construct the % corresponding quasimatrix of monomials by executing {\tt x = % chebfun('x')}; {\tt M = T}; \verb|for j = 0:10, M(:,j+1) = x.^j; end|. % What is the condition number of {\tt M}? (c) Produce a plot of these two % condition numbers for quasimatrices whose columns span ${\cal P}_n$ % over $[-1,1]$ for $n = % 0,1,\dots, 10$. (d) What happens to the condition numbers if $M$ is % constructed from monomials on $[0,1]$ rather than $[-1,1]$ via {\tt x = % chebfun('x',[0,1])}? % \par % {\bf Exercise 3.9. Derivatives at endpoints.} Prove from (3.10) that the % derivatives of the Chebyshev polynomials satisfy $T_n'(1) = n^2$ for each % $n\ge 0$. ({\em Markov's inequality} asserts that for any $p\in {\cal % P}_n$, $\|p'\| \le n^2 \|p\|$, where $\|\cdot\|$ is the supremum norm.) % \par % {\bf Exercise 3.10. Odd and even functions.} Show that if $f$ is an odd % function on $[-1,1]$, its Chebyshev coefficients of even order are zero; % show similarly that if $f$ is even, its odd order coefficients are zero. % \par % {\bf Exercise 3.11. A function neither even nor odd.} Apply % \verb|chebpolyplot| to the chebfun for $f(x) = \exp(x)/(1+10000x^2)$. Why % does the plot have the appearance of a stripe? % \par % {\bf Exercise 3.12. Extrema and roots of Chebyshev polynomials.} % Give formulas for the extrema and roots of $T_n$ in $[-1,1]$. % \par % {\bf Exercise 3.13. Chebyshev coefficients and machine precision.} By a % command like \verb|f = chebfun('exp(x)',np)|, one can force Chebfun to % produce a chebfun of length \verb|np| (i.e., degree $\verb|np|-1$) rather % than determine the length automatically. (a) Do this for the function % with wiggles'' of this section with $\verb|np|=257$, and comment on how % the {\tt chebpolyplot} % result differs from that shown in the text. (b) Likewise for the % function with two spikes'' with $\verb|np|=2049$. % \par % {\bf Exercise 3.14. Chebyshev series for a simple pole.} % (a) Let $t$ be a complex number with $|t|<1$ and define % $F(z) = (z-t)^{-1} + (z^{-1}-t)^{-1}$. What is the Laurent series for $F\kern .5pt$? % (b) For the same $t$, show further that % $$1+2\sum_{k=1}^\infty t^k \kern .7pt T_k(x) = {1-t^2\over % 1-2\kern .5pt tx+t^2}. \eqno (3.15)$$ % (This formula can be interpreted as a generating function for % the Chebyshev polynomials.) % (c) Let $a\not\in [-1,1]$ be a real or complex number and let $t$ be % a real or complex number with $|t|<1$ such that $(t+t^{-1})/2 = a$. % Show that % $${1\over x-a} = {2\over t-t^{-1}}\left[ % 1+2\sum_{k=1}^\infty t^k \kern .7pt T_k(x)\right]. \eqno (3.16)$$ % {\bf Exercise 3.15. Chebyshev series of \boldmath$e^{ax}$.} % It can be shown that the Chebyshev series of $e^{ax}$ is % $$e^{ax} = 2\sum_{k=0}^\infty {}' I_k(a) T_k(x) , \eqno (3.17)$$ % where $I_k$ is the modified Bessel function of the first kind and % the prime indicates that the term $k=0$ is to be multiplied by $1/2$. % Derive the Chebyshev series for $\sinh(ax)$ and $\cosh(ax)$. % \par