# QR-algorithm - convergence property

If $A\in \mathbb R^{n \times m}$ and $A = A^\top$ and if $\vert \lambda_1 \vert >\vert \lambda_2 \vert >\cdots>\vert \lambda_n \vert >0$ then $\lim\limits_{k\to \infty} Q_k = I$, $\lim\limits_{k\to \infty} R_k = \mathrm{diag}(\lambda_1,\dots,\lambda_n)$ and $(A_{k})_{i,j} = O\left(\left(\dfrac{\vert \lambda_{i} \vert}{\vert \lambda_{j} \vert}\right)^k\right)$ for $i > j$.

Okay. I find it hard to understand the last part:

$(A_{k})_{i,j} = O\left(\left(\dfrac{\vert \lambda_{i} \vert}{\vert \lambda_{j} \vert}\right)^k\right)$ for $i > j$.

Is there someone who can explain what it means?

-
Regarding the present question, the top part seems to indicate that you know how to use $\TeX$ here. Has it escaped your notice that the second part is mangled? You will generally find that people are willing to invest time into answering your questions if they get the impression that you're willing to invest time into them yourself. – joriki Nov 1 '11 at 18:53

## 1 Answer

It's more or less just explaining the convergence rate of the QR algorithm. Remember that the endgame for the QR algorithm is to construct the Schur decomposition, $\mathbf A=\mathbf Q\mathbf T\mathbf Q^\top$, where $\mathbf T$ is triangular and $\mathbf Q$ is orthogonal. In the case you're considering, $\mathbf A$ is symmetric ($\mathbf A=\mathbf A^\top$), and thus $\mathbf T$ is the diagonal matrix of eigenvalues.

With this in mind, one expects that with every successive orthogonal similarity transformation, the off-diagonal elements ought to converge to zero. The statement that you were puzzling about just says that the rate of decrease of the off-diagonals roughly follows a decaying exponential, with the base for each element depending on the ratios of the matrix's eigenvalues.

-