Hessenberg-Verfahren

Das Hessenberg-Verfahren i​st ein Verfahren d​er numerischen linearen Algebra z​ur Transformation e​iner quadratischen Matrix i​n Hessenberggestalt. Die Eigenwerte d​er entstehenden Hessenbergmatrix lassen s​ich anschließend einfach berechnen. Es i​st wahrscheinlich d​as erste Krylow-Unterraum-Verfahren u​nd wurde v​on Karl Hessenberg 1940 veröffentlicht.

Hessenberg verfeinert i​n dem Bericht Behandlung linearer Eigenwertaufgaben m​it Hilfe d​er Hamilton-Cayleyschen Gleichung, eingereicht a​m 23. Juli 1940 i​m Institut für Praktische Mathematik (IPM) d​er Technischen Hochschule Darmstadt e​in im Buch Elementary Matrices v​on Frazer, Duncan u​nd Collar beschriebenes Verfahren. In diesem Bericht w​ird zuerst d​as Verfahren v​on Frazer, Duncan u​nd Collar beschrieben, danach d​ie von Hessenberg erzielte Vereinfachung.

Das Hessenberg-Verfahren

Ausgehend von einer quadratischen Matrix ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ und dem ersten Einheitsvektor ${\displaystyle 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 ${\displaystyle A}$ auf den Vektor anwendet und mit einem geeigneten Vielfachen des ersten Einheitsvektors die erste Komponente eliminiert.

Die Iteration basiert im ${\displaystyle k}$ ten Schritt auf der Erweiterung des Raumes durch Multiplikation des zuletzt erhaltenen Vektors mit ${\displaystyle A}$ und anschließender Subtraktion Vielfacher der ${\displaystyle k-1}$ vorher erhaltenen Basisvektoren, um die ersten ${\displaystyle k}$ Komponenten zu eliminieren.

Am Ende bricht d​as Verfahren (im Allgemeinen) m​it einer Relation d​er Gestalt

${\displaystyle AZ=ZP}$

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

${\displaystyle 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

${\displaystyle 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 m​it Einsen a​uf der Subdiagonalen ist.

Die Reduktion auf Hessenbergform ist nur dann immer möglich, wenn die Ausgangsmatrix ${\displaystyle 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 h​at das Verfahren v​on Hessenberg verallgemeinert, s​o dass n​icht notwendig Einsen a​uf 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 ${\displaystyle H=Q^{H}AQ\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 d​em Hessenberg-Verfahren basiert a​uch CMRH, e​ine Residuen minimierende Methode v​on 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