A MULTILEVEL TECHNIQUE FOR THE APPROXIMATE SOLUTION OF OPERATOR LYAPUNOV AND ALGEBRAIC RICCATI-EQUATIONS

We consider multigrid or, more appropriately, multilevel techniques for the numerical solution of operator Lyapunov and algebraic Riccati equations. The Riccati equation, which is quadratic, plays an essential role in the solution of linear-quadratic optimal control problems. The linear Lyapunov equation is important in the stability theory for linear systems and its solution is the primary step in the Newton-Kleinman (NK) algorithm for the solution of algebraic Riccati equations. Both equations are operator equations when the underlying linear system is infinite dimensional. In this case, finite-dimensional discretization is required. However, as the level of discretization increases, the convergence rate of the standard iterative techniques for solving high order matrix Lyapunov and Riccati equations decreases. To deal with this, multileveling is introduced into the iterative NK method for solving the algebraic Riccati equation and Smith's method for solving matrix Lyapunov equations. Theoretical results and analysis indicating why the technique yields a significant improvement in efficiency over existing nonmultigrid techniques are provided, and the results of numerical studies on a test problem involving the optimal linear quadratic control of a one-dimensional heat equation are discussed.