A note on the convergence theorem of the tridiagonal QR algorithm with Wilkinson's shift (Q495845): Difference between revisions

The QR algorithm is used to compute the eigenvalues of a symmetric tridiagonal matrix. The shift in each iteration is computed on the basis of the lower right \(2\times 2\) block in the matrix. The convergence is at least quadratic, but more often cubic or more. All possible cases of the order of convergence are analyzed in this paper, based on the limiting behavior of the lower right \(3\times3\) block. Denoting the limiting block as \[ \left(\begin{matrix} t & C & 0 \\ C & \lambda+D & 0 \\ 0 & 0 &\lambda\end{matrix}\right) \] the main theorem says that if \(C=D=0\), then the convergence is quadratic, if \(C=0\) and \(D\neq0\), then the convergence is better than cubic, and if \(CD\neq0\), then \(t=\lambda-D\) and the convergence is strictly cubic, and finally, if \(C\neq0\) and \(D=0\), then the convergence is at least quadratic.