198 Chapter 5.Evaluation of Functions void pcshft(float a,float b,float d[],int n) Polynomial coefficient shift.Given a coefficient array d[..n-1],this routine generates a coefficient array[..1]such that where z and yare related by (5.8.10).i.e.,the interval-1 <y<1 is mapped to the interval a <<b.The array 又6 retured in.9 int k,j; float fac,cnst; cnst=2.0/(b-a); fac=cnst; for (j=1;i<n;j++) First we rescale by the factor const... d[j]*fac; fac米=cnst 83g cngt=0.5*(a+b); ...which is then redefined as the desired shift. for(j=0;j<=n-2;j++) We accomplish the shift by synthetic division.Synthetic for (k=n-2;k>=j;k--) division is a miracle of high-school algebra.If you NUMERICAL d[k]-=cnst*d[k+1]; never learned it,go do so.You won't be sorry. RECIPES CITED REFERENCES AND FURTHER READING: Acton,F.S.1970,Numerica/Methods That Work;1990,corrected edition (Washington:Mathe- 号 Press. matical Association of America),pp.59.182-183 [synthetic division]. Programs 5.11 Economization of Power Series IENTIFIC One particular application of Chebyshev methods,the economization of power series,is an occasionally useful technique,with a flavor of getting something for nothing. Suppose that you are already computing a function by the use of a convergent power series,for example 9 (ISBN f)三1-+京-7+ (5.11.1) Numerica 10621 (This function is actually sin()/v,but pretend you don't know that.)You might be 43106 doing a problem that requires evaluating the series many times in some particular interval,say [0,(2)2].Everything is fine,except that the series requires a large number of terms before S Recipes its error (approximated by the first neglected term,say)is tolerable.In our example,with =(2)2,the first term smaller than 10-7 is/(27!).This then approximates the error of the finite series whose last term is 12/(25!). Software. Notice that because of the large exponent in the error is much smaller than 10-7 everywhere in the interval except at the very largest values of r.This is the feature that allows "economization":if we are willing to let the error elsewhere in the interval rise to about the same value that the first neglected term has at the extreme end of the interval,then we can replace the 13-term series by one that is significantly shorter. Here are the steps for doing so: 1.Change variables from x to y,as in equation (5.8.10),to map the z interval into -1≤y≤1. 2.Find the coefficients of the Chebyshev sum(like equation 5.8.8)that exactly equals your truncated power series (the one with enough terms for accuracy). 3.Truncate this Chebyshev series to a smaller number of terms,using the coefficient of the first neglected Chebyshev polynomial as an estimate of the error.198 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). void pcshft(float a, float b, float d[], int n) Polynomial coefficient shift. Given a coefficient array d[0..n-1], this routine generates a coefficient array g[0..n-1] such that
n-1 k=0 dkyk =
n-1 k=0 gkxk, where x and y are related by (5.8.10), i.e., the interval −1 <y< 1 is mapped to the interval a <x< b. The array g is returned in d. { int k,j; float fac,cnst; cnst=2.0/(b-a); fac=cnst; for (j=1;j<n;j++) { First we rescale by the factor const... d[j] *= fac; fac *= cnst; } cnst=0.5*(a+b); ...which is then redefined as the desired shift. for (j=0;j<=n-2;j++) We accomplish the shift by synthetic division. Synthetic division is a miracle of high-school algebra. If you never learned it, go do so. You won’t be sorry. for (k=n-2;k>=j;k--) d[k] -= cnst*d[k+1]; } CITED REFERENCES AND FURTHER READING: Acton, F.S. 1970, Numerical Methods That Work; 1990, corrected edition (Washington: Mathe￾matical Association of America), pp. 59, 182–183 [synthetic division]. 5.11 Economization of Power Series One particular application of Chebyshev methods, the economization of power series, is an occasionally useful technique, with a flavor of getting something for nothing. Suppose that you are already computing a function by the use of a convergent power series, for example f(x) ≡ 1 − x 3! + x2 5! − x3 7! + ··· (5.11.1) (This function is actually sin(√x)/ √x, but pretend you don’t know that.) You might be doing a problem that requires evaluating the series many times in some particular interval, say [0,(2π) 2]. Everything is fine, except that the series requires a large number of terms before its error (approximated by the first neglected term, say) is tolerable. In our example, with x = (2π) 2, the first term smaller than 10−7 is x13/(27!). This then approximates the error of the finite series whose last term is x12/(25!). Notice that because of the large exponent in x13, the error is much smaller than 10−7 everywhere in the interval except at the very largest values of x. This is the feature that allows “economization”: if we are willing to let the error elsewhere in the interval rise to about the same value that the first neglected term has at the extreme end of the interval, then we can replace the 13-term series by one that is significantly shorter. Here are the steps for doing so: 1. Change variables from x to y, as in equation (5.8.10), to map the x interval into −1 ≤ y ≤ 1. 2. Find the coefficients of the Chebyshev sum (like equation 5.8.8) that exactly equals your truncated power series (the one with enough terms for accuracy). 3. Truncate this Chebyshev series to a smaller number of terms, using the coefficient of the first neglected Chebyshev polynomial as an estimate of the error