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 & 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.  doi: 10.1080/00207177808922455.  Google Scholar

[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.  doi: 10.1081/STM-200046511.  Google Scholar

[3]

A. Berman and R. J. Plemmons, "Nonnegative Matrices in the Mathematical Sciences,", SIAM, (1994).   Google Scholar

[4]

D. A. Bini, B. Meini and F. Poloni, Transforming algebraic Riccati equations into unilateral quadratic matrix equations,, Numer. Math., 116 (2010), 553.  doi: 10.1007/s00211-010-0319-2.  Google Scholar

[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.  doi: 10.1137/080717304.  Google Scholar

[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.  doi: 10.1016/j.laa.2004.10.010.  Google Scholar

[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.  doi: 10.1080/00207170410001714988.  Google Scholar

[8]

J. Demmel, "Applied Numerical Linear Algebra,", SIAM, (1997).  doi: 10.1137/1.9781611971446.  Google Scholar

[9]

M. Fiedler, "Special Matrices and Their Applications in Numerical Mathematics,", Dover Publications, (2008).   Google Scholar

[10]

C.-H. Guo, Nonsymmetric algebraic Riccati equations and Wiener-Hopf factorization for M-matrices,, SIAM J. Matrix Anal. Appl., 23 (2001), 225.  doi: 10.1137/S0895479800375680.  Google Scholar

[11]

C.-H. Guo, A new class of nonsymmetric algebraic Riccati equations,, Linear Algebra Appl., 426 (2007), 636.  doi: 10.1016/j.laa.2007.05.044.  Google Scholar

[12]

C.-H. Guo and N. Higham, Iterative solution of a nonsymmetric algebraic Riccati equation,, SIAM J. Matrix Anal. Appl., 29 (2007), 396.  doi: 10.1137/050647669.  Google Scholar

[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.  doi: 10.1137/060660837.  Google Scholar

[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.  doi: 10.1137/S089547989834980X.  Google Scholar

[15]

X. Guo, W. Lin and S. Xu, A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation,, Numer. Math., 103 (2006), 393.  doi: 10.1007/s00211-005-0673-7.  Google Scholar

[16]

J. Juang, Existence of algebraic matrix Riccati equations arising in transport theory,, Linear Algebra Appl., 230 (1995), 89.  doi: 10.1016/0024-3795(93)00366-8.  Google Scholar

[17]

J. Juang and W.-W. Lin, Nonsymmetric algebraic Riccati equations and Hamiltonian-like matrices,, SIAM J. Matrix Anal. Appl., 20 (1998), 228.  doi: 10.1137/S0895479897318253.  Google Scholar

[18]

P. Lancaster and L. Rodman, "Algebraic Riccati Equations,", Oxford University Press, (1995).   Google Scholar

[19]

V. Ramaswami, Matrix analytic methods for stochastic fluid flows,, Proceedings of the 16th International Teletraffic Congress, (1999), 19.   Google Scholar

[20]

L. Rogers, Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains,, Ann. Appl. Probab., 4 (1994), 390.  doi: 10.1214/aoap/1177005065.  Google Scholar

[21]

W.-G. Wang, W.-C. Wang and R.-C. Li, Deflating irreducible singular M-matrix algebraic riccati equations,, Technical Report 2011-20, (2011), 2011.   Google Scholar

[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.  doi: 10.1137/110835463.  Google Scholar

[23]

J. Xue, S. Xu and R.-C. Li, Accurate solutions of M-matrix algebraic Riccati equations,, Numer. Math., 120 (2012), 671.  doi: 10.1007/s00211-011-0421-0.  Google Scholar

[24]

J. Xue, S. Xu and R.-C. Li, Accurate solutions of M-matrix Sylvester equations,, Numer. Math., 120 (2012), 639.  doi: 10.1007/s00211-011-0420-1.  Google Scholar

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.  doi: 10.1080/00207177808922455.  Google Scholar

[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.  doi: 10.1081/STM-200046511.  Google Scholar

[3]

A. Berman and R. J. Plemmons, "Nonnegative Matrices in the Mathematical Sciences,", SIAM, (1994).   Google Scholar

[4]

D. A. Bini, B. Meini and F. Poloni, Transforming algebraic Riccati equations into unilateral quadratic matrix equations,, Numer. Math., 116 (2010), 553.  doi: 10.1007/s00211-010-0319-2.  Google Scholar

[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.  doi: 10.1137/080717304.  Google Scholar

[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.  doi: 10.1016/j.laa.2004.10.010.  Google Scholar

[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.  doi: 10.1080/00207170410001714988.  Google Scholar

[8]

J. Demmel, "Applied Numerical Linear Algebra,", SIAM, (1997).  doi: 10.1137/1.9781611971446.  Google Scholar

[9]

M. Fiedler, "Special Matrices and Their Applications in Numerical Mathematics,", Dover Publications, (2008).   Google Scholar

[10]

C.-H. Guo, Nonsymmetric algebraic Riccati equations and Wiener-Hopf factorization for M-matrices,, SIAM J. Matrix Anal. Appl., 23 (2001), 225.  doi: 10.1137/S0895479800375680.  Google Scholar

[11]

C.-H. Guo, A new class of nonsymmetric algebraic Riccati equations,, Linear Algebra Appl., 426 (2007), 636.  doi: 10.1016/j.laa.2007.05.044.  Google Scholar

[12]

C.-H. Guo and N. Higham, Iterative solution of a nonsymmetric algebraic Riccati equation,, SIAM J. Matrix Anal. Appl., 29 (2007), 396.  doi: 10.1137/050647669.  Google Scholar

[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.  doi: 10.1137/060660837.  Google Scholar

[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.  doi: 10.1137/S089547989834980X.  Google Scholar

[15]

X. Guo, W. Lin and S. Xu, A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation,, Numer. Math., 103 (2006), 393.  doi: 10.1007/s00211-005-0673-7.  Google Scholar

[16]

J. Juang, Existence of algebraic matrix Riccati equations arising in transport theory,, Linear Algebra Appl., 230 (1995), 89.  doi: 10.1016/0024-3795(93)00366-8.  Google Scholar

[17]

J. Juang and W.-W. Lin, Nonsymmetric algebraic Riccati equations and Hamiltonian-like matrices,, SIAM J. Matrix Anal. Appl., 20 (1998), 228.  doi: 10.1137/S0895479897318253.  Google Scholar

[18]

P. Lancaster and L. Rodman, "Algebraic Riccati Equations,", Oxford University Press, (1995).   Google Scholar

[19]

V. Ramaswami, Matrix analytic methods for stochastic fluid flows,, Proceedings of the 16th International Teletraffic Congress, (1999), 19.   Google Scholar

[20]

L. Rogers, Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains,, Ann. Appl. Probab., 4 (1994), 390.  doi: 10.1214/aoap/1177005065.  Google Scholar

[21]

W.-G. Wang, W.-C. Wang and R.-C. Li, Deflating irreducible singular M-matrix algebraic riccati equations,, Technical Report 2011-20, (2011), 2011.   Google Scholar

[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.  doi: 10.1137/110835463.  Google Scholar

[23]

J. Xue, S. Xu and R.-C. Li, Accurate solutions of M-matrix algebraic Riccati equations,, Numer. Math., 120 (2012), 671.  doi: 10.1007/s00211-011-0421-0.  Google Scholar

[24]

J. Xue, S. Xu and R.-C. Li, Accurate solutions of M-matrix Sylvester equations,, Numer. Math., 120 (2012), 639.  doi: 10.1007/s00211-011-0420-1.  Google Scholar

[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 & Management Optimization, 2009, 5 (3) : 417-430. doi: 10.3934/jimo.2009.5.417

[2]

Giuseppe Maria Coclite, Lorenzo di Ruvo. A note on the convergence of the solution of the Novikov equation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (6) : 2865-2899. doi: 10.3934/dcdsb.2018290

[3]

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 & Control Theory, 2019, 8 (2) : 315-342. doi: 10.3934/eect.2019017

[4]

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 & Optimization, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2019047

[5]

Liming Ling. The algebraic representation for high order solution of Sasa-Satsuma equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (6) : 1975-2010. doi: 10.3934/dcdss.2016081

[6]

Brian D. O. Anderson, Shaoshuai Mou, A. Stephen Morse, Uwe Helmke. Decentralized gradient algorithm for solution of a linear equation. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 319-328. doi: 10.3934/naco.2016014

[7]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018

[8]

Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & 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 & 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 & Management Optimization, 2017, 13 (5) : 1-20. doi: 10.3934/jimo.2018187

[11]

Yong Duan, Jian-Guo Liu. Convergence analysis of the vortex blob method for the $b$-equation. Discrete & Continuous Dynamical Systems - A, 2014, 34 (5) : 1995-2011. doi: 10.3934/dcds.2014.34.1995

[12]

Yuhong Dai, Nobuo Yamashita. Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 61-69. doi: 10.3934/naco.2011.1.61

[13]

Nur Fadhilah Ibrahim. An algorithm for the largest eigenvalue of nonhomogeneous nonnegative polynomials. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 75-91. doi: 10.3934/naco.2014.4.75

[14]

Sihem Guerarra. Positive and negative definite submatrices in an Hermitian least rank solution of the matrix equation AXA*=B. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 15-22. doi: 10.3934/naco.2019002

[15]

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 & Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1

[16]

Lingling Lv, Zhe Zhang, Lei Zhang, Weishu Wang. An iterative algorithm for periodic sylvester matrix equations. Journal of Industrial & Management Optimization, 2018, 14 (1) : 413-425. doi: 10.3934/jimo.2017053

[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]

Frank Blume. Minimal rates of entropy convergence for rank one systems. Discrete & Continuous Dynamical Systems - A, 2000, 6 (4) : 773-796. doi: 10.3934/dcds.2000.6.773

[19]

Giuseppe Maria Coclite, Lorenzo Di Ruvo. A note on the convergence of the solution of the high order Camassa-Holm equation to the entropy ones of a scalar conservation law. Discrete & Continuous Dynamical Systems - A, 2017, 37 (3) : 1247-1282. doi: 10.3934/dcds.2017052

[20]

Dequan Yue, Wuyi Yue, Gang Xu. Analysis of customers' impatience in an M/M/1 queue with working vacations. Journal of Industrial & Management Optimization, 2012, 8 (4) : 895-908. doi: 10.3934/jimo.2012.8.895

 Impact Factor: 

Metrics

  • PDF downloads (7)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]