Convergence of pure and relaxed Newton methods for solving a matrix polynomial equation arising in stochastic models. (English) Zbl 1286.65064
Summary: We consider a matrix polynomial equation which has the form of \(A_nX^n + A_{n-1}X^{n-1} + \cdots + A_0 = 0\), where \(A_n, A_{n-1}, \dots, A_0\) and \(X\) are square matrices assuming the positivity of coefficients from stochastic models. The monotone convergence of Newton’s method for solving the equation is considered and we show that the elementwise minimal nonnegative solution can be found by the method with the zero starting matrix. Moreover, the relaxed Newton method preserving the monotonicity result is provided. Finally, numerical experiments show that our method reduces the number of iterations significantly.
MSC:
| 65H10 | Numerical computation of solutions to systems of equations |
| 15A24 | Matrix equations and identities |
| 65H04 | Numerical computation of roots of polynomial equations |
Keywords:
matrix polynomial equation; elementwise positive solution; elementwise nonnegative solution; M-matrix; Newton’s method; relaxed Newton method; exact line search; monotone convergence; numerical experimentsSoftware:
SQUINTReferences:
| [1] | Alfa, A. S., Combined elapsed time and matrix-analytic method for the discrete time \(G I / G / 1\) and \(G I^X / G / 1\) systems, Queueing Syst., 45, 5-25 (2003) · Zbl 1046.90016 |
| [2] | Bean, N. G.; Bright, L.; Latouche, G.; Pearce, C. E.M.; Pollett, P. K.; Taylor, P. G., The quasi-stationary behavior of quasi-birth-and-death processes, Ann. Appl. Probab., 7, 134-155 (1997) · Zbl 0883.60085 |
| [3] | Benner, P.; Byers, R., An exact line search method for solving generalized continuous-time algebraic Riccati equation, IEEE Trans. Automat. Control, 43, 1, 101-107 (1998) · Zbl 0908.93026 |
| [4] | Bini, D. A.; Latouche, G.; Meini, B., Numerical Methods for Structured Markov Chains (2005), Oxford University Press · Zbl 1076.60002 |
| [5] | Butler, G. J.; Johnson, C. R.; Wolkowicz, H., Nonnegative solutions of a quadratic matrix equation arising from comparison theorems in ordinary differential equations, SIAM J. Algebr. Discrete Methods, 6, 1, 47-53 (1985) · Zbl 0558.15005 |
| [6] | Davis, G. J., Numerical solution of a quadratic matrix equation, SIAM J. Sci. Statist. Comput., 2, 2, 164-175 (1981) · Zbl 0467.65021 |
| [7] | Davis, G. J., Algorithm 598: an algorithm to compute solvent of the matrix equation \(A X^2 + B X + C = 0\), ACM Trans. Math. Software, 9, 2, 246-254 (1983) · Zbl 0512.65029 |
| [8] | Epton, M. A., Methods for the solution of \(A X D - B X C = E\) and its application in the numerical solution of implicit ordinary differential equations, BIT, 20, 341-345 (1980) · Zbl 0452.65015 |
| [9] | Gloub, G. H.; Van Loan, C. F., Matrix Computations (1996), Johns Hopkins University Press · Zbl 0865.65009 |
| [10] | Gohberg, I.; Lancaster, P.; Rodman, L., Matrix Polynomials (1982), Academic Press · Zbl 0482.15001 |
| [11] | Golub, G. H.; Nash, S.; Van Loan, C. F., A Hessenberg-Schur method for the problem \(A X + X B = C\), IEEE Trans. Automat. Control, C-24, 909 (1979) · Zbl 0421.65022 |
| [12] | Guo, C.-H.; Higham, N. J., Iterative solution of a nonsymmetric algebraic Riccati equation, SIAM J. Matrix Anal. Appl., 29, 396-412 (2007) · Zbl 1146.65035 |
| [13] | Guo, C.-H.; Laub, A. J., On the iterative solution of a class of nonsymmetric algebraic Riccati equations, SIAM J. Matrix Anal. Appl., 67, 1089-1105 (1998) · Zbl 0903.65047 |
| [14] | He, C.; Meini, B.; Rhee, N. H., A shifted cyclic reduction algorithm for quasi-birth-death problems, SIAM J. Matrix Anal. Appl., 23, 673-691 (2001) · Zbl 1004.65055 |
| [15] | He, C.; Meini, B.; Rhee, N. H.; Sohraby, K., A quadratically convergent Bernoulli-like algorithm for solving matrix polynomial equations in Markov chains, Electron. Trans. Numer. Anal., 17, 151-167 (2004) · Zbl 1065.65006 |
| [16] | Higham, N. J.; Kim, H.-M., Numerical analysis of a quadratic matrix equation, IMA J. Numer. Anal., 20, 4, 499-519 (2000) · Zbl 0966.65040 |
| [17] | Higham, N. J.; Kim, H.-M., Solving a quadratic matrix equation by Newtonʼs method with exact line searches, SIAM J. Matrix Anal. Appl., 23, 303-316 (2001) · Zbl 1017.65038 |
| [18] | Kim, H.-M., Convergence of Newtonʼs method for solving a class of quadratic matrix equations, Honam Math. J., 30, 2, 399-409 (2008) · Zbl 1179.65046 |
| [19] | Kratz, W.; Stickel, E., Numerical solution of matrix polynomial equations by Newtonʼs method, IMA J. Numer. Anal., 7, 355-369 (1987) · Zbl 0631.65040 |
| [20] | Lancaster, P., Lambda-matrices and Vibrating Systems (1966), Pergamon Press · Zbl 0146.32003 |
| [21] | Lancaster, P.; Tismenetsky, M., The Theory of Matrices with Applications (1985), Academic Press · Zbl 0516.15018 |
| [22] | Latouche, G., Newtonʼs iteration for nonlinear equations in Markov chains, IMA J. Numer. Anal., 14, 583-598 (1994) · Zbl 0861.65132 |
| [23] | Latouche, G.; Ramaswami, V., Introduction to Matrix Analytic Methods in Stochastic Modeling (1999), ASA-SIAM · Zbl 0922.60001 |
| [24] | Latouche, G.; Ramaswami, V., A logarithmic reduction algorithm for quasi-birth-death processes, J. Appl. Probab., 30, 3, 650-674 (1993) · Zbl 0789.60055 |
| [25] | Neuts, M. F., Moment formulas for the Markov renewal branching process, Adv. in Appl. Probab., 8, 4, 690-711 (1976) · Zbl 0379.60081 |
| [26] | Nocedal, J.; Wright, S. J., Numerical Optimization (1999), Springer-Verlag · Zbl 0930.65067 |
| [27] | Poole, G.; Boullion, T., A survey on M-matrices, SIAM Rev., 16, 4, 419-427 (1974) · Zbl 0292.15009 |
| [28] | Purdue, P., Non-linear matrix integral equations of Voltera type in queueing theory, J. Appl. Probab., 10, 644-651 (1973) · Zbl 0272.60066 |
| [29] | Seo, J. H.; Kim, H.-M., Solving matrix polynomials by Newtonʼs method with exact line searches, J. Korean Soc. Ind. Appl. Math., 12, 2, 55-68 (2008) |
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.
