Accurate solutions of \(M\)-matrix algebraic Riccati equations. (English) Zbl 1260.15025
This paper is concerned with the relative perturbation theory and its entrywise relatively accurate numerical solutions of an Riccati equation \(XDX-AX-B+C=0\), where the block-matrix \([{B\atop -C}{-D\atop A}]\) is a nonsingular or an irreducible singular \(M\)-matrix. Such Riccati equation has a unique nonnegative solution. It is shown that small relative perturbations to the entries of the matrices \(A\), \(B\), \(C\), and \(D\) introduce small relative changes to the entries of the non-negative solution. The authors discuss some minor but important implementation details to three selected numerical methods. The results are illustrated on several numerical experiments.
Reviewer: Martin Plešinger (Liberec)
MSC:
| 15A24 | Matrix equations and identities |
| 65F30 | Other matrix algorithms (MSC2010) |
| 65G99 | Error analysis and interval analysis |
| 65H10 | Numerical computation of solutions to systems of equations |
Software:
Algorithm 432References:
| [1] | Alfa A.S., Xue J., Ye Q.: Accurate computation of the smallest eigenvalue of a diagonally dominant M-matrix. Math. Comp. 71, 217–236 (2002) · Zbl 0984.65033 · doi:10.1090/S0025-5718-01-01325-4 |
| [2] | Anderson B.D.O.: Second-order convergent algorithms for the steady-state Riccati equation. Int. J. Control 28(2), 295–306 (1978) · Zbl 0385.49017 · doi:10.1080/00207177808922455 |
| [3] | Bartels R.H., Stewart G.W.: Algorithm 432: the solution of the matrix equation AXX = C. Commun. ACM 8, 820–826 (1972) · Zbl 1372.65121 · doi:10.1145/361573.361582 |
| [4] | Benner P., Li R.-C., Truhar N.: On ADI method for Sylvester equations. J. Comput. Appl. Math. 233(4), 1035–1045 (2009) · Zbl 1176.65050 · doi:10.1016/j.cam.2009.08.108 |
| [5] | Chiang C.-Y., King-Wah Chu E., 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(2), 227–247 (2009) · Zbl 1195.65053 · doi:10.1137/080717304 |
| [6] | Demmel J.: Applied Numerical Linear Algebra. SIAM, Philadelphia (1997) · Zbl 0879.65017 |
| [7] | Gohberg I., Koltracht I.: Mixed, componentwise, and structured condition numbers. SIAM J. Matrix Anal. Appl. 14(3), 688–704 (1993) · Zbl 0780.15004 · doi:10.1137/0614049 |
| [8] | Golub G.H., Nash S., Van Loan C.F.: Hessenberg–Schur method for the problem AX + XB = C. IEEE Trans. Autom. Control AC 24, 909–913 (1979) · Zbl 0421.65022 · doi:10.1109/TAC.1979.1102170 |
| [9] | Guo C., Higham N.: Iterative solution of a nonsymmetric algebraic Riccati equation. SIAM J. Matrix Anal. Appl. 29, 396–412 (2007) · Zbl 1146.65035 · doi:10.1137/050647669 |
| [10] | 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 |
| [11] | 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 |
| [12] | Guo C.-H., Iannazzo B., Meini B.: On the doubling algorithm for a (shifted) nonsymmetric algebraic Riccati equation. SIAM J. Matrix Anal. Appl. 29(4), 1083–1100 (2007) · Zbl 1157.65025 · doi:10.1137/060660837 |
| [13] | Guo X., Lin W., Xu S.: 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 |
| [14] | 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 |
| [15] | Juang J., Lin W.-W.: Nonsymmetric algebraic Riccati equations and Hamiltonian-like matrices. SIAM J. Matrix Anal. Appl. 20(1), 228–243 (1998) · Zbl 0922.15003 · doi:10.1137/S0895479897318253 |
| [16] | Lin Y., Wei Y.: Normwise, mixed and componentwise condition numbers of nonsymmetric algebraic Riccati equations. J. Appl. Math. Comput. 27, 137–147 (2008) · Zbl 1160.15016 · doi:10.1007/s12190-008-0061-4 |
| [17] | O’Cinneide C.A.: Entrywise perturbation theory and error analysis for Markov chains. Numer. Math. 65, 109–120 (1993) · Zbl 0804.65145 · doi:10.1007/BF01385743 |
| [18] | Rogers L.: 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 |
| [19] | Smith R.A.: Matrix equation XA + BX = C. SIAM J. Appl. Math. 16(1), 198–201 (1968) · Zbl 0157.22603 · doi:10.1137/0116017 |
| [20] | Varga R.S.: Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs (1962) · Zbl 0133.08602 |
| [21] | Xue, J., Xu, S., Li, R.-C.: Accurate solutions of M-matrix Sylvester equations. Numer. Math. (2011) doi: 10.1007/s00211-011-0420-1 · Zbl 1245.65053 |
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.
