The asymptotics of Wilkinson's shift: Loss of cubic convergence (Q2269903)

The paper deals in the principal with one of the most widely used methods for eigenvalue computation. In particular it is the \(QR\) iteration with Wilkinson's shift: Here, the shift \(s\) is the eigenvalue of the bottom \(2\times 2\) principal minor closest to the corner entry. It has been a long-standing question whether the rate of convergence of the algorithm is always cubic. In contrast, the authors show that there exist matrices for which the rate of convergence is strictly quadratic. More precisely, let \(T_{\mathcal{X}}\) be the \(3\times 3\) matrix having only two nonzero entries \((T_{ {\mathcal{X}}})_{12}=(T_{ {\mathcal {X}}})_{21}=1\) and let \({\mathcal{T}}_{\varLambda }\) be the set of real, symmetric tridiagonal matrices with the same spectrum as \(T_{ {\mathcal{X}}}\). There exists a neighborhood \({\mathcal {U}}\subset {\mathcal{T}}_{\varLambda }\) of \(T_{ {\mathcal{X}}}\) which is invariant under Wilkinson's shift strategy with the following properties. For \(T_{0}\in {\mathcal{U}}\), the sequence of iterates \((T_k)\) exhibits either strictly quadratic or strictly cubic convergence to zero of the entry \((T_k)_{23}\). In fact, quadratic convergence occurs exactly when \(\lim T_{k}=T_{ {\mathcal{X}}}\). Let \({\mathcal{X}}\) be the union of such quadratically convergent sequences \((T_k)\): The set \({\mathcal {X}}\) has Hausdorff dimension 1 and is a union of disjoint arcs \({\mathcal{X}}^{\sigma}\) meeting at \(T_{ {\mathcal{X}}}\), where \(\sigma \) ranges over a Cantor set. The introductory part is very elaborated providing a detailed appraisal of the contemporary knowledge of the problem. Basic prerequisites are condensed in a theorem serving as a starting point of the further analysis. The list of references is large enough representing a sufficient overview of resources including an evaluation of their strengths and weaknesses. The concluding remarks are clearly stated including the limitations of results obtained. An outlook for the future is outlined. In any case the paper represents a very good contribution valuable for numerical mathematics. However, being understandable for readers in the engineering area, it can be useful also for applications in numerical analysis of low dimensional dynamical systems.