For AI agents: use /llms.txt for the Nakafa content index.
Der QR-Algorithmus berechnet alle Eigenwerte einer quadratischen Matrix durch wiederholte Basiswechsel. Die Eigenwerte ändern sich dabei nicht. Stattdessen bewegt sich die Matrix auf eine Form zu, aus der sich die Eigenwerte leichter ablesen lassen.
Die folgende Variante ist die unverschobene QR-Iteration. An ihr lässt sich die Grundidee besonders klar erkennen. Praktische Eigenwertlöser verwenden zusätzlich Verschiebungen, reduzieren die Matrix zunächst auf Hessenbergform und trennen konvergierte Blöcke ab. So läuft dieselbe Idee schneller und zuverlässiger.
Beginne mit .
Zerlege die aktuelle Matrix in einen unitären oder orthogonalen Faktor und einen oberen Dreiecksfaktor :
Vertausche die Reihenfolge der Faktoren, um die nächste Iterierte zu erhalten:
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.
Dabei ist 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.
Da unitär ist, gilt . Setzen wir in das umgekehrte Produkt ein, erhalten wir
Damit ist unitär ähnlich zu . Ähnliche Matrizen besitzen dasselbe charakteristische Polynom und somit dieselben Eigenwerte. Die QR-Iteration wechselt die Koordinaten, nicht die zugrunde liegende lineare Abbildung.
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 -Block liefert einen reellen Eigenwert; jeder -Block liefert ein komplex konjugiertes Paar |
Die Eigenwerte müssen nicht in einer vorgegebenen Reihenfolge erscheinen. Mehrfache Eigenwerte und besondere Eigenwertanordnungen verlangen ebenfalls mehr Sorgfalt als eine einfache strenge Betragsordnung vermuten lässt.
Betrachten wir die symmetrische Matrix
Eine QR-Zerlegung mit anschließender Multiplikation in umgekehrter Reihenfolge ergibt
Der Betrag der Nebendiagonaleinträge ist bereits von auf gesunken. Weitere Iterationen treiben beide Einträge gegen null:
Die Grenzdiagonale zeigt die Eigenwerte und . Da jede Iterierte zu ähnlich ist, sind dies die Eigenwerte der ursprünglichen Matrix und keine durch eine veränderte Aufgabe erzeugten Näherungen.
Die QR-Iteration ist ein Ähnlichkeitsprozess. Bei symmetrischen Matrizen nähert sie sich einer Diagonalform; bei allgemeinen reellen Matrizen einer reellen Schurform, die notwendige -Blöcke enthalten kann.
