Efficient computation of the extreme solutions of 𝑋+𝐴*𝑋⁻¹𝐴=𝑄 and 𝑋-𝐴*𝑋⁻¹𝐴=𝑄

Meini, Beatrice

doi:10.1090/S0025-5718-01-01368-0

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