~2026-18800-53: /* Lösen von Gleichungssystemen mit zyklischen/zirkulanten Matrizen */

2026-03-26T10:42:51Z

Lösen von Gleichungssystemen mit zyklischen/zirkulanten Matrizen

Neue Seite

[[Datei:Matrix pattern qtl3.svg|miniatur|hochkant=0.75|Besetzungsmuster einer zirkulanten Matrix der Größe 5×5]]
In der [[lineare Algebra|linearen Algebra]] bezeichnet man eine [[Matrix (Mathematik)|Matrix]] als '''zyklisch''' oder '''zirkulant''', wenn ihre Zeilen und Spalten eine bestimmte [[Permutation]]sbedingung erfüllen. Wegen des unten beschriebenen Zusammenhangs mit der [[Schnelle Fourier-Transformation|diskreten schnellen Fourier-Transformation]] finden zyklische Matrizen Anwendung bei schnellen Lösungsverfahren z. B. für [[Toeplitz-Matrix|Toeplitz-Matrizen]].

Eine zirkulante Matrix ist eine spezielle Toeplitz-Matrix, bei der jeder [[Matrix (Mathematik)|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]], wenn alle Zeilenelemente verschieden sind. Gleichungssysteme mit zirkulanten Matrizen können per [[Diskrete Fourier-Transformation|diskreter Fourier-Transformation]] einfach gelöst werden.

== Definition ==
Eine quadratische Matrix heißt ''zyklisch'', wenn sie mit Zahlen <math>a_0,a_1,\ldots,a_{n-1}</math> die Gestalt
:<math>A:=\begin{pmatrix}
a_0&a_{n-1}&a_{n-2}&\ldots&a_1\\
a_1&a_0&a_{n-1}&\ldots&a_2\\
a_2&a_1&a_0&\ldots&a_3\\
&\ddots&\ddots&\ddots\\
a_{n-1}&a_{n-2}&a_{n-3}&\ldots&a_0\end{pmatrix}</math>
besitzt. Jede Spalte erhält man durch zyklisches Verschieben der links davon stehenden, daher werden auch die Zeilen zyklisch verschoben.

== Eigenschaften ==
Zyklische Matrizen sind [[Persymmetrische Matrix|persymmetrisch]], das heißt spiegelsymmetrisch bezüglich der [[Gegendiagonale]]n. Zyklische Matrizen sind spezielle [[Toeplitz-Matrix|Toeplitz-Matrizen]], bei denen die Elemente unter und über der [[Hauptdiagonale]]n zusammenhängen. Alle zyklischen (zirkulanten) Matrizen sind [[Polynom]]e einer einfachen zyklischen Matrix
:<math>Z:=\begin{pmatrix}
0&0&0&\ldots&0&1\\
1&0&0&\ldots&0&0\\
0&1&0&\ldots&0&0\\
&&\ddots&\ddots&\ddots\\
0&0&0&\ldots&1&0\end{pmatrix}</math>
denn es gilt für die oben eingeführte Matrix
:<math> A=a_0I+a_1Z+a_2Z^2+\ldots+a_{n-1}Z^{n-1}=p(Z)</math>
mit dem Polynom <math>p(x)=a_0+a_1x+a_2x^2+\ldots+a_{n-1}x^{n-1}</math> vom Grad <math>n-1</math>.
Denn in der Matrix <math>Z^k</math> sind die Einsen jeweils um <math>k</math> Positionen nach unten gerückt (zyklisch, kommen oben wieder hinein).
Wegen dieser Eigenschaft besitzen alle zyklischen Matrizen die gleiche Basis von [[Eigenvektor]]en, nämlich die Basis von <math>Z</math>.
Die Matrix <math>Z</math> ist eine spezielle [[Begleitmatrix]], ihr [[charakteristisches Polynom]] ist das Polynom
:<math>\!\,\det(\lambda I-Z)=\lambda^n-1,</math>
das genau die <math>n</math>-ten [[Einheitswurzel]]n als Nullstellen hat.
Daher besitzt die Matrix <math>Z</math> genau <math>n</math> verschiedene [[Eigenwert]]e, die auf dem komplexen Einheitskreis liegen in gleichem Abstand,
:<math>\lambda_k=e^{2\pi i(k-1)/n},\ k=1,\ldots,n.</math>
Der <math>k</math>-te [[Eigenvektor]] hat die Form <math>(\lambda_k^{j-1})_{j=1}^n</math> und alle Eigenvektoren bilden zusammen eine [[Vandermonde-Matrix]] <math>V(\lambda_1,\ldots,\lambda_m)</math> (siehe Artikel [[Begleitmatrix]]).
Diese Vandermonde-Matrix ist dann auch die Eigenvektormatrix von <math>A=p(Z)</math>, während die Eigenwerte von <math>A</math> die Werte <math>p(\lambda_k)</math> besitzen.

== Querverbindungen ==
Das Produkt der zyklischen Matrix <math>A</math> mit einem Vektor <math>x=(x_0,\ldots,x_{n-1})\in\R^n</math> ist
:<math> Ax=\Big(\sum_{j=0}^{n-1}a_{k-j}x_j\Big)_{k=0}^{n-1}.</math>
Dabei sei verabredet, dass Indizes außerhalb von <math>0,\ldots,n-1</math> zyklisch wieder in diesen Indexbereich abgebildet werden (durch [[Modulo]]-Rechnung: <math>(k-1)\mod n</math>).
Damit hat dieses [[Matrix-Vektor-Produkt]] die Form einer diskreten [[Faltung (Mathematik)|Faltung]]s-Operation und daher kann das Produkt <math>Ax</math> mit der Matrix oder mit ihrer [[Inverse]]n <math>A^{-1}x</math> für große <math>n</math> mit Hilfe der [[Schnelle Fourier-Transformation|Schnellen Fourier-Transformation]] (FFT) schnell durchgeführt werden, insbesondere wenn die Dimension eine Zweierpotenz ist <math>n=2^k</math>.

== Lösen von Gleichungssystemen mit zyklischen/zirkulanten Matrizen ==

Gegeben sei ein Gleichungssystem der Form
:<math>
\ \mathbf{A} \mathbf{x} = \mathbf{b},
</math>

mit der oben angegebenen zirkulanten, quadratischen Matrix <math>\ A</math> der Größe <math>\ n</math>. Dann entspricht die Gleichung einer zyklischen [[Faltung (Mathematik) | Faltung]]:

:<math>\ \mathbf{a} * \mathbf{x} = \mathbf{b},</math>

wobei allerdings <math>x</math> unbekannt ist. Der Vektor <math>\ a^T=(a_0,a_{1},a_{2},\ldots,a_{n-1})</math> ist die erste Spalte von<math>\ A</math>. Dann kann man schreiben:

:<math>\ \mathcal{F}_{n}(\mathbf{a} * \mathbf{x}) = \mathcal{F}_{n}(\mathbf{a})\cdot\mathcal{F}_{n}(\mathbf{x}) = \mathcal{F}_{n}(\mathbf{b})</math>,
wobei bei dem Produkt der Fourier-Koeffizienten <math>\mathcal{F}_{n}(\mathbf{a})\cdot\mathcal{F}_{n}(\mathbf{x})</math> die Vektoren komponentenweise miteinander multipliziert werden.
Die Fourier-Transformierte <math>\mathcal{F}_{n}(\mathbf{x})</math> der Lösung erhält man daher durch komponentenweise Division, und die Rücktransformation liefert dann die Lösung selbst:

:<math>\ \mathbf{x} = \mathcal{F}_{n}^{-1}
\left [
\left (
\frac{(\mathcal{F}_n(\mathbf{b}))_{\nu}}
{(\mathcal{F}_n(\mathbf{a}))_{\nu}}
\right )_{\nu \in \mathbf{Z}}
\right ].
</math>

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

== Literatur ==
*[[Robert M. Gray]]: ''Toeplitz and Circulant Matrices: A Review''. Now Publishers (Neuauflage), 2006, ISBN 978-1-933019-23-9
*[[Philip Davis (Mathematiker)|Philipp J. Davis]]: ''Circulant Matrices''. Wiley, 1979

== Weblinks ==
*[https://www.mat.tuhh.de/lehre/material/grnummath.pdf Heinrich Voß: Skript Grundlagen der numerischen Mathematik (PDF, 1.9Mb)], S. 129 ff.
*{{MathWorld|id=CirculantMatrix|title=Circulant Matrix}}

[[Kategorie:Matrix]]

Zyklische Matrix - Versionsgeschichte

~2026-18800-53: /* Lösen von Gleichungssystemen mit zyklischen/zirkulanten Matrizen */