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

We review a family of algorithms for Lyapunov- and Riccati-type equations which are all related to each other by the idea of doubling: they construct the iterate (Formula presented.) of another naturally-arising fixed-point iteration (Xh) via a sort of repeated squaring. The equations we consider are Stein equations X − A∗ X A = Q, Lyapunov equations A∗ X + X A + Q = 0, discrete-time algebraic Riccati equations X = Q + A∗ X(I + G X)−1A, continuous-time algebraic Riccati equations Q + A∗ X + X A − X G X = 0, palindromic quadratic matrix equations A + Q Y + A∗Y2 = 0, and nonlinear matrix equations X + A∗ X−1A = 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.