THEORY OF EQUATIONS
1 Introduction and preliminaries 1 11 Matrix equations 2 12 Algebraic Riccati equations 3 121 Nonsymmetric equations 3 122 Equations associated with M-matrices 3 123 Continuous-time equations 5 124 Discrete-time equations 6 13 Unilateral quadratic matrix equations 8 14 Useful concepts and definitions 9 141 Invariant and deflating subspaces 9 142 Some definitions from control theory 11 143 Matrix polynomials 12 144 Eigenvalue transformations 14 145 Splitting properties 20 15 Hamiltonian and symplectic matrices 22 16 Algorithmic issues 26 161 Convergence speed 26 162 Cost of elementary matrix operations 28 163 Conditioning and numerical stability 29 17 Available software 30 18 Additional notes and further reading 31 2 Theoretical analysis 33 21 Invariant subspaces and algebraic Riccati equations 33 211 Nonsymmetric equations 33 212 Equations associated with M-matrices 37 213 Continuous-time equations 39 214 Discrete-time equations 40 22 Extremal solutions 41 221 Equations associated with M-matrices 42 222 Continuous-time equations 46 223 Discrete-time equations 49 23 Critical solutions 50 24 Shift techniques 52 241 Equations associated with M-matrices 54 242 Continuous-time equations 57 25 Transformations between discrete- and continuous-time 61 26 Unilateral quadraticmatrix equations 62 27 Transforming an algebraic Riccati equation to a UQME 67 271 Simple transformation 68 272 UL-based transformation 70 273 Reduction to a UQME of lower size 73 28 Perturbation results 75 281 Algebraic Riccati equations 76 282 UQMEs 80 29 Additional notes and further reading 81 3 Classical algorithms 83 31 Linearmatrix equations 83 311 Sylvester, Lyapunov, and Stein equations 83 312 Generalized equations 87 32 Invariant subspacesmethods 87 321 Balancing technique 92 33 Newton’s method 92 331 Continuous-time equations 93 332 Equations associated with M-matrices 98 333 Other algebraic Riccati equations 101 334 Iterative refinement and defect correction 102 34 Functional iterations 103 35 Matrix sign function method 105 351 Continuous-time equations 105 352 Computing the matrix sign function 107 353 Other algebraic Riccati equations 109 36 Numerical experiments 111 361 Continuous-time equations 111 362 Equations associated with M-matrices 114 37 Additional notes and further reading 118 4 Structured invariant subspace methods 121 41 Elementarymatrices 122 42 Hamiltonian condensed and special forms 125 421 The PVL form 126 422 URV Decomposition 128 423 Other condensed forms 131 43 Hamiltonian QR algorithm 131 431 The Hamiltonian/symplectic QR step 133 44 Computation of the eigenvalues of a Hamiltonian matrix 135 45 The URV algorithms 136 46 The multishift algorithm 140 47 Additional notes and further reading 142 5 Doubling algorithms 145 51 Structured doubling algorithm 146 511 SDA–I 147 512 SDA–II 151 513 QR-based doubling algorithm 153 52 Cyclic reduction 155 521 Convergence properties 158 522 Applicability 161 523 Interplay with SDAs 167 53 Solving algebraic Riccati equations 168 531 Equations associated with M-matrices 168 532 Continuous-time equations 179 533 Discrete-time equations 184 54 Acceleration techniques 188 55 Numerical experiments 190 551 Continuous-time equations 190 552 Equations associated with M-matrices 191 56 Additional notes and further reading 192 6 Algorithms for large-scale problems 195 61 Linear matrix equations with large and sparse coefficients 196 611 The ADI iteration 196 612 Cholesky factor ADI 198 613 Krylov subspacemethods 201 62 Continuous- and discrete-time Riccati equations 204 63 Additional notes and further reading 206