6.4 Die Fast Fourier Transformation

Die Fourier Transformation ist eine Methode basiert auf der Zerlegung einer Funktion in bestimmte Frequenzen (Eigenfunktionen) ausgedrückt durch die trigonometrischen Grundfunktionen $\sin$ und $\cos$. Bei einer Anzahl von $N=2^P-1$ Eigenfunktionen läßt sich diese Transformation wesentlich beschleunigen und wird als Fast Fourier Transformation (FFT) bezeichnet.

Anwendung :

• Signalverarbeitung,
• Partielle Differentialgleichungen über Rechteckgebieten,
• Vorkonditionierung zyklischer Matrizen (BEM).

Bsp.: Partielle Differentialgleichung im Einheitsquadrat 

Aus der partiellen DGl.
in $\Omega = (0,1)^2$ soll die Funktion $u$ bestimmt werden.

$$\boxed{\begin{array}{rcll} - \triangle u \,+\, c u &=& f & \... ...i \,(:= 0) & \mbox{auf} \;\Gamma = \partial\Omega \end{array}}$$

Mit einem äquidistanten Gitternetz ($N+1$ Linien in jede Dimension) wird das Gebiet diskretisiert und die Differentialgleichung mittels eines 5-Punkte Differenzensternes approximiert.

$\Longrightarrow$ $(4+ch^2) u_{i,j} - (u_{i,j-1} + u_{i,j+1} + u_{i-1,j} + u_{i+1,j}) \,=\, h^2 f_{i,j}$ $i,j = \overline{1,N-1} \makebox[0pt]{}$


$\Longrightarrow$ $\Lambda \underline{u} \,=\, \underline{f}$

Da in obigem Beispiel die Eigenfunktionen des diskretisierten Differentialoperators $\Lambda$

$$\mu_{k,\ell}(ih,jh) \;=\; 2 \sin(k\pi i h) \sin(\ell\pi j h) ... ...e{2em}{\scriptstyle k,\ell = \overline{1,N-1} \makebox[0pt]{}}$$

sind, und sich die zugehörigen Eigenwerte als

$$\lambda_{k,\ell} \;=\; 4 \left[ \sin^2\tfrac{k \pi h}{2} \,+\, \sin^2\tfrac{\ell \pi h}{2} \right] \,+\,c h^2$$

darstellen lassen, können die rechte Seite $f$ und die gesuchte Funktion $u$ als Linearkombination der Eigenfunktionen dargestellt werden.

   

Die Lösung der Differentialgleichung erhält man nunmehr wie folgt

1.

 Zerlegung von $f$ in Eigenfrequenzen  $\mu_{k,\ell}$ (Fourieranalyse)
$\Longrightarrow$ Bestimmung der Zerlegungskoeffizienten  $\gamma_{k,\ell}$ in (6.7a).

2.

  Durch die Eigenwerte des diskr. Operators dividieren
$\Longrightarrow$ $\beta_{k,\ell}\,:=\,\frac{\gamma_{k,\ell}}{\lambda_{k,\ell}}$

3.

  Zusammenbau der diskreten Näherungslösung (Fouriersynthese)
$\Longrightarrow$ $u(ih,jh)$ in (6.7b)

Die Punkte 1 und 3 werden über die Fouriertransformation realisiert.