Skip to main content
9 of 9
added 138 characters in body
wlad
  • 4.9k
  • 2
  • 21
  • 45

A visualisation of the dynamics of the unshifted QR algorithm for PSD matrices is given here, with a remark as to how shifts help: https://www.youtube.com/watch?v=XGAaHoppcvE

The video is by me.

The argument is given for PSD matrices. For the set of PSD matrices similar to some PSD matrix $M$, there are multiple fixed points of the unshifted QR algorithm. Some of these fixed points are stable, while the others are unstable. The introduction of shifts eliminates the unstable fixed points, leaving behind only the stable fixed points. Unstable fixed points are undesirable because they compromise the speed of the algorithm. The existence of the unstable fixed point is an artifact of the continuousness of the function being iterated in the naive QR algorithm, as the video demonstrates by visualizing the naive LR algorithm as well. Therefore the shift must depend discontinuously on the matrix; but this does not compromise the practicality of employing shifts.

Feel free to leave a comment. Cheers!

[EDIT] Now part of a playlist on the QR algorithm's dynamics: https://www.youtube.com/playlist?list=PLvTRlE0qBBp35rv11Wp3WCWSixUisJqY4

wlad
  • 4.9k
  • 2
  • 21
  • 45