Past exam of the numerical analysis course of the University of Oxford / 2014 / 1 / d

A QR factorization of a real $n\times n$ matrix isThus $Q$ is an orthogonal matrix and $R$ is an upper triangular matrix. It exists even if $A$ is singular; requiring positive diagonal entries of $R$ is a convenient uniqueness convention for nonsingular $A$, rather than part of the general existence statement. Over the complex numbers, replace orthogonal by unitary and transpose by conjugate transpose.

For an efficient QR algorithm, first reduce a general real matrix to upper Hessenberg matrix by orthogonal similarities. For a real symmetric matrix, use Householder tridiagonalization; the resulting symmetric tridiagonal matrix is the usual input in this setting. These structures are preserved by suitable QR algorithm implementations and greatly reduce the work per iteration.

The output is the eigenvalues, together with an orthogonal reduction when the factors are accumulated. In the symmetric case the target is a diagonal matrix, whose diagonal entries are the real eigenvalues; the accumulated orthogonal columns are eigenvectors. For a general real matrix, the target is the real form in a Schur decomposition: an upper block triangular matrix with diagonal blocks of size one or two. The two-by-two blocks represent complex conjugate eigenvalue pairs. An arbitrary unshifted iteration need not converge, so these describe the intended converged output, with appropriate shifts and block deflation in the QR algorithm.

With $A_0=A$, repeat the shifted QR algorithm:The QR shift ${\mu }_k$ is chosen from $A_k$, for example its bottom-right entry or an eigenvalue of a trailing two-by-two block. Explicitly using the orthogonality of $Q_k$ givesThus each update is a matrix similarity preserving eigenvalues. Accumulate $Q_0{Q}_1\cdots Q_k$ if eigenvectors or the full reduction are wanted. Once a subdiagonal entry is negligible, block deflation in the QR algorithm separates the corresponding blocks and iteration continues on the active block.