Calculus approach to matrix eigenvalue algorithms
Contents
1 Introduction 5
2 Jacobi-type Algorithms and Cyclic Coordinate Descent 8
2.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.1 Jacobi and Cyclic Coordinate Descent . . . . . . . . . 9
2.1.2 Block Jacobi and Grouped Variable Cyclic Coordinate
Descent . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3 Applications and Examples for 1-dimensional Optimization
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.4 Applications and Examples for Block Jacobi . . . . . . 22
2.2 Local Convergence Analysis . . . . . . . . . . . . . . . . . . . 23
2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3 Re¯ning Estimates of Invariant Subspaces 32
3.1 Lower Unipotent Block Triangular Transformations . . . . . . 33
3.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.1 Main Ideas . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.2 Formulation of the Algorithm . . . . . . . . . . . . . . 40
3.2.3 Local Convergence Analysis . . . . . . . . . . . . . . . 44
3.2.4 Further Insight to Orderings . . . . . . . . . . . . . . . 48
3.3 Orthogonal Transformations . . . . . . . . . . . . . . . . . . . 52
3.3.1 The Algorithm . . . . . . . . . . . . . . . . . . . . . . 57
3.3.2 Local Convergence Analysis . . . . . . . . . . . . . . . 59
3.3.3 Discussion and Outlook . . . . . . . . . . . . . . . . . 62
4 Rayleigh Quotient Iteration, QR-Algorithm, and Some Generalizations
63
4.1 Local Cubic Convergence of RQI . . . . . . . . . . . . . . . . 64
CONTENTS 4
4.2 Parallel Rayleigh Quotient Iteration or Matrix-valued Shifted
QR-Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2.1 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3 Local Convergence Properties of the Shifted QR-Algorithm . . 73