190 Chapter 5.Evaluation of Functions 5.8 Chebyshev Approximation The Chebyshev polynomial of degree n is denoted Tn(),and is given by the explicit formula Tn(x)=cos(n arccos x) (5.8.1) This may look trigonometric at first glance (and there is in fact a close relation between the Chebyshev polynomials and the discrete Fourier transform);however (5.8.1)can be combined with trigonometric identities to yield explicit expressions for Tn(r)(see Figure 5.8.1), T(x)=1 Cam Ti(x)=z T2(x)=2x2-1 T3(x)=4x3-3z (5.8.2) 9 T4(x)=8x4-8x2+1 Press. 44 9 Programs Tn+1()=2xTn(z)-Tn-1()n>1. IENTIFIC (There also exist inverse formulas for the powers of x in terms of the Tn's-see equations5.11.2-5.11.3.) 6 The Chebyshev polynomials are orthogonal in the interval [-1,1]over a weight (1-x2)-1/2. In particular, T:(x)T;(r) i卡j i=j≠0 (5.8.3) /1-x2 Numerical 10-521 i=j=0 43126 The polynomial Tn(x)has n zeros in the interval [-1,1],and they are located 是 at the points (outside (k- k=1,2,.,n (5.8.4) In this same interval there are n+1 extrema (maxima and minima),located at COS k=0,1,n (5.8.5) At all of the maxima Tn(z)=1,while at all of the minima Tn(x)=-1; it is precisely this property that makes the Chebyshev polynomials so useful in polynomial approximation of functions.190 Chapter 5. Evaluation of Functions Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). 5.8 Chebyshev Approximation The Chebyshev polynomial of degree n is denoted T n(x), and is given by the explicit formula Tn(x) = cos(n arccos x) (5.8.1) This may look trigonometric at first glance (and there is in fact a close relation between the Chebyshev polynomials and the discrete Fourier transform); however (5.8.1) can be combined with trigonometric identities to yield explicit expressions for Tn(x) (see Figure 5.8.1), T0(x)=1 T1(x) = x T2(x)=2x2 − 1 T3(x)=4x3 − 3x T4(x)=8x4 − 8x2 + 1 ··· Tn+1(x)=2xTn(x) − Tn−1(x) n ≥ 1. (5.8.2) (There also exist inverse formulas for the powers of x in terms of the T n’s — see equations 5.11.2-5.11.3.) The Chebyshev polynomials are orthogonal in the interval [−1, 1] over a weight (1 − x2)−1/2. In particular,  1 −1 Ti(x)Tj (x) √ 1 − x2 dx = 0 i = j π/2 i = j = 0 π i = j = 0 (5.8.3) The polynomial Tn(x) has n zeros in the interval [−1, 1], and they are located at the points x = cos π(k − 1 2 ) n k = 1, 2,...,n (5.8.4) In this same interval there are n + 1 extrema (maxima and minima), located at x = cos πk n k = 0, 1,...,n (5.8.5) At all of the maxima Tn(x)=1, while at all of the minima Tn(x) = −1; it is precisely this property that makes the Chebyshev polynomials so useful in polynomial approximation of functions.