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