2
$\begingroup$

I am seeking an intuitive understanding of why the QR Algorithm solves the symmetric eigenvalue problem. In class, and also in Golub and Van Loan, it has been suggested that there is somehow deep connection between the power method for finding the largest eigenvector. In fact, the power method can be generalized to "Orthogonal Iterations," where you repeatedly apply the matrix to an n-by-r random matrix (instead of just one random vector), and then orthogonalize at each step, which gives the top-r eigenvectors of the matrix (from which the eigenvalues can be calculated).

The QR Algorithm (with or without shifts) also gives the eigenvalues of the matrix by first making it tridiagonal, and then applying Givens rotations on both sides so that it is diagonal, and the eigenvalues are on the diagonal. Is there a connection between these two techniques? Perhaps these orthogonal Givens rotations are somehow analogous to the random matrix in the "orthogonal iterations" above?

$\endgroup$
2
$\begingroup$

At first I describe the connection of the QR algorithm with the power method and the inverse power method. As I understand this is the main topic you are interested in. Later -- when I have a little more time -- I will extent this to subspace iteration. I think that is what the second part of your question is about.

Keeping the discussion simple, let $A\in\mathbb{C}^{n\times n}$ be a regular complex square matrix with eigenvalues having pairwise distinct absolute values.

The QR algorithm without shift is defined by the iteration \begin{align*} &\text{Start}&A_1 &:= A\\ &\text{QR-decomposition}& Q_i R_i &:= A_i &&@i=1,\ldots\\ &\text{rearranged new iterate}&A_{i+1} &:= R_i Q_i \end{align*} Representing $R_i$ as $R_i = Q_i^H A_i$ and substituting this into the formula for $A_{i+1}$ gives $ A_{i+1} = Q_i^H A_i Q_i$. Thus, the matrix $A_{i+1}$ is similar to $A_i$ and has the same eigenvalues. Defining the combined orthogonal transformation $\bar Q_i := Q_1\cdot\ldots\cdot Q_i$ for $i=1,\ldots$ we obtain \begin{align*} A_{i+1} &= \bar Q_i^H A \bar Q_i&&@ i=1,\ldots \end{align*} or $A_i = \bar Q^H_{i-1} A \bar Q_i$ for $i=2,\ldots$. We substitute $A_i$ in the above QR-decomposition with this formula and obtain \begin{align*} Q_i R_i &= A_i = \bar Q_{i-1}^H A \bar Q_{i-1}\\ \bar Q_i R_i &= A \bar Q_{i-1} \end{align*} Taking the first column on both sides of the last equation one gets \begin{align*} \bar Q_i(:,1)\cdot R_i(1,1) = A\cdot \bar Q_{i-1}(:,1) \end{align*} (with Octave notation of the matrix elements) which shows that $R_i(1,1)$ and $\bar Q_i(:,1)$ are just the approximations for the eigenvalue and the eigenvector, respectively, in the power-iteration for the matrix $A$. The elements $R_i(1,1)$ with $i=1,\ldots$ converge to largest of the eigenvalues whose eigenvectors belong to the invariant subspace of $A$ spanned by the vectors $A^k Q_1(:,1)$ with $k=0,\ldots,n-1$.

Analogously to the above procedure we use the formula for the rearranged new iterate of the QR-algorithm to get \begin{align*} \bar Q_i^H A \bar Q_i &= A_{i+1} = R_i Q_i\\ \bar Q_i^H A &= R_i \bar Q_{i-1}^H \end{align*} The last row of the last equation results to \begin{align*} \bar Q_i^H(n,:) \cdot A &= R_i(n,n)\cdot \bar Q^H_{i-1}(n,:). \end{align*} Theoretically, one can calculate the sequences $\bar Q_i^H(n,:)$ and $R_i(n,n)$ for $i=2,\ldots$ from $\bar Q_1^H(n,:)=Q_1^H(n,:)$ by the inverse power iteration \begin{align*} &\text{Solve}& x\cdot A &= \bar Q_{i-1}^H(n,:)&&\text{for }x\in\mathbb{C}^{1,n}\\ &\text{Normalize} & \bar Q_i^H(n,:) &:= \frac{x}{|x|}\\ &\text{Set}& R_i(n,n) &:= |x| \end{align*} where $R_i(n,n)$ are the approximations for the smallest of the eigenvalues of $A$ with corresponding left-eigenvector in the subspace spanned by the vectors $Q_1^H(n,:)\cdot A^k$ with $k=0,\ldots,n-1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.