Numerika pro teoretické fyziky ← →

Kapitola 14

Rychlá Fourierova transformace a její využití

Fourierova transformace

Definice a volba normalizace

Definice (Fourierova transformace)

Pro libovolnou funkci \(u \in L^2(\mathbb{R})\) je Fourierův obraz dán vztahem

\begin{equation}\label{eq:12b:ft} \hat{u}(\xi) = (\mathcal{F}u)(\xi) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} e^{-i\xi x}\, u(x)\, \mathrm{d}x , \qquad \xi \in \mathbb{R} . \end{equation}

Obraz \(\hat{u}\) je opět z \(L^2(\mathbb{R})\) a funkci \(u(x)\) lze z \(\hat{u}(\xi)\) získat zpět pomocí inverzní Fourierovy transformace

\begin{equation}\label{eq:12b:ift} u(x) = (\mathcal{F}^{-1}\hat{u})(x) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} e^{i\xi x}\, \hat{u}(\xi)\, \mathrm{d}\xi , \qquad x \in \mathbb{R} . \end{equation}
Poznámka

Občas se v literatuře liší faktor \(\frac{1}{\sqrt{2\pi}}\), případně je použito \(e^{-i 2\pi \xi x}\). Obecně je-li

\begin{equation}\label{eq:12b:ft_obecne} \hat{u}(\xi) = \frac{a}{\sqrt{2\pi}} \int_{-\infty}^{\infty} e^{-i c \xi x}\, u(x)\, \mathrm{d}x \qquad \text{a} \qquad u(x) = \frac{b}{\sqrt{2\pi}} \int_{-\infty}^{\infty} e^{i c \xi x}\, \hat{u}(\xi)\, \mathrm{d}\xi , \end{equation}

pak musí být

\[ \frac{ab}{|c|} = 1 , \]

což plyne z identity

\[ \frac{1}{2\pi} \int_{-\infty}^{\infty} e^{i c \xi (x-x')}\, \mathrm{d}\xi = \frac{1}{|c|}\,\delta(x-x') . \]

Parsevalova rovnost a konvoluce

Pro obecnou volbu konstant \eqref{eq:12b:ft_obecne} má Parsevalova rovnost tvar

\begin{equation}\label{eq:12b:parseval_obecne} \int_{-\infty}^{\infty} f(x)\, g^*(x)\, \mathrm{d}x = \frac{|c|}{|a|^2} \int_{-\infty}^{\infty} \hat{f}(\xi)\, \hat{g}^{\,*}(\xi)\, \mathrm{d}\xi \qquad \text{neboli} \qquad \|f\|_2 = \sqrt{\frac{|c|}{|a|^2}}\, \|\hat{f}\|_2 , \end{equation}

takže speciálně pro \(a = 1\) a \(c = 1\) dostáváme

\begin{equation}\label{eq:12b:parseval} \int_{-\infty}^{\infty} f(x)\, g^*(x)\, \mathrm{d}x = \int_{-\infty}^{\infty} \hat{f}(\xi)\, \hat{g}^{\,*}(\xi)\, \mathrm{d}\xi \qquad \text{neboli} \qquad \|f\|_2 = \|\hat{f}\| . \end{equation}

Pro konvoluci

\begin{equation}\label{eq:12b:konvoluce} (u*v)(x) = \int_{-\infty}^{\infty} u(x-y)\, v(y)\, \mathrm{d}y = \int_{-\infty}^{\infty} u(y)\, v(x-y)\, \mathrm{d}y \end{equation}

platí (je-li \(u \in L^2\) a \(v \in L^1\) nebo obráceně)

\begin{equation}\label{eq:12b:konvolucni_veta} \widehat{u*v}(\xi) = \hat{u}(\xi)\, \hat{v}(\xi) . \end{equation}

Vlastnosti Fourierovy transformace

  1. Linearita: \(\widehat{u+v}(\xi) = \hat{u}(\xi) + \hat{v}(\xi)\) a \(\widehat{cu}(\xi) = c\, \hat{u}(\xi)\).
  2. Translace: pokud \(x_0 \in \mathbb{R}\), pak \(\widehat{u(x+x_0)}(\xi) = e^{i\xi x_0}\, \hat{u}(\xi)\).
  3. Modulace: pokud \(\xi_0 \in \mathbb{R}\), pak \(\widehat{e^{i\xi_0 x} u(x)}(\xi) = \hat{u}(\xi - \xi_0)\).
  4. Dilatace: pokud \(c \in \mathbb{R}\), \(c \neq 0\), pak \(\widehat{u(cx)}(\xi) = \hat{u}(\xi/c)\,/|c|\).
  5. Sdružení: \(\widehat{u^*}(\xi) = \hat{u}(-\xi)^*\).
  6. Derivace: \(\widehat{u_x}(\xi) = i\xi\, \hat{u}(\xi)\).

Diskrétní Fourierova transformace

Vzorkování a Nyquistova kritická frekvence

Uvažujme funkci \(h(t)\) zadanou pouze s jistou vzorkovací frekvencí v bodech \(t_n = n\,\Delta t\), kde \(n = \dots, -3, -2, -1, 0, 1, 2, 3, \dots\). Hodnota \(\frac{1}{\Delta t}\) přitom odpovídá počtu bodů (sampling rate) za jednu sekundu.

Nejvyšší frekvence, kterou lze takto popsat, je dána Nyquistovou kritickou frekvencí.

Definice (Nyquistova kritická frekvence)
\begin{equation}\label{eq:12b:nyquist} f_c = \frac{1}{2\Delta t} . \end{equation}
Interaktivní ukázka · Vzorkování a Nyquistova frekvence

Sinusovka s vyznačenými vzorkovacími body; rozestup dvou sousedních vzorků je \(\Delta t\). Ve výchozím nastavení je \(f = f_c\), takže vzorky padnou přesně do maxim a minim — právě dva na periodu. Posuvníky mění frekvenci signálu, krok \(\Delta t\) i fázi; pod plátnem se počítá \(f_c = 1/(2\Delta t)\) a počet vzorků na periodu \(1/(f\Delta t)\). Vyzkoušejte si, že při \(f = f_c\) závisí velikost vzorků na fázi — pro \(\varphi = 0\) leží všechny vzorky v nulách a vlna z nich není vidět vůbec.

Máme tedy dva body na jednu periodu, což je minimum nutné k zachycení této frekvence, tj. vlny \(\sin 2\pi f_c t\).

Problém aliasingu

Interaktivní ukázka · Alias rychlé sinusovky

Rychle kmitající sinusovka vzorkovaná v bodech vyznačených tečkami; její vzorky leží na pomalé sinusovce nakreslené silnější čarou — aliasu rychlého signálu. Alias se počítá složením frekvence do pásma \(\langle -f_c, f_c \rangle\), tedy \(f_a = f - k/\Delta t\), a pod plátnem se ukazuje, že se obě sinusovky ve vzorkovacích bodech shodují až na zaokrouhlovací chybu. Projeďte posuvníkem \(f\) přes \(f_c\) a sledujte, jak se alias „odrazí“ zpět do pásma; posuvníkem \(\Delta t\) si ověřte, že rozhoduje jen poměr \(f\) a \(1/\Delta t\).

Interaktivní ukázka · Přeložené („aliased“) spektrum

Spektrum se svislými čarami v bodech \(-f_c\) a \(f_c\): čárkovaně je skutečné spektrum přesahující za \(\pm f_c\), plnou čarou vzniklé přeložené spektrum („aliased spectrum“), které je uvnitř intervalu vyšší. Modelové spektrum se dvěma hrby a pomalu klesajícími křídly je zvoleno tak, aby jev byl dobře vidět; přeložené spektrum se z něj počítá jako součet všech kopií posunutých o násobky \(1/\Delta t = 2 f_c\). Na okrajích pásma je zkreslení největší — hodnoty se tam sčítají z obou sousedních kopií — a z periodicity přeloženého spektra plyne \(\hat{H}_{\mathrm{alias}}(-f_c) = \hat{H}_{\mathrm{alias}}(f_c)\). Zaškrtávátkem si posunuté kopie zobrazte; posuvníky měňte \(f_c\) i šířku spektra a sledujte pod plátnem, kolik procent \(\int|\hat{H}|^2\) leží mimo pásmo a jak roste přebytek uvnitř.

Je tedy nutné vzorkovat podle nejvyšší frekvence, případně použít filtry apod.

Odvození diskrétní Fourierovy transformace

Máme-li funkci \(h(t)\) vzorkovánu v časech \(t_k = k\,\Delta t\), \(k = 0, 1, \dots, N-1\), tj. máme posloupnost \(h_k = h(t_k)\), pak její Fourierův obraz můžeme aproximovat, ovšem jen v určitých frekvencích: z \(N\) bodů lze určit nejvýše \(N\) nezávislých frekvencí mezi \(-f_c\) a \(f_c\), a sice

\[ \begin{array}{ccc} f_n = \dfrac{n}{N\Delta t} , & n = -\dfrac{N}{2} , & \dots ,\ \dfrac{N}{2} \\[4pt] & \Updownarrow & \Updownarrow \\[2pt] & -f_c & +f_c \end{array} \]

Jde o \(N+1\) frekvencí, ale hodnota pro \(-f_c\) a \(f_c\) bude stejná.

Máme tedy

\begin{align*} H(f_n) &= \int_{-\infty}^{\infty} h(t)\, e^{2\pi i f_n t}\, \mathrm{d}t \simeq \\ &\simeq \sum_{k=0}^{N-1} h_k\, e^{2\pi i f_n t_k}\ \Delta t = \\ &= \Delta t \underbrace{\sum_{k=0}^{N-1} h_k\, e^{2\pi i k n/N}}_{H_n} = \Delta t\, H_n . \end{align*}

I když jsme brali

\[ n = -\frac{N}{2}, \dots, \frac{N}{2} , \]

hodnota \(H_n\) se nezmění, přičteme-li k \(n\) číslo \(N\), takže

\begin{equation}\label{eq:12b:periodicita} H_{-n} = H_{N-n} . \end{equation}

Vztah

\begin{equation}\label{eq:12b:dft} H_n = \sum_{k=0}^{N-1} h_k\, e^{2\pi i k n/N} \end{equation}

je tzv. diskrétní Fourierova transformace posloupnosti \(h_k\); povšimněme si, že nezávisí na \(\Delta t\). Proto se obvykle hledá \(H_n\) pro \(n = 0, \dots, N-1\), tedy pro stejný rozsah indexů jako u \(k\).

Je ovšem nutné dát pak pozor na to, které frekvence odpovídají kterému \(H_n\). Obvykle tedy \(H_0\) přísluší nulové frekvenci, hodnoty \(H_1, \dots, H_{N/2-1}\) odpovídají kladným frekvencím \(0 < f < f_c\), hodnoty \(H_{N/2+1}\) až \(H_{N-1}\) odpovídají záporným frekvencím \(-f_c < f < 0\) a \(H_{N/2}\) odpovídá oběma hodnotám \(f_c\) i \(-f_c\).

Inverzní diskrétní Fourierova transformace

Inverzní diskrétní Fourierova transformace, která dává přesně \(h_k\) z \(H_n\), pak je

\begin{equation}\label{eq:12b:idft} h_k = \frac{1}{N}\sum_{n=0}^{N-1} H_n\, e^{-2\pi i k n/N} . \end{equation}

Od \eqref{eq:12b:dft} se liší jen znaménkem v exponentu a faktorem \(\frac{1}{N}\), takže ji lze počítat prakticky stejně.

Rychlá Fourierova transformace (FFT)

I když je diskrétní Fourierova transformace na první pohled metodou řádu \(\mathcal{O}(N^2)\), lze ji pro \(N = 2^x\) provést v řádu \(\mathcal{O}(N \log_2 N)\) operací, neboť podle Danielsona a Lanczose platí

\begin{align*} H_n &= \sum_{k=0}^{N-1} e^{2\pi i k n/N}\, h_k = \\[4pt] &= \sum_{k=0}^{N/2-1} e^{2\pi i n (2k)/N}\, h_{2k} + \sum_{k=0}^{N/2-1} e^{2\pi i n (2k+1)/N}\, h_{2k+1} = \\[4pt] &= \sum_{k=0}^{N/2-1} e^{2\pi i n k/(N/2)}\, h_{2k} + W^n \sum_{n=0}^{N/2-1} e^{2\pi i n k/(N/2)}\, h_{2k+1} = \\[4pt] &= \underbrace{H_n^{e}}_{\text{DFT sudých}} + \underbrace{W^n H_n^{o}}_{\text{DFT lichých vzorků } h_k} . \end{align*}

Tento princip pak použijeme rekurzivně na \(H_n^{e}\) a \(H_n^{o}\), až bude

\[ H_n^{eoeeo\cdots oe} = h_k \]

pro jisté \(k\) odpovídající vzoru \(eoee\cdots\). A sice obrátíme-li vzor \(eoeeo\ldots oe\) binárně, kde \(e = 0\) a \(o = 1\), dostaneme odpovídající \(k\). Je tedy nutno posloupnost přeuspořádat pomocí bit reversal (přehození bitů), například takto.

Interaktivní ukázka · Přeuspořádání bit reversal

Přeuspořádání pomocí bit reversal, pro dvoubitové vzory \(00 \to 00\), \(01 \to 10\), \(10 \to 01\), \(11 \to 11\). Posuvníkem lze zvolit počet bitů (tedy \(N = 2, 4, 8, 16\)); šedé šipky jsou pevné body permutace, modré skutečné přesuny. Posuvník „index \(k\)“ zvýrazní jeden prvek a pod plátnem ukáže jeho vzor sudých a lichých dělení (\(e\) = sudé, \(o\) = liché, čteno od nejnižšího bitu) i cílovou pozici po binárním obrácení. Poslední řádek počítá radix-2 FFT s tímto přeuspořádáním a srovnává ji s přímou sumou \eqref{eq:12b:dft} — shoda vychází na úrovni zaokrouhlovací chyby, přestože operací je \(N \log_2 N\) místo \(N^2\).

Přeuspořádání lze provést v řádu \(\mathcal{O}(N \log_2 N)\) operací.

Potom se výsledky kombinují zpět pomocí Danielsonova–Lanczosova vztahu, a to \(\log_2 N\)-krát, vždy v řádu \(N\) operací. Podrobnosti algoritmu viz Numerical Recipes.

Existují i verze pro \(N \neq 2^x\), ale jejich efektivita je horší a záleží na faktorizaci čísla \(N\).

Výpočet Fourierovy transformace pomocí DFT (FFT)

Nechť máme program, který vrací

\begin{equation}\label{eq:12b:dft_program} H_n = \sum_{k=0}^{N-1} h_k\, e^{2\pi i k n/N} , \qquad n = 0, \dots, N-1 , \end{equation}

a chceme pomocí něj (přibližně) spočítat například

\begin{equation}\label{eq:12b:integral} I(\omega_n) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} e^{i\omega_n t}\, h(t)\, \mathrm{d}t \end{equation}

pomocí hodnot \(h_k\) v bodech \(t_k = t_{\min} + k\,\Delta t\), \(k = 0, \dots, N-1\).

Za předpokladu, že \(h_k\) jsou mimo body \(t_k\) nulové, dostaneme pomocí lichoběžníkového pravidla

\[ I(\omega_m) \cong \frac{1}{\sqrt{2\pi}} \sum_{r=0}^{N-1} h_r\, e^{i\omega_m t_r}\, \Delta t , \]

kde

\begin{align*} t_r &= t_{\min} + r\,\Delta t , \\ \omega_m &= \frac{2\pi m}{N\Delta t} , \qquad m = -\tfrac{N}{2}, \dots, \tfrac{N}{2} , \end{align*}

a tedy

\begin{equation}\label{eq:12b:ft_pres_dft} I(\omega_m) \cong \frac{\Delta t}{\sqrt{2\pi}}\, e^{i\omega_m t_{\min}} \sum_{r=0}^{N-1} h_r\, e^{2\pi i r m/N} . \end{equation}

Faktorem \(\frac{\Delta t}{\sqrt{2\pi}}\, e^{i\omega_m t_{\min}}\) je přitom nutno výsledek transformace násobit, přičemž suma v \eqref{eq:12b:ft_pres_dft} je

\[ \tilde{H}_m = \begin{cases} H_{m+N} & \text{pro } m < 0 , \\ H_m & \text{pro } m \geq 0 . \end{cases} \]

Navíc je třeba dávat pozor na umístění záporných frekvencí v \(H_n\).

Časový vývoj v kvantové mechanice pomocí split-operator metody

Časový vývoj je dán evolučním operátorem \(U = e^{-iHt}\), tedy

\begin{equation}\label{eq:12b:evoluce} |\psi(t)\rangle = e^{-iHt} |\psi_0\rangle , \qquad (\hbar = 1 \text{ — atomové jednotky}) , \end{equation}

kde \(H = T + V\), přičemž \(T\) je operátor kinetické energie a \(V\) potenciální energie.

Tyto dva operátory spolu nekomutují, a tedy \(e^{-iHt} \neq e^{-iTt} e^{-iVt}\).

Do řádu \(\mathcal{O}(\Delta t^2)\) pro malé \(\Delta t\) ovšem platí

\begin{equation}\label{eq:12b:split_operator} e^{-iH\Delta t} = e^{-\frac{iV\Delta t}{2}}\, e^{-iT\Delta t}\, e^{-\frac{iV\Delta t}{2}} + \mathcal{O}(\Delta t^3) , \end{equation}

přičemž člen \(e^{-iT\Delta t}\) je v \(p\)-reprezentaci roven \(e^{-i\frac{p^2}{2m}\Delta t}\). Jde tedy o pouhé násobení: působení \(e^{-iH\Delta t}\) lze pomocí přechodů mezi \(\psi^x(x)\) a \(\psi^p(p) = \langle p | \psi \rangle\) převést na násobení buď \(e^{-\frac{iV\Delta t}{2}} \psi^x(x)\), nebo \(e^{-i\frac{p^2}{2m}\Delta t} \psi^p(p)\).

Je-li \(\psi^p(p)\) určeno pomocí diskrétní (rychlé) Fourierovy transformace, je nutno dát pozor na to, jakým \(p\) násobíme.

Přechod mezi \(\psi^x(x)\) a \(\psi^p(p)\) je dán Fourierovými vztahy

\begin{equation}\label{eq:12b:psi_p} \psi^p(p) = \frac{1}{(2\pi)^{1/2}} \int_{-\infty}^{\infty} e^{-ipx} \psi^x(x)\, \mathrm{d}x \qquad \text{(inverzní FT)} , \end{equation} \begin{equation}\label{eq:12b:psi_x} \psi^x(x) = \frac{1}{(2\pi)^{1/2}} \int_{-\infty}^{\infty} e^{ipx} \psi^p(p)\, \mathrm{d}p . \end{equation}

Přecházíme-li tam a zpět, konstantní faktory nehrají roli, takže stačí násobit obraz z diskrétní Fourierovy transformace vhodným \(e^{-i\frac{p^2}{2m}\Delta t}\), a sice s hodnotami

\begin{align*} p_j &= \frac{2\pi j}{N \Delta x} & &\text{pro } j = 0, \dots, \tfrac{N}{2} - 1 , \\ p_j &= \frac{2\pi}{N \Delta x}(j - N) & &\text{pro } j = \tfrac{N}{2}, \dots, N - 1 . \end{align*}

Zobecnění na metody vyššího řádu pomocí symetrické kompozice viz J. Chem. Phys. 150 (2019) 204113.