Does DFT give exact results on the gridpoints?

232 Views Asked by At

Let's suppose we have a periodic function $f(x)$ with period $L$ and we know its Fourier Series coefficients $A_n$. Now I have a set of $N$ equally spaced gridpoints between $[0, L)$ at distances $x_i=\{0, a, 2a, ..., Na\}$ at which I want to evaluate my function, ie. I'm interested in $f(x_i)$. Does the inverse Discrete Fourier Transform of $\{A_0, A_1, ...,A_N \}$ give an EXACT result? I know the Fourier Series can be approximated with the Discrete Fourier Transform, but I wonder whether it actually gives the exact values on the gridpoints. If so, can I see the proof?

If not, what is the precise relationship between a periodic function's Fourier coefficients $A_k$ and its Discrete Fourier Transform $\tilde{F}_k$?

Thanks!

Edit: Here is what I got so far:

The Fourier Series of $f(x)$ evaluated at the point $x_n=n L/N$ is:

$f(x_n) = \sum_{k=-\infty}^{\infty} A_k e^{i2\pi k n/N}$

I regroup the sum so that the outer one is performed on the $\{0,N\}$ interval and the inner sum takes care of the periodic translations:

$f(x_n) =\sum_{k=0}^{N} \sum_{\Delta=-\infty}^{\infty} A_{k+N\Delta} e^{i2\pi (k+N \Delta ) n/N}$

and since $e^{i2\pi (k+N \Delta ) n/N} = e^{i2\pi k n/N}$

we have:

$f(x_n) =\sum_{k=0}^{N} e^{i2\pi kn/N} \sum_{\Delta=-\infty}^{\infty} A_{k+N\Delta} $

so we recognize the DFT:

$\tilde{F}_k = \sum_{\Delta=-\infty}^{\infty} A_{k+N\Delta} $

Now I try to simplify the sum, so I plug the formula of the Fourier Series coefficients:

$ A_{k+N\Delta} = \frac{1}{L} \int_{-L/2}^{L/2} f(x) e^{-i2\pi k x/L} e^{-i2\pi \Delta N x/L} dx $

into the sum:

$\tilde{F}_k = \frac{1}{L} \int_{-L/2}^{L/2} dx\ f(x) e^{-i2\pi k x/L} \sum_{\Delta=-\infty}^{\infty} e^{-i2\pi \Delta N x/L} $

This is where I lost the thread: the second sum gives a Dirac delta function. If I plug that into the integral, that removes the integral and I'm left with $\tilde{F}_k = some\ constant \times f(0)$ which is clearly wrong...

1

There are 1 best solutions below

0
On

DFT has the following definition: $f^{DFT}_k=\frac{1}{N}\sum_{0}^{N-1} f_je^{-\frac{i2\pi jk}{N}} $

The Fourier series is by definition the limit of DFT for the case when $\frac{1}{N}=\frac{\Delta x}{L}\to0$. k stays discrete but varies in steps of $\frac{2\pi}{L}$ from $-\infty$ to $\infty$

You can't take DFT as a special case of FS because it's the other way around so you cannot avoid discretizing at some point. If you do so then for any finite period N in x space, the values in k space will have period N as well, thus the only possible value for $\Delta$ is $\Delta=0$ so the sum is not Dirac delta but 1, and than you discretize the rest and you get back to the original definition of DFT.

So FFT is as good of an approximation for FS as your numerical integration.

The other way round if you have all the infinite number of FS coefficients you just apply the formula for the inverse transform for as many coefficients you need to get arbitrary precision. The formulas for iDFT and iFS are the same the latter having it's limits at infity so if you calculate numerically you always end up doing the same ie iDFT.

So from a practical point of view FS and FFT are the same for large N or large K.