Skip to main content

Subsection 10.2.4 A simple shifted QR algorithm

The equivalence of the subspace iteration and the QR algorithm tells us a lot about convergence:

  • The first \(n \) columns of \(V^{(k)} \) converge to the subspace spanned by the eigenvectors associated with \(\lambda_0, \ldots, \lambda_{k-1} \text{.}\)

  • The last \(m-n \) columns of \(V^{(k)} \) converge to the subspace orthogonal to the subspace spanned by the eigenvectors associated with \(\lambda_0, \ldots, \lambda_{k-1} \text{.}\)

  • If \(A \) is Hermitian, and hence the eigenvectors associated with \(\lambda_0, \ldots, \lambda_{k-1} \) are orthogonal to those associated with \(\lambda_k, \ldots, \lambda_{m-1} \) provided \(\vert \lambda_{k-1} \vert \gt \vert \lambda_k \vert \text{,}\) then the subspace orthongal to the subspace spanned by the eigenvectors associated with \(\lambda_0, \ldots, \lambda_{k-1} \) is the subspace spanned by the eigenvectors associated with \(\lambda_k, \ldots, \lambda_{m-1} \text{.}\)

  • The rate of convergence of these respective subspaces is linear with a constant \(\vert \lambda_k \vert / \vert \lambda_{k-1} \vert \text{.}\)

What if in this situation we focus on \(n = m-1 \text{?}\) Then

  • The last column of \(V^{(k)} \) converges to point in the direction of the eigenvector associated with \(\lambda_{m-1} \text{,}\) the smallest in magnitude.

  • The rate of convergence of that vector is linear with a constant \(\vert \lambda_{m-1} \vert / \vert \lambda_{m-2} \vert \text{.}\)

In other words, the subpace iteration acts upon the last column of \(V^{(k)} \) in the same way as would an inverse iteration. This suggests that that convergence can be greatly accellerated by shifting the matrix by an estimate of the eigenvalue smallest in magnitude. We could compute the Rayleigh quotient with the last column of \(V^{(k)} \) but a moment of reflection tells us that that estimate is already available as the bottom-right most element of \(A^{(k)} \text{,}\) which after all converges to an diagonal matrix with eigenvalues. Thus we arrive upon a simple shifted QR algorithm:

\begin{equation*} \begin{array}{l} \mbox{A simple shifted QR algorithm} \\ \\ V = I \\ {\bf for~} k:=0, \ldots \\ ~~~( Q, R ) := {\rm QR}( A - \alpha_{m-1,m-1} I ) \\ ~~~ A = R Q + \alpha_{m-1,m-1} I \\ ~~~ V = V Q \\ {\bf endfor} \\ \end{array} \end{equation*}
This algorithm inherits the cubic convergence of the Rayleigh quotient iteration, for the last column of \(V \text{.}\)

To more carefully examine this algorithm, let us annotate it as we did for the simple QR algorithm in the last unit.

\begin{equation*} \begin{array}{l} \mbox{A simple shifted QR algorithm} \\ \\ A^{(0)} = A \\ V^{(0)} = I \\ R^{(0)} = I \\ {\bf for~} k:=0, \ldots \\ ~~~\mu^{(k)} = \alpha_{m-1,m-1}^{(k)} \\ ~~~( Q^{(k+1)}, R^{(k+1)} ) := {\rm QR}( A^{(k)} - \mu^{(k)} I ) \\ ~~~ A^{(k+1)} = R^{(k+1)} Q^{(k+1)} + \mu^{(k)} I \\ ~~~ V^{(k+1)} = V^{(k)} Q^{(k+1)} \\ {\bf endfor} \end{array} \end{equation*}

The following exercises clarify some of the finer points.

Homework 10.2.4.1.

Show that \(A^{(k+1)} = {Q^{(k+1)}~}^H A^{(k)} Q^{(k+1)} \text{.}\)

Solution

The algorithm computes the QR factorization of \(A^{(k)} \)

\begin{equation*} A^{(k)} - \mu^{(k)} = Q^{(k+1)} R^{(k+1)} \end{equation*}

after which

\begin{equation*} A^{(k+1)} := R^{(k+1)} Q^{(k+1)} + \mu^{(k)}I \end{equation*}

Hence

\begin{equation*} A^{(k+1)} = R^{(k+1)} Q^{(k+1)} + \mu^{(k)}I = {Q^{(k+1)}~}^H (A^{(k)}-\mu^{(k)} I ) Q^{(k+1)} + \mu^{(k)}I = {Q^{(k+1)}~}^H A^{(k)} Q^{(k+1)}-\mu^{(k)} {Q^{(k+1)}~}^H Q^{(k+1)} + \mu^{(k)}I = {Q^{(k+1)}~}^H A^{(k)} Q^{(k+1)}. \end{equation*}

This last exercise confirms that the eigenvalues of \(A^{(k)} \) equal the eigenvalues of \(A \text{.}\)

Homework 10.2.4.2.

Show that

\begin{equation*} \begin{array}{l} ( A - \mu_{k-1} ) ( A - \mu_{k-2} ) \cdots ( A - \mu_1 ) ( A - \mu_0 ) \\ ~~~~~= \begin{array}[t]{c} \underbrace{ Q^{(0)} Q^{(1)} \cdots Q^{(k)} } \\ \mbox{unitary} \end{array} \begin{array}[t]{c} \underbrace{ R^{(k)} \cdots R^{(1)} R^{(0)}. } \\ \mbox{upper triangular} \end{array} \end{array} \end{equation*}
Solution

The algorithm computes the QR factorization of \(A^{(k)} \)

\begin{equation*} A^{(k)} - \mu^{(k)} = Q^{(k+1)} R^{(k+1)} \end{equation*}

after which

\begin{equation*} A^{(k+1)} := R^{(k+1)} Q^{(k+1)} + \mu^{(k)}I \end{equation*}

Hence

\begin{equation*} A^{(k+1)} = R^{(k+1)} Q^{(k+1)} + \mu^{(k)}I = {Q^{(k+1)}~}^H (A^{(k)}-\mu^{(k)} I ) Q^{(k+1)} + \mu^{(k)}I = {Q^{(k+1)}~}^H A^{(k)} Q^{(k+1)}-\mu^{(k)} {Q^{(k+1)}~}^H Q^{(k+1)} + \mu^{(k)}I = {Q^{(k+1)}~}^H A^{(k)} Q^{(k+1)}. \end{equation*}