Iterative and doubling algorithms for Riccati-type matrix equations: a comparative introduction

Abstract

We review a family of algorithms for Lyapunov- and Riccati-type equations which are all related to each other by the idea of \emph{doubling}: they construct the iterate $Q_k=X_{2^k}$ of another naturally-arising fixed-point iteration $(X_h)$ via a sort of repeated squaring. The equations we consider are Stein equations $X-A^{\ast }XA=Q$, Lyapunov equations $A^{\ast }X+XA+Q=0$, discrete-time algebraic Riccati equations $X=Q+A^{\ast }X(I+GX{)}^{-1}A$, continuous-time algebraic Riccati equations $Q+A^{\ast }X+XA-XGX=0$, palindromic quadratic matrix equations $A+QY+A^{\ast }{Y}^2=0$, and nonlinear matrix equations $X+A^{\ast }{X}^{-1}A=Q$. We draw comparisons among these algorithms, highlight the connections between them and to other algorithms such as subspace iteration, and discuss open issues in their theory.

Review article for GAMM Mitteilungen