Evaluation of Functions part 9

The Chebyshev polynomial of degree n is denoted Tn (x), and is given by the explicit formulaThis 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
Nội dung trích xuất từ tài liệu:
Evaluation of Functions part 9190 Chapter 5. Evaluation of Functions5.8 Chebyshev Approximation The Chebyshev polynomial of degree n is denoted Tn (x), and is given bythe explicit formula visit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America). readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMs Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine- 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) Tn (x) = cos(n arccos x) (5.8.1)This may look trigonometric at first glance (and there is in fact a close relationbetween the Chebyshev polynomials and the discrete Fourier transform); however(5.8.1) can be combined with trigonometric identities to yield explicit expressionsfor Tn (x) (see Figure 5.8.1), T0 (x) = 1 T1 (x) = x T2 (x) = 2x2 − 1 T3 (x) = 4x3 − 3x (5.8.2) T4 (x) = 8x4 − 8x2 + 1 ··· Tn+1 (x) = 2xTn (x) − Tn−1 (x) n ≥ 1.(There also exist inverse formulas for the powers of x in terms of the Tn ’s — seeequations 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 0 i=j Ti (x)Tj (x) √ dx = π/2 i=j=0 (5.8.3) −1 1 − x2 π i=j=0 The polynomial Tn (x) has n zeros in the interval [−1, 1], and they are locatedat the points π(k − 1 ) 2 x = cos k = 1, 2, . . . , n (5.8.4) n In this same interval there are n + 1 extrema (maxima and minima), located at πk x = cos k = 0, 1, . . . , n (5.8.5) nAt 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 inpolynomial approximation of functions. 5.8 Chebyshev Approximation 191 1 T0 T1 T2 .5 visit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America). readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMs Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine- 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)Chebyshev polynomials T3 0 T6 −.5 T5 T4 −1 −1 −.8 −.6 −.4 −.2 0 .2 .4 .6 .8 1 x Figure 5.8.1. Chebyshev polynomials T0 (x) through T6 (x). Note that Tj has j roots in the interval (−1, 1) and that all the polynomials are bounded between ±1. The Chebyshev polynomials satisfy a discrete orthogonality relation as well as the continuous ...