MN10LAB

FFT

<<< Powrót do strony głównej przedmiotu Metody numeryczne

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__

Ć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

$w_j^{*}{w}_k=\{\begin{array}{l}N,\text{gdy }j=k\\ 0,\text{w przeciwnym przypadku,}\end{array}$

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

$\begin{array}{rl}{F}_{N}f& =\frac{1}{2}(Re(w+T_{N}w)+iIm(w-T_{N}w))\\ F_{N}g& =\frac{1}{2}(Im(w+T_{N}w)-iRe(w-T_{N}w)),\end{array}$

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\stackrel{‾}{f}},$

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

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

Ćwiczenie: czy twoje programy naprawdę działają szybko?

Zaimplementuj rekurencyjną wersję FFT i porównaj wyniki (zwłaszcza: czas wykonania) z wynikami procedury z biblioteki FFTW, a także z procedurą opartą na mnożeniu wprost przez macierz $F_N$ (możesz nawet skorzystać ze zoptymalizowanych BLASów).