Numerical Approximation of the Fourier Transform by the Fast Fourier Transform (FFT) Algorithm

The Fourier transforms of some classical functions are calculated and their real and imaginary parts are plotted. The Fourier transform (FT) is numerically calculated by using the step function approximation to the Fourier integral; this finally leads to the discrete Fourier transform (DFT).

The DFT is rapidly evaluated by using the fast Fourier transform (FFT) algorithm. The list of data for the FFT is obtained from a finite number of sample points using an initial function. The number of sample points is chosen to be an integer power of 2, which is convenient for the evaluation of the FFT. To obtain accurate result for the continuous Fourier transform (CFT) the sample spacing must be small enough and the number of sample points must be large. This implies that the list of values at sample points for a given initial function contains many zeros, because the sampling range becomes very wide. After evaluating the FFT, the output list also contains a large number of zeros, but only the central fraction of the output list is of interest. The final result of this procedure is the continuous Fourier transform in the form of points whose spacing depends on the number of the input sample points and its sample spacing. These facts make the straightforward application of the FFT to the numerical approximation of the Fourier transform fundamentally inflexible.

Usually this procedure is used when the input sample spacing and output spacing are comparable. This Demonstration lets you control this aspect of the algorithm. The accuracy of the continuous Fourier transform is visible when the values of data points number and the sample spacing are changed.

The method is fast and reliable for functions that tend to zero quickly for large absolute values of the argument. This condition on the function is needed to avoid an undesirable aliasing effect. The algorithm is very useful in performing a fast continuous Fourier transform for numerical data.