Efficient computation of the extreme solutions of $X+A^*X^{-1}A=Q$ and $X-A^*X^{-1}A=Q$
HTML articles powered by AMS MathViewer
- by Beatrice Meini PDF
- Math. Comp. 71 (2002), 1189-1204 Request permission
Abstract:
We propose a new quadratically convergent algorithm, having a low computational cost per step and good numerical stability properties, which allows the simultaneous approximation of the extreme solutions of the matrix equations $X+A^* X^{-1}A=Q$ and $X-A^*X^{-1}A=Q$. The algorithm is based on the cyclic reduction method.References
- Nail Akar and Khosrow Sohraby, An invariant subspace approach in $M/G/1$ and $G/M/1$ type Markov chains, Comm. Statist. Stochastic Models 13 (1997), no.Β 3, 381β416. MR 1457654, DOI 10.1080/15326349708807433
- W. N. Anderson Jr., T. D. Morley, and G. E. Trapp, Positive solutions to $X=A-BX^{-1}B^*$, Linear Algebra Appl. 134 (1990), 53β62. MR 1060009, DOI 10.1016/0024-3795(90)90005-W
- D. A. Bini, L. Gemignani, and B. Meini, Computations with infinite Toeplitz matrices and polynomials, Linear Algebra Appl., to appear.
- β, Factorization of analytic functions by means of Koenigβs theorem and Toeplitz computations, Numer. Math. 89 (2001), 49β82.
- Dario Bini and Beatrice Meini, On the solution of a nonlinear matrix equation arising in queueing problems, SIAM J. Matrix Anal. Appl. 17 (1996), no.Β 4, 906β926. MR 1410708, DOI 10.1137/S0895479895284804
- Dario Andrea Bini and Beatrice Meini, Improved cyclic reduction for solving queueing problems, Numer. Algorithms 15 (1997), no.Β 1, 57β74. MR 1460963, DOI 10.1023/A:1019206402431
- Dario Andrea Bini and Beatrice Meini, Effective methods for solving banded Toeplitz systems, SIAM J. Matrix Anal. Appl. 20 (1999), no.Β 3, 700β719. MR 1685049, DOI 10.1137/S0895479897324585
- H. Dym, Hermitian block Toeplitz matrices, orthogonal polynomials, reproducing kernel pontryagin spaces, interpolation and extension, Oper. Theory, Adv. Appl. 34 (1998), 79β135, Orthogonal matrix-valued polynomials and applications, Pap. Semin. Oper. Theory, Tel Aviv/Isr.
- Jacob C. Engwerda, On the existence of a positive definite solution of the matrix equation $X+A^{\mathsf T}X^{-1}A=I$, Linear Algebra Appl. 194 (1993), 91β108. MR 1243822, DOI 10.1016/0024-3795(93)90115-5
- Jacob C. Engwerda, AndrΓ© C. M. Ran, and Arie L. Rijkeboer, Necessary and sufficient conditions for the existence of a positive definite solution of the matrix equation $X+A^*X^{-1}A=Q$, Linear Algebra Appl. 186 (1993), 255β275. MR 1217209, DOI 10.1016/0024-3795(93)90295-Y
- Augusto Ferrante and Bernard C. Levy, Hermitian solutions of the equation $X=Q+NX^{-1}N^*$, Linear Algebra Appl. 247 (1996), 359β373. MR 1412761, DOI 10.1016/0024-3795(95)00121-2
- J. D. Gardiner, A. J. Laub, J. J. Amato, and C. B. Moler, Solution of the Sylvester matrix equation $AXB^T+CXD^T=E$, ACM Trans. Math. Software 18 (1992), 223β231.
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
- Chun-Hua Guo, Newtonβs method for discrete algebraic Riccati equations when the closed-loop matrix has eigenvalues on the unit circle, SIAM J. Matrix Anal. Appl. 20 (1999), no.Β 2, 279β294. MR 1646848, DOI 10.1137/S0895479897322999
- Chun-Hua Guo and Peter Lancaster, Iterative solution of two matrix equations, Math. Comp. 68 (1999), no.Β 228, 1589β1603. MR 1651757, DOI 10.1090/S0025-5718-99-01122-9
- Guy Latouche, A note on two matrices occurring in the solution of quasi-birth-and-death processes, Comm. Statist. Stochastic Models 3 (1987), no.Β 2, 251β257. MR 903593, DOI 10.1080/15326348708807055
- Guy Latouche and V. Ramaswami, A logarithmic reduction algorithm for quasi-birth-death processes, J. Appl. Probab. 30 (1993), no.Β 3, 650β674. MR 1232742, DOI 10.2307/3214773
- G. Latouche and V. Ramaswami, Introduction to matrix analytic methods in stochastic modeling, ASA-SIAM Series on Statistics and Applied Probability, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; American Statistical Association, Alexandria, VA, 1999. MR 1674122, DOI 10.1137/1.9780898719734
- G. Latouche and G.W. Stewart, Numerical methods for M/G/1 type queues, Computations with Markov Chains (W. J. Stewart, ed.), Kluwer Academic Publishers, 1995, pp. 571β581.
- Beatrice Meini, New convergence results on functional iteration techniques for the numerical solution of $M/G/1$ type Markov chains, Numer. Math. 78 (1997), no.Β 1, 39β58. MR 1483568, DOI 10.1007/s002110050303
- M. Miranda and P. Tilli, Block Toeplitz matrices and preconditioning, Calcolo 33 (1996), no.Β 1-2, 79β86 (1998). Toeplitz matrices: structures, algorithms and applications (Cortona, 1996). MR 1632462, DOI 10.1007/BF02575709
- M. Miranda and P. Tilli, Asymptotic spectra of Hermitian block Toeplitz matrices and preconditioning results, SIAM J. Matrix Anal. Appl. 21 (2000), no.Β 3, 867β881. MR 1740877, DOI 10.1137/S0895479896313036
- Marcel F. Neuts, Matrix-geometric solutions in stochastic models, Johns Hopkins Series in the Mathematical Sciences, vol. 2, Johns Hopkins University Press, Baltimore, Md., 1981. An algorithmic approach. MR 618123
- Stefano Serra, Asymptotic results on the spectra of block Toeplitz preconditioned matrices, SIAM J. Matrix Anal. Appl. 20 (1999), no.Β 1, 31β44. MR 1644459, DOI 10.1137/S0895479896310160
- S. Serra, Spectral and computational analysis of block Toeplitz matrices having nonnegative definite matrix-valued generating functions, BIT 39 (1999), no.Β 1, 152β175. MR 1682396, DOI 10.1023/A:1022329526925
- Ronald L. Smith, Some interlacing properties of the Schur complement of a Hermitian matrix, Linear Algebra Appl. 177 (1992), 137β144. MR 1195974, DOI 10.1016/0024-3795(92)90321-Z
- P. Tilli, Asymptotic spectral distribution of Toeplitz-related matrices, Fast reliable algorithms for matrices with structure (T. Kailath and A. H. Sayed, eds.), SIAM, Philadelphia, 1999, pp. 153β187.
- Xingzhi Zhan, Computing the extremal positive definite solutions of a matrix equation, SIAM J. Sci. Comput. 17 (1996), no.Β 5, 1167β1174. MR 1404867, DOI 10.1137/S1064827594277041
- Xingzhi Zhan and Jianjun Xie, On the matrix equation $X+A^{\mathsf T}X^{-1}A=I$, Linear Algebra Appl. 247 (1996), 337β345. MR 1412759, DOI 10.1016/0024-3795(95)00120-4
Additional Information
- Beatrice Meini
- Affiliation: Dipartimento di Matematica, UniversitΓ di Pisa, via Buonarroti 2, 56127 Pisa, Italy
- Email: meini@dm.unipi.it
- Received by editor(s): January 25, 2000
- Received by editor(s) in revised form: September 19, 2000
- Published electronically: November 20, 2001
- © Copyright 2001 American Mathematical Society
- Journal: Math. Comp. 71 (2002), 1189-1204
- MSC (2000): Primary 15A24; Secondary 65F10, 65H05
- DOI: https://doi.org/10.1090/S0025-5718-01-01368-0
- MathSciNet review: 1898750