The Asymptotics of Wilkinson's Iteration: Loss of Cubic Convergence

preprint2008arXivOpen access

Abstract

One of the most widely used methods for eigenvalue computation is the QRQR iteration with Wilkinson's shift: here the shift ss is the eigenvalue of the bottom 2×22\times 2 principal minor closest to the corner entry. It has been a long-standing conjecture that the rate of convergence of the algorithm is cubic. In contrast, we show that there exist matrices for which the rate of convergence is strictly quadratic. More precisely, let TXT_X be the 3×33 \times 3 matrix having only two nonzero entries (TX)12=(TX)21=1(T_X)_{12} = (T_X)_{21} = 1 and let TLT_L be the set of real, symmetric tridiagonal matrices with the same spectrum as TXT_X. There exists a neighborhood U⊂TLU \subset T_L of TXT_X which is invariant under Wilkinson's shift strategy with the following properties. For T0∈UT_0 \in U, the sequence of iterates (Tk)(T_k) exhibits either strictly quadratic or strictly cubic convergence to zero of the entry (Tk)23(T_k)_{23}. In fact, quadratic convergence occurs exactly when lim⁡Tk=TX\lim T_k = T_X. Let XX be the union of such quadratically convergent sequences (Tk)(T_k): the set XX has Hausdorff dimension 1 and is a union of disjoint arcs XσX^σ meeting at TXT_X, where σσ ranges over a Cantor set.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.