Page 454 - Numerical Methods for Chemical Engineering

Fourier series and transforms in one dimension 443

From these results, we define the discrete Fourier transform
N
(n−1)(k−1) −i2π/N
F n = f k W W = e n = 1, 2,..., N (9.48)
k=1
such that
( t) (n − 1)π
F(ω n ) ≈ √ F n ω n = (9.49)
2π P
Similarly, we approximate the inverse Fourier transform
+∞ 2ω max
'
1 iωt 1 iωt
'
f (t) = √ F(ω)e dω → √ F(ω)e dω (9.50)
2π 2π
−∞ 0
by
N
1 iω n t
f (t) ≈ √ F(ω n )e ( ω) (9.51)
2π
n=1
Substituting for F(ω n ) and ω n ,wehaveat t k = (k − 1) t
( ω) ( t) i(n−1)( ω)(k−1)( t)
N
f (t k ) ≈ √ √ F n e (9.52)
2π 2π n=1
a b
Using again e ab = (e ) and ( ω)( t) = 2π/N,
N N
1 . i( ω)( t) / (n−1)(k−1) 1 ∗ (n−1)(k−1)
f (t k ) ≈ F n e = F n [W ] (9.53)
N N
n=1 n=1
∗
where W = [e −i2π/N ∗ i2π/N = e i( ω)( t) . These relations define the discrete Fourier
] = e
transform pair
N N
(n−1)(k−1) 1 ∗ (n−1)(k−1)
F n = f k W f k = F n [W ]
N
k=1 n=1 (9.54)
W = e −i2π/N n = 1, 2,..., N
that is related to the original, continuous Fourier transform pair by
( t) (n − 1)π
F(ω n ) ≈ √ F n ω n = f (t k ) = f k t k = (k − 1) t (9.55)
2π P
The fast Fourier transform (FFT)

Computing the discrete Fourier transform directly from (9.48) requires a number of oper-
2
ations that scales as N . Here, we present an alternative decimation procedure that scales
2
only as Nlog N « N . Let us break the summation over k into contributions from the even
2
and odd terms,
N N
(n−1)(k−1) (n−1)(k−1)
F n = f k W + f k W (9.56)
k=1 k=1
k even k odd