Ignoring eigenvectors, the shifted QR algorithm for computing eigenvalues in the symmetric tridiagional case costs $O(n)$ per iteration, converges globally, and converges cubically near the end. What is its worst case complexity (which presumably depends on the desired error)?


With the right shift stategy (mixing RQ and W shift appropriately), it is globally cubically convergent, with a guaranteed linear convergence factor, which makes its complexity of the order of $N$ times the logarithm of the off-diagonal entries. Unfortunately,

See http://www.springerlink.com/content/f1w76x84463l52t7/ for local cubic convergence.

  • $\begingroup$ Does that mean there is no entry-independent worst case upper bound? $\endgroup$ – Geoffrey Irving Aug 13 '12 at 20:18
  • $\begingroup$ Probably no known one. But my knowledge about this is about 10 years old, so you should check more recent literature. $\endgroup$ – Arnold Neumaier Aug 14 '12 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.