×

Monotone convergence of Newton-like methods for \(M\)-matrix algebraic Riccati equations. (English) Zbl 1273.65060

Summary: For the algebraic Riccati equation whose four coefficient matrices form a nonsingular \(M\)-matrix or an irreducible singular \(M\)-matrix \(K\), the minimal nonnegative solution can be found by Newton’s method and the doubling algorithm. When the two diagonal blocks of the matrix \(K\) have both large and small diagonal entries, the doubling algorithm often requires many more iterations than Newton’s method. In those cases, Newton’s method may be more efficient than the doubling algorithm. This has motivated us to study Newton-like methods that have higher-order convergence and are not much more expensive each iteration. We find that the Chebyshev method of order three and a two-step modified Chebyshev method of order four can be more efficient than Newton’s method. For the Riccati equation, these two Newton-like methods are actually special cases of the Newton-Shamanskii method. We show that, starting with zero initial guess or some other suitable initial guess, the sequence generated by the Newton-Shamanskii method converges monotonically to the minimal nonnegative solution.We also explain that the Newton-like methods can be used to great advantage when solving some Riccati equations involving a parameter.

MSC:

65F30 Other matrix algorithms (MSC2010)
Full Text: DOI

References:

[1] Bai, Z.-Z., Guo, X.-X., Xu, S.-F.: Alternately linearized implicit iteration methods for the minimal nonnegative solutions of the nonsymmetric algebraic Riccati equations. Numer. Linear Algebra Appl. 13, 655-674 (2006) · Zbl 1174.65381 · doi:10.1002/nla.500
[2] Bartels, R.H., Stewart, G.W.: Solution of the matrix equation AX + XB = C. Commun. ACM 15, 820-826 (1972) · Zbl 1372.65121 · doi:10.1145/361573.361582
[3] Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Sciences. Revised Reprint of the 1979 Academic Press Original. SIAM, Philadelphia (1994) · Zbl 0815.15016
[4] Bini, D.A., Iannazzo, B., Latouche, G., Meini, B.: On the solution of Riccati equations arising in fluid queues. Linear Algebra Appl. 413, 474-494 (2006) · Zbl 1108.65036 · doi:10.1016/j.laa.2005.04.019
[5] Bini, D.A., Iannazzo, B., Meini, B.: Numerical Solution of Algebraic Riccati Equations. SIAM, Philadelphia (2012) · Zbl 1244.65058
[6] Bini, D.A., Meini, B., Poloni, F.: Transforming algebraic Riccati equations into unilateral quadratic matrix equations. Numer. Math. 116, 553-578 (2010) · Zbl 1202.15016 · doi:10.1007/s00211-010-0319-2
[7] Candela, V., Marquina, A.: Recurrence relations for rational cubic methods II: the Chebyshev method. Computing 45, 355-367 (1990) · Zbl 0714.65061 · doi:10.1007/BF02238803
[8] Chiang, C.-Y., Chu, E.K.-W., Guo, C.-H., Huang, T.-M., Lin, W.-W., Xu, S.-F.: Convergence analysis of the doubling algorithm for several nonlinear matrix equations in the critical case. SIAM J. Matrix Anal. Appl. 31, 227-247 (2009) · Zbl 1195.65053 · doi:10.1137/080717304
[9] Gao, Y.-H., Bai, Z.-Z.: On inexact Newton methods based on doubling iteration scheme for non-symmetric algebraic Riccati equations. Numer. Linear Algebra Appl. 18, 325-341 (2011) · Zbl 1249.65093 · doi:10.1002/nla.727
[10] Golub, G.H., Nash, S., Van Loan, C.: A Hessenberg-Schur method for the problem AX + XB = C. IEEE Trans. Autom. Control 24, 909-913 (1979) · Zbl 0421.65022 · doi:10.1109/TAC.1979.1102170
[11] Guo, C.-H.: Nonsymmetric algebraic Riccati equations and Wiener-Hopf factorization for M-matrices. SIAM J. Matrix Anal. Appl. 23, 225-242 (2001) · Zbl 0996.65047 · doi:10.1137/S0895479800375680
[12] Guo, C.-H.: A note on the minimal nonnegative solution of a nonsymmetric algebraic Riccati equation. Linear Algebra Appl. 357, 299-302 (2002) · Zbl 1017.15005 · doi:10.1016/S0024-3795(02)00431-7
[13] Guo, C.-H.: Efficient methods for solving a nonsymmetric algebraic Riccati equation arising in stochastic fluid models. J. Comput. Appl. Math. 192, 353-373 (2006) · Zbl 1102.65049 · doi:10.1016/j.cam.2005.05.012
[14] 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 · doi:10.1137/050647669
[15] Guo, C.-H., Iannazzo, B., Meini, B.: On the doubling algorithm for a (shifted) nonsymmetric algebraic Riccati equation. SIAM J. Matrix Anal. Appl. 29, 1083-1100 (2007) · Zbl 1157.65025 · doi:10.1137/060660837
[16] Guo, C.-H., Laub, A.J.: On the iterative solution of a class of nonsymmetric algebraic Riccati equations. SIAM J. Matrix Anal. Appl. 22, 376-391 (2000) · Zbl 0973.65025 · doi:10.1137/S089547989834980X
[17] Guo, X.-X., Bai, Z.-Z.: On the minimal nonnegative solution of nonsymmetric algebraic Riccati equation. J. Comput. Math. 23, 305-320 (2005) · Zbl 1079.65052
[18] Guo, X.-X., Lin, W.-W., Xu, S.-F.: A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation. Numer. Math. 103, 393-412 (2006) · Zbl 1097.65055 · doi:10.1007/s00211-005-0673-7
[19] Higham, N.J.: Functions of Matrices: Theory and Computation. SIAM, Philadelphia (2008) · Zbl 1167.15001 · doi:10.1137/1.9780898717778
[20] Iannazzo, B., Poloni, F.: A subspace shift technique for nonsymmetric algebraic Riccati equations associated with an M-matrix. Numer. Linear Algebra Appl. (2012). doi:10.1002/nla.1836 · Zbl 1313.15030 · doi:10.1002/nla.1836
[21] Juang, J.: Existence of algebraic matrix Riccati equations arising in transport theory. Linear Algebra Appl. 230, 89-100 (1995) · Zbl 0839.15006 · doi:10.1016/0024-3795(93)00366-8
[22] Juang, J., Lin, W.-W.: Nonsymmetric algebraic Riccati equations and Hamiltonian-like matrices. SIAM J. Matrix Anal. Appl. 20, 228-243 (1998) · Zbl 0922.15003 · doi:10.1137/S0895479897318253
[23] Kelley, C.T.: A Shamanskii-like acceleration scheme for nonlinear equations at singular roots. Math. Comput. 47, 609-623 (1986) · Zbl 0613.65062
[24] Lin, Y., Bao, L.: Convergence analysis of the Newton-Shamanskii method for a nonsymmetric algebraic Riccati equation. Numer. Linear Algebra Appl. 15, 535-546 (2008) · Zbl 1212.65179 · doi:10.1002/nla.582
[25] Rogers, L.C.G.: Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains. Ann. Appl. Probab. 4, 390-413 (1994) · Zbl 0806.60052 · doi:10.1214/aoap/1177005065
[26] Sargolzaei, P., Soleymani, F.: Accurate 14th-order methods for solving nonlinear equations. Numer. Algorithms 58, 513-527 (2011) · Zbl 1242.65100 · doi:10.1007/s11075-011-9467-4
[27] Sharma, J.R., Sharma, R.: A new family of modified Ostrowski’s methods with accelerated eighth order convergence. Numer. Algorithms 54, 445-458 (2010) · Zbl 1195.65067 · doi:10.1007/s11075-009-9345-5
[28] Traub, J.F.: Iterative Methods for the Solution of Equations. Prentice-Hall, Englewood Cliffs (1964) · Zbl 0121.11204
[29] Wang, W.-G., Wang, W.-C., Li, R.-C.: Alternating-directional doubling algorithm for M-matrix algebraic Riccati equations. SIAM J. Matrix Anal. Appl 33, 170-194 (2012) · Zbl 1258.65045 · doi:10.1137/110835463
[30] Xue, J., Xu, S., Li, R.-C.: Accurate solutions of M-matrix algebraic Riccati equations. Numer. Math. 120, 671-700 (2012) · Zbl 1260.15025 · doi:10.1007/s00211-011-0421-0
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.