imported>Aka: Halbgeviertstrich

2017-11-15T17:35:56Z

Halbgeviertstrich

Neue Seite

Das '''Hessenberg-Verfahren''' ist ein Verfahren der [[Numerische lineare Algebra|numerischen linearen Algebra]] zur Transformation einer quadratischen Matrix in [[Hessenbergmatrix|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 [[Technische Universität Darmstadt|Technischen Hochschule Darmstadt]] ein im Buch ''Elementary Matrices'' von Frazer, Duncan und Collar beschriebenes Verfahren. In 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 <math>A\in\mathbb{C}^{n \times n}</math> und dem ersten Einheitsvektor <math>e_1=\begin{pmatrix}1&0&\cdots&0\end{pmatrix}^T\in\mathbb{C}^n</math> konstruiert Hessenberg eine Basis eines Krylov-Unterraums, indem er zuerst die Matrix <math>A</math> auf den Vektor anwendet und mit einem geeigneten Vielfachen des ersten Einheitsvektors die erste Komponente eliminiert.

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

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

:<math>AZ=ZP</math>

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

:<math>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}</math>

und

:<math>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}.</math>

eine unreduzierte [[Hessenbergmatrix]] mit Einsen auf der Subdiagonalen ist.

Die Reduktion auf [[Hessenbergmatrix|Hessenbergform]] ist nur dann immer möglich, wenn die Ausgangsmatrix <math>A</math> 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==
[[James Hardy Wilkinson|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 <math>H=Q^HAQ\in\mathbb{C}^{n\times n}</math> gilt heute die unitäre Reduktion mit [[Householder-Spiegelung]]en oder [[Givens-Rotation]]en als das numerisch stabilste Standardverfahren, vgl. [[QR-Algorithmus#Transformation auf Hessenberg-Form|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

[[Kategorie:Numerische lineare Algebra]]

Hessenberg-Verfahren - Versionsgeschichte

imported>Aka: Halbgeviertstrich