# QR Iteration and power methods convergence

The QR iteration does the following:
for some matrix of interest $A=A_0$ and $k=1,2,3 \dots$

\begin{align} A_{k-1}&=Q_{k}R_{k}\\ A_{k}&=R_{k}Q_{k}\\ \hat{Q} &=Q_{1}Q_{2}...Q_{k}\\ \end{align} Assume $\vert\lambda_1\vert>\vert\lambda_2\vert$ and $\mathbf{e}^{T}_{1}\mathbf{x}\neq 0$ (i.e. $x_1 \ne 0$ where $\mathbf{e_1}^T=[1,0,\dots]$ and $\mathbf{x}$ is a column vector).

(a) show that as k goes to infinity, the first column of $\hat{Q}_{k}$ converges to $\mathbf{x}$ in the following way:

$$\hat{Q}_{k}\mathbf{e}_1=\pm \mathbf{x}+O\left(\left|\frac{\lambda_2}{\lambda_1}\right|^k\right)$$

where the sign $\pm$ is fixed for all k if $\lambda_{1}>0$, and alternates with k if $\lambda_{1}<0$.

(b) Use (a) prove that for k goes to infinity

$$A_k\mathbf{e}_1=\lambda_1\mathbf{e}_1+O\left(\left| \frac{\lambda_2}{\lambda_1}\right|^k\right)$$

-
This question addresses the convergence of the QR iteration to (the largest) eigenvector and eigenvalue. Can someone (the OP or anyone else that is able) clarify the question further? –  adam W Jan 7 '13 at 17:21
@adamW not sure what kind of clarification you are looking for. en.wikipedia.org/wiki/QR_decomposition for definition of $Q_k$ and $R_k$ and en.wikipedia.org/wiki/QR_algorithm with $p(A)=A$ leads to the given $A_k = R_k Q_k$. This is a direct generalization of the simple power iteration. –  example Jan 14 '13 at 14:55
@example I assumed that because the original question was a homework one, that there was some sort of understandable answer to the specific $\mathrel{O}$ notation and convergence for $|\lambda_1| > |\lambda_2|$. I have implemented the code for QR iteration (in complex with single shifts) so I am familiar enough with that. Any response that more formally answers this question I think should enlighten me further. Feel free to edit the question as the original required some cleanup. –  adam W Jan 14 '13 at 16:05