Least-Squares Solution of Ill-Conditioned Lyapunov Equations

In this paper we present an algorithm to compute a least-squares solution of ill-conditioned Lyapunov equations. The method uses inverse iteration to compute left and right singular "vectore for the subspace associated with the smallest singular values of the Lyapunov operator. This subspace is assumed to be of small dimension relation to the size of the problem. Once these vectors have been estimated, projections onto any of the four fundamental subspaces of the Lyapunov operator can be computed. Here we project onto the range space and then form a better conditioned problem from which the least-squares solution can be extracted. Because of the structure of the reformulated problem, an iterative solution method is used to refine the least-squares solution. Usually, preconditioning strategies are needed to make iterative solvers for large-scale problems economical. However, the calculation of many of the standard preconditioners entails an unacceptably high overhead. Instead, we show how to calculate a good estimate of the least-squares solution and then use this as a starting vector for a non-preconditioned iterative solver. Numerical examples show that the iterative method usually requires only a small number of steps to achieve acceptable accuracy.