QRAlgorithmen

Der QR-Algorithmus (QR-Algorithm) ist eine Familie numerischer Verfahren zur Bestimmung von Eigenwerten und, falls gewünscht, Eigenvektoren einer quadratischen Matrix durch die wiederholte Anwendung von QR-Zerlegungen. Ausgangspunkt ist eine Matrix A. In jedem Schritt wird A_k in A_k = Q_k R_k zerlegt. Danach setzt man A_{k+1} = R_k Q_k. Da A_{k+1} = Q_k^{-1} A_k Q_k ist, bleibt A_k bis auf eine Äquivalenztransformation similar zu A_0; damit enthalten A_k dieselben Eigenwerte wie das ursprüngliche A.

Bei allgemeinen Matrizen wird der Algorithmus typischerweise mit einer Vorverarbeitung auf eine obere Hessenbergform begonnen, damit die QR-Zerlegung kostengünstig bleibt. Für symmetrische Matrizen konvergiert der QR-Algorithmus gegen eine Diagonalisierung, d.h. die Diagonalelemente konvergieren gegen die Eigenwerte. Bei unsymmetrischen Matrizen konvergiert er aufgebläht zu einer oberen Hessenberg- oder quasi-diagonalen Form, aus der die Eigenwerte abgelesen werden können.

Um die Konvergenz zu beschleunigen, kommen Verschiebungen zum Einsatz, wie der Wilkinson-Verschiebung; in der klassischen Implementierung werden oft das Implicit QR-Verfahren (ohne explizite QR-Zerlegung in jedem Schritt) und Deflation genutzt, sobald Unterdiagonaleneinträge klein werden und Blockdiagonalstrukturen entstehen. Die Komplexität eines QR-Schritts beträgt O(n^3); insgesamt wird der Algorithmus in Praxis in stabilen Implementierungen wie LAPACK verwendet, die Householder-Reflektionen und Shift-Strategien einsetzen.

Historisch gehört der QR-Algorithmus zu den Kernmethoden der numerischen Linearen Algebra. Er wurde in den 1960er Jahren von Francis eingeführt und später von Wilkinson wesentlich verbessert. Anwendungen umfassen die Berechnung von Eigenwertspektren in Naturwissenschaften, Technik und Statistik sowie die Lösung von Differentialgleichungssystemen, Stabilitätsanalyse und Mustererkennung.