A new shift of the QL algorithm for irreducible symmetric tridiagonal matrices
type: Item
instance of: scholarly article
title: A new shift of the QL algorithm for irreducible symmetric tridiagonal matrices
zbMATH Open document ID: 0572.65023
DOI: 10.1016/0024-3795(85)90101-6
author: Zhenyue Zhang
author: Erxiong Jiang
published in: Linear Algebra and its Applications
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65F15
zbMATH DE Number: 3913547
zbMATH Keywords: QL algorithm
zbMATH Keywords: tridiagonal matrix
zbMATH Keywords: Rayleigh quotient shift
zbMATH Keywords: Wilkinson's shift
zbMATH Keywords: convergence
zbMATH Keywords: numerical examples
reviewed by: Myron Sussman
MaRDI profile type: Publication
full work available at URL: 0024-3795(85)90101-6
OpenAlex ID: W2027554429
cites work: A new look at the Lanczos algorithm for solving symmetric systems of linear equations
cites work: Q4727282
cites work: Global convergence of tridiagonal QR algorithm with origin shifts
cites work: A New Proof of Global Convergence for the Tridiagonal $QL$ Algorithm
description: scientific article; zbMATH DE number 3913547