Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Lexikon:

Diskrete Fourier-Transformation zyklischer Gleichungssysteme

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht
Eine zyklische Matrix

$\displaystyle A = \left(\begin{array}{cccc} a_0 & a_{n-1} & \cdots & a_1 \\ a_... ... \\ \vdots &&& \vdots \\ a_{n-1} & a_{n-2} & \cdots & a_0 \end{array}\right) $

besitzt die Eigenwerte

$\displaystyle \lambda_j = \sum_{k=0}^{n-1} a_k w_n^{-kj},\quad w_n = \exp(2\pi\mathrm{i}/n) \,, $

und kann durch die Fourier-Matrix diagonalisiert werden:

$\displaystyle \frac{1}{n} W_n^\ast A W_n = \operatorname{diag}(\lambda), \quad \lambda = W_n^\ast a \,. $

Folglich lässt sich die Lösung eines zyklischen Gleichungssystems $ Ax = b$ in der Form

$\displaystyle x = W_n \operatorname{diag}(\lambda)^{-1} (W_n^\ast b/n) $

berechnen.

Für $ n=2^\ell$ ist die schnelle Fourier-Transformation anwendbar, und man erhält den folgenden Lösungsalgorithmus:

         $ c = \operatorname{IFFT}(b)$
  $ \lambda = n\,\operatorname{IFFT}(a)$
  $ y_j = c_j /\lambda_j$,     $ j=0,\ldots,n-1$
  $ x = \operatorname{FFT}(y)\,.$

Erläuterung:

[Beispiele] [Verweise]
  automatisch erstellt am 8. 11. 2013