Evaluation of Fourier integrals using -splines

Authors:
M. Lax and G. P. Agrawal

Journal:
Math. Comp. **39** (1982), 535-548

MSC:
Primary 65D30; Secondary 42A15, 65R10

DOI:
https://doi.org/10.1090/S0025-5718-1982-0669645-5

Corrigendum:
Math. Comp. **43** (1984), 347.

Corrigendum:
Math. Comp. **43** (1984), 347.

MathSciNet review:
669645

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Finite Fourier integrals of functions possessing jumps in value, in the first or in the second derivative, are shown to be evaluated more efficiently, and more accurately, using a continuous Fourier transform (CFT) method than the discrete transform method used by the fast Fourier transform (FFT) algorithm. A *B*-spline fit is made to the input function, and the Fourier transform of the set of *B*-splines is performed analytically for a possibly nonuniform mesh. Several applications of the CFT method are made to compare its performance with the FFT method. The use of a 256-point FFT yields errors of order , whereas the same information used by the CFT algorithm yields errors of order --the machine accuracy available in single precision. Comparable accuracy is obtainable from the FFT over the limited original domain if more than 20,000 points are used.

**[1]**F. Abramovici, "The accurate calculation of Fourier integrals by the fast Fourier transform technique,"*J. Comput. Phys.*, v. 11, 1973, pp. 28-37. MR**0413436 (54:1550)****[2]**M. Abramowitz & I. A. Stegun (Editors),*Handbook of Mathematical Functions*, Dover, New York, 1965, p. 300.**[3]**G. P. Agrawal & M. Lax, "Fraunhofer diffraction in the beam approximation from two longitudinally separated slits,"*J. Opt. Soc. Amer.*, v. 72, 1982, pp. 164-166.**[4]**P. J. Davis,*Interpolation and Approximation*, Blaisdell, New York, 1963, Section 3.7. MR**0157156 (28:393)****[5]**C. de Boor, "On calculating with*B*-splines,"*J. Approx. Theory*, v. 6, 1972, pp. 50-62. MR**0338617 (49:3381)****[6]**C. de Boor, "Package for calculating with*B*-splines,"*SIAM J. Numer. Anal.*, v. 14, 1977, pp. 441-472; C. de Boor,*A Practical Guide to Splines*, Springer-Verlag, New York, 1978. MR**0428691 (55:1711)****[7]**B. Einarsson, "Numerical calculation of Fourier integrals with cubic splines,"*BIT*, v. 8, 1968, pp. 279-286;*BIT*, v. 9, 1969, pp. 183-184 (errata). MR**0239757 (39:1114)****[8]**B. Einarsson, "Use of Richardson extrapolation for the numerical calculation of Fourier transforms,"*J. Comput. Phys.*, v. 21, 1976, pp. 365-370. MR**0416080 (54:4156)****[9]**L. N. G. Filon, "On a quadrature formula for trigonometric integrals,"*Proc. Roy. Soc. Edinburgh*, v. 49, 1928, pp. 38-47.**[10]**S. M. Flatte & F. D. Tappert, "Calculation of the effect of internal waves on oceanic sound transmission,"*J. Acoust. Soc. Amer.*, v. 58, 1975, pp. 1151-1159.**[11]**J. Gazdag, "Numerical convective schemes based on accurate computation of space derivatives,"*J. Comput. Phys.*, v. 13, 1973, pp. 100-113.**[12]**R. W. Hockney, "A fast direct solution of Poisson's equation using Fourier analysis,"*J. Assoc. Comput. Mach.*, v. 17, 1965, pp. 95-113. MR**0213048 (35:3913)****[13]**H. Jeffreys & B. S. Jeffreys,*Methods of Mathematical Physics*, Cambridge Univ. Press, Oxford, 1978, p. 262.**[14]**M. Lax, G. P. Agrawal & W. H. Louisell, "Continuous Fourier transform spline solution of unstable resonator field distribution,"*Opt. Lett.*, v. 9, 1979, pp. 303-305.**[15]**R. C. le Bail, "Use of Fast Fourier Transforms for solving partial differential equations in physics,"*J. Comput. Phys.*, v. 9, 1972, pp. 440-465. MR**0309342 (46:8452)****[16]**M. J. Marsden & G. D. Taylor, "Numerical evaluation of Fourier integrals," in*Numerische Methoden der Approximations Theorie*, Band I (Vortragsauszuge einer Tagung, Oberwolfach, 1971), pp. 61-76; Internat. Schriftenreibe zur Numer. Math. Band 16, Birkhauser, Basel, 1972. MR**0386234 (52:7092)****[17]**J. Marti, "An algorithm recursively computing the exact Fourier coefficients of*B*-splines with non-equidistant knots,"*J. Appl. Math. and Phys.*, v. 29, 1978, pp. 301-305. MR**498770 (81f:65010)****[18]**R. Piessens & M. Branders, "Computation of oscillating integrals,"*J. Comput. Appl. Math.*, v. 1, 1975, pp. 153-164.**[19]**R. Piessens & A. Haegemans, "Algorithm for the automatic integration of highly oscillatory functions,"*Computing*, v. 13, 1974, pp. 183-193. MR**0455302 (56:13541)****[20]**I. J. Schoenberg, "Contributions to the problem of approximation of equidistant data by analytic functions,"*Quart Appl. Math.*, v. 4, 1946, pp. 45-49, 121-141. MR**0015914 (7:487b)****[21]**I. J. Schoenberg,*Cardinal Spline Interpolation*, SIAM, Philadelphia, Pa., 1973, p. 2. MR**0420078 (54:8095)****[22]**A. E. Siegman & E. A. Sziklas, "Mode calculations in unstable resonators with flowing saturable gain, 2: Fast Fourier transform method,"*Appl. Optics*, v. 14, 1975, pp. 1874-1889.**[23]**S. D. Silliman, "The numerical evaluation by splines of Fourier transforms,"*J. Approx. Theory*, v. 12, 1974, pp. 32-51. MR**0356556 (50:9026)****[24]**R. C. Singleton, "An algorithm for computing the mixed radix fast Fourier transform,"*IEEE Trans. Audio Electroacoust.*, v. AU-17, 1969, pp. 93-103.**[25]**F. D. Tappert,*Numerical Solutions of the Korteweg-de Vries Equation and its Generalizations by the Split-Step Fourier Method*, Lectures in Appl. Math., vol. 15, Amer. Math. Soc., Providence, R. I., 1974, pp. 215-216.

Retrieve articles in *Mathematics of Computation*
with MSC:
65D30,
42A15,
65R10

Retrieve articles in all journals with MSC: 65D30, 42A15, 65R10

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1982-0669645-5

Keywords:
Fourier integral,
*B*-splines,
fast Fourier transform,
continuous Fourier transform

Article copyright:
© Copyright 1982
American Mathematical Society