Franklin's Notes

Hessenberg reduction

Knowing the Schur factorization of a matrix $A\in\mathbb C^{m\times m}$ greatly simplifies the problem of finding the eigenvalues of $A$. However, the most apparent way of computing a Schur factorization, namely the repeated application of Householder reflectors to $A$ from both sides, does not actually result in a guaranteed Schur factorization. However, we can obtain a modified matrix factorization in this way, known as the Hessenberg reduction, which takes the form $A=QHQ^\ast$, where $H\in\mathbb C^{m\times m}$ is an upper Hessenberg matrix, that is, a matrix with zeroes in all entries below the first subdiagonal, so that it can be thought of as "almost upper triangular". Although this doesn't make computing eigenvalues quite as easy as a Schur factorization, it is still beneficial.

With respect to stability, Hessenberg reduction gives rise to the same situation as Householder QR. That is, Hessenberg reduction is backwards stable , so that if $\tilde Q \tilde H \tilde Q^\ast$ is the computed Hessenberg reduction of $A$, then $\tilde Q \tilde H \tilde Q^\ast = A +\delta A$, for some $\delta A$ such that

Additionally, if $A$ is a Hermitian matrix , and $A=QHQ^\ast$ is a Hessenberg reduction, then it follows easily that $H=H^\ast$. But since $H$ is Hessenberg, it follows that $H$ must be both upper and lower Hessenberg, so that it is a tridiagonal matrix.




back to home page