Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$$

share|improve this question
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.