Page 461 - A First Course In Stochastic Models

456 APPENDICES

is sought that agrees with f at n equally spaced points x l = 2πℓ/n between 0 and
2π. More specifically, we look for complex numbers c 0 , . . . , c n−1 such that

n−1
ik(2πℓ/n)
c k e = f ℓ , ℓ = 0, . . . , n − 1. (D.1)
k=0
It is convenient to write these linear equations in matrix notation as
Fc = f.

Here F is a complex-valued matrix whose (ℓ, k)th element (F) ℓk is given by
kℓ
(F) ℓk = w , ℓ, k = 0, . . . , n − 1,
where the complex number w is defined by
w = e 2πi/n .

Let F be the matrix whose elements are the complex conjugates of the elements
of the matrix F. The matrix F has the nice property that

FF = FF = nI, (D.2)
where I is the identity matrix (the column vectors of the symmetric matrix F
form an orthogonal system). To verify this, let w = e −2πi/n denote the complex
conjugate of w. The inproduct of the rth row of F and the sth column of F is
given by
0
0
s
2r
r
γ rs = w w + w w + w w 2s + · · · + w (n−1)r w (n−1)s .
0
For r = s each term equals e = 1 and so the sum γ rs is n. For r = s the sum γ rs
s
n
r
can be written as 1 + α + · · · + α n−1 = (1 − α )/(1 − α) with α = w w ( = 1).
n
n
n
Since w = e 2πi = 1 and w = e −2πi = 1, we have α = 1 and so γ rs = 0 for
r = s. This gives (D.2). By (D.2), we have F −1 = (1/n)F. It now follows that
the vector c of Fourier coefficients is given by c = (1/n)Ff . Componentwise, we
have
n−1
1 −2πiℓk/n
c k = f ℓ e , k = 0, . . . , n − 1. (D.3)
n
ℓ=0
This inversion formula parallels the formula c k = (2π) −1 π f (x) e −ikx dx in
−π
continuous Fourier analysis. Notice that (D.3) inherits the structure of (D.1).
In many applications, however, we proceed in reverse order: we know the
Fourier coefficients c k and wish to calculate the original coefficients f j . By the
formula (D.1) we can transform c back into f . The matrix multiplications in (D.1)
2
would normally require n multiplications. However, the discrete FFT method per-
forms the multiplications in an extremely fast and ingenious way that requires
2
only n log (n) multiplications instead of n . The key to the method is the simple
2
observation that the discrete Fourier transform of length n (n even) can be written