Fast Fourier Transform (FFT)

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  
        .  

Numerical Integration calculation for the Fourier trigonometric polynomial.  

    Assume that    is periodic with period    and is piecewise continuous on  , we shall 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  .  

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 .  We shall 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  .