Power iterations and the QR algorithm

Reading: Golub & Van Loan §7.3–7.5, pp. 365–394.

By the end of this week you should be able to

• Implement power, inverse, and shifted inverse iteration, and predict their convergence rates.
• Reduce a matrix to Hessenberg form and explain why that is the right preprocessing step.
• Describe the shifted QR iteration and where its cubic convergence comes from.

Algorithms introduced

• Power, inverse, and Rayleigh quotient iteration
• Hessenberg reduction
• The practical shifted QR algorithm

Where this shows up in AI

PageRank is a power iteration on a stochastic matrix. Dominant-eigenvector methods appear throughout graph learning and ranking.

Materials