Hessenberg-Form und QR-Algorithmus

Der QR-Algorithmus

Zu jeder (reellen) Matrix A existiert eine so genannte QR-Zerlegung

mit einer Orthogonalmatrix Q und einer Rechtsdreiecksmatrix R. Für die Realisierung dieser Zerlegung gibt es verschiedene Strategien, mit dem Schmidtschen Orthonormierungsverfahren wird eine Möglichkeit auf der Seite "Inverse simultane Vektoriteration (symm. AEWP)" gezeigt (dort mit einer Rechteckmatrix und einem etwas weiter gefassten Ziel).

Auf der Basis der QR-Zerlegung für quadratische Matrizen existiert ein sehr einfacher Algorithmus für das Erzeugen der Schurschen Form einer (reellen) Matrix A:

Jeder Iterationsschritt besteht also aus einer QR-Zerlegung und einer anschließenden Matrixmultiplikation. Die Matrizen H_k konvergieren gegen die Schursche Form der Matrix A, deren Hauptdiagonalelemente die Eigenwerte der Matrix A sind (bei konjugiert komplexen Eigenwertpaaren repräsentiert ein 2*2-Hauptdiagonalblock diese beiden Eigenwerte).

Reduzierung einer Matrix auf Hessenberg-Form

Der Aufwand für die oben beschriebene QR-Zerlegung kann wesentlich reduziert werden, wenn die Matrix A vorher auf die so genannte Hessenberg-Form transformiert wird. Dies ist eine Matrix, auf der zusätzlich zur Rechtsdreiecksmatrix die  Nebendiagonale unter der Hauptdiagonalen mit von Null verschiedenen Elementen besetzt ist. Dabei ist darauf zu achten, dass nur Transformationen zugelassen sind, die die Eigenwerte nicht verändern.

Dies wird erreicht durch Ähnlichkeitstransformationen mit elementaren Orthogonalmatrizen . Das Ziel wird erreicht durch die so genannten Givens-Rotationen, mit denen durch eine p-q-Transformation, die nur die Zeilen p und q und die Spalten p und q der Ausgangsmatrix verändert, erreicht werden kann, dass das Matrixelement a_q,p−1 zu Null wird, wenn der Rotationswinkels φ_k der Gleichung

genügt. Im Gegensatz zum Jacobi-Verfahren, bei dem mit einer p-q-Transformation das Element a_q,p zu Null wird, ist es bei der Givens-Rotation das linke Nachbarelement. Dies hat den Vorteil, dass (im Gegensatz zum Jacobi-Verfahren) durch geeignete Wahl der Reihenfolge der Transformationen bereits erzeugte Nullen nicht wieder zerstört werden, hat allerdings den Nachteil, dass die Nebendiagonale unterhalb der Hauptdiagonalen auf diesem Wege nicht zu Null gemacht werden kann.

Wenn man z. B. die Nullen unterhalb der Nebendiagonalen spaltenweise von links nach rechts erzeugt, kommt man nach genau (n−1)(n−2)/2 Transformationen zum Ziel. Diese Anzahl entspricht der Anzahl der Nullen in der Hessenberg-Form der Matrix, das Erzeugen dieser Form ist also (im Gegensatz zum Jacobi-Verfahren) kein iterativer Prozess.

Bei symmetrischen Matrizen entstehen die Null-Elemente automatisch auch im rechten oberen Bereich der Matrix, so dass das Ergebnis schließlich eine so genannte symmetrische Tridiagonalmatrix ist.

Der oben angegebene QR-Algorithmus wird also in dem Sinne modifiziert, dass die erste Zeile, die die Startmatrix für die Iteration festlegt, durch die Hessenberg-Transformation der Matrix A ersetzt wird.

Demonstration der Aussagen an einem Beispiel

Das auch für verschiedene andere Aussagen verwendete kleine Beispiel, dessen Hintergrund hier beschrieben wird, soll genutzt werden, um die oben gemachten Aussagen mit Matlab zu demonstrieren. In Matlab stehen für die Transformation einer Matrix auf Hessenberg-Form die Function hess und für die QR-Zerlegung einer Matrix die Function qr zur Verfügung.

Im nebenstehend zu sehenden Script werden die beiden symmetrischen Matrizen des Allgemeinen Matrizeneigenwertproblems in den Zeilen 3 bis 17 aufgebaut. In Zeile 22 wird daraus die unsymmetrische Matrix Aq, in Zeile 28 wird die symmetrische Matrixd  As eines jeweils äquivalenten Speziellen Matrizeneigenwertproblems erzeugt (siehe dazu: "Allgemeines → Spezielles Matrizeneigenwertproblem").

In Zeile 30 werden beide Matrizen in die Hessenberg-Form transformiert (und in das Command Window ausgegeben).

In den Zeilen 31 bis 34 werden für beide Matrizen 20 Iterationsschritte des oben beschriebenen QR-Algorithmus ausgeführt, die die Matrizen in die Schursche Form bringen, so dass auf den Hauptdiagonalen die Eigenwerte zu finden sind.

Nachstehend ist zunächst ein Ausschnitt des Command Windows zu sehen, der die in der Zeile 30 ermittelten Hessenberg-Formen zeigt. Die aus der unssymmetrischen Matrix Aq erzeugte Matrix Hqk zeigt die typische Besetzung mit von Null verschiedenen Elementen ("Rechtsdreiecksmatrix + Nebendiagonale"). Die aus der symmetrischen Matrix As erzeugte Hessenberg-Matrix Hsk ist eine symmetrische Tridiagonalmatrix:

Nach 20 Iterationsschritten des QR-Algorithmus zeigen die Matrizen Schursche Form . Die unsymmetrische Matrix führt (es ergeben sich nur reelle Eigenwerte) auf eine reine Rechtsdreiecksmatrix, die symmetrische Matrix führt auf eine reine Diagonalmatrix. In beiden Matrizen stehen die Eigenwerte auf den Hauptdiagonalen: