598 Appendix A
with respect to the basisψp, takes on a tridiagonal form; the eigenvalues of the
p×ptridiagonal matrix obtained afterpLanczos-iterations will converge to the
eigenvalues of the original matrix. It can be shown that the lowest and highest
eigenvalues converge most rapidly in this process, so that the method can be used
successfully for these parts of the spectrum. The number of steps needed to achieve
sufficient accuracy depends strongly on the spectrum; for example, if a set of small
eigenvalues is separated from the rest by a relatively large gap, convergence to these
small eigenvalues is fast.
A9 The fast Fourier transform
A9.1 General considerationsFourier transforms occur very often in physics. They can be used to diagonalise
operators, for example when an equation contains the operator∇^2 acting on a func-
tionψ. After Fourier-transforming the equation, this differential operator becomes
a multiplicative factor−k^2 in front of the Fourier transform ofψ, wherekis the
wave vector. In quantum mechanics the stationary solutions for a free particle are
found in this way: these are plane waves with energyE=^2 k^2 / 2 m.
In data analysis, the Fourier transform is often used as a tool to reduce the data: in
music notation one uses the fact that specifying tones by their pitch (which is nothing
but a frequency) requires much less data than specifying the real-time oscillatory
signal. A further application of Fourier transform is filtering out high-frequency
noise present in experimental data.
The fast Fourier transform, or FFT, is a method to perform the Fourier trans-
form much more efficiently than the straightforward calculation. It is based on
the Danielson–Lanczos lemma (see the next subsection) and uses the fact that in
determining the Fourier transform of a discrete periodic function, the factor eikx
assumes the same value for different combinations ofxandk. We shall explain
the method in the next subsection, emphasising the main idea and why it works,
but avoid the details involved in coding it up for the computer. Here we recall the
definition and some generalities concerning the Fourier transform.
First, we define the Fourier transform for the one-dimensional case. General-
isation to more dimensions is obvious. We consider first the Fourier transform of
a periodic functionf(x)with periodL, defined on a discrete set ofNequidistant
points with spacingh=L/N:
xj=jL/N, j=0,...,N−1. (A.132)Note that in contrast to our discussion of partial differential equations,Ldoes not
denote the number of grid points (N), but a distance. In that case, the Fourier