Numerical solution of algebraic Riccati equations. (English) Zbl 1244.65058

Fundamentals of Algorithms 9. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-1-611972-08-5/pbk; 978-1-611972-09-2/ebook). xvi, 250 p. (2012).
The book is concerned with a concise and comprehensive treatment of the basic theory of algebraic Riccati equations (ARE, for short) and a description of both the classical and advanced algorithms for their solution. The authors put a particular emphasis on nonsymmetric ARE and on the equations associated with M-matrices due to their importance in applications in fluid queues, stochastic processes, and transport theory. Moreover, besides the presentation of the general ideas and the analysis tools, the authors provide a detailed description of all the classical and advanced numerical solution algorithms.
The book is organized in 6 chapters, an appendix (containing basic properties of norms and factorizations of matrices, Krylov subspaces, Kronecker product, Householder and Givens transforms, matrix functions and Laurent series) and a bibliography with 286 titles in the field of the book and related topics.
In Chapter 1 the authors introduce the basic definitions concerning ARE and unilateral quadratic matrix equations, giving their properties and some applications. Chapter 2 presents the main theoretical issues related to ARE, according to discrete-time, continuous-time, nonsymmetric equations and equations associated with M-matrices: invariant and deflating subspaces, extremal solutions, critical solutions, unilateral quadratic matrix equations and perturbation results on the solutions of some matrix equations.
In Chapter 3 classical algorithms for solving ARE are described: computing invariant subspaces, Schur method, Newton iteration, methods based on the matrix sign function. Chapter 4 presents specific methods for the Hamiltonian structure of continuous-time problems: the Paige-van Loan form, the URV decomposition, the Hamiltonian QR algorithm, the URV algorithms, the multishift algorithm. In Chapter 5 the authors present the class of doubling algorithms: the structure-preserving doubling algorithm, the QR-based form, the cyclic reduction technique. Chapter 6 reports some ideas on algorithms concerning large-scale problems where the matrix coefficients have some rank structure or are sparse matrices and the solution is well approximated by a low rank matrix.
The book is addressed to researchers who work in the design and analysis of algorithms and wish to improve or to elaborate and adapt the known techniques to specific problems of interest. It can also be used by practitioners who solve problems from real applications and need a simple explanation of the available algorithms, together with explicit software for their solution.


65F30 Other matrix algorithms (MSC2010)
15A24 Matrix equations and identities
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis
Full Text: DOI Link