Module for Fast Fourier Transform (FFT)

Check out the new Numerical Analysis Projects page.

Definition (Piecewise Continuous).  The function    is piecewise continuous on the closed interval  ,  if there exists values    with    such that  f  is continuous in each of the open intervals  ,  for    and has left-hand and right-hand limits at each of the values  ,  for  .  

Definition (Fourier Series).  If    is periodic with period    and is piecewise continuous on  ,  then the Fourier Series    for    is

    ,

where the coefficients    are given by the so-called Euler's formulae:  

    ,  
and  
    .  

Theorem (Fourier Expansion).  Assume that    is the Fourier Series for  .   If    are piecewise continuous on  ,  then    is convergent for all  .  

The relation    holds for all   where    is continuous.  If    is a point of discontinuity of  ,  then

     ,  

where    denote the left-hand and right-hand limits, respectively.  With this understanding, we have the Fourier Series expansion:

     .  

Definition (Fourier Polynomial).  If    is periodic with period    and is piecewise continuous on  ,  then the Fourier Polynomial    for    of degree m is

    ,

where the coefficients    are given by the so-called Euler's formulae:  

    ,  
and  
    .  

Animations (Fourier Series  Fourier Series).  Internet hyperlinks to animations.

Example 1.  Assume that is periodic with period  ,  i.e.  ,  and is defined by

      for  .  

Find the Fourier polynomial of degree n = 5.  
Solution 1.

Numerical Integration calculation for the Fourier trigonometric polynomial.  

Assume that    is periodic with period    and is piecewise continuous on  ,

To construct the Fourier trigonometric polynomial over [0,2L] of degree m.

    ,   

There are n subintervals of equal width    based on  .  The coefficients are   

      for  .  
and
      for  .  

The construction is possible provided that  .  

Remark.  The sums can be viewed as numerical integration of Euler's formulae when [0,2L] is divided into n subintervals.  The trapezoidal rule uses the weights for both the and .  Since f(x) has period  ,  it follows that . This permits us to use 1 for all the weights and the summation index from  .  

Example 2.  Assume that is periodic with period  ,  i.e.  ,  and is defined by

      for  .  

Find the Fourier polynomial of degree n = 5  for the 12  equally spaced points in the interval  .  

Use the "numerical integration" method for finding the coefficients.
Solution 2.

The Fast Fourier Transform for data.  

The FFT is used to find the trigonometric polynomial when only data points are given.  We will demonstrate three ways to calculate the FFT.  The first method involves computing sums, similar to "numerical integration," the second method involves "curve fitting," the third method involves "complex numbers."  

Computing the FFT with sums.  

Given data points where and over [0,2L] where for .

Also given that , to that the data is periodic with period .

To construct the FFT polynomial over [0,2L] of degree m.

    ,   

The abscissa's form  n subintervals of equal width    based on  .  The coefficients are   

      for  
and
      for  .  

The construction is possible provided that  .  

Remark.  Notice that the sums involve only ordinates .  

Animations (Discrete Fourier series FFT  Discrete Fourier series FFT).  Internet hyperlinks to animations.

Example 3.  Given the 12  equally spaced data points



which can be extended periodically over , if we define.  

Find the Fourier polynomial of degree n = 5  for the 12  equally spaced points over interval  .  

Use numerical sums to find the coefficients.

Solution 3.

Fitting a Fourier trigonometric polynomial to data.  

The built in Mathematica Fit subroutine can be used to perform the computation.

Caution.  Do not include both endpoints of the interval.

Example 4.  Given the 12  equally spaced data points



which can be extended periodically over , if we define  .  

Find the Fourier polynomial of degree n = 5  for the 12  equally spaced points over interval  .  

Use Mathematica's Fit subroutine to find the coefficients.

Solution 4.

Background for using Mathematica's FFT. Trigonometric curve fitting at discrete points is equivalent to finding the Fast Fourier Transform (FFT) for a discrete data set. The coefficients of the trigonometric polynomial can be obtained using Mathematica's built in "Fourier" procedure (FFT).  To uncover these secrets, click the right end of this cell.

Caution.  However, we first we need to use that part of the period function    defined in the interval  .  That's the way Mathematica expects us to see it !  Be sure to redefine    on the interval  .   

Example 5.  Given the 12  equally spaced data points



which can be extended periodically over , if we define  .  

Find the Fourier polynomial of degree n = 5  for the 12  equally spaced points over interval  .  

Use Mathematica's built in Fourier subroutine to find the solution.

Solution 5.

Old Lab Project (Trigonometric Polynomials-FFT  Trigonometric Polynomials-FFT).  
Internet hyperlinks to an old lab project.  

Research Experience for Undergraduates

Fast Fourier Transform  Fast Fourier Transform  
Internet hyperlinks to web sites and a bibliography of

Downloads (Fast Fourier Transform Fast Fourier Transform).  
Download this Mathematica notebook.  

(c) John H. Mathews 2003