QR iteration

Steps

starts with $A_1=A$ and repeat for $k=1,2,...$
$Q_k{R}_k=A_k$ by QR factorization
$A_{k+1}=R_k{Q}_k$
when $A_{k+1}-A_k<tol$, stop

after convergence,
The diagonal entries of $A$ are the corresponding eigenvalues.
Eigenvectors are the columns of matrix $Q={\prod }_j^k{Q}_j$.

Cost

• Symmetric
  • $\frac{4}{3}{n}^3$ for only eigenvalues
  • $9n^3$ for both eigenvalues and eigenvectors
• General
  • $10n^3$ for eigenvalues only
  • $25n^3$ for both