c5-8 (779492)
Текст из файла
190Chapter 5.Evaluation of Functions5.8 Chebyshev ApproximationThe Chebyshev polynomial of degree n is denoted Tn (x), and is given bythe explicit formula(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) = 1T1 (x) = xT2 (x) = 2x2 − 1T3 (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,Z1−1Ti (x)Tj (x)√dx =1 − x2(0π/2πi 6= ji=j=6 0i=j=0(5.8.3)The polynomial Tn (x) has n zeros in the interval [−1, 1], and they are locatedat the pointsx = cosπ(k − 12 )nk = 1, 2, . . . , n(5.8.4)In this same interval there are n + 1 extrema (maxima and minima), located atx = cosπknk = 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 inpolynomial approximation of functions.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit 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).Tn (x) = cos(n arccos x)1915.8 Chebyshev Approximation1T0T1T2Chebyshev polynomialsT30T6−.5T5T4−1−1−.8−.6−.4−.20x.2.4.6.81Figure 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 asthe continuous one (5.8.3): If xk (k = 1, . . . , m) are the m zeros of Tm (x) givenby (5.8.4), and if i, j < m, then(0Ti (xk )Tj (xk ) = m/2k=1mi 6= ji=j=6 0i=j=0mX(5.8.6)It is not too difficult to combine equations (5.8.1), (5.8.4), and (5.8.6) to provethe following theorem: If f(x) is an arbitrary function in the interval [−1, 1], andif N coefficients cj , j = 0, .
. . , N − 1, are defined byN2 Xf(xk )Tj (xk )Nk=1Nπj(k − 12 )π(k − 12 )2 Xcos=f cosNNNcj =(5.8.7)k=1then the approximation formulaf(x) ≈" N−1Xk=0#1ck Tk (x) − c02(5.8.8)Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit 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)..5192Chapter 5.Evaluation of Functionsk=0with the same cj ’s, computed from (5.8.7).
Since the Tk (x)’s are all boundedbetween ±1, the difference between (5.8.9) and (5.8.8) can be no larger than thesum of the neglected ck ’s (k = m, . . . , N − 1). In fact, if the ck ’s are rapidlydecreasing (which is the typical case), then the error is dominated by cm Tm (x),an oscillatory function with m + 1 equal extrema distributed smoothly over theinterval [−1, 1].
This smooth spreading out of the error is a very important property:The Chebyshev approximation (5.8.9) is very nearly the same polynomial as thatholy grail of approximating polynomials the minimax polynomial, which (among allpolynomials of the same degree) has the smallest maximum deviation from the truefunction f(x). The minimax polynomial is very difficult to find; the Chebyshevapproximating polynomial is almost identical and is very easy to compute!So, given some (perhaps difficult) means of computing the function f(x), wenow need algorithms for implementing (5.8.7) and (after inspection of the resultingck ’s and choice of a truncating value m) evaluating (5.8.9). The latter equation thenbecomes an easy way of computing f(x) for all subsequent time.The first of these tasks is straightforward.
A generalization of equation (5.8.7)that is here implemented is to allow the range of approximation to be between twoarbitrary limits a and b, instead of just −1 to 1. This is effected by a change of variabley≡x − 12 (b + a)12 (b − a)(5.8.10)and by the approximation of f(x) by a Chebyshev polynomial in y.#include <math.h>#include "nrutil.h"#define PI 3.141592653589793void chebft(float a, float b, float c[], int n, float (*func)(float))Chebyshev fit: Given a function func, lower and upper limits of the interval [a,b], and amaximum degree n, this routine computes the n coefficients c[0..n-1] such that func(x) ≈P[ n-1k=0 ck Tk (y)] − c0 /2, where y and x are related by (5.8.10).
This routine is to be used withmoderately large n (e.g., 30 or 50), the array of c’s subsequently to be truncated at the smallervalue m such that cm and subsequent elements are negligible.{int k,j;float fac,bpa,bma,*f;Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited.
To order Numerical Recipes books,diskettes, or CDROMsvisit 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).is exact for x equal to all of the N zeros of TN (x).For a fixed N , equation (5.8.8) is a polynomial in x which approximates thefunction f(x) in the interval [−1, 1] (where all the zeros of TN (x) are located). Whyis this particular approximating polynomial better than any other one, exact on someother set of N points? The answer is not that (5.8.8) is necessarily more accuratethan some other approximating polynomial of the same order N (for some specifieddefinition of “accurate”), but rather that (5.8.8) can be truncated to a polynomial oflower degree m N in a very graceful way, one that does yield the “most accurate”approximation of degree m (in a sense that can be made precise).
Suppose N isso large that (5.8.8) is virtually a perfect approximation of f(x). Now considerthe truncated approximation#" m−1X1ck Tk (x) − c0(5.8.9)f(x) ≈25.8 Chebyshev Approximation193}(If you find that the execution time of chebft is dominated by the calculation ofN 2 cosines, rather than by the N evaluations of your function, then you should lookahead to §12.3, especially equation 12.3.22, which shows how fast cosine transformmethods can be used to evaluate equation 5.8.7.)Now that we have the Chebyshev coefficients, how do we evaluate the approximation? One could use the recurrence relation of equation (5.8.2) to generate valuesfor Tk (x) from T0 = 1, T1 = x, while also accumulating the sum of (5.8.9).
Itis better to use Clenshaw’s recurrence formula (§5.5), effecting the two processessimultaneously. Applied to the Chebyshev series (5.8.9), the recurrence isdm+1 ≡ dm ≡ 0dj = 2xdj+1 − dj+2 + cjj = m − 1, m − 2, . . . , 1(5.8.11)1f(x) ≡ d0 = xd1 − d2 + c02float chebev(float a, float b, float c[], int m, float x)Chebyshev evaluation: All arguments are input. c[0..m-1] is an array of Chebyshev coefficients, the first m elements of c output from chebft (which must have been called with thePm-1same a and b). The Chebyshev polynomialk=0 ck Tk (y) − c0 /2 is evaluated at a pointy = [x − (b + a)/2]/[(b − a)/2], and the result is returned as the function value.{void nrerror(char error_text[]);float d=0.0,dd=0.0,sv,y,y2;int j;if ((x-a)*(x-b) > 0.0) nrerror("x not in range in routine chebev");y2=2.0*(y=(2.0*x-a-b)/(b-a));Change of variable.for (j=m-1;j>=1;j--) {Clenshaw’s recurrence.sv=d;d=y2*d-dd+c[j];dd=sv;}return y*d-dd+0.5*c[0];Last step is different.}Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit 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).f=vector(0,n-1);bma=0.5*(b-a);bpa=0.5*(b+a);for (k=0;k<n;k++) {We evaluate the function at the n points requiredfloat y=cos(PI*(k+0.5)/n);by (5.8.7).f[k]=(*func)(y*bma+bpa);}fac=2.0/n;for (j=0;j<n;j++) {double sum=0.0;We will accumulate the sum in double precision,for (k=0;k<n;k++)a nicety that you can ignore.sum += f[k]*cos(PI*j*(k+0.5)/n);c[j]=fac*sum;}free_vector(f,0,n-1);194Chapter 5.Evaluation of FunctionsIf we are approximating an even function on the interval [−1, 1], its expansionwill involve only even Chebyshev polynomials.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
