Return to Answer

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!

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

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 shifts must depend discontinuously on the matrix; but this does not compromise the practicality of employing shifts.

Feel free to leave a comment. Cheers!

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!

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 shifts must depend discontinuously on the matrix; however this does not alter the practicality of the algorithm.

Feel free to leave a comment. Cheers!

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 shifts must depend discontinuously on the matrix; but this does not compromise the practicality of employing shifts.

Feel free to leave a comment. Cheers!