Personal tools

MN10LAB

From Studia Informatyczne


FFT

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

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

Ćwiczenie

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

Rozwiązanie

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

\displaystyle  w_j^* w_k = \begincases  N, \qquad  \mbox{gdy }  j = k\\ 0,   \qquad  \mbox{w przeciwnym przypadku,}  \endcases

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

Ćwiczenie

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

Rozwiązanie

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

\displaystyle  w = F_N(f + i\, g).

Po dłuższych rachunkach stwierdzamy, że

\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 \displaystyle T_N jest operatorem, który odwraca kolejność wszystkich (oprócz pierwszej) współrzędnych wektora, tzn. \displaystyle T_Nw = [w_0,w_{N-1},w_{N-2},\ldots,w_1]^T.

Ćwiczenie

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

Wskazówka

Sprowadź zadanie do poprzedniego!

Ćwiczenie

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

Wskazówka

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

Rozwiązanie

Ponieważ

\displaystyle  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 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 \displaystyle F_N (możesz nawet skorzystać ze zoptymalizowanych BLASów).