A new shift of the QL algorithm for irreducible symmetric tridiagonal matrices (Q1062422): Difference between revisions

In this clearly-written paper the authors suggest a new shift for the QL algorithm. This shift consists of a choice between two alternative shifts, based on iteration data. Suppose that the tridiagonal matrix on the current iteration is given by \[ \begin{pmatrix} \alpha_1 & \beta_1 \\ \beta_1 & \alpha_2 & \beta_2 \\ \vdots & \vdots & \vdots \end{pmatrix} \] then two common shifts \(\sigma\) for the QL algorithm are given by (1) Rayleigh quotient shift, given by \(\sigma_ 1=\alpha_ 1\), and (2) Wilkinson's shift, given as that eigenvalue \(\sigma_ 2\) of the matrix \(\begin{pmatrix} \alpha_1 & \beta_1 \\ \beta_1 & \alpha_2 \end{pmatrix}\) which is closer to \(\alpha_1\). The authors propose choosing \(\sigma_1\) when \(\beta^2_2 \geq 2\beta^2_1\) and \(\sigma_2\) otherwise. With this choice of shift, the authors are able to show in the first place that convergence is guaranteed and in the second place that the convergence is at least cubic if the original matrix is irreducible. The proof is based on calculations which follow traditional lines. The authors include some numerical examples which show that their choice of shift results in total numbers of iterations which do not differ greatly from those of either the Rayleigh quotient or Wilkinson shifts.