Diskrete Fouriertransformation.

Sei eine ganze Zahl $ \mbox{$n\ge 1$}$ gegeben. Sei $ \mbox{$\zeta := \exp(2\pi\text{i}/n)$}$ . Insbesondere ist $ \mbox{$\zeta^n = 1$}$ .

Unter der diskreten Fouriertransformation versteht man die $ \mbox{$\mathbb{C}$}$ -lineare Abbildung

$ \mbox{$\displaystyle \begin{array}{rcl} \mathbb{C}^n & \overset{f}{\rightarro... ...\sum_{j = 0}^{n-1} \zeta^{-kj} y_j\big)_{0\le k\le n-1} \; . \\ \end{array}$}$
Ihre inverse Abbildung ist gegeben durch
$ \mbox{$\displaystyle \begin{array}{rcl} \mathbb{C}^n & \overset{f^{-1}}{\righ... ...(\sum_{k = 0}^{n-1} \zeta^{jk} c_k\big)_{0\le j\le n-1} \; . \\ \end{array}$}$

Bei Bedarf sei $ \mbox{$y_{j + n} = y_j$}$ und $ \mbox{$c_{k+n} = c_k$}$ für $ \mbox{$j,\, k\,\in\,\mathbb{Z}$}$ , i.e. die Vektorindizierung werde $ \mbox{$n$}$ -periodisch fortgesetzt.

Die Darstellungsmatrix von $ \mbox{$f$}$ bezüglich Standardbasen ist gegeben durch

$ \mbox{$\displaystyle F \; = \; n^{-1}\big(\zeta^{-kj}\big)_{0\le k\le n-1,\; ... ...1)\cdot 1} & \dots & \zeta^{- (n-1)\cdot (n-1)} \\ \end{array}\right) \; . $}$
Es ist $ \mbox{$n^{1/2} F\in\mathbb{C}^{n\times n}$}$ eine unitäre Matrix, d.h. $ \mbox{$(n^{1/2} F)^{-1} = n^{1/2} \bar{F}^\text{t}$}$ .

Regeln. Seien $ \mbox{$y,\, y'\,\in\,\mathbb{C}^n$}$ , und schreibe $ \mbox{$c := f(y)$}$ und $ \mbox{$c' := f(y')$}$ . Seien $ \mbox{$\lambda,\,\lambda'\,\in\,\mathbb{C}$}$ .

Mit der sog. Schnellen Fouriertransformation kann man die Rechengeschwindigkeit für den Fall, daß $ \mbox{$n$}$ eine Potenz von $ \mbox{$2$}$ ist (oder jedenfalls durch eine große $ \mbox{$2$}$ -Potenz teilbar ist), noch verbessern. Die resultierende Abbildung ist dieselbe wie bei der gewöhnlich durchgeführten Fouriertransformation.