Hessenberg-Verfahren

Das Hessenberg-Verfahren ist ein Verfahren der numerischen linearen Algebra zur Transformation einer quadratischen Matrix in Hessenberggestalt. Die Eigenwerte der entstehenden Hessenbergmatrix lassen sich anschließend einfach berechnen. Es ist wahrscheinlich das erste Krylow-Unterraum-Verfahren und wurde von Karl Hessenberg 1940 veröffentlicht.

Hessenberg verfeinert in dem Bericht Behandlung linearer Eigenwertaufgaben mit Hilfe der Hamilton-Cayleyschen Gleichung, eingereicht am 23. Juli 1940 im Institut für Praktische Mathematik (IPM) der Technischen Hochschule Darmstadt ein im Buch Elementary Matrices von Frazer, Duncan und Collar beschriebenes Verfahren. Im diesem Bericht wird zuerst das Verfahren von Frazer, Duncan und Collar beschrieben, danach die von Hessenberg erzielte Vereinfachung.

Das Hessenberg-Verfahren

Ausgehend von einer quadratischen Matrix $A\in\mathbb{C}^{n \times n}$ und dem ersten Einheitsvektor $e_1=\begin{pmatrix}1&0&\cdots&0\end{pmatrix}^T\in\mathbb{C}^n$ konstruiert Hessenberg eine Basis eines Krylov-Unterraums, indem er zuerst die Matrix A auf den Vektor anwendet und mit einem geeigneten Vielfachen des ersten Einheitsvektors die erste Komponente eliminiert.

Die Iteration basiert im kten Schritt auf der Erweiterung des Raumes durch Multiplikation des zuletzt erhaltenen Vektors mit A und anschließender Subtraktion Vielfacher der k − 1 vorher erhaltenen Basisvektoren, um die ersten k Komponenten zu eliminieren.

Am Ende bricht das Verfahren (im Allgemeinen) mit einer Relation der Gestalt

AZ = ZP

ab, wobei in der unteren Dreiecksmatrix $Z\in\mathbb{C}^{n \times n}$ die (modifizierten) Basisvektoren des Krylov-Unterraums enthalten sind,

$Z=\begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & z_{22} & \ddots & \vdots \\ \vdots & \vdots & \ddots & 0 \\ 0 & z_{n2} & \cdots & z_{nn} \end{pmatrix}\in\mathbb{C}^{n \times n}$

und

$P=\begin{pmatrix} \alpha_{10} & \alpha_{20} & \cdots & \alpha_{n-1,0} & \alpha_{n0} \\ 1 & \alpha_{21} & \cdots & \alpha_{n-1,1} & \alpha_{n1} \\ 0 & 1 & \cdots & \alpha_{n-1,2} & \alpha_{n2} \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & \cdots & 0 & 1 & \alpha_{n,n-1} \end{pmatrix}\in\mathbb{C}^{n \times n}.$

eine unreduzierte Hessenbergmatrix mit Einsen auf der Subdiagonalen ist.

Die Reduktion auf Hessenbergform ist nur dann immer möglich, wenn die Ausgangsmatrix A nicht-derogativ ist, also zu jedem Eigenwert der Matrix immer nur ein Jordanblock gehört. Hessenberg gibt bereits Verfeinerungen für derogative Matrizen an, als Ergebnis erhält man dann eine reduzierte Hessenbergmatrix mit entweder Einsen oder Nullen in der Subdiagonalen.

Verwandte Verfahren und Verallgemeinerungen

Jim Wilkinson hat das Verfahren von Hessenberg verallgemeinert, so dass nicht notwendig Einsen auf der Subdiagonalen auftreten müssen, sondern beliebige Elemente ungleich Null.

Das Hessenberg-Verfahren ist eine auf der LR-Zerlegung basierende Reduktion auf Hessenbergform. Die auf der QR-Zerlegung basierende Reduktion auf Hessenbergform ist bekannt als das Arnoldi-Verfahren, das allerdings meist als Näherungsverfahren nicht bis zur vollen Dimension n durchgeführt wird. Für die vollständige Reduktion einer Matrix A auf Hessenbergform $H=Q^HAQ\in\mathbb{C}^{n\times n}$ gilt heute die unitäre Reduktion mit Householder-Spiegelungen oder Givens-Rotationen als das numerisch stabilste Standardverfahren, vgl. QR-Algorithmus.

Auf dem Hessenberg-Verfahren basiert auch CMRH, eine Residuen minimierende Methode von Hassane Sadok.

Referenzen

• Behandlung linearer Eigenwertaufgaben mit Hilfe der Hamilton-Cayleyschen Gleichung, K. Hessenberg (als Bearbeiter), A. Walther (Institutsdirektor), 1. Bericht der Reihe Numerische Verfahren des Instituts für Praktische Mathematik (IPM) der Technischen Hochschule Darmstadt, 23. Juli 1940, 37 Seiten
• Graphische und numerische Verfahren, L. Collatz, FIAT Review Angewandte Mathematik, Band 3, Teil I, Herausgeber Alwin Walther, 1948, Seiten 1-92
• The Algebraic Eigenvalue Problem, J. H. Wilkinson, 1965, Oxford University Press, Seiten 377-382
• Bemerkungen zum Verfahren von Hessenberg, Rudolf Zurmühl, Numerische Mathematik Vol. 4, 1963, Seiten 377-380
• CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm, H. Sadok, Numerical Algorithms 20, 1999, Seiten 303-321