Every method so far in this topic finds one eigenvalue/eigenvector pair at a time. This note builds the algorithm that actually underlies essentially every "compute the eigenvalues" call in production numerical software: the QR algorithm, which finds all eigenvalues of a matrix simultaneously by repeatedly applying the factorisation from Topic 2 in a specific, self-reinforcing pattern, converging to a triangular (hence eigenvalue-revealing) matrix.
Learning objectives. By the end of this note you should be able to:
- state the basic QR algorithm and explain why it preserves eigenvalues at every step;
- explain (informally) why the algorithm converges to triangular form;
- state the shifted version and explain why shifts are essential in practice;
- connect the shifted QR algorithm to the inverse-iteration machinery from earlier in the topic.
In this lesson
- The basic algorithm
- Shifted QR: dramatically faster convergence
Before you start
The full lesson, with worked examples and exercise solutions, is for members.
Read the full lessonNew to SelfMadeQuant.com? See membership options or browse the Linear Algebra, Optimisation and Numerical Methods syllabus.