Numerical Methods for Eigenvalue Problems Lecture Notes

(I) . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.5 QR-decomposition and applications . . . . . . . . . . . . . . . . . . . . . . . . 141.5.1 Orthogonal transformations . . . . . . . . . . . . . . . . . . . . . . . . 141.5.2 QR-decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.5.3 Example: Gram-Schmidt process for two vectors . . . . . . . . . . . . 161.5.4 Application: direct solution of linear systems . . . . . . . . . . . . . . 171.5.5 Application: solving least-squares problems . . . . . . . . . . . . . . . 171.6 Canonical forms of matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.6.1 The Schur decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 181.6.2 Normal and diagonalizable matrices . . . . . . . . . . . . . . . . . . . 191.6.3 The Singular Value Decomposition . . . . . . . . . . . . . . . . . . . . 202 The Eigenproblem 232.1 Perturbation theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.1.1 Motivation to study perturbation theory . . . . . . . . . . . . . . . . . 242.1.2 Classical perturbation bounds . . . . . . . . . . . . . . . . . . . . . . . 252.2 Pseudo-eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.2.1 Pseudo-eigenvalues and elementary properties . . . . . . . . . . . . . . 263 Small Eigenproblems 293.1 The QR-iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.1.1 QR-factorization of an upper Hessenberg matrix . . . . . . . . . . . . 293.1.2 The basic QR-iteration . . . . . . . . . . . . . . . . . . . . . . . . . . 303.1.3 Computational considerations . . . . . . . . . . . . . . . . . . . . . . . 313.2 The Power iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.2.1 The QR-iteration with shifts . . . . . . . . . . . . . . . . . . . . . . . 343.2.2 Real Schur Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 353