Continuous functions defined in terms of cos and sin 

Consider a function of the form where and are constants. The value is the period of the function. 

>

 

>

 

(1)

 

Set to the following values. 

>

 

 

 

	(2)

 

>

 

>

 

Remarks 

• so is the period of the function. In this case the period is .
  

• The frequency is the value . In this case the frequency is .

Next consider a function of the following form which has two terms. 

>

 

>

 

(3)

 

where and where the period is . 

>

 

(4)

 

>

 

(5)

 

>

 

 

 

	(6)

 

>

 

>

 

Let us look at the terms making up the sum. 

>

 

(7)

 

>

 

(8)

 

>

 

(9)

 

>

 

>

 

Remarks 

• The above plot is for the term    where

• The coefficient represents the amount of information in this harmonic.

• The period of this harmonic is

• The frequency of this harmonic is

>

 

>

 

>

 

Remarks 

• The above plot is for the term    where

• The coefficient represents the amount of information in this harmonic.

• The period of this harmonic is

• The frequency of this harmonic is

>

 

Below is a table of the individual plots and the combined plot. 

>

 

Three plots    Above left: The LowFreq term   Above right: The HighFreq term     Lower right: The Combined function

Orthogonality Properties of cos and sin 

>

 

We are interested in representing in terms of a sum of trig functions as follows: 

where the coefficients and are to be determined from the function . 

For simplicity, suppose that the function is defined for , with period  so will be represented in the following form. 

>

 

(10)

 

>

 

The following orthogonality properties allow us to determine formulas for and in terms of integrals involving  . 

>

 

>

 

>

 

(11)

 

>

 

(12)

 

>

 

(13)

 

>

 

(14)

 

>

 

(15)

 

>

 

(16)

 

We will also need the values 

>

 

(17)

 

>

 

(18)

 

By exploiting these orthogonality properties, we can derive a formula for each and . 

>

 

Example: Computing Fourier Series Coefficients 

Consider the following continuous function. 

>

 

>

 

(29)

 

>

 

>

 

Compute some of the Fourier coefficients of  . 

Note: In the following, we use Maple's inert operator and then we invoke numerical integration by applying . 

>

 

(30)

 

>

 

 

 

 

 

 

 

 

 

 

	(31)

 

Compute and store the Fourier coefficients up to . 

>

 

Compute and store the partial sums of the Fourier series for . 

>

 

Display plots of (in blue) superimposed on the plot of the original function (in red). 

>

 

>

 

When we see that the Fourier series approximation matches the original function very well. 

We can use the Maple command to do "floating point normalization", meaning to round the numbers to a specified number of digits and to set to zero any values that are small relative to the number of digits specified. 

For example, suppose that we are interested in 4 digits of accuracy. 

>

 

(32)

 

>

 

(33)

 

>

 

(34)

 

Apply to decrease the number of terms in . 

>

 

(35)

 

>

 

(36)

 

>

 

(37)

 

We have decreased the number of terms in from to while retaining 4 digits of accuracy. 

>

 

>

 

Complex exponential form 

As a more compact representation for Fourier series, we choose to use complex exponential form, based on the well-known relationships: 

>

 

>

 

(38)

 

>

 

(39)

 

or 

>

 

(40)

 

>

 

(41)

 

The complex exponential form for the Fourier series is 

>

 

(42)

 

and by using orthogonality properties for complex exponentials similar to the case of and , one can show that 

>

 

(43)

 

>

 

The correspondence between the coefficients and the coefficients , in the - representation is as follows: 

for ", mathvariant = "normal", fence = "false", separator = "false", stretchy = "false", symmetric = "fal..." align="center" border="0"> . 

We will see that in applications, we are most interested in the relative magnitudes of the coefficients corresponding to various frequencies . Note that 

  and    . 

In typical applications, there is a small amount of information in the high-frequency terms. In other words, the coefficients will be very small in magnitude for large . Therefore, it is reasonable to truncate to a finite summation: 

>

 

(44)

 

for some integer . 

>

 

Discrete Fourier Transform (DFT) 

Analogous to the continuous Fourier series discussed above, we define the Discrete Fourier Transform (DFT) as follows. 

• Suppose we are given a finite set of data values , for .
  

• This data is a sampling of some continuous function but we do not know ; we will work only with the discrete data.
  

• Approximate the underlying function in a Fourier series using complex exponential form as follows:   for
  

• Or, in a notation using   which is a primitive root of unity:    for .
  

• Question: Given how do we determine the "Fourier coefficients" ?
  

• This can be viewed as a problem of polynomial interpolation.
  

• Specifically, find the polynomial    which interpolates the given data at the roots of unity .
  

• I.e., the equations to be solved are:    for .
  

• The Vandermonde linear system for this interpolation problem takes the form    where the -by- Vandermonde matrix is for and where and are vectors of length with entries and respectively.
  

• For example (noting that for a Matrix in Maple, the indexing is from 1 to ) :
  

>

 

>

 

(45)

 

>

 

(46)

 

>

 

>

 

The Vandermonde system is 

>

 

(47)

 

>

 

• Although solving an -by- linear system costs, in general, operations, in this case the matrix is very special and we can express its inverse as follows:   for .
  

• For example:
  

>

 

>

 

(48)

 

>

 

(49)

 

>

 

(50)

 

>

 

(51)

 

>

 

• Since the solution to the Vandermonde system is simply we obtain the following formula for the Fourier coefficients for .
  

• We refer to the transformation    as the forward DFT and we refer to the transformation    as the inverse DFT.  The formula for the inverse DFT is the formula stated near the beginning of this section:
  
   for .
  

>

 

Fast Fourier Transform (FFT) 

• Both the forward DFT and the inverse DFT can be viewed as a problem of polynomial evaluation.
  

• For simplicity, assume that is a power of : for some nonnegative integer .
  

• Suppose we write a procedure FFTeval which is designed to evaluate a polynomial represented by the vector of coefficients of length at the points where is a primitive root of unity:   or  
  

• Evaluating a polynomial at one point costs, in general, operations and therefore it costs, in general, operations to evaluate a polynomial of length at points.
  

• However, our task is to evaluate at a very special set of points, namely the roots of unity. Due to the symmetries which hold for this special set of evaluation points, we are able to design procedure FFTeval such that its cost is .
  

• The fundamental symmetry which is exploited in procedure FFTeval is the following. For the evaluation points , half of the points are negatives of the other half. In other words,   for (Proof:   .)
  

• The above symmetry is exploited by breaking the given polynomial of length into two halves, separating the even and odd  powers as follows:
  
     
  
  
  
  
  
  
  
  
  
  
  
  
  where and are polynomials of length :
  
        and    .
  

• If follows that if one computes the values for and the values for then with only a small amount of additional work one has all values for :
        for ;
        for .
  

• This is a typical divide and conquer algorithm: To solve a problem of size we solve two problems each of size and then combine values to get the desired result. This can be implemented as a recursive procedure and one can see that the additional work (in addition to the two recursive calls) is operations.
  

• The recursive procedure is valid because the symmetry mentioned above (half of the evaluation points are negatives of the other half) holds at each recursive level. For example, if then the evaluation points at the top level are the eight roots of unity, the evaluation points at the next level are the squares of these values, namely the four roots of unity , at the next level it is the squares of these values, namely the two square roots of unity , and then we reach the base of the recursion with one evaluation point .
  

• Recursive procedure FFTeval is presented below. Note that a Vector in Maple is indexed from 1 to
  

>

 

>

 

Forward FFT: 

Define . 

Then   

Inverse FFT:
 

With defined as above,
 

. 

Example: 

>

 

(52)

 

>

 

(53)

 

>

 

(54)

 

>

 

(55)

 

Forward FFT: 

>

 

(56)

 

Check that the Inverse FFT recovers the original data values: 

>

 

(57)

 

>

 

(58)

 

>

 

(59)

 

>

 

(60)

 

>