Convergence rates to deflation of simple shift strategies

Details Convergence rates to deflation of simple shift strategies Convergence rates to deflation of simple shift strategies

2009-12-17

arxiv.org/abs/0912.3376v2

Mathematics

Numerical Analysis

19 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Convergence rates to deflation of simple shift strategies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Convergence rates to deflation of simple shift strategies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convergence rates to deflation of simple shift strategies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-685666