AATA The LR and QR methods

Section 5.4 The LR and QR methods

The first main idea of the LR and QR methods is the following result:

Theorem 5.4.1.

If \(A,B\) are \(n\times n\) matrices and \(A\) is invertible, the spectra of \(AB\) and \(BA\) coincide:

\begin{equation*} \sigma(AB)=\sigma(BA). \end{equation*}

Proof.

This is an immediate consequence of Theorem 5.1.2 since

\begin{equation*} AB = A\cdot BA\cdot A^{-1}. \end{equation*}

Consider now a non-degenerate matrix \(A\) that admits a LU decomposition (see Section 4.3 for a discussion of when a matrices might not admit a LU decomposition). The previous section shows that we can decompose \(A\) as either \(LU\) or \(QR\text{.}\) None of the matrices \(L,U,Q,R\) can be degenerate and so we have that

\begin{equation*} \sigma(A) = \sigma(LU) = \sigma(UL) = \sigma(QR) = \sigma(RQ). \end{equation*}

Hence, starting with \(A\) and using either the LU or the QR decompositions, we can generate a whole sequence of matrices all with the same spectrum in the following inductive way:

Set \(A_0=A\text{;}\)
Given \(A_i,\,i\geq0\text{,}\) decompose it as \(A_i=L_iU_i\) (or as \(A_i=Q_iR_i\)) ...
... and set \(A_{i+1} = U_i L_i\) (or \(A_{i+1}=R_i Q_i\)).

The reason why this algorithm is useful comes from the following result:

Theorem 5.4.2.

The sequences above, whether done using the LU decomposition (when possible) or the QR decomposition, converge to a upper diagonal matrix \(A_\infty\text{.}\) In particular, the spectrum of \(A\) coincides with the elements on the diagonal of \(A_\infty\text{.}\)

The LR algorithm is implemented in the code below. In the last line we call MATLAB's own method to evaluate eigenvalues in order to double check that our implementation works fine.

The QR algorithm is implemented in the code below. As above, in the last line we call MATLAB's own method to evaluate eigenvalues to double check that our implementation works fine.

Final Remark 1. Since LU decomposition can require pivoting and gets unstable more easily, in practice only the QR decomposition is used to evaluate the eigenvalues of a matrix.

Final Remark 2. In concrete, the algorithm used to evaluate the eigenvalues is not even the elementary QR method illustrated above but some more sofisticated version of it. Some detail about it, together with MATLAB implementations, can be found at this nice QR algorithm page by A. Townsend (Cornell).