Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Kurs: Fourier-Analysis - Diskrete Fourier-Transformation - Schnelle Fourier-Transformation

Diskrete Fourier-Transformation

[vorangehende Seite] [nachfolgende Seite] [Gesamtverzeichnis][Seitenübersicht]
Die Multiplikation eines $ n$-Vektors $ c$ mit der Fourier-Matrix $ W_n$ wird als diskrete Fourier-Transformation bezeichnet:

$\displaystyle f = W_nc \qquad\Leftrightarrow\qquad c = \frac{1}{n} W_n^\ast f \,. $

Definitionsgemäß ist also

$\displaystyle f_j = \sum_{k=0}^{n-1} c_k w_n^{jk},\quad j=0,\ldots,n-1 \qquad\L... ...ow\qquad c_k = \frac{1}{n} \sum_{j=0}^{n-1} f_j w_n^{-kj},\quad k=0,\ldots,n-1 $

mit $ w_n = \exp(2\pi\mathrm{i}/n$), wobei die Vektoren $ c$ und $ f$ von 0 bis $ n-1$ indiziert werden.

Die diskrete Fourier-Transformation entspricht der Auswertung des trigonometrischen Polynoms

$\displaystyle p(x) = \sum_{k=0}^{n-1} c_k e^{\mathrm{i}kx} $

an den Punkten $ x_j = 2\pi j/n$:

$\displaystyle f_j = p(x_j),\quad j=0,\ldots,n-1 \,. $

Die inverse Transformation kann als Riemann-Summe für die Fourier-Koeffizienten interpretiert werden:

$\displaystyle \langle f,e_k \rangle_{2\pi} = \frac{1}{2\pi} \int\limits_{0}^{2\... ...thrm{i}kx}\,dx \approx \frac{1}{n} \sum_{j=0}^{n-1} f(x_j) e^{-\mathrm{i}kx_j} $

mit $ x_j = 2\pi j/n$. Diese Approximation ist für glatte periodische Funktionen und $ n\gg \vert k\vert$ sehr genau.
Als Beispiel wird die diskrete Fourier-Transformation des Vektors

\begin{displaymath} c =\left( \begin{array}{c} 3 \\ -2 \\ 0 \\ 1\\ \end{array}\right) \end{displaymath}

berechnet.

Man erhält

\begin{displaymath} f=W_4c= \left(\begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & \mat... ...\ 3-3\mathrm{i} \\ 4 \\ 3+3\mathrm{i}\\ \end{array}\right)\,. \end{displaymath}

Für die inverse Fourier-Transformation ergibt sich entsprechend

\begin{displaymath} c=\frac{1}{4}W_4^\ast f = \frac{1}{4}\left(\begin{array}{ccc... ...( \begin{array}{c} 12 \\ -8 \\ 0 \\ 4\\ \end{array}\right)\,. \end{displaymath}

[vorangehende Seite] [nachfolgende Seite] [Gesamtverzeichnis][Seitenübersicht]
  automatisch erstellt am 13.11.2013