×

Direct methods and ADI-preconditioned Krylov subspace methods for generalized Lyapunov equations. (English) Zbl 1212.65175

Summary: We consider linear matrix equations where the linear mapping is the sum of a standard Lyapunov operator and a positive operator. These equations play a role in the context of stochastic or bilinear control systems. To solve them efficiently one can fall back on known efficient methods developed for standard Lyapunov equations. In this paper, we describe a direct and an iterative method based on this idea. The direct method is applicable if the generalized Lyapunov operator is a low-rank perturbation of a standard Lyapunov operator; it is related to the Sherman-Morrison-Woodbury formula. The iterative method requires a stability assumption; it uses convergent regular splittings, an alternate direction implicit iteration as preconditioner, and Krylov subspace methods.

MSC:

65F30 Other matrix algorithms (MSC2010)
15A24 Matrix equations and identities
93E25 Computational methods in stochastic control (MSC2010)
65F10 Iterative numerical methods for linear systems
65F08 Preconditioners for iterative methods
65F05 Direct numerical methods for linear systems and matrix inversion
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Khasminskij, Stochastic Stability of Differential Equations (1980)
[2] Kleinman, On the stability of linear stochastic systems, IEEE Transactions on Automatic Control AC-14 pp 429– (1969)
[3] Wonham, On a matrix Riccati equation of stochastic control, SIAM Journal on Control 6 pp 681– (1968) · Zbl 0182.20803
[4] Damm, Rational Matrix Equations in Stochastic Control (2004)
[5] Al-Baiyat SA, Bettayeb M. A new model reduction scheme for k-power bilinear systems. Proceedings of the 32nd Conference on Decision and Control, San Antonio, TX, 1993; 22-27.
[6] Gray WS, Mesko J. Energy functions and algebraic Gramians for bilinear systems. Fourth IFAC Nonlinear Control Systems Design Symposium, Enschede, The Netherlands, 1998; 103-108. Preprint.
[7] Zhang, On H2 model reduction of bilinear systems, Automatica 38 (2) pp 205– (2002)
[8] Bartels, Solution of the matrix equation AX+XB=C: algorithm 432, Communications of the ACM 15 pp 820– (1972) · Zbl 1372.65121
[9] Golub, A Hessenberg-Schur method for the problem AX+XB=C, IEEE Transactions on Automatic Control AC-24 pp 909– (1979)
[10] Epton, Methods for the solution of AXD-BXC=E and its application in the numerical solution of implicit ordinary differential equations, BIT 20 pp 341– (1980) · Zbl 0452.65015
[11] Hammarling, Numerical solution of the stable, non-negative definite Lyapunov equation, IMA Journal of Numerical Analysis 2 pp 303– (1982) · Zbl 0492.65017
[12] Gardiner, Solution of the Sylvester matrix equation AXBT+CXDT=E, ACM Transactions on Mathematical Software 18 pp 223– (1992)
[13] Gardiner, Algorithm 705: a Fortran-77 software package for solving the Sylvester matrix equation AXBT+CXDT=E, ACM Transactions on Mathematical Software 18 pp 232– (1992)
[14] Penzl, Numerical solution of generalized Lyapunov equations, Advances in Computational Mathematics 8 (1-2) pp 33– (1998) · Zbl 0909.65026
[15] Richter, Efficient computation of the solutions to modified Lyapunov equations, SIAM Journal on Matrix Analysis and Applications 14 (2) pp 420– (1993) · Zbl 0773.65031
[16] Collins, Efficient solutions of linearly coupled Lyapunov equations, SIAM Journal on Matrix Analysis and Applications 18 (2) pp 291– (1997) · Zbl 0872.65020
[17] Hochbruck, Preconditioned Krylov subspace methods for Lyapunov matrix equations, SIAM Journal on Matrix Analysis and Applications 16 (1) pp 156– (1995) · Zbl 0827.65048
[18] Horn, Topics in Matrix Analysis (1991) · Zbl 0729.15001 · doi:10.1017/CBO9780511840371
[19] Vetter, Vector structures and solutions of linear matrix equations, Linear Algebra and its Applications 10 pp 181– (1975) · Zbl 0307.15003
[20] Golub, Matrix Computations (1989)
[21] Stewart, Matrix Perturbation Theory (1990) · Zbl 0706.65013
[22] Demmel, Applied Numerical Linear Algebra (1997) · doi:10.1137/1.9781611971446
[23] Schneider, Positive operators and an inertia theorem, Numerische Mathematik 7 pp 11– (1965) · Zbl 0158.28003
[24] Damm, Newton’s method for a rational matrix equation occurring in stochastic control, Linear Algebra and its Applications 332-334 pp 81– (2001)
[25] Berman, Nonnegative Matrices in the Mathematical Sciences (1994) · Zbl 0815.15016 · doi:10.1137/1.9781611971262
[26] Varga, Matrix Iterative Analysis (2000) · Zbl 1216.65042 · doi:10.1007/978-3-642-05156-2
[27] Van der Vorst, The superlinear convergence behaviour of GMRES, Journal of Computational and Applied Mathematics 48 pp 327– (1993) · Zbl 0797.65026
[28] Moret, A note on the superlinear convergence of GMRES, SIAM Journal on Scientific Computing 34 pp 513– (1997) · Zbl 0873.65054
[29] Simoncini, On the occurrence of superlinear convergence of exact and inexact Krylov subspace methods, SIAM Review 47 (2) pp 247– (2005) · Zbl 1079.65034
[30] Trefethen, Numerical Linear Algebra (2000)
[31] Saad, Iterative Methods for Sparse Linear Systems (2003) · Zbl 1031.65046 · doi:10.1137/1.9780898718003
[32] Wachspress, ADI iterative solution of Lyapunov equations, Applied Mathematical Letters 1 pp 87– (1988) · Zbl 0785.65057
[33] Lu, Solution of Lyapunov equations by alternating direction implicit iteration, Computers and Mathematics with Applications 21 (9) pp 43– (1991) · Zbl 0724.65041
[34] Penzl, A cyclic low-rank Smith method for large sparse Lyapunov equations, SIAM Journal on Scientific Computing 21 (4) pp 1401– (2000) · Zbl 0958.65052
[35] Li, Low rank solution of Lyapunov equations, SIAM Journal on Matrix Analysis and Applications 24 (1) pp 260– (2002) · Zbl 1016.65024
[36] Wachspress, Optimum alternating-direction-implicit iteration parameters for a model problem, Journal of the Society for Industrial and Applied Mathematics 10 pp 339– (1962) · Zbl 0111.31401
[37] Wachspress, The ADI Model Problem (1995)
[38] Abramowitz, Handbook of Mathematical Functions (1964)
[39] Saak, Effiziente numerische Lösung eines Optimalsteuerproblems für die Abkühlung von Stahlprofilen (2003)
[40] Penzl, Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case, Systems and Control Letters 40 (2) pp 139– (2000) · Zbl 0977.93034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.