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

Parser nie mógł rozpoznać (nieznana funkcja „\begincases”): {\displaystyle \displaystyle w_j^* 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\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).