Alle Eigenwerte mit dem QR Verfahren berechnen

Eigenwerte durch wiederholte Basiswechsel bestimmen

Der $\mathrm{QR}$ -Algorithmus berechnet alle Eigenwerte einer quadratischen Matrix durch wiederholte Basiswechsel. Jeder Schritt erzeugt eine $ähnliche Matrix$ , sodass die Eigenwerte gleich bleiben. Ziel der Iteration ist eine Diagonalform oder Schurform. Für die Konvergenz braucht man geeignete Verschiebungs- und Deflationsstrategien. Aus deren Diagonaleinträgen oder kleinen Diagonalblöcken lassen sich die Eigenwerte bestimmen.

Die folgende Variante ist die unverschobene $\mathrm{QR}$ -Iteration. Praktische Eigenwertlöser verwenden zusätzlich Verschiebungen, reduzieren die Matrix auf Hessenbergform und trennen konvergierte Blöcke ab. Diese Schritte verbessern Geschwindigkeit und numerische Zuverlässigkeit.

Eine Iteration mit QR

Reduziere die Matrix für den folgenden Deflationstest zunächst durch unitäre Ähnlichkeit auf $obere Hessenbergform$ . Alle Einträge unterhalb der ersten Nebendiagonalen sind dann null. Beginne mit dieser Matrix. Das folgende 2×2-Beispiel erfüllt die Bedingung bereits.

Beginne mit $A_0=A$ .
Zerlege die aktuelle Matrix in einen unitären oder orthogonalen Faktor $Q_k$ und einen oberen Dreiecksfaktor $R_k$ :

$A_k=Q_kR_k$
Vertausche die Reihenfolge der Faktoren, um die nächste Iterierte zu erhalten:

$A_{k+1}=R_kQ_k$
Wiederhole die Zerlegung und die Multiplikation in umgekehrter Reihenfolge. Ein sehr kleines Subdiagonalelement kann auf null gesetzt werden, sobald es gegenüber den benachbarten Diagonalelementen vernachlässigbar ist. Diese $Deflation$ trennt einen konvergierten Eigenwert oder Block ab.

$\begin{aligned} &|(A_k)_{j+1,j}| \\ &\leq \tau\left(|(A_k)_{j,j}|+|(A_k)_{j+1,j+1}|\right) \end{aligned}$

Dabei ist $\tau$ eine Toleranz, die zur numerischen Genauigkeit und zur Skalierung des Problems passt. Kleine Änderungen der Diagonale allein sind kein ausreichendes Abbruchkriterium, denn unterhalb der Diagonale können noch wesentliche Einträge stehen.

Warum die Eigenwerte gleich bleiben

Da $Q_k$ unitär ist, gilt $Q_k^{*}Q_k=I$ . Setzen wir $R_k=Q_k^{*}A_k$ in das umgekehrte Produkt ein, erhalten wir

A_{k+1}=R_kQ_k

Damit ist $A_{k+1}$ unitär ähnlich zu $A_k$ . $Ähnliche Matrizen besitzen dasselbe charakteristische Polynom$ und somit dieselben Eigenwerte. Jeder $\mathrm{QR}$ -Schritt stellt dieselbe lineare Abbildung in neuen Koordinaten dar.

Die entstehende Form

Die Grenzform hängt von der Matrix und dem $verwendeten Zahlkörper$ ab.

Matrix	Konvergierte Form	Eigenwerte ablesen
Reell symmetrisch oder komplex hermitesch	Diagonalmatrix	Die Diagonaleinträge sind die reellen Eigenwerte
Allgemein komplex	Obere Dreiecksschurform	Die Diagonaleinträge sind die Eigenwerte
Allgemein reell	Reelle obere Quasidreiecksform	Jeder $1\times1$ -Block liefert einen reellen Eigenwert. Jeder $2\times2$ -Block liefert ein komplex konjugiertes Paar

Die Eigenwerte können in jeder Reihenfolge erscheinen. Mehrfache Werte und besondere Anordnungen müssen gesondert behandelt werden, weil eine strenge Betragsordnung diese Fälle nicht abdeckt.

Die unverschobene Iteration $konvergiert nicht immer zur angegebenen Form$ . Beispielsweise besitzt die folgende symmetrische Matrix die Faktoren $Q=C$ und $R=I$ . Die nächste Iterierte bleibt deshalb unverändert:

C=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad C=CI,\qquad RQ=IC=C

Die Eigenwerte sind 1 und −1. Ihre gleichen Beträge zeigen, warum praktische Verfahren geeignete Verschiebungen und Konvergenzprüfungen benötigen.

Durchgerechnetes symmetrisches Beispiel

Betrachten wir die symmetrische Matrix

A_0=\begin{pmatrix}2&1\\1&2\end{pmatrix}

Eine $\mathrm{QR}$ -Zerlegung mit anschließender Multiplikation in umgekehrter Reihenfolge ergibt

\begin{aligned} &Q_0=\frac{1}{\sqrt5}\begin{pmatrix}2&-1\\1&2\end{pmatrix}, \\ &R_0=\begin{pmatrix}\sqrt5&\frac4{\sqrt5}\\0&\frac3{\sqrt5}\end{pmatrix} \end{aligned}

Der $Betrag der Nebendiagonaleinträge$ ist bereits von $1$ auf $3/5$ gesunken. Weitere Iterationen treiben beide Einträge gegen null:

A_k\longrightarrow\begin{pmatrix}3&0\\0&1\end{pmatrix}

Die Grenzdiagonale enthält die Eigenwerte $3$ und $1$ . Da jede Iterierte zu $A_0$ ähnlich ist, sind dies die Eigenwerte der ursprünglichen Matrix und keine durch eine veränderte Aufgabe erzeugten Näherungen.