606 Chapter 13.Fourier and Spectral Applications Various numerical schemes can be used to solve sparse linear systems of this "hierarchically band diagonal"form.Beylkin,Coifman,and Rokhlin [1]make the interesting observations that (1)the product of two such matrices is itself hierarchically band diagonal(truncating,of course,newly generated elements that are smaller than the predetermined threshold e);and moreover that(2)the product can be formed in order N operations. Fast matrix multiplication makes it possible to find the matrix inverse by Schultz's (or Hotelling's)method,see $2.5. Other schemes are also possible for fast solution ofhierarchically band diagonal forms.For example,one can use the conjugate gradient method,implemented in $2.7 as linbcg. 菲 CITED REFERENCES AND FURTHER READING: Daubechies,I.1992,Wavelets (Philadelphia:S.I.A.M.). Strang.G.1989,S/AM Review,vol.31.pp.614-627. Beylkin,G.,Coifman,R.,and Rokhlin,V.1991,Communications on Pure and Applied Mathe- RECIPES matics,vol.44,Pp.141-183.[1] Daubechies,1.1988,Communications on Pure and Applied Mathematics,vol.41.pp.909-996. 2] Vaidyanathan,P.P.1990,Proceedings of the IEEE,vol.78,pp.56-93.[3] Mallat,S.G.1989,IEEE Transactions on Pattern Analysis and Machine Intelligence,vol.11, 。 pp.674-693.[4 Freedman,M.H.,and Press,W.H.1992,preprint.[5] 13.11 Numerical Use of the Sampling Theorem 61 In 86.10 we implemented an approximating formula for Dawson's integral due to Rybicki.Now that we have become Fourier sophisticates,we can learn that the formula derives from numerical application of the sampling theorem (812.1).normally considered to be a purely analytic tool.Our discussion is identical to Rybicki[1]. For present purposes,the sampling theorem is most conveniently stated as follows: Numerica 10621 Consider an arbitrary function g(t)and the grid of sampling pointsn=o+nh,where n ranges over the integers and a is a constant that allows an arbitrary shift of the sampling 43106 grid.We then write %g7G g(t)= g(tn)sinc (t-tn)+e(t) (13.11.1) h where sincx =sin x/r.The summation over the sampling points is called the sampling representation of g(t),and e(t)is its error term.The sampling theorem asserts that the sampling representation is exact,that is,e(t)=0,if the Fourier transform of g(t), G(w)= g(t)edt (13.11.2) vanishes identically forw>h When can sampling representations be used to advantage for the approximate numerical computation of functions?In order that the error term be small,the Fourier transform G(w) must be sufficiently small for/h.On the other hand,in order for the summation in(13.11.1)to be approximated by a reasonably small number of terms,the function g(t)606 Chapter 13. Fourier and Spectral Applications 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). Various numerical schemes can be used to solve sparse linear systems of this “hierarchically band diagonal” form. Beylkin, Coifman, and Rokhlin [1] make the interesting observations that (1) the product of two such matrices is itself hierarchically band diagonal (truncating, of course, newly generated elements that are smaller than the predetermined threshold
); and moreover that (2) the product can be formed in order N operations. Fast matrix multiplication makes it possible to find the matrix inverse by Schultz’s (or Hotelling’s) method, see §2.5. Other schemes are also possible for fast solution of hierarchically band diagonal forms. For example, one can use the conjugate gradient method, implemented in §2.7 as linbcg. CITED REFERENCES AND FURTHER READING: Daubechies, I. 1992, Wavelets (Philadelphia: S.I.A.M.). Strang, G. 1989, SIAM Review, vol. 31, pp. 614–627. Beylkin, G., Coifman, R., and Rokhlin, V. 1991, Communications on Pure and Applied Mathe￾matics, vol. 44, pp. 141–183. [1] Daubechies, I. 1988, Communications on Pure and Applied Mathematics, vol. 41, pp. 909–996. [2] Vaidyanathan, P.P. 1990, Proceedings of the IEEE, vol. 78, pp. 56–93. [3] Mallat, S.G. 1989, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, pp. 674–693. [4] Freedman, M.H., and Press, W.H. 1992, preprint. [5] 13.11 Numerical Use of the Sampling Theorem In §6.10 we implemented an approximating formula for Dawson’s integral due to Rybicki. Now that we have become Fourier sophisticates, we can learn that the formula derives from numerical application of the sampling theorem (§12.1), normally considered to be a purely analytic tool. Our discussion is identical to Rybicki [1]. For present purposes, the sampling theorem is most conveniently stated as follows: Consider an arbitrary function g(t) and the grid of sampling points tn = α + nh, where n ranges over the integers and α is a constant that allows an arbitrary shift of the sampling grid. We then write g(t) =
∞ n=−∞ g(tn) sinc π h(t − tn) + e(t) (13.11.1) where sinc x ≡ sin x/x. The summation over the sampling points is called the sampling representation of g(t), and e(t) is its error term. The sampling theorem asserts that the sampling representation is exact, that is, e(t) ≡ 0, if the Fourier transform of g(t), G(ω) = ∞ −∞ g(t)eiωt dt (13.11.2) vanishes identically for |ω| ≥ π/h. When can sampling representations be used to advantage for the approximate numerical computation of functions? In order that the error term be small, the Fourier transform G(ω) must be sufficiently small for |ω| ≥ π/h. On the other hand, in order for the summation in (13.11.1) to be approximated by a reasonably small number of terms, the function g(t)