0
$\begingroup$

Considering pure QR algorithm (without shifts and preliminary tridiagonal reduction) are there sufficient conditions for algorithm to converge to quasi-diagonal form?

For the the following matrix $$ A = \left(\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right). $$ with eigenvalues $\lambda_1 = 1$ and $\lambda_2 = -1$ it apparently does not. QR decomposition produces the following $$ A = QR = \left(\begin{array}{cc} 0 & 1\\ 1 & 0\end{array}\right) \left(\begin{array}{cc} 1 & 0\\ 0 & 1 \end{array}\right), $$ which generates stationary sequence $\{A^{(k)}\}$.

$\endgroup$
2
  • $\begingroup$ You didn't miss anything. Maybe you just missunderstood what is known about the QR-algorithm. There is no general convergence statement for the QR-algorithm, only theorems like "for almost all inputs it converges". You just found an example that shows you that "almost all" is as good as is gets... $\endgroup$ Sep 9 '13 at 16:25
  • $\begingroup$ Shifts. You're missing shifts. Check out the document in @guest's answer. $\endgroup$ Sep 9 '13 at 16:29
2
$\begingroup$

This example is explained in section 11.5 here.

$\endgroup$
0

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