Thompson - Computing for Scientists and Engineers (523188), страница 59
Текст из файла (страница 59)
nto proveParseval’s theorem is a special case of a theorem on autocorrelations, usually attributed to Wiener and Khinchin, for which the autocorrelation may be computed in either k or x domains, giving the same result. Parseval’s theorem is obtained from theWiener-Khinchin theorem by setting the lag to zero. A special kind of orthogonalityof theproduces the Parseval relation directly, as you may now prove.Exercise 9.3(a) Show that the Parseval theorem holds for any expansion of the form (9.1)provided that the expansion functions satisfy(9.9)where the complex-conjugate operation replaces the orthogonality defined inSection 6.2 andis the Kronecker delta, which is unity if k = l and is zerootherwise.(b) Show that the two definitions of orthogonality are equivalent when theare the complex-exponential functions as in (9.2), whereis given by (9.5).
nThus, the Parseval theorem is much more general than originally indicated, and hasled us to discuss an alternative definition of orthogonality. The two definitions areconfusing in the mathematics of this area, but they agree for the exponential functionif the Kronecker delta in (9.9) is replaced byand complex conjugation.9.2 DISCRETE FOURIER TRANSFORMS321One aspect of the DFT may be puzzling you. How is it that there are 2N + 1complex-number coefficients ck but only N (generally complex) y values? The answer is that the complex conjugate of each ck is obtained just by taking complex conjugates on both sides of (9.6). Together with the constraint (9.8) provided by theParseval relation, this reduces the number of real numbers needed to describe the ckto 2N, which is generally the number of real numbers describing the N values of y.Since data that are processed by Fourier expansions are usually real numbers, itis worthwhile to check what simplifications arise in the DFT if the yj are real.Exercise 9.4Suppose that all the yj data values in the expression (9.6) for the DFT coefficients, ck, are real.(a) Show that for real data(9.10)so that only the coefficients for k > 0 need to be computed.(b) Thence show that c0 must be purely real, given by(9.11)in terms of the average value of the y data,(c) Show that for real data the simplest expression for it in terms of the DFT coefficients is(9.12)In applications the average value is often subtracted before the DFT is made.
nThere are two major restrictions to use of the discrete Fourier transform:1. The data values yj = y(xj) must be obtained at equally spaced points xj, withspacing h. If the yj are experimental data, this is usually practicable. In mathematical analysis the discreteness of the data leads to relatively few interestingproperties that can be investigated directly by the DFT, because the sums in (9.6)cannot usually be performed analytically.2.
The maximum frequency, k, for which coefficients, ck, are obtained is related tothe number of data points, N, by k < N. Although there may well be an underlying function with Fourier amplitudes at higher frequencies, one can never discover this by using the DFT. This fact, or variations of it, is called Shannon’ssampling theorem or sometimes the Nyquist criterion.322DISCRETE FOURIER TRANSFORMS AND FOURIER SERIESThe discrete Fourier transform is very convenient for computerized data analysisbecause the necessary sums can easily be summed into loop structures.
Within aloop there appears to be, according to (9.6), a formidable amount of computationwith complex exponentials. The evolution of the fast Fourier transform algorithm,together with the development of computers to handle the intricate logic involved init, allows for very efficient computation of the DFT, as we describe in Section 9.3.Exponential decay and harmonic oscillationThere are very few discrete Fourier transforms that can be calculated analytically, except for the rectangular pulse and for the train of spikes, which are not typical ofreal-world problems.
However, the complex-exponential function, which is oftenencountered in applications (such as in Sections 6.5, 7.2, 8.1, and 8.6), can betransformed simply and analytically. This property does not seem to have been emphasized previously, since such authoritative sources as Brigham or Weaver do notmention it.We first consider the general exponential, then specialize to exponential decayand to harmonic oscillation.
The complex exponential for x > 0 is(9.13)The condition on ensures convergence for positive x when the number of points inthe transfom, N, is allowed to increase indefinitely, as is done to obtain the Fourierintegral transform in Chapter 10. We first derive the transform of this exponentialin closed form, then we specialize to pure exponential decay and to harmonic oscillation. Then we have several numerical examples to illustrate these analytical results.For convenience of analysis we modify our conventions for the transform over Npoints with step h by starting at the point j = 0, rather than at j = 1, since then wedon’t have to subtract an awkward expression for the average value of the function.Therefore we write the transform as(9.14)in which the frequency variableand the index k are related by(9.15)In most uses of the transform the choice k = 0, 1, …, N - 1 is made, but this isnot necessary in what follows, so that nonintegral k values are allowed.
Equation (9.14) also differs from our previous discrete transform by the overall factor h,which ensures convergence to the Fourier integral for large N asas shown9.2 DISCRETE FOURIER TRANSFORMS323in Section 10.1. The subtracted term in this equation ensures the correctness of theinverse transform by removing half the value at the point of discontinuity, k = 0.The summation in (9.14) is just a geometric series (Section 3.1) with multiplier(9.16)and the series sum is given by(9.17)The discrete Fourier transform of the complex exponential (9.13) is therefore(9.18)unless the product of the exponents in the denominator is unity, in which case(9.19)which is also the value obtained by applying L’Hôpital’s rule to (9.18).
Thus, wehave obtained directly a closed form for the discrete Fourier transform of the complex exponential (9.13). In (9.18) N may be any positive integer, so this exact andnontrivial expression may be used to check an FFT program, such as in Section 9.3. The symmetry property (9.10) is also readily verified for real.Exercise 9.5Show that if is real, then the coefficients for positive and negative k are related through (9.10). nExponential decay is described by choosing in (9.13) to be real and positive.By appropriately choosing units for a and h, the time step h can be measured inunits ofso we can then setand (9.18) becomes(9.20)which can be separated into real and imaginary parts for numerical computation.Exercise 9.6(a) Multiply numerator and denominator by the complex conjugate of the denominator. Then use Euler’s theorem for the complex exponential to obtain sineand cosine expressions in the real and imaginary parts in (9.20).324DISCRETE FOURIER TRANSFORMS AND FOURIER SERIES(b) Write and run a simple program for this formula and compare your resultswith those in Figures 9.2 and 9.3, which have step h = 1 and use integer values of k from 0 up to N - 1 for N = 32, 64, and 128.
These are powers of 2for which the FFT in Section 9.3 may be used, and n is stopped at N - 1, aswould be done in an FFT calculation. nFIGURE 9.2 Real part of the discrete Fourier transform of the exponentially damped function(9.13), shown for 32, 64, and 128 points in the transform.FIGURE 9.3 Imaginary part of the discrete Fourier transform of the exponentially damped function (9.13), shown for 32, 64, and 128 points in the transform.9.2 DISCRETE FOURIER TRANSFORMS325The symmetry about N/2 of Re ck and the antisymmetry of Im ck are evident inFigures 9.2 and 9.3. This example of the discrete Fourier transform is discussedfurther in Section 9.3 when we consider an efficient numerical algorithm, the FFT,for computing the transform.
It is also discussed further in Section 10.2 for the integral transform.Harmonic oscillation is a second example of the discrete Fourier transform ofthe exponential (9.13). The mathematics of complex exponentials is discussed inSections 2.3 and 2.4, while the science of resonances is presented in Section 8.1.The DFT of a harmonic oscillation is obtained by settinga pure oscillatorwith a single frequency(To treat this rigorously to produce convergence of thegeometric series for large N, a small positive real part, must be included inAfter convergence has been achieved, one can letThe analytical result forthe transform can be simplified by substituting in (9.13)then expressingthe complex exponentials in terms of half angles before converting to sines by usingEuler’s theorem on complex exponentials, (2.39).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
