The Numerical Jordan Form

"The Numerical Jordan Form is the first book dedicated to exploring the algorithmic and computational methods for determining the Jordan form of a matrix, as well as addressing the numerical difficulties in finding it. Unlike the "pure" Jordan form, the numerical Jordan form preserves its structure under small perturbations of the matrix elements so that its determination presents a well-posed computational problem. If this structure is well conditioned, it can be determined reliably in the presence of uncertainties and rounding errors. This book addresses the form's application in solving some important problems such as the estimation of eigenvalue sensitivity and computing the matrix exponential. Special attention is paid to the Jordan-Schur form of a matrix which, the author suggests, is not exploited sufficiently in the area of matrix computations. Since the mathematical objects under consideration can be sensitive to changes in the elements of the given matrix, the book also investigates the perturbation analysis of eigenvalues and invariant subspaces. This study is supplemented by a collection over 100 M-files suitable for MATLAB in order to implement the state-of-the art algorithms presented in the book for reducing a square matrix into the numerical Jordan form. Researchers in the fields of numerical analysis and matrix computations and any scientists who utilise matrices in their work will find this book a useful resource, and it is also a suitable reference book for graduate and advance undergraduate courses in this subject area"-- Provided by publisher Contents Preface List of Algorithms Notation 1. Numerical Matrix Computations 1.1 Basic Rounding Error Analysis 1.1.1 Floating Point Numbers 1.1.2 Approximating Real Numbers 1.1.3 Arithmetic Floating Point Operations 1.1.4 Complex Arithmetic 1.1.5 Notes and References 1.2 Error Analysis of Matrix Operations 1.2.1 Scalar Product: Strict Error Bounds 1.2.2 Scalar Product — First-Order Bounds 1.2.3 Operation Count 1.2.4 Matrix-Vector Product 1.2.5 Matrix–Matrix Product 1.2.6 Notes and References 1.3 Conditioning and Numerical Stability 1.3.1 Well-Conditioned and Ill-Conditioned Problems 1.3.2 Backward Error Analysis 1.3.3 Condition Numbers 1.3.4 Sensitivity of a System of Linear Equations 1.3.5 Notes and References 1.4 Solving Triangular Systems of Equations 1.4.1 Forward Substitution 1.4.2 Back Substitution 1.4.3 Error Analysis 1.4.4 Notes and References 1.5 Elementary Transformations and QR Decomposition 1.5.1 Elementary Triangular Matrices 1.5.2 Plane Rotations 1.5.3 Householder Transformations 1.5.4 Computing the QR Decomposition 1.5.5 Error Analysis of the QR Decomposition 1.5.6 Notes and References 1.6 Computing the Rank and Fundamental Subspaces 1.6.1 Numerical Rank of a Matrix 1.6.2 Computing the Fundamental Subspaces 1.6.3 Notes and References 2. The Eigenvalue Problem 2.1 Eigenvalues and Eigenvectors 2.1.1 Basic Definitions 2.1.2 Diagonal Form of a Matrix 2.1.3 Eigenvector Normalization 2.1.4 Eigenspaces 2.1.5 Schur Decomposition 2.1.6 Block-Diagonal Form 2.1.7 Notes and References 2.1.7.1 Eigenvalues and Eigenvectors 2.1.7.2 Schur Form 2.1.7.3 Sylvester Equation 2.2 Jordan and Weyr Canonical Forms 2.2.1 Jordan Structure: A Unique Eigenvector 2.2.2 Jordan Structure: q Eigenvectors 2.2.3 Segre and Weyr Characteristics 2.2.4 Jordan Normal Form 2.2.5 Weyr Canonical Form 2.2.6 Frobenius Canonical Form 2.2.7 Spectral Projections 2.2.8 Angles between Eigenspaces 2.2.9 Notes and References 2.2.9.1 Multiple Eigenvalues 2.2.9.2 Jordan Canonical Form 2.2.9.3 Weyr Canonical Form 2.2.9.4 Frobenius Canonical Form 2.2.9.5 Spectral Decomposition and Angles between Eigenspaces 2.3 The Generalized Eigenvalue Problem 2.3.1 Generalized Eigenvalues and Eigenvectors 2.3.2 Generalized Schur Form 2.3.3 Generalized Block-Diagonal Form 2.3.4 Weierstrass Canonical Form 2.3.5 Kronecker Canonical Form 2.3.6 Notes and References 3. The Eigenvalue Sensitivity Problem 3.1 Measuring Eigenvalue Sensitivity 3.2 Gershgorin Theorem 3.3 Sensitivity of Simple Eigenvalues 3.4 Significance of the Jordan Structure 3.5 Sensitivity of Multiple Eigenvalues 3.6 Sensitivity of Invariant Subspaces 3.7 Componentwise Sensitivity of the Schur Decomposition 3.7.1 Sensitivity of the Unitary Transformation Matrix 3.7.2 Sensitivity of Eigenvalues and Invariant Subspaces 3.7.3 Sensitivity of the Superdiagonal Elements 3.8 Sensitivity of the Generalized Eigenvalue Problem 3.9 Notes and References 3.9.1 Perturbation Theory for Eigenvalues 3.9.2 Gershgorin Theorem 3.9.3 First-Order Perturbation Analysis 3.9.4 Sensitivity of Multiple Eigenvalues 3.9.5 Sensitivity of Invariant Subspaces 3.9.6 Sensitivity of the Schur Decomposition 3.9.7 Sensitivity of the Generalized Eigenvalue Problem 4. Numerical Solution of the Eigenvalue Problem 4.1 Reduction into Schur Form 4.1.1 QR Algorithm with Explicit Shift 4.1.2 Reduction into Hessenberg Form 4.1.3 QR Algorithm for Hessenberg Matrices 4.1.4 Accuracy of the Computed Eigenvalues 4.1.5 Accuracy of the Computed Invariant Subspaces 4.1.6 Notes and References 4.1.6.1 Hessenberg Form 4.1.6.2 QR Algorithm 4.2 Numerical Solution of the Sylvester Equation 4.2.1 Sensitivity and Conditioning 4.2.2 Solution Methods 4.2.3 Bartels–Stewart Algorithm 4.2.4 Backward Error Estimate 4.2.5 Forward Error Estimate 4.2.6 Notes and References 4.3 Computing Perturbation Bounds of Eigenspaces 4.3.1 Computing Spectral Projections 4.3.2 Computing Bounds of Eigenspaces 4.3.3 Notes and References 4.4 Reduction into Generalized Schur Form 4.4.1 QZ Algorithm 4.4.2 Reduction into GUPTRI Form 4.4.3 Notes and References 4.4.3.1 Reduction into Generalized Schur Form 4.4.3.2 GUPTRI Form 5. Geometry of Jordan Forms 5.1 Geometry of Matrix Space 5.1.1 Orbits and Bundles of Matrices 5.1.2 Determining the Orbit and Bundle Codimension 5.1.2.1 Centralizer Codimension 5.1.2.2 Solution of the Matrix Equation AX = XA (Gantmacher, 1959a, Chapter VIII) 5.1.3 Generic and Nongeneric Bundles 5.2 Stratification of Jordan Bundles 5.2.1 Matrix Stratification 5.2.2 Stratification Rules 5.3 Normal Forms of Matrices Depending on Parameters 5.3.1 Matrix Deformations 5.3.2 The Construction of Versal Deformations 5.3.3 Selection of the Normal Form 5.3.4 Examples 5.4 Bifurcation Diagrams 5.4.1 One-Parameter Matrix Families 5.4.2 Two-Parameter Matrix Families 5.4.3 Three-Parameter Matrix Families 5.4.3.1 The Case αα 5.4.3.2 The Case α3β2 5.4.3.3 The Case α4 5.4.3.4 Case α2β2γ2 5.5 Reduction into Jordan Form as an Ill-Posed Problem 5.6 The Numerical Jordan Form: Rigorous Definition 5.7 Numerical Structure of a Matrix 5.8 Notes and References 5.8.1 Geometry of Matrix Space 5.8.2 Structural Stability and Genericity 5.8.3 Stratification of Jordan Bundles 5.8.4 Bifurcation 5.8.5 Well-Posed and Ill-Posed Problems 5.8.6 Finding the Jordan Form as a Regularization Problem 5.8.7 Geometry of Matrix Pencils 6. Reduction into Jordan–Schur Form 6.1 Algorithms for Reduction into Jordan Form 6.1.1 Algorithm of Kublanovskaya–Ruhe–Kågström 6.1.2 Algorithm Using the Chain Relations 6.1.3 Algorithm Based on the Generalized Eigenvalue Problem 6.1.4 Algorithm of Zeng and Li 6.1.5 Symbolic Computation 6.2 The Jordan–Schur Form 6.3 Reduction into Ordered Schur Form 6.4 Clustering of Multiple Eigenvalues 6.5 Reduction into Staircase Form 6.5.1 First Step 6.5.2 Next Steps 6.5.3 Strategy for Choosing a Bundle 6.6 Reduction into Jordan–Schur Form 6.7 Numerical Issues 6.7.1 Operation Count 6.7.2 Well-Conditioned Numerical Structures 6.7.3 Ill-Conditioned Numerical Structures 6.7.4 Stratification of the Jordan–Schur Forms 6.7.5 Choice of Appropriate Tolerances 6.8 Notes and References 7. Reduction into Weyr and Jordan Forms 7.1 Block-Diagonalization 7.2 Orthonormalization 7.3 Reduction into Block-Diagonal Staircase Form 7.4 Reduction into Numerical Weyr Form 7.4.1 A Simple Example 7.4.2 The Case of n-Tuple Eigenvalue 7.5 Reduction into Numerical Jordan Form 7.5.1 Transforming the Weyr Form into Jordan Form 7.5.2 The Full Algorithm 7.5.3 Numerical Examples 7.6 Numerical Issues 7.6.1 Operation Count 7.6.2 Well-Conditioned Numerical Structures 7.6.3 Ill-Conditioned Numerical Structures 7.6.4 Stratification of Jordan Forms 7.6.5 Choice of Appropriate Tolerances 7.7 Notes and References 8. Case Study 1: Eigenvalue Sensitivity Analysis 8.1 Block-Diagonal Form Method 8.2 Numerical Jordan Form Method 8.3 Notes and References 9. Case Study 2: Computing the Matrix Exponential 9.1 Definition and Basic Properties 9.2 Sensitivity of the Matrix Exponential 9.3 Series Methods 9.3.1 Taylor Series 9.3.2 Padé Approximations 9.4 Decomposition Methods 9.4.1 Diagonalization and Block-Diagonalization 9.4.2 Jordan Decomposition 9.4.3 Schur–Parlett Method 9.4.4 Schur–Fréchet Method 9.6 Block-Diagonal Staircase Form Method 9.7 Jordan–Schur Methods 9.7.1 Schur–Parlett Method 9.7.2 Schur–Fréchet Method 9.7.3 Numerical Properties of Jordan and Jordan–Schur Algorithms 9.8 Notes and References Appendix: Review of Linear Algebra and Matrix Analysis A.1 Vectors and Matrices A.2 Linear Subspaces A.3 Linear Transformations and Matrices A.3.1 Linear Transformations A.3.2 Matrix of the Linear Transformation A.3.3 Operations on Linear Transformations A.3.4 Change of Basis A.4 Vector Norms A.5 Orthogonality A.6 Singular Value Decomposition A.7 Matrix Norms A.7.1 Definition and Properties A.7.2 Unitary Equivalent Norms A.7.3 Relationships between Matrix Norms A.8 Computations with Subspaces A.9 Projections, Distances and Angles A.9.1 Projections A.9.2 Distances between Vectors and Subspaces A.9.3 Angles between Vectors and Subspaces A.10 Notes and References Bibliography Index