Convergence rates to deflation of simple shift strategies. (arXiv:0912.3376v1 [math.NA])

The computation of eigenvalues of real symmetric tridiagonal matrices
frequently proceeds by a sequence of QR steps with shifts. We introduce simple
shift strategies, functions sigma satisfying natural conditions, taking each n
x n matrix T to a real number sigma(T). The strategy specifies the shift to be
applied by the QR step at T. Rayleigh and Wilkinson's are examples of simple
shift strategies. We show that if sigma is continuous then there exist initial
conditions for which deflation does not occur, i.e., subdiagonal entries do not
tend to zero. In case of deflation, we consider the rate of convergence to zero
of the (n, n-1) entry: for simple shift strategies this is always at least
quadratic. If the function sigma is smooth in a suitable region and the
spectrum of T does not include three consecutive eigenvalues in arithmetic
progression then convergence is cubic. This implies cubic convergence to
deflation of Wilkinson's shift for generic spectra. The study of the algorithm
near deflation uses tubular coordinates, under which QR steps with shifts are
given by a simple formula.

Published by

Original source : http://arxiv.org/abs/0912.3376...