Hessenberg matrix

In linear algebra, a Hessenberg matrix is a special kind of square matrix, one that is "almost" triangular. To be exact, an upper Hessenberg matrix has zero entries below the first subdiagonal, and a lower Hessenberg matrix has zero entries above the first superdiagonal.[1] They are named after Karl Hessenberg.[2]

For example:

\begin{bmatrix}
1 & 4 & 2 & 3 \\
3 & 4 & 1 & 7 \\
0 & 2 & 3 & 4 \\
0 & 0 & 1 & 3 \\
\end{bmatrix}

is upper Hessenberg and

\begin{bmatrix}
1 & 2 & 0 & 0 \\
5 & 2 & 3 & 0 \\
3 & 4 & 3 & 7 \\
5 & 6 & 1 & 1 \\
\end{bmatrix}

is lower Hessenberg.

Computer programming

Many linear algebra algorithms require significantly less computational effort when applied to triangular matrices, and this improvement often carries over to Hessenberg matrices as well. If the constraints of a linear algebra problem do not allow a general matrix to be conveniently reduced to a triangular one, reduction to Hessenberg form is often the next best thing. In fact, reduction of any matrix to a Hessenberg form can be achieved in a finite number of steps (for example, through Householder's algorithm of unitary similarity transforms). Subsequent reduction of Hessenberg matrix to a triangular matrix can be achieved through iterative procedures, such as shifted QR-factorization. In eigenvalue algorithms, the Hessenberg matrix can be further reduced to a triangular matrix through Shifted QR-factorization combined with deflation steps. Reducing a general matrix to a Hessenberg matrix and then reducing further to a triangular matrix, instead of directly reducing a general matrix to a triangular matrix, often economizes the arithmetic involved in the QR algorithm for eigenvalue problems.

Properties

The product of a Hessenberg matrix with a triangular matrix is again Hessenberg. More precisely, if A is upper Hessenberg and T is upper triangular, then AT and TA are upper Hessenberg.

A matrix that is both upper Hessenberg and lower Hessenberg is a tridiagonal matrix.

See also

Notes

  1. Horn & Johnson (1985), page 28; Stoer & Bulirsch (2002), page 251
  2. Biswa Nath Datta (2010) Numerical Linear Algebra and Applications, 2nd Ed., Society for Industrial and Applied Mathematics (SIAM) ISBN 978-0-89871-685-6, p. 307

References

External links

This article is issued from Wikipedia - version of the Tuesday, February 26, 2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.