# American Institute of Mathematical Sciences

2013, 3(3): 491-518. doi: 10.3934/naco.2013.3.491

## Deflating irreducible singular M-matrix algebraic Riccati equations

 1 School of Mathematical Sciences, Ocean University of China, Qingdao, 266100, China 2 Department of Mathematics, University of Texas at Arlington, P.O. Box 19408, Arlington, TX 76019, United States, United States

Received  April 2012 Revised  December 2012 Published  July 2013

A deflation technique is presented for an irreducible singular $M$-matrix Algebraic Riccati Equation (MARE). The technique improves the rate of convergence of a doubling algorithm, especially for an MARE in the critical case for which without deflation the doubling algorithm converges linearly and with deflation it converges quadratically. The deflation also improves the conditioning of the MARE in the critical case and thus enables its minimal nonnegative solution to be computed more accurately.
Citation: Wei-guo Wang, Wei-chao Wang, Ren-cang Li. Deflating irreducible singular M-matrix algebraic Riccati equations. Numerical Algebra, Control and Optimization, 2013, 3 (3) : 491-518. doi: 10.3934/naco.2013.3.491
##### References:
 [1] B. D. O. Anderson, Second-order convergent algorithms for the steady-state Riccati equation, Internat. J. Control, 28 (1978), 295-306. doi: 10.1080/00207177808922455. [2] N. G. Bean, M. M. O'Reilly and P. G. Taylor, Algorithms for return probabilities for stochastic fluid flows, Stoch. Models, 21 (2005), 149-184. doi: 10.1081/STM-200046511. [3] A. Berman and R. J. Plemmons, "Nonnegative Matrices in the Mathematical Sciences," SIAM, Philadelphia, 1994. ( This SIAM edition is a corrected reproduction of the work first published in 1979 by Academic Press, San Diego, CA.) [4] D. A. Bini, B. Meini and F. Poloni, Transforming algebraic Riccati equations into unilateral quadratic matrix equations, Numer. Math., 116 (2010), 553-578. doi: 10.1007/s00211-010-0319-2. [5] C.-Y. Chiang, E. K.-W. Chu, C.-H. Guo, T.-M. Huang, W.-W. Lin and S.-F. Xu, Convergence analysis of the doubling algorithm for several nonlinear matrix equations in the critical case, SIAM J. Matrix Anal. Appl., 31 (2009), 227-247. doi: 10.1137/080717304. [6] E. K.-W. Chu, H.-Y. Fan and W.-W. Lin, A structure-preserving doubling algorithm for continuous-time algebraic Riccati equations, Linear Algebra Appl., 396 (2005), 55-80. doi: 10.1016/j.laa.2004.10.010. [7] E. K. W. Chu, H.-Y. Fan, W. W. Lin and C. S. Wang, Structure-preserving algorithms for periodic discrete-time algebraic Riccati equations., Internat. J. Control, 77 (2004), 767-788. doi: 10.1080/00207170410001714988. [8] J. Demmel, "Applied Numerical Linear Algebra," SIAM, Philadelphia, PA, 1997. doi: 10.1137/1.9781611971446. [9] M. Fiedler, "Special Matrices and Their Applications in Numerical Mathematics," Dover Publications, Inc., Mineola, New York, 2nd ed., 2008. [10] C.-H. Guo, Nonsymmetric algebraic Riccati equations and Wiener-Hopf factorization for M-matrices, SIAM J. Matrix Anal. Appl., 23 (2001), 225-242. doi: 10.1137/S0895479800375680. [11] C.-H. Guo, A new class of nonsymmetric algebraic Riccati equations, Linear Algebra Appl., 426 (2007), 636-649. doi: 10.1016/j.laa.2007.05.044. [12] C.-H. Guo and N. Higham, Iterative solution of a nonsymmetric algebraic Riccati equation, SIAM J. Matrix Anal. Appl., 29 (2007), 396-412. doi: 10.1137/050647669. [13] C.-H. Guo, B. Iannazzo and B. Meini, On the doubling algorithm for a (shifted) nonsymmetric algebraic Riccati equation, SIAM J. Matrix Anal. Appl., 29 (2007), 1083-1100. doi: 10.1137/060660837. [14] C.-H. Guo and A. J. Laub, On the iterative solution of a class of nonsymmetric algebraic Riccati equations, SIAM J. Matrix Anal. Appl., 22 (2000), 376-391. doi: 10.1137/S089547989834980X. [15] X. Guo, W. Lin and S. Xu, A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation, Numer. Math., 103 (2006), 393-412. doi: 10.1007/s00211-005-0673-7. [16] J. Juang, Existence of algebraic matrix Riccati equations arising in transport theory, Linear Algebra Appl., 230 (1995), 89-100. doi: 10.1016/0024-3795(93)00366-8. [17] J. Juang and W.-W. Lin, Nonsymmetric algebraic Riccati equations and Hamiltonian-like matrices, SIAM J. Matrix Anal. Appl., 20 (1998), 228-243. doi: 10.1137/S0895479897318253. [18] P. Lancaster and L. Rodman, "Algebraic Riccati Equations," Oxford University Press, New York, USA, 1995. [19] V. Ramaswami, Matrix analytic methods for stochastic fluid flows, Proceedings of the 16th International Teletraffic Congress, Edinburg, 1999, Elsevier Science, 19-30. [20] L. Rogers, Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains, Ann. Appl. Probab., 4 (1994), 390-413. doi: 10.1214/aoap/1177005065. [21] W.-G. Wang, W.-C. Wang and R.-C. Li, Deflating irreducible singular M-matrix algebraic riccati equations, Technical Report 2011-20, Department of Mathematics, University of Texas at Arlington, September 2011. [22] W.-G. Wang, W.-C. Wang and R.-C. Li, Alternating-directional doubling algorithm for M-matrix algebraic Riccati equations, SIAM J. Matrix Anal. Appl., 33 (2012), 170-194. doi: 10.1137/110835463. [23] J. Xue, S. Xu and R.-C. Li, Accurate solutions of M-matrix algebraic Riccati equations, Numer. Math., 120 (2012), 671-700. doi: 10.1007/s00211-011-0421-0. [24] J. Xue, S. Xu and R.-C. Li, Accurate solutions of M-matrix Sylvester equations, Numer. Math., 120 (2012), 639-670. doi: 10.1007/s00211-011-0420-1.

show all references

##### References:
 [1] B. D. O. Anderson, Second-order convergent algorithms for the steady-state Riccati equation, Internat. J. Control, 28 (1978), 295-306. doi: 10.1080/00207177808922455. [2] N. G. Bean, M. M. O'Reilly and P. G. Taylor, Algorithms for return probabilities for stochastic fluid flows, Stoch. Models, 21 (2005), 149-184. doi: 10.1081/STM-200046511. [3] A. Berman and R. J. Plemmons, "Nonnegative Matrices in the Mathematical Sciences," SIAM, Philadelphia, 1994. ( This SIAM edition is a corrected reproduction of the work first published in 1979 by Academic Press, San Diego, CA.) [4] D. A. Bini, B. Meini and F. Poloni, Transforming algebraic Riccati equations into unilateral quadratic matrix equations, Numer. Math., 116 (2010), 553-578. doi: 10.1007/s00211-010-0319-2. [5] C.-Y. Chiang, E. K.-W. Chu, C.-H. Guo, T.-M. Huang, W.-W. Lin and S.-F. Xu, Convergence analysis of the doubling algorithm for several nonlinear matrix equations in the critical case, SIAM J. Matrix Anal. Appl., 31 (2009), 227-247. doi: 10.1137/080717304. [6] E. K.-W. Chu, H.-Y. Fan and W.-W. Lin, A structure-preserving doubling algorithm for continuous-time algebraic Riccati equations, Linear Algebra Appl., 396 (2005), 55-80. doi: 10.1016/j.laa.2004.10.010. [7] E. K. W. Chu, H.-Y. Fan, W. W. Lin and C. S. Wang, Structure-preserving algorithms for periodic discrete-time algebraic Riccati equations., Internat. J. Control, 77 (2004), 767-788. doi: 10.1080/00207170410001714988. [8] J. Demmel, "Applied Numerical Linear Algebra," SIAM, Philadelphia, PA, 1997. doi: 10.1137/1.9781611971446. [9] M. Fiedler, "Special Matrices and Their Applications in Numerical Mathematics," Dover Publications, Inc., Mineola, New York, 2nd ed., 2008. [10] C.-H. Guo, Nonsymmetric algebraic Riccati equations and Wiener-Hopf factorization for M-matrices, SIAM J. Matrix Anal. Appl., 23 (2001), 225-242. doi: 10.1137/S0895479800375680. [11] C.-H. Guo, A new class of nonsymmetric algebraic Riccati equations, Linear Algebra Appl., 426 (2007), 636-649. doi: 10.1016/j.laa.2007.05.044. [12] C.-H. Guo and N. Higham, Iterative solution of a nonsymmetric algebraic Riccati equation, SIAM J. Matrix Anal. Appl., 29 (2007), 396-412. doi: 10.1137/050647669. [13] C.-H. Guo, B. Iannazzo and B. Meini, On the doubling algorithm for a (shifted) nonsymmetric algebraic Riccati equation, SIAM J. Matrix Anal. Appl., 29 (2007), 1083-1100. doi: 10.1137/060660837. [14] C.-H. Guo and A. J. Laub, On the iterative solution of a class of nonsymmetric algebraic Riccati equations, SIAM J. Matrix Anal. Appl., 22 (2000), 376-391. doi: 10.1137/S089547989834980X. [15] X. Guo, W. Lin and S. Xu, A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation, Numer. Math., 103 (2006), 393-412. doi: 10.1007/s00211-005-0673-7. [16] J. Juang, Existence of algebraic matrix Riccati equations arising in transport theory, Linear Algebra Appl., 230 (1995), 89-100. doi: 10.1016/0024-3795(93)00366-8. [17] J. Juang and W.-W. Lin, Nonsymmetric algebraic Riccati equations and Hamiltonian-like matrices, SIAM J. Matrix Anal. Appl., 20 (1998), 228-243. doi: 10.1137/S0895479897318253. [18] P. Lancaster and L. Rodman, "Algebraic Riccati Equations," Oxford University Press, New York, USA, 1995. [19] V. Ramaswami, Matrix analytic methods for stochastic fluid flows, Proceedings of the 16th International Teletraffic Congress, Edinburg, 1999, Elsevier Science, 19-30. [20] L. Rogers, Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains, Ann. Appl. Probab., 4 (1994), 390-413. doi: 10.1214/aoap/1177005065. [21] W.-G. Wang, W.-C. Wang and R.-C. Li, Deflating irreducible singular M-matrix algebraic riccati equations, Technical Report 2011-20, Department of Mathematics, University of Texas at Arlington, September 2011. [22] W.-G. Wang, W.-C. Wang and R.-C. Li, Alternating-directional doubling algorithm for M-matrix algebraic Riccati equations, SIAM J. Matrix Anal. Appl., 33 (2012), 170-194. doi: 10.1137/110835463. [23] J. Xue, S. Xu and R.-C. Li, Accurate solutions of M-matrix algebraic Riccati equations, Numer. Math., 120 (2012), 671-700. doi: 10.1007/s00211-011-0421-0. [24] J. Xue, S. Xu and R.-C. Li, Accurate solutions of M-matrix Sylvester equations, Numer. Math., 120 (2012), 639-670. doi: 10.1007/s00211-011-0420-1.
 [1] Dequan Yue, Wuyi Yue. Block-partitioning matrix solution of M/M/R/N queueing system with balking, reneging and server breakdowns. Journal of Industrial and Management Optimization, 2009, 5 (3) : 417-430. doi: 10.3934/jimo.2009.5.417 [2] Monika Eisenmann, Etienne Emmrich, Volker Mehrmann. Convergence of the backward Euler scheme for the operator-valued Riccati differential equation with semi-definite data. Evolution Equations and Control Theory, 2019, 8 (2) : 315-342. doi: 10.3934/eect.2019017 [3] Giuseppe Maria Coclite, Lorenzo di Ruvo. A note on the convergence of the solution of the Novikov equation. Discrete and Continuous Dynamical Systems - B, 2019, 24 (6) : 2865-2899. doi: 10.3934/dcdsb.2018290 [4] Liming Ling. The algebraic representation for high order solution of Sasa-Satsuma equation. Discrete and Continuous Dynamical Systems - S, 2016, 9 (6) : 1975-2010. doi: 10.3934/dcdss.2016081 [5] Vassilios A. Tsachouridis, Georgios Giantamidis, Stylianos Basagiannis, Kostas Kouramas. Formal analysis of the Schulz matrix inversion algorithm: A paradigm towards computer aided verification of general matrix flow solvers. Numerical Algebra, Control and Optimization, 2020, 10 (2) : 177-206. doi: 10.3934/naco.2019047 [6] Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control and Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018 [7] Brian D. O. Anderson, Shaoshuai Mou, A. Stephen Morse, Uwe Helmke. Decentralized gradient algorithm for solution of a linear equation. Numerical Algebra, Control and Optimization, 2016, 6 (3) : 319-328. doi: 10.3934/naco.2016014 [8] Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control and Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193 [9] Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control and Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023 [10] Yan Tang. Convergence analysis of a new iterative algorithm for solving split variational inclusion problems. Journal of Industrial and Management Optimization, 2020, 16 (2) : 945-964. doi: 10.3934/jimo.2018187 [11] Guoyong Gu, Junfeng Yang. A unified and tight linear convergence analysis of the relaxed proximal point algorithm. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022107 [12] Yong Duan, Jian-Guo Liu. Convergence analysis of the vortex blob method for the $b$-equation. Discrete and Continuous Dynamical Systems, 2014, 34 (5) : 1995-2011. doi: 10.3934/dcds.2014.34.1995 [13] Yuhong Dai, Nobuo Yamashita. Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 61-69. doi: 10.3934/naco.2011.1.61 [14] Nur Fadhilah Ibrahim. An algorithm for the largest eigenvalue of nonhomogeneous nonnegative polynomials. Numerical Algebra, Control and Optimization, 2014, 4 (1) : 75-91. doi: 10.3934/naco.2014.4.75 [15] Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016 [16] Sihem Guerarra. Positive and negative definite submatrices in an Hermitian least rank solution of the matrix equation AXA*=B. Numerical Algebra, Control and Optimization, 2019, 9 (1) : 15-22. doi: 10.3934/naco.2019002 [17] Irene Márquez-Corbella, Edgar Martínez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Advances in Mathematics of Communications, 2011, 5 (2) : 233-244. doi: 10.3934/amc.2011.5.233 [18] Chia-Huang Wu, Kuo-Hsiung Wang, Jau-Chuan Ke, Jyh-Bin Ke. A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations. Journal of Industrial and Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1 [19] Lingling Lv, Zhe Zhang, Lei Zhang, Weishu Wang. An iterative algorithm for periodic sylvester matrix equations. Journal of Industrial and Management Optimization, 2018, 14 (1) : 413-425. doi: 10.3934/jimo.2017053 [20] József Z. Farkas, Gary T. Smith, Glenn F. Webb. A dynamic model of CT scans for quantifying doubling time of ground glass opacities using histogram analysis. Mathematical Biosciences & Engineering, 2018, 15 (5) : 1203-1224. doi: 10.3934/mbe.2018055

Impact Factor: