3
$\begingroup$

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)?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Does that mean there is no entry-independent worst case upper bound? $\endgroup$ Commented Aug 13, 2012 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$ Commented Aug 14, 2012 at 7:02
  • $\begingroup$ The link to springerlink.com is broken. I'm not able to find any copy saved on the Wayback Machine either. $\endgroup$
    – user43608
    Commented Jul 25, 2022 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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