Dynamics of the Symmetric Eigenvalue Problem with Shift Strategies
Ricardo S. Leite, Nicolau C. Saldanha, Carlos Tomei · International Mathematics Research Notices · 2012
A common algorithm for the computation of eigenvalues of real symmetric tridiagonal matrices is the iteration of certain special maps Fσ called shifted QR steps. Such maps preserve spectrum and a natural common domain is , the manifold of real symmetric tridiagonal matrices conjugate to the diagonal matrix Λ. More precisely, a (generic) shift defines a map . A strategy specifies the shift to be applied at T so that Fσ(T)=Fσ(T)(T). Good shift strategies should lead to fast deflation: some off-diagonal coordinate tends to zero, allowing for reduction of the problem to submatrices. For topological reasons, continuous shift strategies do not obtain fast deflation; many standard strategies are indeed discontinuous. Practical implementation only gives rise systematically to bottom deflation, convergence to zero of the lowest off-diagonal entry b(T). For most shift strategies, convergence to zero of b(T) is cubic, |b(Fσ(T))|=Θ(|b(T)|k) for k=3. The existence of arithmetic progressions in the spectrum of T sometimes implies instead quadratic convergence, k=2. The complete integrability of the Toda lattice and the dynamics at non-smooth points are central to our discussion. The text does not assume knowledge of numerical linear algebra.