www.wikidata.de-de.nina.az

Zyklische Matrix In der linearen Algebra bezeichnet man eine Matrix als zyklisch oder zirkulant wenn ihre Zeilen und Spa

Zyklische Matrix

In der linearen Algebra bezeichnet man eine Matrix als zyklisch oder zirkulant, wenn ihre Zeilen und Spalten eine bestimmte Permutationsbedingung erfüllen. Wegen des unten beschriebenen Zusammenhangs mit der diskreten schnellen Fourier-Transformation finden zyklische Matrizen Anwendung bei schnellen Lösungsverfahren z. B. für Toeplitz-Matrizen.

Besetzungsmuster einer zirkulanten Matrix der Größe 5×5

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, wenn alle Zeilenelemente verschieden sind. Gleichungssysteme mit zirkulanten Matrizen können per diskreter Fourier-Transformation einfach gelöst werden.

Definition Bearbeiten

Eine quadratische Matrix heißt zyklisch, wenn sie mit Zahlen die Gestalt

besitzt. Jede Spalte erhält man durch zyklisches Verschieben der links davon stehenden, daher werden auch die Zeilen zyklisch verschoben.

Eigenschaften Bearbeiten

Zyklische Matrizen sind persymmetrisch, das heißt spiegelsymmetrisch bezüglich der Gegendiagonalen. Zyklische Matrizen sind spezielle Toeplitz-Matrizen, bei denen die Elemente unter und über der Hauptdiagonalen zusammenhängen. Alle zyklischen (zirkulanten) Matrizen sind Polynome einer einfachen zyklischen Matrix

denn es gilt für die oben eingeführte Matrix

mit dem Polynom vom Grad . Denn in der Matrix sind die Einsen jeweils um Positionen nach unten gerückt (zyklisch, kommen oben wieder hinein). Wegen dieser Eigenschaft besitzen alle zyklischen Matrizen die gleiche Basis von Eigenvektoren, nämlich die Basis von . Die Matrix ist eine spezielle Begleitmatrix, ihr charakteristisches Polynom ist das Polynom

das genau die -ten Einheitswurzeln als Nullstellen hat. Daher besitzt die Matrix genau verschiedene Eigenwerte, die auf dem komplexen Einheitskreis liegen in gleichem Abstand,

Der -te Eigenvektor hat die Form und alle Eigenvektoren bilden zusammen eine Vandermonde-Matrix (siehe Artikel Begleitmatrix). Diese Vandermonde-Matrix ist dann auch die Eigenvektormatrix von , während die Eigenwerte von die Werte besitzen.

Querverbindungen Bearbeiten

Das Produkt der zyklischen Matrix mit einem Vektor ist

Dabei sei verabredet, dass Indizes außerhalb von zyklisch wieder in diesen Indexbereich abgebildet werden (durch Modulo-Rechnung: ). Damit hat dieses Matrix-Vektor-Produkt die Form einer diskreten Faltungs-Operation und daher kann das Produkt mit der Matrix oder mit ihrer Inversen für große mit Hilfe der Schnellen Fourier-Transformation (FFT) schnell durchgeführt werden, insbesondere wenn die Dimension eine Zweierpotenz ist .

Lösen von Gleichungssystemen mit zyklischen/zirkulanten Matrizen Bearbeiten

Gegeben sei ein Gleichungssystem der Form

mit der oben angegebenen zirkulanten, quadratischen Matrix der Größe . Dann entspricht die Gleichung einer zyklischen Faltung:

wobei allerdings unbekannt ist. Der Vektor ist die erste Zeile von . Dann kann man schreiben:

wobei bei dem Produkt der Fourier-Koeffizienten die Vektoren komponentenweise miteinander multipliziert werden. Die Fourier-Transformierte der Lösung erhält man daher durch komponentenweise Division, und die Rücktransformation liefert dann die Lösung selbst:

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

Literatur Bearbeiten

  • Robert M. Gray: Toeplitz and Circulant Matrices: A Review. Now Publishers (Neuauflage), 2006, ISBN 9781933019239
  • Philipp J. Davis: Circulant Matrices. Wiley, 1979

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der linearen Algebra bezeichnet man eine Matrix als zyklisch oder zirkulant wenn ihre Zeilen und Spalten eine bestimmte Permutationsbedingung erfullen Wegen des unten beschriebenen Zusammenhangs mit der diskreten schnellen Fourier Transformation finden zyklische Matrizen Anwendung bei schnellen Losungsverfahren z B fur Toeplitz Matrizen Besetzungsmuster einer zirkulanten Matrix der Grosse 5 5Eine zirkulante Matrix ist eine spezielle Toeplitz Matrix bei der jeder Zeilenvektor relativ zum daruberliegenden Zeilenvektor um einen Eintrag nach rechts verschoben ist Anders ausgedruckt ist sie ein Beispiel fur ein Lateinisches Quadrat wenn alle Zeilenelemente verschieden sind Gleichungssysteme mit zirkulanten Matrizen konnen per diskreter Fourier Transformation einfach gelost werden Inhaltsverzeichnis 1 Definition 2 Eigenschaften 3 Querverbindungen 4 Losen von Gleichungssystemen mit zyklischen zirkulanten Matrizen 5 Literatur 6 WeblinksDefinition BearbeitenEine quadratische Matrix heisst zyklisch wenn sie mit Zahlen a 0 a 1 a n 1 displaystyle a 0 a 1 ldots a n 1 nbsp die Gestalt A a 0 a n 1 a n 2 a 1 a 1 a 0 a n 1 a 2 a 2 a 1 a 0 a 3 a n 1 a n 2 a n 3 a 0 displaystyle A begin pmatrix a 0 amp a n 1 amp a n 2 amp ldots amp a 1 a 1 amp a 0 amp a n 1 amp ldots amp a 2 a 2 amp a 1 amp a 0 amp ldots amp a 3 amp ddots amp ddots amp ddots a n 1 amp a n 2 amp a n 3 amp ldots amp a 0 end pmatrix nbsp besitzt Jede Spalte erhalt man durch zyklisches Verschieben der links davon stehenden daher werden auch die Zeilen zyklisch verschoben Eigenschaften BearbeitenZyklische Matrizen sind persymmetrisch das heisst spiegelsymmetrisch bezuglich der Gegendiagonalen Zyklische Matrizen sind spezielle Toeplitz Matrizen bei denen die Elemente unter und uber der Hauptdiagonalen zusammenhangen Alle zyklischen zirkulanten Matrizen sind Polynome einer einfachen zyklischen Matrix Z 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 displaystyle Z begin pmatrix 0 amp 0 amp 0 amp ldots amp 0 amp 1 1 amp 0 amp 0 amp ldots amp 0 amp 0 0 amp 1 amp 0 amp ldots amp 0 amp 0 amp amp ddots amp ddots amp ddots 0 amp 0 amp 0 amp ldots amp 1 amp 0 end pmatrix nbsp denn es gilt fur die oben eingefuhrte Matrix A a 0 I a 1 Z a 2 Z 2 a n 1 Z n 1 p Z displaystyle A a 0 I a 1 Z a 2 Z 2 ldots a n 1 Z n 1 p Z nbsp mit dem Polynom p x a 0 a 1 x a 2 x 2 a n 1 x n 1 displaystyle p x a 0 a 1 x a 2 x 2 ldots a n 1 x n 1 nbsp vom Grad n 1 displaystyle n 1 nbsp Denn in der Matrix Z k displaystyle Z k nbsp sind die Einsen jeweils um k displaystyle k nbsp Positionen nach unten geruckt zyklisch kommen oben wieder hinein Wegen dieser Eigenschaft besitzen alle zyklischen Matrizen die gleiche Basis von Eigenvektoren namlich die Basis von Z displaystyle Z nbsp Die Matrix Z displaystyle Z nbsp ist eine spezielle Begleitmatrix ihr charakteristisches Polynom ist das Polynom det l I Z l n 1 displaystyle det lambda I Z lambda n 1 nbsp das genau die n displaystyle n nbsp ten Einheitswurzeln als Nullstellen hat Daher besitzt die Matrix Z displaystyle Z nbsp genau n displaystyle n nbsp verschiedene Eigenwerte die auf dem komplexen Einheitskreis liegen in gleichem Abstand l k e 2 p i k 1 n k 1 n displaystyle lambda k e 2 pi i k 1 n k 1 ldots n nbsp Der k displaystyle k nbsp te Eigenvektor hat die Form l k j 1 j 1 n displaystyle lambda k j 1 j 1 n nbsp und alle Eigenvektoren bilden zusammen eine Vandermonde Matrix V l 1 l m displaystyle V lambda 1 ldots lambda m nbsp siehe Artikel Begleitmatrix Diese Vandermonde Matrix ist dann auch die Eigenvektormatrix von A p Z displaystyle A p Z nbsp wahrend die Eigenwerte von A displaystyle A nbsp die Werte p l k displaystyle p lambda k nbsp besitzen Querverbindungen BearbeitenDas Produkt der zyklischen Matrix A displaystyle A nbsp mit einem Vektor x x 0 x n 1 R n displaystyle x x 0 ldots x n 1 in mathbb R n nbsp ist A x j 0 n 1 a k j x j k 0 n 1 displaystyle Ax Big sum j 0 n 1 a k j x j Big k 0 n 1 nbsp Dabei sei verabredet dass Indizes ausserhalb von 0 n 1 displaystyle 0 ldots n 1 nbsp zyklisch wieder in diesen Indexbereich abgebildet werden durch Modulo Rechnung k 1 mod n displaystyle k 1 mod n nbsp Damit hat dieses Matrix Vektor Produkt die Form einer diskreten Faltungs Operation und daher kann das Produkt A x displaystyle Ax nbsp mit der Matrix oder mit ihrer Inversen A 1 x displaystyle A 1 x nbsp fur grosse n displaystyle n nbsp mit Hilfe der Schnellen Fourier Transformation FFT schnell durchgefuhrt werden insbesondere wenn die Dimension eine Zweierpotenz ist n 2 k displaystyle n 2 k nbsp Losen von Gleichungssystemen mit zyklischen zirkulanten Matrizen BearbeitenGegeben sei ein Gleichungssystem der Form A x b displaystyle mathbf A mathbf x mathbf b nbsp mit der oben angegebenen zirkulanten quadratischen Matrix A displaystyle A nbsp der Grosse n displaystyle n nbsp Dann entspricht die Gleichung einer zyklischen Faltung a x b displaystyle mathbf a mathbf x mathbf b nbsp wobei allerdings x displaystyle x nbsp unbekannt ist Der Vektor a T a 0 a n 1 a n 2 a 1 displaystyle a T a 0 a n 1 a n 2 ldots a 1 nbsp ist die erste Zeile von A displaystyle A nbsp Dann kann man schreiben F n a x F n a F n x F n b displaystyle mathcal F n mathbf a mathbf x mathcal F n mathbf a cdot mathcal F n mathbf x mathcal F n mathbf b nbsp wobei bei dem Produkt der Fourier Koeffizienten F n a F n x displaystyle mathcal F n mathbf a cdot mathcal F n mathbf x nbsp die Vektoren komponentenweise miteinander multipliziert werden Die Fourier Transformierte F n x displaystyle mathcal F n mathbf x nbsp der Losung erhalt man daher durch komponentenweise Division und die Rucktransformation liefert dann die Losung selbst x F n 1 F n b n F n a n n Z displaystyle 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 nbsp Dieser Ansatz ist bedeutend schneller als das Gausssche Eliminationsverfahren besonders wenn eine schnelle Fourier Transformation verwendet wird Literatur BearbeitenRobert M Gray Toeplitz and Circulant Matrices A Review Now Publishers Neuauflage 2006 ISBN 9781933019239 Philipp J Davis Circulant Matrices Wiley 1979Weblinks BearbeitenHeinrich Voss Skript Grundlagen der numerischen Mathematik PDF 1 9Mb S 129 ff Eric W Weisstein Circulant Matrix In MathWorld englisch Abgerufen von https de wikipedia org w index php title Zyklische Matrix amp oldid 233829212