Module for Fast Fourier Transform (FFT)

Check out the new Numerical Analysis Projects page.


Definition (Piecewise Continuous).  The function  [Graphics:Images/FourierSeriesMod_gr_1.gif]  is piecewise continuous on the closed interval  [Graphics:Images/FourierSeriesMod_gr_2.gif],  if there exists values  [Graphics:Images/FourierSeriesMod_gr_3.gif]  with  [Graphics:Images/FourierSeriesMod_gr_4.gif]  such that  f  is continuous in each of the open intervals  [Graphics:Images/FourierSeriesMod_gr_5.gif],  for  [Graphics:Images/FourierSeriesMod_gr_6.gif]  and has left-hand and right-hand limits at each of the values  [Graphics:Images/FourierSeriesMod_gr_7.gif],  for  [Graphics:Images/FourierSeriesMod_gr_8.gif].  

Definition (Fourier Series).  If  [Graphics:Images/FourierSeriesMod_gr_9.gif]  is periodic with period  [Graphics:Images/FourierSeriesMod_gr_10.gif]  and is piecewise continuous on  [Graphics:Images/FourierSeriesMod_gr_11.gif],  then the Fourier Series  [Graphics:Images/FourierSeriesMod_gr_12.gif]  for  [Graphics:Images/FourierSeriesMod_gr_13.gif]  is

    [Graphics:Images/FourierSeriesMod_gr_14.gif],

where the coefficients  [Graphics:Images/FourierSeriesMod_gr_15.gif]  are given by the so-called Euler's formulae:  

    [Graphics:Images/FourierSeriesMod_gr_16.gif],  
and  
    [Graphics:Images/FourierSeriesMod_gr_17.gif].  

Theorem (Fourier Expansion).  Assume that  [Graphics:Images/FourierSeriesMod_gr_18.gif]  is the Fourier Series for  [Graphics:Images/FourierSeriesMod_gr_19.gif].   If  [Graphics:Images/FourierSeriesMod_gr_20.gif]  are piecewise continuous on  [Graphics:Images/FourierSeriesMod_gr_21.gif],  then  [Graphics:Images/FourierSeriesMod_gr_22.gif]  is convergent for all  [Graphics:Images/FourierSeriesMod_gr_23.gif].  

The relation  [Graphics:Images/FourierSeriesMod_gr_24.gif]  holds for all  [Graphics:Images/FourierSeriesMod_gr_25.gif] where  [Graphics:Images/FourierSeriesMod_gr_26.gif]  is continuous.  If  [Graphics:Images/FourierSeriesMod_gr_27.gif]  is a point of discontinuity of  [Graphics:Images/FourierSeriesMod_gr_28.gif],  then

     [Graphics:Images/FourierSeriesMod_gr_29.gif],  

where  [Graphics:Images/FourierSeriesMod_gr_30.gif]  denote the left-hand and right-hand limits, respectively.  With this understanding, we have the Fourier Series expansion:

    [Graphics:Images/FourierSeriesMod_gr_31.gif] .  

Definition (Fourier Polynomial).  If  [Graphics:Images/FourierSeriesMod_gr_32.gif]  is periodic with period  [Graphics:Images/FourierSeriesMod_gr_33.gif]  and is piecewise continuous on  [Graphics:Images/FourierSeriesMod_gr_34.gif],  then the Fourier Polynomial  [Graphics:Images/FourierSeriesMod_gr_35.gif]  for  [Graphics:Images/FourierSeriesMod_gr_36.gif]  of degree m is

    [Graphics:Images/FourierSeriesMod_gr_37.gif],

where the coefficients  [Graphics:Images/FourierSeriesMod_gr_38.gif]  are given by the so-called Euler's formulae:  

    [Graphics:Images/FourierSeriesMod_gr_39.gif],  
and  
    [Graphics:Images/FourierSeriesMod_gr_40.gif].  

 

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

 

Example 1.  Assume that [Graphics:Images/FourierSeriesMod_gr_41.gif] is periodic with period  [Graphics:Images/FourierSeriesMod_gr_42.gif],  i.e.  [Graphics:Images/FourierSeriesMod_gr_43.gif],  and is defined by

    [Graphics:Images/FourierSeriesMod_gr_44.gif]  for  [Graphics:Images/FourierSeriesMod_gr_45.gif].  

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

 

Numerical Integration calculation for the Fourier trigonometric polynomial.  

Assume that  [Graphics:Images/FourierSeriesMod_gr_67.gif]  is periodic with period  [Graphics:Images/FourierSeriesMod_gr_68.gif]  and is piecewise continuous on  [Graphics:Images/FourierSeriesMod_gr_69.gif],

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

    [Graphics:Images/FourierSeriesMod_gr_70.gif],   

There are n subintervals of equal width  [Graphics:Images/FourierSeriesMod_gr_71.gif]  based on  [Graphics:Images/FourierSeriesMod_gr_72.gif].  The coefficients are   

    [Graphics:Images/FourierSeriesMod_gr_73.gif]  for  [Graphics:Images/FourierSeriesMod_gr_74.gif].  
and
    [Graphics:Images/FourierSeriesMod_gr_75.gif]  for  [Graphics:Images/FourierSeriesMod_gr_76.gif].  

The construction is possible provided that  [Graphics:Images/FourierSeriesMod_gr_77.gif].  

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 [Graphics:Images/FourierSeriesMod_gr_78.gif] for both the [Graphics:Images/FourierSeriesMod_gr_79.gif] and [Graphics:Images/FourierSeriesMod_gr_80.gif].  Since f(x) has period  [Graphics:Images/FourierSeriesMod_gr_81.gif],  it follows that [Graphics:Images/FourierSeriesMod_gr_82.gif]. This permits us to use 1 for all the weights and the summation index from  [Graphics:Images/FourierSeriesMod_gr_83.gif].  

 

Example 2.  Assume that [Graphics:Images/FourierSeriesMod_gr_84.gif] is periodic with period  [Graphics:Images/FourierSeriesMod_gr_85.gif],  i.e.  [Graphics:Images/FourierSeriesMod_gr_86.gif],  and is defined by

    [Graphics:Images/FourierSeriesMod_gr_87.gif]  for  [Graphics:Images/FourierSeriesMod_gr_88.gif].  

Find the Fourier polynomial of degree n = 5  for the 12  equally spaced points in the interval  [Graphics:Images/FourierSeriesMod_gr_89.gif].  

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 [Graphics:Images/FourierSeriesMod_gr_127.gif] where [Graphics:Images/FourierSeriesMod_gr_128.gif] and [Graphics:Images/FourierSeriesMod_gr_129.gif] over [0,2L] where [Graphics:Images/FourierSeriesMod_gr_130.gif] for [Graphics:Images/FourierSeriesMod_gr_131.gif].

Also given that [Graphics:Images/FourierSeriesMod_gr_132.gif], to that the data is periodic with period [Graphics:Images/FourierSeriesMod_gr_133.gif].

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

    [Graphics:Images/FourierSeriesMod_gr_134.gif],   

The abscissa's form  n subintervals of equal width  [Graphics:Images/FourierSeriesMod_gr_135.gif]  based on  [Graphics:Images/FourierSeriesMod_gr_136.gif].  The coefficients are   

    [Graphics:Images/FourierSeriesMod_gr_137.gif]  for  [Graphics:Images/FourierSeriesMod_gr_138.gif]
and
    [Graphics:Images/FourierSeriesMod_gr_139.gif]  for  [Graphics:Images/FourierSeriesMod_gr_140.gif].  

The construction is possible provided that  [Graphics:Images/FourierSeriesMod_gr_141.gif].  

Remark.  Notice that the sums [Graphics:Images/FourierSeriesMod_gr_142.gif] involve only [Graphics:Images/FourierSeriesMod_gr_143.gif] ordinates [Graphics:Images/FourierSeriesMod_gr_144.gif].  

 

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

 

Example 3.  Given the 12  equally spaced data points

[Graphics:Images/FourierSeriesMod_gr_145.gif][Graphics:Images/FourierSeriesMod_gr_146.gif][Graphics:Images/FourierSeriesMod_gr_147.gif][Graphics:Images/FourierSeriesMod_gr_148.gif]

which can be extended periodically over [Graphics:Images/FourierSeriesMod_gr_149.gif], if we define[Graphics:Images/FourierSeriesMod_gr_150.gif].  

Find the Fourier polynomial of degree n = 5  for the 12  equally spaced points over interval  [Graphics:Images/FourierSeriesMod_gr_151.gif].  

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

[Graphics:Images/FourierSeriesMod_gr_198.gif][Graphics:Images/FourierSeriesMod_gr_199.gif][Graphics:Images/FourierSeriesMod_gr_200.gif][Graphics:Images/FourierSeriesMod_gr_201.gif]

which can be extended periodically over [Graphics:Images/FourierSeriesMod_gr_202.gif], if we define  [Graphics:Images/FourierSeriesMod_gr_203.gif].  

Find the Fourier polynomial of degree n = 5  for the 12  equally spaced points over interval  [Graphics:Images/FourierSeriesMod_gr_204.gif].  

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  [Graphics:Images/FourierSeriesMod_gr_238.gif]  defined in the interval  [Graphics:Images/FourierSeriesMod_gr_239.gif].  That's the way Mathematica expects us to see it !  Be sure to redefine  [Graphics:Images/FourierSeriesMod_gr_240.gif]  on the interval  [Graphics:Images/FourierSeriesMod_gr_241.gif].   

 

Example 5.  Given the 12  equally spaced data points

[Graphics:Images/FourierSeriesMod_gr_242.gif][Graphics:Images/FourierSeriesMod_gr_243.gif][Graphics:Images/FourierSeriesMod_gr_244.gif][Graphics:Images/FourierSeriesMod_gr_245.gif]

which can be extended periodically over [Graphics:Images/FourierSeriesMod_gr_246.gif], if we define  [Graphics:Images/FourierSeriesMod_gr_247.gif].  

Find the Fourier polynomial of degree n = 5  for the 12  equally spaced points over interval  [Graphics:Images/FourierSeriesMod_gr_248.gif].  

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