Mathematics of Computation

Efficient computation of the extreme solutions of $X+A^*X^{-1}A=Q$ and $X-A^*X^{-1}A=Q$

Author(s): Beatrice Meini.
Journal: Math. Comp. 71 (2002), 1189-1204.
MSC (2000): Primary 15A24; Secondary 65F10, 65H05
Posted: November 20, 2001
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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.

1.: N. Akar and K. Sohraby, An invariant subspace approach in M/G/1 and G/M/1 type Markov chains, Commun. Statist. Stochastic Models 13 (1997), 381-416. MR 98a:60091
2.: 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 91c:47031
3.: D. A. Bini, L. Gemignani, and B. Meini, Computations with infinite Toeplitz matrices and polynomials, Linear Algebra Appl., to appear.
4.: -, Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations, Numer. Math. 89 (2001), 49-82.
5.: D. A. Bini and B. Meini, On the solution of a nonlinear matrix equation arising in queueing problems, SIAM J. Matrix Anal. Appl. 17 (1996), 906-926. MR 97g:15015
6.: -, Improved cyclic reduction for solving queueing problems, Numerical Algorithms 15 (1997), 57-74. MR 98i:65125
7.: -, Effective methods for solving banded Toeplitz systems, SIAM J. Matrix Anal. Appl. 20 (1999), 700-719. MR 2000a:15002
8.: 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. CMP 90:03
9.: J. C. Engwerda, On the existence of a positive definite solution of the matrix equation $X+A^TX^{-1}A=I$ , Linear Algebra Appl. 194 (1993), 91-108. MR 94j:15013
10.: J. C. Engwerda, A. C. M. Ran, and A. 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 94j:15012
11.: A. Ferrante and B. C. Levy, Hermitian solutions of the equation $X=Q+NX^{-1}N^*$ , Linear Algebra Appl. 247 (1996), 359-373. MR 97m:93071
12.: J. D. Gardiner, A. J. Laub, J. J. Amato, and C. B. Moler, Solution of the Sylvester matrix equation , ACM Trans. Math. Software 18 (1992), 223-231. CMP 92:13
13.: G.H. Golub and C.F. Van Loan, Matrix computations, The Johns Hopkins University Press, Baltimore, 1989. MR 90d:65055
14.: C.-H. Guo, Newtons'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), 279-294. MR 99j:65086
15.: C.-H. Guo and P. Lancaster, Iterative solution of two matrix equations, Math. Comp. 68 (1999), 1589-1603. MR 99m:65061
16.: G. Latouche, A note on two matrices occurring in the solution of quasi-birth-and-death processes, Commun. Statist. Stochastic Models 3 (1987), 251-257. MR 89d:60151
17.: G. Latouche and V. Ramaswami, A logarithmic reduction algorithm for Quasi-Birth-Death processes, J. Appl. Probability 30 (1993), 650-674. MR 94c:60159
18.: G. Latouche and V. Ramaswami, Introduction to matrix analytic methods in stochastic modeling, ASA-SIAM Series on Statistics and Applied Probability 5, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. MR 2000b:60224
19.: 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.
20.: B. Meini, New convergence results on functional iteration techniques for the numerical solution of M/G/1 type Markov chains, Numer. Math. 78 (1997), 39-58. MR 98g:60122
21.: 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 99e:65079
22.: -, Asymptotic spectra of Hermitian block Toeplitz matrices and preconditioning results, SIAM J. Matrix Anal. Appl. 21 (2000), no. 3, 867-881 (electronic). MR 2001a:65031
23.: M. F. Neuts, Matrix-geometric solutions in stochastic models: An algorithmic approach, The Johns Hopkins University Press, Baltimore, MD, 1981. MR 82j:60177
24.: S. Serra, Asymptotic results on the spectra of block Toeplitz preconditioned matrices, SIAM J. Matrix Anal. Appl. 20 (1999), no. 1, 31-44 (electronic). MR 99k:65039
25.: -, Spectral and computational analysis of block Toeplitz matrices having nonnegative definite matrix-valued generating functions, BIT 39 (1999), no. 1, 152-175. MR 2000a:65057
26.: R. L. Smith, Some interlacing properties of the Schur complement of a Hermitian matrix, Linear Algebra Appl. 177 (1992), 137-144. MR 93j:15018
27.: 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. CMP 2000:02
28.: X. Zhan, Computing the extremal positive definite solutions of a matrix equation, SIAM J. Sci. Comput. 17 (1996), 1167-1174. MR 97g:65074
29.: X. Zhan and J. Xie, On the matrix equation $X+A^T X^{-1} A=I$ , Linear Algebra Appl. 247 (1996), 337-345. MR 97k:15036

Retrieve articles in Mathematics of Computation with MSC (2000): 15A24, 65F10, 65H05

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS