Hessenberg process

The Hessenberg method is a numerical linear algebra method for transforming a square matrix in Hessenberg shape . The eigenvalues ​​of the resulting Hessenberg matrix can then be easily calculated. It is probably the first Krylow subspace method and was published by Karl Hessenberg in 1940.

In the report Treatment of linear eigenvalue problems with the help of the Hamilton-Cayley equation , submitted on July 23, 1940 at the Institute for Practical Mathematics (IPM) of the Technical University of Darmstadt, Hessenberg refines a method described in the book Elementary Matrices by Frazer, Duncan and Collar. This report first describes the Frazer, Duncan and Collar method, then the simplification achieved by Hessenberg.

The Hessenberg process

Starting from a square matrix and the first unit vector , Hessenberg constructs a basis of a Krylov subspace by first applying the matrix to the vector and eliminating the first component with a suitable multiple of the first unit vector. ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ ${\displaystyle e_{1}={\begin{pmatrix}1&0&\cdots &0\end{pmatrix}}^{T}\in \mathbb {C} ^{n}}$ ${\displaystyle A}$

In the th step, the iteration is based on the expansion of the space by multiplying the vector obtained last by and then subtracting multiples of the previously obtained basic vectors in order to eliminate the first components. ${\displaystyle k}$ ${\displaystyle A}$ ${\displaystyle k-1}$ ${\displaystyle k}$

In the end, the process (in general) breaks with a relation of form

${\displaystyle AZ=ZP}$

from, where the (modified) basis vectors of the Krylov subspace are contained in the lower triangular matrix , ${\displaystyle Z\in \mathbb {C} ^{n\times n}}$

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

and

${\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}.}$

is an unreduced Hessenberg matrix with ones on the subdiagonal.

The reduction to Hessenberg form is only always possible if the output matrix is non-derogative, i.e. only one Jordan block belongs to each eigenvalue of the matrix. Hessenberg already gives refinements for derogative matrices, the result is a reduced Hessenberg matrix with either ones or zeros in the subdiagonal. ${\displaystyle A}$

Related Procedures and Generalizations

Jim Wilkinson generalized Hessenberg's method so that ones do not necessarily have to appear on the subdiagonal, but arbitrary elements not equal to zero.

The Hessenberg method is a reduction to the Hessenberg form based on the LR decomposition . The reduction to the Hessenberg form based on the QR decomposition is known as the Arnoldi method , which, however, is usually not carried out as an approximation method up to the full dimension n . For the complete reduction of a matrix A to Hessenberg form , the unitary reduction with Householder reflections or Givens rotations is the numerically most stable standard method, cf. QR algorithm . ${\displaystyle H=Q^{H}AQ\in \mathbb {C} ^{n\times n}}$

CMRH , a residual minimizing method by Hassane Sadok, is also based on the Hessenberg method.

credentials

• Treatment of linear eigenvalue problems with the help of the Hamilton-Cayley equation , K. Hessenberg (as editor), A. Walther (institute director), 1st report of the series Numerical Methods of the Institute for Practical Mathematics (IPM) of the Technical University of Darmstadt, July 23, 1940 , 37 pages
• Graphical and numerical methods , L. Collatz, FIAT Review Applied Mathematics , Volume 3, Part I, editor Alwin Walther, 1948, pages 1-92
• The Algebraic Eigenvalue Problem , JH Wilkinson, 1965, Oxford University Press, pp. 377-382
• Comments on the method by Hessenberg , Rudolf Zurmühl, Numerische Mathematik Vol. 4, 1963, pages 377-380
• CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm , H. Sadok, Numerical Algorithms 20, 1999, pages 303-321