next up previous
Next: QR decomposition of upper Up: Eigenvalue Problems Previous: Householder Transformations

QR Algorithm

The basic QR algorithm to compute eigenvalues makes use of the Schur Normal Form. Schur's theorem states that


The basic QR algorithm can be written as follows:

 Given  tex2html_wrap_inline303  ¯ tex2html_wrap_inline487 ,
define  tex2html_wrap_inline489 .

For tex2html_wrap_inline491 do

Calculate the QR decomposition tex2html_wrap_inline493 ,

Define tex2html_wrap_inline495 .

Computing the QR decomposition of a general matrix is computationally intensive ( tex2html_wrap_inline497 operations) to perform at each step. To save this overhead, we use similarity transformations to convert tex2html_wrap_inline303 to an upper Hessenberg matrix. Computing the QR decomposition of upper Hessenberg matrices is only an tex2html_wrap_inline501 operation. It is important to note that the QR decomposition of an upper Hessenberg matrix yields an orthogonal component tex2html_wrap_inline503 which also upper Hessenberg. Therefore, tex2html_wrap_inline505 's generated by the basic QR algorithm on upper Hessenberg matrices preserve the upper Hessenberg property.

Shankar Krishnan
Mon Apr 21 01:16:56 EDT 1997