The Asymptotics of Wilkinson’s Shift: Loss of Cubic Convergence

• Published in: Foundations of computational mathematics 2010-02, Vol.10 (1), p.15-36
• Main Authors: Leite, Ricardo S., Saldanha, Nicolau C., Tomei, Carlos
• Format: Article
• Language: English
• Subjects: Algorithms; Applications of Mathematics; Applied mathematics; Computer Science; Economics; Eigenvalues; Linear and Multilinear Algebras; Math Applications in Computer Science; Mathematical models; Mathematics; Mathematics and Statistics; Matrix Theory; Numerical Analysis
• ISSN: 1615-3375; 1615-3383
• DOI: 10.1007/s10208-009-9047-3

One of the most widely used methods for eigenvalue computation is the QR iteration with Wilkinson’s shift: Here, the shift s is the eigenvalue of the bottom 2×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, we show that there exist matrices for which the rate of convergence is strictly quadratic. More precisely, let be the 3×3 matrix having only two nonzero entries and let be the set of real, symmetric tridiagonal matrices with the same spectrum as . There exists a neighborhood of which is invariant under Wilkinson’s shift strategy with the following properties. For , 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 . Let be the union of such quadratically convergent sequences ( T k ): The set has Hausdorff dimension 1 and is a union of disjoint arcs meeting at , where σ ranges over a Cantor set.