QR-Algorithmus

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der QR-Algorithmus ist ein numerisches Verfahren zur Berechnung aller Eigenwerte und eventuell der Eigenvektoren einer quadratischen Matrix. Das auch QR-Verfahren oder QR-Iteration genannte Verfahren basiert auf der QR-Zerlegung und wurde im Jahre 1961 unabhängig voneinander von J. G. F. Francis und V. N. Kublanovskaya eingeführt. Oft konvergieren die Iterierten aus diesem Algorithmus gegen die Schur-Form der Matrix. Das Verfahren ist recht aufwändig und damit auf heutigen Rechnern für Matrizen mit hunderttausenden Zeilen und Spalten nicht praktikabel.

Zur effizienteren Umsetzung wird die Matrix in einem ersten Schritt mit Ähnlichkeitstransformationen (meist Givens-Rotationen von rechts und links) auf eine obere Hessenbergform gebracht.

[Bearbeiten] QR-Algorithmus ohne Shifts

Der QR-Algorithmus ohne Shifts (auch unter dem Namen QR-Algorithmus in der Grundform bekannt), berechnet ausgehend von $A_0=A\in\mathbb{C}^{n\times n}$ eine Folge von Matrizen $A i$ :

for $i\in\mathbb{N}_0$ do
Berechne die QR-Zerlegung von $A i$ : $A i = Q i R i$
Berechne die neue Iterierte: $A i + 1 = R i Q i$
end for

Die Konvergenz dieses Algorithmus ist nicht immer gegeben und so existiert eine zweite Variante.

[Bearbeiten] QR-Algorithmus mit Shifts

Meist wird zwecks Konvergenzbeschleunigung bzw. um überhaupt Konvergenz zu erreichen, mit spektralen Shifts $κ i$ gearbeitet:

for $i\in\mathbb{N}_0$ do
Berechne die QR-Zerlegung von $A i - κ i I$ : $A i - κ i I = Q i R i$
Berechne die neue Iterierte: $A i + 1 = R i Q i + κ i I$
end for

Der QR-Algorithmus ohne Shifts entspricht dem QR-Algorithmus mit Shifts identisch Null.

[Bearbeiten] Ähnlichkeitstransformationen

Die im QR-Algorithmus berechneten Matrizen sind zueinander unitär ähnlich, da aufgrund von $A_i-\kappa_iI=Q_iR_i\quad\Leftrightarrow\quad R_i=Q_i^H(A_i-\kappa_iI)$

gilt. Damit haben alle Matrizen $A i$ die selben Eigenwerte (mit der algebraischen und geometrischen Vielfachheit gezählt).

[Bearbeiten] Wahl der Shifts, Konvergenz

Eine einfache aber nicht sehr effektive Wahl ist die Wahl von Shifts identisch Null. Die Iterierten $A i$ des resultierenden Algorithmus, des QR-Algorithmus in der Grundform, konvergieren im Wesentlichen, wenn alle Eigenwerte dem Betrage nach verschieden sind, gegen eine obere Dreiecksmatrix mit den Eigenwerten auf der Diagonalen. Konvergenz im Wesentlichen bedeutet, daß die Elemente des unteren Dreiecks von $A i$ gegen Null gehen und die Diagonalelemente gegen die Eigenwerte. Über die Elemente im oberen Dreieck wird also nichts ausgesagt.

Werden die Shifts als das Matrixelement unten rechts der aktuellen Iterierten gewählt, also $\kappa_i=a_{nn}^{(i)}$ , so konvergiert der Algorithmus unter geeigneten Umständen quadratisch oder sogar kubisch. Dieser Shift ist als Rayleigh-Quotienten-Shift bekannt, da er über die Inverse Iteration mit einem Rayleigh-Quotienten im Zusammenhang steht.

Bei der Rechnung im Reellen ( $A\in\mathbb{R}^{n\times n}$ ) möchte man die reelle Schur-Form berechnen und trotzdem mit konjugiert komplexen Eigenwerten arbeiten können. Dazu gibt es verschiedene Shift-Strategien.

Eine Erweiterung von einfachen Shifts ist der nach James Hardy Wilkinson benannte Wilkinson-Shift. Für den Wilkinson-Shift wird der näher am letzten Matrixelement liegende Eigenwert der letzten $2\times 2$ Hauptunterabschnittsmatrix