PHY.K02UF Molecular and Solid State Physics
|
| |||
PHY.K02UF Molecular and Solid State Physics | ||||
A discrete Fourier transform can be used to determine a periodic function that goes through a discrete series of data points. Consider a set of $N$ equally spaced data points $(x_q,f_q)$, $x_q = q\Delta x$. We seek a periodic function $f(x)$ with a period $a = N\Delta x$ that passes through all of the points. This function can be expressed as a Fourier series,
$$f(x) = \sum\limits_{n=-\infty}^{\infty}F_n\exp \left(\frac{i2\pi nx}{N\Delta x}\right).$$Although it is possible to construct many periodic functions that go through all the data points $f_q$ with wavelengths smaller than $\Delta x$, it makes sense to restrict the sum over $n$ to the fewest necessary to go through all the points. For $N$ points, at least $N$ exponential terms are needed so we will take $n = n^*,n^*+1,n^*+2,\cdots,\,n*+N-1$. Here $n^*$ can be any integer so there are infinitely many periodic functions that will pass through all of the data points but the smoothest function $f(x)$, is obtained for $n^*=\text{Int}(-N/2+1)$, where $\text{Int}(x)$ rounds down to the nearest integer.
To determine the values of $F_n$, the points $(x_q,f_q)$ are substituted into expression for the Fourier series,
$$f_q = \sum\limits_{n=n^*}^{n^*+N-1}F_n\exp \left(\frac{i2\pi nx_q}{N\Delta x}\right).$$Since $x_q=q\Delta x$,
$$f_q = \sum\limits_{n=n^*}^{n^*+N-1}F_ne^{i2\pi qn/N}.$$Multiply by $e^{-i2\pi qn'/N}$ and sum over $q$.
$$\sum\limits_{q=0}^{N-1}F_ne^{-i2\pi qn'/N} = \sum\limits_{q=0}^{N-1}\sum\limits_{n=n^*}^{n^*+N-1}F_ne^{i2\pi q(n-n')/N}.$$In the double sum on the right side, consider a specific value of $n$ and the sum over $q$. Each term $e^{i2\pi q(n-n')/N}$ can be represented as a vector that originates at the origin and ends on the unit circle in the complex plane. These vectors are uniformly distributed around the unit circle and add to zero unless $n=n'$. When $n=n'$, the double sum evaluates to $NF_n$. This yields an expression for the Fourier coefficients,
$$F_n = \frac{1}{N} \sum\limits_{q=0}^{N-1}f_qe^{-i2\pi qn/N}.$$This equation is called the Discrete Fourier Transform of the data series $f_q$. In the form below, a column of values for $f_q$ can be input. This data is plotted as red points as a function of $q$. When the button is pushed, the Fourier coefficients for are calculated using a discrete Fourier transform and the correponding continuous function is plotted as the blue line. Add points to the $f_q$ list to see how the function adjusts. Fits with other values of $n^*$ can be displayed by inputting an integer for $n^*$ and pressing the button.
| $f_q$
$n$ $\text{Re}[F_n]$ $\text{Im}[F_n]$ |
| ||||||||||||
In terms of sines and cosines, the Fourier series is,
$$f(x) = \sum\limits_{n=n^*}^{n^*+N-1}\text{Re}[F_n]\cos \left(\frac{2\pi nx}{N\Delta x}\right) + \text{Im}[F_n]\sin \left(\frac{2\pi nx}{N\Delta x}\right).$$The smoothest fit uses the $N$ values of $n$ that are the closest to zero. These are the components with the longest wavelengths. An infinite number of periodic functions that go through all of the data points using shorter wavelengths can be found. Change $n^*$ to another number besides the 'smoothest fit' value to see one of these functions.
The Discrete Fourier Transform discussed here is not numerically efficient for large data sets. There is a better (but more complicated) algorithm called a Fast Fourier Transform that performs the same calculation more efficiently. The standard FFT algorithm uses $n^*=0$ as the default.