Fourier transforms

Let $f(x)$ be a real or complex function defined on the interval $[0,L]$. Let

$$Tf(t) \ = \ \int^L_0 f(x)e^{itx}dx.$$

be the Fourier transform of $f(x)$. Let $N$ a power of $2$, and

$$D \ = \ \frac{L}{N}.$$

The discrete Fourier transform of $f$ is

$$T_Nf(t) \ = \ D\mathop{\hbox{$\displaystyle\sum$}}\limits _{p=0}^{N-1}f(pD)e^{itpD}.$$

It is the true Fourier transform of the function

$$\mathop{\hbox{$\displaystyle\sum$}}\limits _{p=0}^{N-1}Df(pD)\delta_{pD},$$

which is an approximation of $f$. Here we assume that $f$ is linear between $pD$ and $(p+1)D$, hence we have the exact formula

$$Tf(t) \ \ = \ \ \frac{2(1-\cos(tD))}{t^2D^2}T_Nf(t) \ + \ \frac{1-itD-e^{-itD}}{t^2D}(f(L)e^{itL}-f(0)).$$

A FFT would give the value of $T_Nf(t)$ for all multiples of $2\pi/L$. Suppose we have

$$t \ = \ \frac{2\pi}{L}(q+\epsilon),$$

with $q$ an integer and $\epsilon\leq\frac{1}{2}$. Then we have

$$T_Nf(t) \ = \ D\mathop{\hbox{$\displaystyle\sum$}}\limits _{p=0}^{N-1}f(pD)e^{2i\pi\frac{pq}{N}}. e^{2i\pi\frac{p}{N}\epsilon}.$$

Developping the last exponential, we get

$$T_Nf(t) \ = \ D\mathop{\hbox{$\displaystyle\sum$}}\limits _{n... ...}^{N-1}f(pD)(\frac{2i\pi p}{N})^n e^{2i\pi\frac{pq}{N}}\biggl).$$

This means that we would get the exact formula for $T_Nf(t)$ if we had all the FFT's of the functions

$$f_n(x) \ = \ f(x)(\frac{2i\pi x}{L})^n.$$

In fact only the $n$ between 0 and 20 are needed to get double precision. We can even reduce this number by taking approximations of the exponential using Tschebychev polynomials.

We can of course also define Fourier transforms of a function $f(x)$ defined on an arbitrary interval $[a,b]$, by first computing the Fourier transform of $f(x-a)$ (defined on $[0,b-a]$) and multiplying the result by $e^{ita}$.