Zyklische Matrix

aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 17. April 2018 um 14:03 Uhr durch imported>Aka(568) (Abkürzung korrigiert, Leerzeichen in Überschrift, Links normiert).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Datei:Matrix pattern qtl3.svg
Besetzungsmuster einer zirkulanten Matrix der Größe 5×5

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.

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

Eine quadratische Matrix heißt zyklisch, wenn sie mit Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_0,a_1,\ldots,a_{n-1}} die Gestalt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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}}

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

Eigenschaften

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A=a_0I+a_1Z+a_2Z^2+\ldots+a_{n-1}Z^{n-1}=p(Z)}

mit dem Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(x)=a_0+a_1x+a_2x^2+\ldots+a_{n-1}x^{n-1}} vom Grad . Denn in der Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z^k} sind die Einsen jeweils um Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z} . Die Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z} ist eine spezielle Begleitmatrix, ihr charakteristisches Polynom ist das Polynom

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \!\,\det(\lambda I-Z)=\lambda^n-1,}

das genau die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -ten Einheitswurzeln als Nullstellen hat. Daher besitzt die Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Z} genau Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} verschiedene Eigenwerte, die auf dem komplexen Einheitskreis liegen in gleichem Abstand,

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \lambda _{k}=e^{2\pi i(k-1)/n},\ k=1,\ldots ,n.}

Der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -te Eigenvektor hat die Form Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\lambda_k^{j-1})_{j=1}^n} und alle Eigenvektoren bilden zusammen eine Vandermonde-Matrix (siehe Artikel Begleitmatrix). Diese Vandermonde-Matrix ist dann auch die Eigenvektormatrix von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A=p(Z)} , während die Eigenwerte von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} die Werte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(\lambda_k)} besitzen.

Querverbindungen

Das Produkt der zyklischen Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} mit einem Vektor ist

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Ax=\Big(\sum_{j=0}^{n-1}a_{k-j}x_j\Big)_{k=0}^{n-1}.}

Dabei sei verabredet, dass Indizes außerhalb von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0,\ldots,n-1} zyklisch wieder in diesen Indexbereich abgebildet werden (durch Modulo-Rechnung: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (k-1)\mod n} ). Damit hat dieses Matrix-Vektor-Produkt die Form einer diskreten Faltungs-Operation und daher kann das Produkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Ax} mit der Matrix oder mit ihrer Inversen Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle A^{-1}x} für große Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} mit Hilfe der Schnellen Fourier-Transformation (FFT) schnell durchgeführt werden, insbesondere wenn die Dimension eine Zweierpotenz ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=2^k} .

Lösen von Gleichungssystemen mit zyklischen/zirkulanten Matrizen

Gegeben sei ein Gleichungssystem der Form

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \ \mathbf {A} \mathbf {x} =\mathbf {b} ,}

mit der oben angegebenen zirkulanten, quadratischen Matrix der Größe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ n} . Dann entspricht die Gleichung einer zyklischen Faltung:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ \mathbf{a} * \mathbf{x} = \mathbf{b},}

wobei allerdings Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} unbekannt ist. Der Vektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ a^T=(a_0,a_{n-1},a_{n-2},\ldots,a_1)} ist die erste Zeile von . Dann kann man schreiben:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ \mathcal{F}_{n}(\mathbf{a} * \mathbf{x}) = \mathcal{F}_{n}(\mathbf{a})\cdot\mathcal{F}_{n}(\mathbf{x}) = \mathcal{F}_{n}(\mathbf{b})} ,

wobei bei dem Produkt der Fourier-Koeffizienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{F}_{n}(\mathbf{a})\cdot\mathcal{F}_{n}(\mathbf{x})} die Vektoren komponentenweise miteinander multipliziert werden. Die Fourier-Transformierte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{F}_{n}(\mathbf{x})} der Lösung erhält man daher durch komponentenweise Division, und die Rücktransformation liefert dann die Lösung selbst:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 ]. }

Dieser Ansatz ist bedeutend schneller als das 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 9781933019239
  • Philipp J. Davis: Circulant Matrices. Wiley, 1979

Weblinks

Abgerufen von „https://de.wikiup.org/index.php?title=Zyklische_Matrix&oldid=176606949“