Zirkulante Matrix

Eine zirkulante Matrix ist eine spezielle Toeplitz-Matrix, bei der jeder Zeilenvektor relativ zum darüberliegenden Zeilenvektor um einen Eintrag nach rechts verschoben ist. Anders ausgedrückt ist sie ein Beispiel für ein Lateinisches Quadrat. Zirkulante Matrizen können per diskreter Fourier-Transformation einfach gelöst werden.

Definition

Eine $n\times n$ Matrix C folgender Form

$C= \begin{bmatrix} c_1 & c_2 & c_3 & \dots & c_n \\ c_n & c_1 & c_2 & & c_{n-1} \\ c_{n-1} & c_n & c_1 & & c_{n-2} \\ \vdots & & & \ddots & \vdots \\ c_2 & c_3 & c_4 & \dots & c_1 \end{bmatrix}$

nennt man zirkulante Matrix.

Lösen von Gleichungssystemen mit zirkulanten Matrizen

Gegeben sei ein Gleichungssystem der Form

$\ \mathbf{C} \mathbf{x} = \mathbf{b},$

wobei $\ C$ eine zirkulante, quadratische Matrix der Größe $\ n$ sei. Dann kann man die Gleichung als zyklische Faltung schreiben:

$\ \mathbf{c} * \mathbf{x} = \mathbf{b}$

Hierbei ist $\ c$ die erste Spalte / Zeile von $\ C$, und die Vektoren $\ c$, $\ x$ und $\ b$ sind in beide Richtungen zyklisch erweitert. Dann kann man schreiben:

$\ \mathcal{F}_{n}(\mathbf{c} * \mathbf{x}) = \mathcal{F}_{n}(\mathbf{c}) \mathcal{F}_{n}(\mathbf{x}) = \mathcal{F}_{n}(\mathbf{b})$

so dass gilt:

$\ \mathbf{x} = \mathcal{F}_{n}^{-1} \left [ \left ( \frac{(\mathcal{F}_n(\mathbf{b}))_{\nu}} {(\mathcal{F}_n(\mathbf{c}))_{\nu}} \right )_{\nu \in \mathbf{Z}} \right ].$

Dieser Ansatz ist bedeutend schneller als das Gaußsche Eliminationsverfahren, besonders wenn eine schnelle Fourier-Transformation verwendet wird.