Convergence analysis of un-shifted QR algorithm for computing Eigen-values.

423 Views Asked by At

The convergence proof of $QR$ algorithm is difficult so most of the books(i have found it only on slides) show that the algorithm converges in the following way:

$3$ steps:

$A_0 = Q_0R_0\qquad A_1 = R_0 Q_0 $

$A_1 = Q_1R_1\qquad A_2 = R_1 Q_1 $

$A_2 = Q_2R_2\qquad A_3 = R_2 Q_2 $

and

$[Q_0Q_1Q_2][R_2R_1R_0] = Q_0Q_1A_2R_1R_0$

$ = Q_0Q_1R_1Q_1R_1R_0$

$ = Q_0R_0Q_0R_0Q_0R_0$

$ =A^3$

How does this show that the matrix $A$ will converge to upper triangular matrix?

I am not looking for the proof of unshifted QR algorithm but trying to understand how this shows that the algorithm will converge.

Here is a picture of the slides which show similarity transformation and also the insight into convergence. I don't understand how does this computation gives insight into convergence. If someone can explain in details then it will be a great help for me. I also added the link to the slides here: Link to slides

Link to the slides