MN08LAB

Ćwiczenia: FFT

Ćwiczenie

Udowodnij, że faktycznie macierz $U_N=\frac{1}{\sqrt{N}}{F}_N$ jest macierzą unitarną, to znaczy $U_N^{*}=U_N^{-1}$.

Rozwiązanie

Należy przeliczyć, korzystając ze struktury macierzy $F_N$ i jej symetrii, że

Parser nie mógł rozpoznać (nieznana funkcja „\begincases”): {\displaystyle \displaystyle w_j^T w_k = \begincases N, \qquad \mbox{gdy } j = k\\ 0, \qquad \mbox{w przeciwnym przypadku,} \endcases }

gdzie $w_j$ oznacza $j$-ty wiersz (kolumnę) macierzy $F_N$. Dowód tego faktu to prosty wniosek ze wzoru na sumę $N$ wyrazów ciągu geometrycznego.

Ćwiczenie

Jak zastosować FFT do szybkiego wymnożenia dwóch, rzeczywistych wektorów długości $N$ przez macierz DFT?

Rozwiązanie

Niech dane wektory to $f,g\in R^N$. Oczywiście możemy przyłożyć DFT do zespolonego wektora $f+i\cdot g$,

$w=F_N(f+ig).$

Po dłuższych rachunkach, stwierdzamy, że

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned F_N f &= \frac{1}{2} \left( Re(w + T_N w) + i\, Im(w- T_Nw)\right)\\ F_N g &= \frac{1}{2} \left( Im(w + T_N w) - i\, Re(w- T_Nw)\right), \endaligned}

gdzie $T_N$ jest operatorem, który odwraca kolejność wszystkich (oprócz pierwszej) współrzędnych wektora, tzn. $T_{N}w=[w_0,w_{N-1},w_{N-2},\dots ,w_1{]}^T$.

Ćwiczenie

Jak zastosować FFT do szybkiego wymnożenia jednego rzeczywistego wektora długości $2N$ przez macierz $F_{2N}$?

Wskazówka

Sprowadź zadanie do poprzedniego!

Ćwiczenie

Podaj algorytm wyznaczania $f=F_N^{-1}c$, gdzie $c\in C^N$ jest zadanym wektorem, a $F_N$ jest macierzą DFT.

Wskazówka

Sprowadź zadanie do zadania mnożenia przez macierz DFT!

Rozwiązanie

Ponieważ

$F_N^{-1}f=\frac{1}{N}{F}_N^{*}f=\frac{1}{N}\overline{F_N^T}f=\frac{1}{N}\overline{F_N\overline{f}},$

to stąd algorytm w Octave (przypomnijmy, że w Octave operator ' oznacza hermitowskie sprzężenie) mógłby wyglądać tak:

Algorytm

---

f = (fft(c'))'/N;

Ćwiczenie

Sprawdź eksperymentalnie, że mnożenie przez cykliczną macierz Toeplitza rzeczywiście daje się wykonać przy użyciu FFT. Czy przy okazji można coś powiedzieć o wartościach własnych i wektorach własnych takiej macierzy?

Ćwiczenie

Zaimplementuj FFT i porównaj wyniki (zwłaszcza: czas wykonania) z wynikami procedury z Octave oraz z FFTW, a także z procedurą opartą na mnożeniu wprost przez macierz $F_N$.