A preconditioned block Arnoldi method for large scale Lyapunov and algebraic Riccati equations. (English) Zbl 1339.49024
Summary: In the present paper, we propose a preconditioned Newton-block Arnoldi method for solving large continuous time algebraic Riccati equations. Such equations appear in control theory, model reduction, and circuit simulation amongst other problems. At each step of the Newton process, we solve a large Lyapunov matrix equation with a low rank right hand side. These equations are solved by using the block Arnoldi process associated with a preconditioner based on the alternating direction implicit iteration method. We give some theoretical results and report numerical tests to show the effectiveness of the proposed approach.
MSC:
| 49M15 | Newton-type methods |
| 65F30 | Other matrix algorithms (MSC2010) |
| 15A24 | Matrix equations and identities |
Keywords:
Newton-block-Arnoldi method; algebraic Riccati equations; Lyapunov equations; block-Krylov subspaces; low-rank approximations; Stein equationReferences:
| [1] | Anderson, B.D.O., Moore, J.B.: Linear Optimal Control. Prentice-Hall, Englewood Cliffs, NJ (1971) · Zbl 0321.49001 |
| [2] | Arnold III, W.F., Laub, A.J.: Generalized eigenproblem algorithms and software for algebraic Riccati equations. Proc. IEEE 72, 1746-1754 (1984) · doi:10.1109/PROC.1984.13083 |
| [3] | Bartels, R.H., Stewart, G.W.: Algorithm 432: solution of the matrix equation AX + XB \[== C\]. Circ. Syst. Signal Proc. 13, 820-826 (1994) · Zbl 1372.65121 |
| [4] | Bouhamidi, A., Hached, M., Heyouni, M., Jbilou, K.: A preconditioned block Arnoldi method for large Sylvester matrix equations. Numer. Linear Algebra Appl. 236(6), 1531-1542 (2011) · Zbl 1289.65099 |
| [5] | Datta, B.N.: Numerical Methods for Linear Control Systems. Elsevier, Amsterdam (2004) · Zbl 1079.65072 |
| [6] | Druskin, V., Simoncini, V.: Adaptive rational Krylov subspaces for large-scale dynamical systems. Syst. Control Lett. 60, 546-560 (2011) · Zbl 1236.93035 · doi:10.1016/j.sysconle.2011.04.013 |
| [7] | Druskin, V., Knizhnerman, L., Simoncini, V.: Analysis of the rational Krylov subspace and ADI methods for solving the Lyapunov equation. SIAM J. Numer. Anal. 49, 1875-1898 (2011) · Zbl 1244.65060 · doi:10.1137/100813257 |
| [8] | Feitzinger, F., Hylla, T., Sachs, E.W.: It inexact Kleinman-Newton method for Riccati equations. SIAM J. Matrix Anal. Appl. 31, 272-288 (2009) · Zbl 1191.49033 · doi:10.1137/070700978 |
| [9] | Heyouni, M., Jbilou, K.: An extended block Arnoldi algorithm for large-scale solutions of the continuous-time algebraic Riccati equation. Elect. Trans. Numer. Anal. 33, 53-62 (2009) · Zbl 1171.65035 |
| [10] | Jaimoukha, I.M., Kasenally, E.M.: Krylov subspace methods for solving large Lyapunov equations. SIAM J. Matrix Anal. Appl. 31(1), 227-251 (1994) · Zbl 0798.65060 |
| [11] | Jbilou, K.: Block Krylov subspace methods for large continuous-time algebraic Riccati equations. Numer. Algorithms 34, 339-353 (2003) · Zbl 1045.65036 · doi:10.1023/B:NUMA.0000005349.18793.28 |
| [12] | Jbilou, K.: An Arnoldi based algorithm for large algebraic Riccati equations. Appl. Math. Lett. 19, 437-444 (2006) · Zbl 1094.65038 · doi:10.1016/j.aml.2005.07.001 |
| [13] | Jbilou, K., Riquet, A.J.: Projection methods for large Lyapunov matrix equations. Linear Algebra Appl. 415(2), 344-358 (2006) · Zbl 1094.65039 · doi:10.1016/j.laa.2004.11.004 |
| [14] | Jbilou, K.: ADI preconditioned Krylov methods for large Lyapunov matrix equations. Linear Algebra Appl. 432, 2473-2485 (2010) · Zbl 1189.65078 · doi:10.1016/j.laa.2009.12.025 |
| [15] | Kelly, C.: Iterative Methods for Linear and Nonlinear Equations. SIAM, Philadelphia (1995) · Zbl 0832.65046 · doi:10.1137/1.9781611970944 |
| [16] | Kleinman, D.L.: On an iterative technique for Riccati equation computations. IEEC Trans. Autom. Control 13, 114-115 (1968) · doi:10.1109/TAC.1968.1098829 |
| [17] | Lancaster, P., Rodman, L.: The Algebraic Riccati Equations. Clarendon Press, Oxford (1995) · Zbl 0836.15005 |
| [18] | Laub, A.J.: A Schur method for solving algebraic Riccati equations. IEEE Trans. Autom. Control AC 24, 913-921 (1979) · Zbl 0424.65013 · doi:10.1109/TAC.1979.1102178 |
| [19] | Li, J.-R., White, J.: Low-rank solutions of Lyapunov equations. SIAM J. Matrix Anal. Appl. 24(1), 60-280 (2002) · Zbl 1016.65024 |
| [20] | Lu, A., Wachspress, E.L.: Solution of Lyapunov equations by alternating direction implicit iteration. Comput. Math. Appl. 21, 43-58 (1991) · Zbl 0724.65041 · doi:10.1016/0898-1221(91)90124-M |
| [21] | Mehrmann, V.: The autonomous linear quadratic control problem, theory and numerical solution. In: Number in Lecture Notes in Control and Information Sciences. Springer, Heidelberg (1991) · Zbl 0746.93001 |
| [22] | Peaceman, D., Rachford, H.: The numerical solution of elliptic and parabolic differential equations. J. Soc. Ind. Appl. Math. 3, 28-41 (1955) · Zbl 0067.35801 · doi:10.1137/0103003 |
| [23] | Penzl, T.: A cyclic low-rank Smith method for large Lyapunov equations. SIAM J. Sci. Comput. 21(4), 1401-1418 (2000) · Zbl 0958.65052 · doi:10.1137/S1064827598347666 |
| [24] | Penzl, T.: LYAPACK A MATLAB toolbox for Large Lyapunov and Riccati Equations, Model Reduction Problems, and Linear-quadratic Optimal Control Problems. http://www.tu-chemintz.de/sfb393/lyapack · Zbl 1372.65121 |
| [25] | Ruhe, A.: Rational Krylov sequence methods for eigenvalue computations. Linear Algebra Appl. 58, 391-405 (1984) · Zbl 0554.65025 · doi:10.1016/0024-3795(84)90221-0 |
| [26] | Saad, Y.; Kaashoek, MA (ed.); Shuppen, JH (ed.); Ran, AC (ed.), Numerical solution of large Lyapunov equations, 503-511 (1990), Boston · Zbl 0719.65034 |
| [27] | Simoncini, V.: A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J. Sci. Comput. 29, 1268-1288 (2007) · Zbl 1146.65038 · doi:10.1137/06066120X |
| [28] | Van Dooren, P.: Gramian based model reduction of large-scale dynamical systems. In: Numerical Analysis, pp. 231-247, Chapman and Hall/CRC Press, London (2000) · Zbl 0952.65051 |
| [29] | Wachspress, E.L.: Iterative solution of the Lyapunov matrix equation. Appl. Math. Lett. 1, 87-90 (1988) · Zbl 0631.65037 · doi:10.1016/0893-9659(88)90183-8 |
| [30] | Wonham, W.M.: On a matrix Riccati equation of Stochastic control. SIAM J. Control 6, 681-697 (1968) · Zbl 0182.20803 · doi:10.1137/0306044 |
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.
