Abstract
In this lecture we will discuss three main classes of Krylov and QR type methods: the classical, the extended, and the rational versions. We will initially focus on the classical QR method and reintepret all ingredients such as: associated Krylov spaces, associated Hessenberg matrices, implicit theorems, bulge chasing, eigenvalue swapping, and subspace iteration. Another look at these essentials will allow us to straightforwardly generalize all of this to the extended and rational case. More precisely, we will start by deducing the structure of the recurrence pencil associated to all Krylov methods. It will be shown that the rational Krylov method produces the most general pencil, namely two Hessenberg matrices, which implicitly store the poles of the rational Krylov method. We will revisit the implicit Q-Theorem and link it to its dual theorem, the implicit HK-Theorem, allowing us to provide a pole chasing algorithm for two Hessenberg matrices. This generalizes the classical and extended QR algorithms. Correctness will follow directly from the previous analysis of the classical QR algorithm. The rational QR algorithm allows for additional freedom, which is the introduction of poles. Even without a good pole-strategy we will see that the iteration count reduces with almost 10 procent.