There are a few issues with your code. The first is the use of linspace
. It includes both endpoints of the interval, thus both $0$ and $4\pi$ appear. This is not what you want to happen with the discretization for the purpose of Fourier transform. E.g., linspace(0,2*pi,4)
returns the vector $0,2\pi/3, 4\pi/3, 2\pi$ but what we actually want is $0,\pi/2, \pi , 3\pi/2$. Solution: introduce the step $dx=2\pi/N$ and create the vector a+[0:N-1]*dx
.
Second, the correct version of $2\pi i \xi$ in the discrete setting is not obvious, due to multiple ways to enumerate the terms of Fourier series. In the code below this role is played by vector $k$. I adapted it from Finding Derivatives using Fourier Spectral Methods.
a = 0;
b = 4*pi;
N = 4096;
dx = (b-a)/N;
t = a + dx*(0:N-1);
f = sin(t);
fftx = fft(f);
k = 2*pi/(b-a)*[0:N/2-1, 0, -N/2+1:-1];
dffft = 1i*k.*fftx;
df = ifft(dffft);
plot(t,df)
Why the strange $k$ vector? Part of it is scaling: the "wider" the function, the more narrow is its Fourier transform (it scales in the opposite direction). This is why we divide by $(b-a)$ there. To understand the weird [0:N/2-1, 0, -N/2+1:-1]
, think of what the components of fft
are: they are the coefficients of the complex polynomial that matches $f$. For a simple example, take t=0:pi/4:(2*pi-pi/4)
; that is, $N=8$ here. Applying fft
to
f = 3+7*exp(1i*t)+8*exp(3i*t)+9*exp(5i*t)+10*exp(7i*t)
we get 8*[3 7 0 8 0 9 0 10]
which is, as expected, the coefficients of exponentials in $f$ (multiplied by $8$, which isn't important). Multiplying the coefficients by 1i*[0:7]
gives us the Fourier coefficients of $f'$, and ifft
returns $f'$ itself. Sweet. As long as we work with polynomials of $e^{it}$, all this works fine.
Trouble arises when our $f$ has negative powers of $e^{it}$, for example $\sin t = \frac{1}{2}(e^{it}-e^{-it})$. Where does $e^{-it}$ go under the fft
? Same place where $e^{7it}$ goes, since $e^{-it} \equiv e^{7it}$ on our grid. But... then our algorithm will multiply it by $7i$, not by $-i$! Most assuredly,
$$(\sin t)' \ne \frac{1}{2}(ie^{it}-7ie^{-it})$$
This is the problem that [0:N/2-1, 0, -N/2+1:-1]
solves. It simply recognizes that $e^{7it}$ should be treated as $e^{-it}$ for the purpose of taking the derivative: that is, it should be multiplied by $-i$, not by $7i$.
With $N=8$, the multiplying vector is [0 1 2 3 0 -3 -2 -1]
. It
- kills the constant term,
- multiplies $e^{ikt}$ component by $k$ for $k=1,2,3$,
- kills the $e^{4it}$ component (What else to do with it? We don't know if it's $e^{4it}$ or $e^{-4it}$. Note that $\sin 4t $ will have zero DFT at this scale).
- multiplies $e^{ikt} = e^{i(k-8)t}$ component by $k-8$ for $k=5,6,7$.
Best Answer
You are correct. $F^H = \bar{F}$ since $F^T = F$. Thus $F^{-1} = F^H = \bar{F}$, and so:
$$ \hat{\mathbf{a}} = F\mathbf{a} \Leftrightarrow F^H\hat{\mathbf{a}} = \mathbf{a} \Leftrightarrow \bar{F}\hat{\mathbf{a}} = \mathbf{a} $$
where $\mathbf{a} = \begin{bmatrix} a_0 & a_1 & \cdots & a_{n-1} \end{bmatrix}^T$ and similar for $\mathbf{\hat{a}}$
You're notation is a little off here. You have a matrix operating on a scalar. I believe what you intended is the DFT matrix acting on the vector of $a_k$'s as I've written above.
As you can see from above, they are equivalent. So it is perfectly acceptable to write it either way.
Now, the question of why is $F^{-1}$ typically written as $F^H$ instead of $\bar{F}$, is a different question all together. I can't say for certain, but I would conjecture that this is because this is because $F$ is a type of matrix from a larger class, called unitary matrices. For a unitary matrix, $P$, it is the case that:
$$ P^{-1} = P^H $$
Writing $F^H$ is perhaps more obvious a reminder that the DFT matrix is unitary, and unitary matrices have useful properties which are often used in derivations (such as norm preservation, i.e., Parseval's theorem).