A structure-preserving doubling algorithm for solving a class of quadratic matrix equation with $ M $-matrix

Cairong Chen; Cairong Chen

doi:10.3934/era.2022030

Electronic Research Archive

2022, Volume 30, Issue 2: 574-584. doi: 10.3934/era.2022030

Previous Article Next Article

Research article Special Issues

A structure-preserving doubling algorithm for solving a class of quadratic matrix equation with $ M $-matrix

Cairong Chen ^,

School of Mathematics and Statistics, FJKLMAA and Center for Applied Mathematics of Fujian Province, Fujian Normal University, Fuzhou 350007, China

Received: 12 December 2021 Revised: 28 January 2022 Accepted: 07 February 2022 Published: 11 February 2022

Consider the problem of finding the maximal nonpositive solvent $ \varPhi $ of the quadratic matrix equation (QME) $ X^2 + BX + C = 0 $ with $ B $ being a nonsingular $ M $-matrix and $ C $ an $ M $-matrix such that $ B^{-1}C\ge 0 $. Such QME arises from an overdamped vibrating system. Recently, under the condition that $ B - C - I $ is a nonsingular $ M $-matrix, Yu et al. (Appl. Math. Comput., 218 (2011): 3303–3310) proved that $ \rho(\varPhi)\le 1 $ for this QME. In this paper, under the same condition, we slightly improve their result and prove that $ \rho(\varPhi) < 1 $, which is important for the quadratic convergence of the structure-preserving doubling algorithm. Then, a new globally monotonically and quadratically convergent structure-preserving doubling algorithm for solving the QME is developed. Numerical examples are presented to demonstrate the feasibility and effectiveness of our method.
- Quadratic matrix equation,
- structure-preserving doubling algorithm,
- $ M $-matrix,
- maximal nonpositive solvent,
- quadratic convergence
Citation: Cairong Chen. A structure-preserving doubling algorithm for solving a class of quadratic matrix equation with $ M $-matrix[J]. Electronic Research Archive, 2022, 30(2): 574-584. doi: 10.3934/era.2022030

Related Papers:

Abstract

Consider the problem of finding the maximal nonpositive solvent $ \varPhi $ of the quadratic matrix equation (QME) $ X^2 + BX + C = 0 $ with $ B $ being a nonsingular $ M $-matrix and $ C $ an $ M $-matrix such that $ B^{-1}C\ge 0 $. Such QME arises from an overdamped vibrating system. Recently, under the condition that $ B - C - I $ is a nonsingular $ M $-matrix, Yu et al. (Appl. Math. Comput., 218 (2011): 3303–3310) proved that $ \rho(\varPhi)\le 1 $ for this QME. In this paper, under the same condition, we slightly improve their result and prove that $ \rho(\varPhi) < 1 $, which is important for the quadratic convergence of the structure-preserving doubling algorithm. Then, a new globally monotonically and quadratically convergent structure-preserving doubling algorithm for solving the QME is developed. Numerical examples are presented to demonstrate the feasibility and effectiveness of our method.

References

[1]	F. Tisseur, Backward error and condition of polynomial eigenvalue problems, Linear Algebra Appl., 309 (2000), 339–361. https://doi.org/10.1016/S0024-3795(99)00063-4 doi: 10.1016/S0024-3795(99)00063-4
[2]	F. Tisseur, K. Meerbergen, The quadratic eigenvalue problem, SIAM Rev., 43 (2001), 235–286. https://doi.org/10.1137/S0036144500381988 doi: 10.1137/S0036144500381988
[3]	B. Yu, N. Dong, Q. Tang, F. H. Wen, On iterative methods for the quadratic matrix equation with M-matrix, Appl. Math. Comput., 218 (2011), 3303–3310. https://doi.org/10.1016/j.amc.2011.08.070 doi: 10.1016/j.amc.2011.08.070
[4]	Y. J. Kim, H. M. Kim, Diagonal update method for a quadratic matrix equation, Appl. Math. Comput., 283 (2016), 208–215. https://doi.org/10.1016/j.amc.2016.02.016 doi: 10.1016/j.amc.2016.02.016
[5]	C. Y. He, B. Meini, N. H. Rhee, A shifted cyclic reduction algorithm for quasi-birth-death problems, SIAM J. Matrix Anal. Appl., 23 (2002), 679–691. https://doi.org/10.1137/S0895479800371955 doi: 10.1137/S0895479800371955
[6]	B. Meini, Solving QBD problems: the cyclic reduction algorithm versus the invariant subspace method, Adv. Performance Anal., 1 (1998), 215–225.
[7]	C. H. Guo, P. Lancaster, Algorithms for hyperbolic quadratic eigenvalue problems, Math. Comp., 74 (2005), 1777–1791. https://doi.org/10.1090/S0025-5718-05-01748-5 doi: 10.1090/S0025-5718-05-01748-5
[8]	C. H. Guo, N. J. Higham, F. Tisseur, Detecting and solving hyperbolic quadratic eigenvalue problems, SIAM J. Matrix Anal. Appl., 30 (2009), 1593–1613. https://doi.org/10.1137/070704058 doi: 10.1137/070704058
[9]	G. J. Davis, Numerical solution of a quadratic matrix equation, SIAM J. Sci. Statist. Comput., 2 (1981), 164–175. https://doi.org/10.1137/0902014 doi: 10.1137/0902014
[10]	N. J. Higham, H. M. Kim, Numerical analysis of a quadratic matrix equation, IMA J. Numer. Anal., 20 (2000), 499–519. https://doi.org/10.1093/imanum/20.4.499 doi: 10.1093/imanum/20.4.499
[11]	N. J. Higham, H. M. Kim, Solving a quadratic matrix equation by Newton's method with exact line searches, SIAM J. Matrix Anal. Appl., 23 (2001), 303–316. https://doi.org/10.1137/S0895479899350976 doi: 10.1137/S0895479899350976
[12]	Z. Z. Bai, X. X. Guo, J. F. Yin, On two iteration methods for the quadratic matrix equations, Int. J. Numer. Anal. Model., 2 (2005), 114–122.
[13]	C. H. Guo, On a quadratic matrix equation associated with an $M$-matrix, IMA J. Numer. Anal., 23 (2003), 11–27. https://doi.org/10.1093/imanum/23.1.11 doi: 10.1093/imanum/23.1.11
[14]	L. Z. Lu, Z. Ahmed, J. R. Guan, Numerical methods for a quadratic matrix equation with a nonsingular $M$-matrix, Appl. Math. Lett., 52 (2016), 46–52. https://doi.org/10.1016/j.aml.2015.08.006 doi: 10.1016/j.aml.2015.08.006
[15]	W. Kratz, E. Stickel, Numerical solution of matrix polynomial equations by Newton's method, IMA J. Numer. Anal., 7 (1987), 355–369. https://doi.org/10.1093/imanum/7.3.355 doi: 10.1093/imanum/7.3.355
[16]	B. Yu, N. Dong, A structure-preserving doubling algorithm for quadratic matrix equations arising form damped mass-spring system, Adv. Model. Optim., 12 (2010), 85–100.
[17]	B. Yu, N. Dong, Q. Tang, Iterative methods for the quadratic bilinear equation arising from a class of quadratic dynamic systems, ScienceAsia, 47 (2021), 785–792. http://dx.doi.org/10.2306/scienceasia1513-1874.2021.104 doi: 10.2306/scienceasia1513-1874.2021.104
[18]	B. Yu, D. H. Li, N. Dong, Convergence of the cyclic reduction algorithm for a class of weakly overdamped quadratics, J. Comput. Math., 30 (2012), 139–156. https://www.jstor.org/stable/43693690
[19]	C. R. Chen, R. C. Li, C. F. Ma, Highly accurate doubling algorithm for quadratic matrix equation from quasi-birth-and-death process, Linear Algebra Appl., 583 (2019), 1–45. https://doi.org/10.1016/j.laa.2019.08.018 doi: 10.1016/j.laa.2019.08.018
[20]	E. K. W. Chu, H. Y. Fan, W. W. Lin, A structure-preserving doubling algorithm for continuous-time algebraic Riccati equations, Linear Algebra Appl., 396 (2005), 55–80. https://doi.org/10.1016/j.laa.2004.10.010 doi: 10.1016/j.laa.2004.10.010
[21]	E. K. W. Chu, H. Y. Fan, W. W. Lin, C. S. Wang, Structure-preserving algorithms for periodic discrete-time algebraic Riccati equations, Int. J. Control, 77 (2004), 767–788. https://doi.org/10.1080/00207170410001714988 doi: 10.1080/00207170410001714988
[22]	C. H. Guo, B. Iannazzo, B. Meini, On the doubling algorithm for a (shifted) nonsymmetric algebraic Riccati equation, SIAM J. Matrix Anal. Appl., 29 (2007), 1083–1100. https://doi.org/10.1137/060660837 doi: 10.1137/060660837
[23]	X. X. Guo, W. W. Lin, S. F. Xu, A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation, Numer. Math., 103 (2006), 393–412. https://doi.org/10.1007/s00211-005-0673-7 doi: 10.1007/s00211-005-0673-7
[24]	T. M. Huang, W. Q. Huang, R. C. Li, W. W. Lin, A new two-phase structure-preserving doubling algorithm for critically singular $M$-matrix algebraic Riccati equations, Numer. Linear Algebra Appl., 23 (2016), 291–313. https://doi.org/10.1002/nla.2025 doi: 10.1002/nla.2025
[25]	W. G. Wang, W. C. Wang, R. C. Li, Alternating-directional doubling algorithm for $M$-matrix algebraic Riccati equations, SIAM J. Matrix Anal. Appl., 33 (2012), 170–194. https://doi.org/10.1137/110835463 doi: 10.1137/110835463
[26]	C. Y. Chiang, E. K. W. Chu, C. H. Guo, T. M. Huang, W. W. Lin, 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. https://doi.org/10.1137/080717304 doi: 10.1137/080717304
[27]	T. M. Huang, R. C. Li, W. W. Lin, Structure-Preserving Doubling Algorithms for Nonlinear Matrix Equations, SIAM, Philadelphia, 2018.
[28]	A. Berman, R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, SIAM, Philadelphia, 1994.
[29]	C. D. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, Philadelphia, 2000.
[30]	J. Meng, S. H. Seo, H. M. Kim, Condition numbers and backward error of a matrix polynomial equation arising in stochastic models, J. Sci. Comput., 76 (2018), 759–776. https://doi.org/10.1007/s10915-018-0641-x doi: 10.1007/s10915-018-0641-x

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)