American Institute of Mathematical Sciences

Advanced
November  2020, 16(6): 3047-3063. doi: 10.3934/jimo.2019093

Parametric Smith iterative algorithms for discrete Lyapunov matrix equations

Ai-Guo Wu , Ying Zhang , and  Hui-Jie Sun

School of Mechanical Engineering and Automation, Harbin Institute of Technology (Shenzhen), Shenzhen 518055, China

* Corresponding author: zhangyinghit@126.com

Received  November 2018 Revised  March 2019 Published  July 2019

Fund Project: The authors are supported by Shenzhen Municipal Basic Research Project for Discipline Layout with Project No.JCYJ20170811160715620, by the National Natural Science Foundation of China under Grant No. 61822305, by Guangdong Natural Science Foundation under Grant No. 2017A030313340, and by Shenzhen Municipal Project for International Cooperation with Project No. GJHZ20180420180849805

An iterative algorithm is established in this paper for solving the discrete Lyapunov matrix equations. The proposed algorithm contains a tunable parameter, and includes the Smith iteration as a special case, and thus is called the parametric Smith iterative algorithm. Some convergence conditions are developed for the proposed parametric Smith iterative algorithm. Moreover, the optimal parameter for the proposed algorithm to have the fastest convergence rate is also provided for a special case. Finally, numerical examples are employed to illustrate the effectiveness of the proposed algorithm.

Keywords: Lyapunov matrix equations, iterative algorithms, convergence rate.
Mathematics Subject Classification: Primary: 34D20, 15A06; Secondary: 15A24.
Citation: Ai-Guo Wu, Ying Zhang, Hui-Jie Sun. Parametric Smith iterative algorithms for discrete Lyapunov matrix equations. Journal of Industrial & Management Optimization, 2020, 16 (6) : 3047-3063. doi: 10.3934/jimo.2019093
References:
[1]

S. Azou, P. Brehonnet, P. Vilbe and L. C. Calvez, A new discrete impulse response Gramian and its application to model reduction, IEEE Transactions on Automatic Control, 45 (2000), 533-537.  doi: 10.1109/9.847738.  Google Scholar

[2]

J. Bibby, Axiomatisations of the average and a further generalisation of monotonic sequences, Glasgow Math. Journal, 15 (1974), 63-65.  doi: 10.1017/S0017089500002135.  Google Scholar

[3]

M. Dehghan and M. Hajarian, The general coupled matrix equations over generalized bisymmetric matrices, Linear Algebra and its Appl., 432 (2010), 1531-1552.  doi: 10.1016/j.laa.2009.11.014.  Google Scholar

[4]

F. Ding and T. Chen, Gradient based iterative algorithms for solving a class of matrix equations, IEEE Trans. on Automat. Control, 50 (2005), 1216-1221.  doi: 10.1109/TAC.2005.852558.  Google Scholar

[5]

S. Hammarling, Numerical solution of the discrete-time, convergent, non-negative definite Lyapunov equation, Systems and Control Letters, 17 (1991), 137-139.  doi: 10.1016/0167-6911(91)90039-H.  Google Scholar

[6]

S. J. Hammarling, Numerical solution of the stable, nonnegative definite Lyapunov equation, IMA J. of Numerical Anal., 2 (1982), 303-323.  doi: 10.1093/imanum/2.3.303.  Google Scholar

[7]

T. Kailath, Linear Systems, Prentice-Hall, New Jersey, 1980.  Google Scholar

[8]

L. Lv and Z. Zhang, Finite iterative solutions to periodic Sylvester matrix equations, J. of the Franklin Institute, 354 (2017), 2358-2370.  doi: 10.1016/j.jfranklin.2017.01.004.  Google Scholar

[9]

Q. Niu, X. Wang and L.-Z. Lu, A relaxed gradient based algorithm for solving Sylvester equations, Asian Journal of Control, 13 (2011), 461-464.  doi: 10.1002/asjc.328.  Google Scholar

[10]

T. Penzl, A cyclic low-rank Smith method for large sparse Lyapunov equations, SIAM J. on Scientific Computing, 21 (1999), 1401-1408.  doi: 10.1137/S1064827598347666.  Google Scholar

[11]

V. Ptak, The discrete Lyapunov equation in controllable canonical form, IEEE Trans. on Auto. Control, 26 (1981), 580-581.  doi: 10.1109/TAC.1981.1102644.  Google Scholar

[12]

M. Sadkane and L. Grammont, A note on the Lyapunov stability of periodic discrete-time systems, J. of Comp. and Appl. Math., 176 (2005), 463-466.  doi: 10.1016/j.cam.2004.08.012.  Google Scholar

[13]

V. Sreeram and P. Agathoklis, Model reduction of linear discrete systems via weighted impulse response gramians, Int. J. of Control, 53 (1991), 129-144.  doi: 10.1080/00207179108953613.  Google Scholar

[14]

Z. Tian, C. M. Fan, Y. Deng and P. H. Wen, New explicit iteration algorithms for solving coupled continuous Markovian jump Lyapunov matrix equations, J. of the Franklin Institute, 355 (2018), 8346-8372.  doi: 10.1016/j.jfranklin.2018.09.027.  Google Scholar

[15]

Z. Tian and C. Gu, A numerical algorithm for Lyapunov equations, Appl. Math. and Comp., 202 (2008), 44-53.  doi: 10.1016/j.amc.2007.12.057.  Google Scholar

[16]

Z. Tian, M. Tian, C. Gu and X. Hao, An accelerated Jacobi-gradient based iterative algorithm for solving Sylvester matrix equations, Filomat, 8 (2017), 2381-2390.  doi: 10.2298/FIL1708381T.  Google Scholar

[17]

V. Varga, A note on Hammarling's algorithm for the discrete Lyapunov equation, Systems and Control Letters, 15 (1990), 273-275.  doi: 10.1016/0167-6911(90)90121-A.  Google Scholar

[18]

Y. Zhang, A. G. Wu and C. T. Shao, Implicit iterative algorithms with a tuning parameter for discrete stochastic Lyapunov matrix equations, IET Control Theory and Appl., 11 (2017), 1554-1560.  doi: 10.1049/iet-cta.2016.1601.  Google Scholar

[19]

Y. Zhang, A. G. Wu and H. J. Sun, An implicit iterative algorithm with a tuning parameter for Itô Lyapunov matrix equations, Int. J. of Systems Science, 49 (2018), 425-434.  doi: 10.1080/00207721.2017.1407009.  Google Scholar

show all references

References:
[1]

S. Azou, P. Brehonnet, P. Vilbe and L. C. Calvez, A new discrete impulse response Gramian and its application to model reduction, IEEE Transactions on Automatic Control, 45 (2000), 533-537.  doi: 10.1109/9.847738.  Google Scholar

[2]

J. Bibby, Axiomatisations of the average and a further generalisation of monotonic sequences, Glasgow Math. Journal, 15 (1974), 63-65.  doi: 10.1017/S0017089500002135.  Google Scholar

[3]

M. Dehghan and M. Hajarian, The general coupled matrix equations over generalized bisymmetric matrices, Linear Algebra and its Appl., 432 (2010), 1531-1552.  doi: 10.1016/j.laa.2009.11.014.  Google Scholar

[4]

F. Ding and T. Chen, Gradient based iterative algorithms for solving a class of matrix equations, IEEE Trans. on Automat. Control, 50 (2005), 1216-1221.  doi: 10.1109/TAC.2005.852558.  Google Scholar

[5]

S. Hammarling, Numerical solution of the discrete-time, convergent, non-negative definite Lyapunov equation, Systems and Control Letters, 17 (1991), 137-139.  doi: 10.1016/0167-6911(91)90039-H.  Google Scholar

[6]

S. J. Hammarling, Numerical solution of the stable, nonnegative definite Lyapunov equation, IMA J. of Numerical Anal., 2 (1982), 303-323.  doi: 10.1093/imanum/2.3.303.  Google Scholar

[7]

T. Kailath, Linear Systems, Prentice-Hall, New Jersey, 1980.  Google Scholar

[8]

L. Lv and Z. Zhang, Finite iterative solutions to periodic Sylvester matrix equations, J. of the Franklin Institute, 354 (2017), 2358-2370.  doi: 10.1016/j.jfranklin.2017.01.004.  Google Scholar

[9]

Q. Niu, X. Wang and L.-Z. Lu, A relaxed gradient based algorithm for solving Sylvester equations, Asian Journal of Control, 13 (2011), 461-464.  doi: 10.1002/asjc.328.  Google Scholar

[10]

T. Penzl, A cyclic low-rank Smith method for large sparse Lyapunov equations, SIAM J. on Scientific Computing, 21 (1999), 1401-1408.  doi: 10.1137/S1064827598347666.  Google Scholar

[11]

V. Ptak, The discrete Lyapunov equation in controllable canonical form, IEEE Trans. on Auto. Control, 26 (1981), 580-581.  doi: 10.1109/TAC.1981.1102644.  Google Scholar

[12]

M. Sadkane and L. Grammont, A note on the Lyapunov stability of periodic discrete-time systems, J. of Comp. and Appl. Math., 176 (2005), 463-466.  doi: 10.1016/j.cam.2004.08.012.  Google Scholar

[13]

V. Sreeram and P. Agathoklis, Model reduction of linear discrete systems via weighted impulse response gramians, Int. J. of Control, 53 (1991), 129-144.  doi: 10.1080/00207179108953613.  Google Scholar

[14]

Z. Tian, C. M. Fan, Y. Deng and P. H. Wen, New explicit iteration algorithms for solving coupled continuous Markovian jump Lyapunov matrix equations, J. of the Franklin Institute, 355 (2018), 8346-8372.  doi: 10.1016/j.jfranklin.2018.09.027.  Google Scholar

[15]

Z. Tian and C. Gu, A numerical algorithm for Lyapunov equations, Appl. Math. and Comp., 202 (2008), 44-53.  doi: 10.1016/j.amc.2007.12.057.  Google Scholar

[16]

Z. Tian, M. Tian, C. Gu and X. Hao, An accelerated Jacobi-gradient based iterative algorithm for solving Sylvester matrix equations, Filomat, 8 (2017), 2381-2390.  doi: 10.2298/FIL1708381T.  Google Scholar

[17]

V. Varga, A note on Hammarling's algorithm for the discrete Lyapunov equation, Systems and Control Letters, 15 (1990), 273-275.  doi: 10.1016/0167-6911(90)90121-A.  Google Scholar

[18]

Y. Zhang, A. G. Wu and C. T. Shao, Implicit iterative algorithms with a tuning parameter for discrete stochastic Lyapunov matrix equations, IET Control Theory and Appl., 11 (2017), 1554-1560.  doi: 10.1049/iet-cta.2016.1601.  Google Scholar

[19]

Y. Zhang, A. G. Wu and H. J. Sun, An implicit iterative algorithm with a tuning parameter for Itô Lyapunov matrix equations, Int. J. of Systems Science, 49 (2018), 425-434.  doi: 10.1080/00207721.2017.1407009.  Google Scholar

Figure 1.  Convergence performance of the algorithm (3) for Example 1
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Spectral radius of $ G $ for Example 1
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Convergence curve of the algorithm (5) for Example 1
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Convergence performance of the algorithm (3) for Example 2
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Spectral radius of $ G $ for Example 2
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  Convergence curve of the algorithm (5) for Example 2
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  Spectral radius of $ G $ for Example 3
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  Convergence curve of the algorithm (5) for Example 3
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[2]

Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006
[3]

Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020378
[4]

Jing Qin, Shuang Li, Deanna Needell, Anna Ma, Rachel Grotheer, Chenxi Huang, Natalie Durgin. Stochastic greedy algorithms for multiple measurement vectors. Inverse Problems & Imaging, 2021, 15 (1) : 79-107. doi: 10.3934/ipi.2020066
[5]

Riccarda Rossi, Ulisse Stefanelli, Marita Thomas. Rate-independent evolution of sets. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 89-119. doi: 10.3934/dcdss.2020304
[6]

Peter Giesl, Zachary Langhorne, Carlos Argáez, Sigurdur Hafstein. Computing complete Lyapunov functions for discrete-time dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 299-336. doi: 10.3934/dcdsb.2020331
[7]

Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067
[8]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065
[9]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012
[10]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012
[11]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003
[12]

Matania Ben–Artzi, Joseph Falcovitz, Jiequan Li. The convergence of the GRP scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 1-27. doi: 10.3934/dcds.2009.23.1
[13]

Jian Zhang, Tony T. Lee, Tong Ye, Liang Huang. An approximate mean queue length formula for queueing systems with varying service rate. Journal of Industrial & Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106
[14]

Patrick Martinez, Judith Vancostenoble. Lipschitz stability for the growth rate coefficients in a nonlinear Fisher-KPP equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 695-721. doi: 10.3934/dcdss.2020362
[15]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465
[16]

Philipp Harms. Strong convergence rates for markovian representations of fractional processes. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020367
[17]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29
[18]

Dorothee Knees, Chiara Zanini. Existence of parameterized BV-solutions for rate-independent systems with discontinuous loads. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 121-149. doi: 10.3934/dcdss.2020332
[19]

Xueli Bai, Fang Li. Global dynamics of competition models with nonsymmetric nonlocal dispersals when one diffusion rate is small. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3075-3092. doi: 10.3934/dcds.2020035
[20]

Xing Wu, Keqin Su. Global existence and optimal decay rate of solutions to hyperbolic chemotaxis system in Besov spaces. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021002

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (93)
  • HTML views (541)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences