Large-scale discrete-time algebraic Riccati equations— Doubling algorithm and error analysis

We consider the numerical solution of large-scale discrete-time algebraic Riccati equations. The doubling algorithm is adapted, with the iterates for AA not computed explicitly but recursively. The resulting algorithm is efficient, with computational complexity and memory requirement proportional to the size of the problem, and essentially converges quadratically. An error analysis, on the truncation of iterates, and some numerical results are presented.