13.11 Numerical Use of the Sampling Theorem 607 itself should be very small outside of a fairly limited range of values of t.Thus we are led to two conditions to be satisfied in order that (13.11.1)be useful numerically:Both the function g(t)and its Fourier transform G(w)must rapidly approach zero for large values of their respective arguments. Unfortunately,these two conditions are mutually antagonistic-the Uncertainty Princi- ple in quantum mechanics.There exist strict limits on how rapidly the simultaneous approach to zero can be in both arguments.According to a theorem of Hardy [2],ifg(t)=O(e) asll一and Gw)=O(ew2)asw一o,theng()≡Ce-t2 where C is a constant.This can be interpreted as saying that of all functions the Gaussian is the most rapidly decaying in both t and w,and in this sense is the "best"function to be expressed numerically as a sampling representation. Let us then write for the Gaussian g(t)=e-2 81 e-13 =∑esimc-)+e0 (13.11.3) n=-00 The error e(t)depends on the parameters h and a as well as on t,but it is sufficient for 3 the present purposes to state the bound, le(t)<e-(/2h)2 RECIPES (13.11.4) 令 which can be understood simply as the order of magnitude of the Fourier transform of the Gaussian at the point where it "spills over"into the regionw>h. When the summation in(13.11.3)is approximated by one with finite limits,say from Press. No-N to No +N,where No is the integer nearest to-/h,there is a further truncation error.However,if N is chosen so that N>/(2h2),the truncation error in the summation 9 is less than the bound given by (13.11.4),and,since this bound is an overestimate,we shall continue to use it for (13.11.3)as well.The truncated summation gives a remarkably accurate representation for the Gaussian even for moderate values of N.For example, le(t)<5 x 10-5 for h=1/2 and N 7;le(t)<2 x 10-10 for h 1/3 and N =15; IENTIFIC and le(t)<7x 10-18 for h 1/4 and N =25. One may ask,what is the point of such a numerical representation for the Gaussian, which can be computed so easily and quickly as an exponential?The answer is that many transcendental functions can be expressed as an integral involving the Gaussian,and by substituting (13.11.3)one can often find excellent approximations to the integrals as a sum over elementary functions. Let us consider as an example the function w(z)of the complex variable z=+iy, related to the complex error function by Numerical 色 w(z)=e-=2erfc(-iz) (13.11.5) 43126 having the integral representation w(z)= 1 fe-dt (13.11.6) mi Jc t-z where the contour C extends from-oo to oo,passing below z(see,e.g.,[31).Many methods exist for the evaluation of this function (e.g.,[4)).Substituting the sampling representation (13.11.3)into (13.11.6)and performing the resulting elementary contour integrals,we obtain 1 w(z)≈ he-号1-(-1)”e-w(a-/h (13.11.7) tn-z n=-0 where we now omit the error term.One should note that there is no singularity as zm for some n=m,but a special treatment of the mth term will be required in this case (for example,by power series expansion). An alternative form of equation(13.11.7)can be found by expressing the complex expo- nential in(13.11.7)in terms of trigonometric functions and using the sampling representation13.11 Numerical Use of the Sampling Theorem 607 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). itself should be very small outside of a fairly limited range of values of t. Thus we are led to two conditions to be satisfied in order that (13.11.1) be useful numerically: Both the function g(t) and its Fourier transform G(ω) must rapidly approach zero for large values of their respective arguments. Unfortunately, these two conditions are mutually antagonistic — the Uncertainty Princi￾ple in quantum mechanics. There exist strict limits on how rapidly the simultaneous approach to zero can be in both arguments. According to a theorem of Hardy [2], if g(t) = O(e−t2 ) as |t|→∞ and G(ω) = O(e−ω2/4) as |ω|→∞, then g(t) ≡ Ce−t2 , where C is a constant. This can be interpreted as saying that of all functions the Gaussian is the most rapidly decaying in both t and ω, and in this sense is the “best” function to be expressed numerically as a sampling representation. Let us then write for the Gaussian g(t) = e−t2 , e −t2 =
∞ n=−∞ e −t2 n sinc π h(t − tn) + e(t) (13.11.3) The error e(t) depends on the parameters h and α as well as on t, but it is sufficient for the present purposes to state the bound, |e(t)| < e−(π/2h)2 (13.11.4) which can be understood simply as the order of magnitude of the Fourier transform of the Gaussian at the point where it “spills over” into the region |ω| > π/h. When the summation in (13.11.3) is approximated by one with finite limits, say from N0 − N to N0 + N, where N0 is the integer nearest to −α/h, there is a further truncation error. However, if N is chosen so that N > π/(2h2), the truncation error in the summation is less than the bound given by (13.11.4), and, since this bound is an overestimate, we shall continue to use it for (13.11.3) as well. The truncated summation gives a remarkably accurate representation for the Gaussian even for moderate values of N. For example, |e(t)| < 5 × 10−5 for h = 1/2 and N = 7; |e(t)| < 2 × 10−10 for h = 1/3 and N = 15; and |e(t)| < 7 × 10−18 for h = 1/4 and N = 25. One may ask, what is the point of such a numerical representation for the Gaussian, which can be computed so easily and quickly as an exponential? The answer is that many transcendental functions can be expressed as an integral involving the Gaussian, and by substituting (13.11.3) one can often find excellent approximations to the integrals as a sum over elementary functions. Let us consider as an example the function w(z) of the complex variable z = x + iy, related to the complex error function by w(z) = e−z2 erfc(−iz) (13.11.5) having the integral representation w(z) = 1 πi C e−t2 dt t − z (13.11.6) where the contour C extends from −∞ to ∞, passing below z (see, e.g., [3]). Many methods exist for the evaluation of this function (e.g., [4]). Substituting the sampling representation (13.11.3) into (13.11.6) and performing the resulting elementary contour integrals, we obtain w(z) ≈ 1 πi
∞ n=−∞ he−t2 n 1 − (−1)ne−πi(α−z)/h tn − z (13.11.7) where we now omit the error term. One should note that there is no singularity as z → tm for some n = m, but a special treatment of the mth term will be required in this case (for example, by power series expansion). An alternative form of equation (13.11.7) can be found by expressing the complex expo￾nential in (13.11.7) in terms of trigonometric functions and using the sampling representation