Thompson - Computing for Scientists and Engineers (523188), страница 58
Текст из файла (страница 58)
“On the Mathematical Theory of Suspension Bridges, with Tables forFacilitating Their Construction,” Philosophical Transactions of the Royal Societyof London, 116, 202 (1826).Haberman, R., Mathematical Models, Prentice Hall, Englewood Cliffs, NewJersey, 1977.Honig, E., “New Wine into Old Bottles: A Nuptial Arch,” American Journal ofPhysics, 59, 472 (1991).Ingard, K. U., Fundamentals of Waves and Oscillations, Cambridge UniversityPress, Cambridge, England, 1988.Jain, M.
K., Numerical Solution of Differential Equations, Wiley Eastern, NewDelhi, second edition, 1984.Nakamura, S., Applied Numerical Methods with Software, Prentice Hall,Englewood Cliffs, New Jersey, 1991.Noumerov, B. V., Monthly Notices of the Royal Astronomical Society, 84, 592(1924).Pippard, A. B., The Physics of Vibration, Cambridge University Press, Cambridge,England, 1988,Press, W. H., B. P. Flannery, S.
A. Teukolsky, and W. T. Vetterling, NumericalRecipes in C, Cambridge University Press, New York, 1988.White, H. E., and D. H. White, Physics and Music, Saunders College, Philadelphia, 1980.Zill, D. G., Differential Equations with Boundary-Value Problems, Prindle, Weber,& Schmidt, Boston, 1986.314Previous Home NextChapter 9DISCRETE FOURIER TRANSFORMSAND FOURIER SERIESIn this chapter and in the next we develop mathematical and computational techniques applicable to describing data and functions in terms of the orthogonal functions introduced in Chapter 6 for linear least-squares fitting. In particular, we usethe complex-exponential or cosine and sine functions over appropriate ranges as theorthogonal functions. In pure mathematics the term Fourier analysis or Fourierexpansion usually refers to the more general orthogonal functions, whereas inapplied mathematics as used in science and engineering the trigonometric functionsare often those of relevance because of their interpretation in terms of simple harmonic motions and harmonics of a fundamental frequency of oscillation.The topics that we emphasize in this chapter are the following.
In Section 9.1we distinguish between the different kinds of Fourier expansions, the discrete transform, the series, and the integral transform. Section 9.2 is used to develop the discrete transform, whose practical computation is described by the Fast Fourier Transform (FFT) algorithm developed in Section 9.3. We then derive in Section 9.4 thecommon Fourier series from the discrete transform, and in Section 9.5 we givesome obligatory exercises with series and show some of their novel applications.As a diversion, Section 9.6 discusses the pesky practical problems of the Wilbraham-Gibbs overshoot.Turning to practical applications, we develop a program for the FFT in Section 9.7 as Project 9A. In Section 9.8 we implement as Project 9B a Fourier analysis of an electroencephalogram (EEG).
We end the chapter with relevant referenceson Fourier expansions.Chapter 10 we devote to Fourier integral transforms, a natural extension of theresults in Chapter 9. Both mathematical and applied developments are made, withparticular reference to powerful analytical results and their use in computing derivatives and integrals. We introduce convolutions and correlations, and their approximate computation by the FFT is discussed.315316DISCRETE FOURIER TRANSFORMS AND FOURIER SERIESAlthough the results that we derive are mathematically correct, we do not examine rigorously such assumptions as the convergence of Fourier series. These arediscussed with mathematical elegance in the monograph by Champeney on Fouriertheorems, and in Chapter 6 of the book by Protter and Morrey.9.1 OVERVIEW OF FOURIER EXPANSIONSIn this section we provide an overview of the uses of Fourier expansions, the different types of expansions, and the nomenclature used to describe them.
The distinction between the different types is important both at the analysis level and in practicalnumerical applications.The uses of Fourier expansionsThere are several motivations for using Fourier expansions in mathematics, science,and engineering.
A primary analytical motivation arises from the elegant mathematics of the complex-exponential function and its relation to cosine and sine functions,as reviewed in Section 2.3. A further motivation is the association of the successiveterms in expansions, such as in successive Fourier-series terms, with harmonics offrequencies.
This connection also relates vibrations and waves (Section 2.4) withresonances (Section 8.1).At the level of numerics and applications, one motivation for using Fourier expansions arises from linear-least-squares fitting in terms of orthogonal functions, atopic developed in Section 6.2.
There we showed that the fitting coefficients maybe determined independently of each other if the fitting functions are orthogonalover appropriate regions of x and with suitable weight factors. As we derive in thischapter and the next, suitable orthogonal functions can be found for each type ofFourier expansion.Types and nomenclature of Fourier expansionsThe distinction between the various types of Fourier expansions and their nomenclature is confusing, and it is not always consistent between different authors. Our nomenclature is summarized here and is related to subsequent sections. The chart below illustrates schematically the features of the three types of Fourier expansions.In each type of expansion the functions (x) are complex exponentials or arecosines and sines of kx.
The left-hand side of the chart indicates the three types ofFourier expansions and their mathematical distinctions, while the right-hand side indicates the fast Fourier transform algorithm for computing the discrete transform,which is derived in Section 9.3 and programmed in Section 9.7. What are, generically, the similarities and differences between the three expansions?9.1 OVERVIEW OF FOURIER EXPANSIONS317FIGURE 9.1 Schematic of the types and nomenclature of Fourier expansions.lThe discrete Fourier transform (DFT) uses summations in both stages It istherefore completely symmetric between the discrete data in the x domain, y(xj), andthe coefficients ck in the k domain, as we show in detail in Section 9.2.
The DFTis most useful for analyzing data, especially because the Fast Fourier Transform(FFT) algorithm (Sections 9.3 and 9.7) allows very efficient computation of the discrete transform and its inverse.lThe Fourier series differs from the DFT in that the summation in computing thecoefficients is replaced by integration. The y values must therefore be defined over acontinuous range of x, which makes the Fourier series most applicable for y(x) described by formulas, as we describe in Sections 9.4 and 9.5. Confusion betweenthe discrete and series transforms is likely in practical applications because the integrals are often approximated by trapezoid-rule sums (Section 4.6).318DISCRETE FOURIER TRANSFORMS AND FOURIER SERIESlIn the Fourier integral transform (FIT), also just called the Fourier transform, wego all the way, with y(x) being given in terms of integrals overand vice versa.The Fourier transform is often most useful for analytical work, especially becausethe symmetry between y(x) andhas been regained.
These analytical integralresults are often approximated by summations in practical work, so there is oftenconfusion between the FIT and the DFT, especially when approximating the integraltransform numerically by using the FFT algorithm. The Fourier integral transformis so mathematically tractable and has so many applications that we devote Chapter 10 to exploring its properties and applications. For the complex-exponentialfunction it is possible to calculate both its DFT and its FFT analytically, a fact apparently unknown to other authors. I therefore show in Sections 9.2 and 10.2 the calculations, then you have opportunity to compare the two types of Fourier expansion.Our order of presenting the Fourier expansions indicated in the above chart is notinevitable.
By beginning with discrete series, then taking limits to obtain integrals,we follow the Riemann and graphical approaches to the definition of integrals. If webegan with the integral transforms and worked toward the discrete transforms, wewould have to discretize the functions by introducing Dirac delta distributions, thusintroducing additional mathematical pains without any gains.
Various approachesare described in the treatises by Körner, Bôcher, and Champeney.9.2 DISCRETE FOURIER TRANSFORMSThe first kind of Fourier expansion that we consider is direct use of summations inthe expansion of a function or data in terms of the complex-exponential function forFurthermore, we assume that the x values are available at equally-spacedpoints xj = jh, with the origin of the x coordinates chosen so that j = 1,2,...,N .Derivation of the discrete transformLet us try a Fourier expansion of the form(9.1)where the expansion functions are the complex exponentials(9.2)In (9.1), although the sum is over the index k, its range is not yet specified, nor hasthe quantity in (9.2) been specified.
Both the range and will be chosen to get9.2 DISCRETE FOURIER TRANSFORMS319an orthogonal expansion, and thefactor in (9.2) will produce orthonormality,that is, a sum whose value is unity whenever it is nonzero. This property is derivedbelow.Consider the orthogonality sum, S, corresponding to (6.13) in the least-squaresdiscussion. With the choice (9.2) for the expansion functions, S is given by(9.3)Exercise 9.1(a) To evaluate S, show that the substitutiongeometric-series formula (3.2), forproduces the(9.4)(b) Thence show that for orthogonality (S = 0) one requires(9.5)(c) With this value of a, show for r = 1 (l = -k) that S = 1, which justifiesthe normalization of the function in (9.2).
nThus, in the linear-least-squares formula (6.18), choosing weight factors wj allunity, we have the coefficients for the discrete Fourier transform(9.6)Here the coefficients have a range of k values -N to N.The complementary expansion of the functions in terms of the Fourier coefficients is(9.7)This expression may be used for any value of x, not just at the points where the ydata exist, the yj.Note that the Fourier coefficients, ck, are complex numbers even if the functiony (x) is purely real. This property and others will now be derived.320DISCRETE FOURIER TRANSFORMS AND FOURIER SERIESProperties of the discrete transformIt is worthwhile now to derive many properties of the discrete Fourier transform,since many of them extend to the other Fourier expansions, the series and the integral.
The first property is called Parseval’s theorem:(9.8)In electrical engineering and physics if the k are frequencies, then the left-hand sideis a measure of the total power in a system as computed in the frequency domain,while the right-hand side is the power computed in the time domain, so that x = t,the time. In quantum mechanics the k usually refer to momentum space and the x toconfiguration space, then the interpretation of the Parseval theorem is that total probabilities are the same in both representations.Exercise 9.2Use (9.8) and (9.6), with the orthonormality conditions on theParseval’s theorem.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
