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 aq,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 aq,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.
|