Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

Iterative and semi-iterative methods for computing stationary probability vectors of Markov operators


Authors: Ivo Marek and Daniel B. Szyld
Journal: Math. Comp. 61 (1993), 719-731
MSC: Primary 65J10; Secondary 15A48, 47A50, 47B65, 60J10
MathSciNet review: 1192973
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Iterative and semi-iterative methods for computing stationary probability vectors of Markov-type operators are proposed and their convergence properties are analyzed. The methods studied apply to certain classes of problems in infinite-dimensional spaces as well as to classical $ n \times n$ stochastic matrices.


References [Enhancements On Off] (What's this?)

  • [1] G. P. Barker and S.-J. Yang, Semi-iterative and iterative methods for singular 𝑀-matrices, SIAM J. Matrix Anal. Appl. 9 (1988), no. 2, 168–180. MR 938496, 10.1137/0609014
  • [2] G. P. Barker and R. J. Plemmons, Convergent iterations for computing stationary distributions of Markov chains, SIAM J. Algebraic Discrete Methods 7 (1986), no. 3, 390–398. MR 844041, 10.1137/0607044
  • [3] V. A. Barker, Numerical solution of sparse singular systems of equations arising from ergodic Markov chains, Comm. Statist. Stochastic Models 5 (1989), no. 3, 335–381. MR 1010533, 10.1080/15326348908807115
  • [4] Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1979. Computer Science and Applied Mathematics. MR 544666
  • [5] E. B. Dynkin, Markov processes. Vols. I, II, Translated with the authorization and assistance of the author by J. Fabius, V. Greenberg, A. Maitra, G. Majone. Die Grundlehren der Mathematischen Wissenschaften, Bände 121, vol. 122, Academic Press Inc., Publishers, New York; Springer-Verlag, Berlin-Göttingen-Heidelberg, 1965. MR 0193671
  • [6] Michael Eiermann, Ivo Marek, and Wilhelm Niethammer, On the solution of singular linear systems of algebraic equations by semi-iterative methods, Numer. Math. 53 (1988), no. 3, 265–283. MR 948587, 10.1007/BF01404464
  • [7] Michael Eiermann and Wilhelm Niethammer, On the construction of semi-iterative methods, SIAM J. Numer. Anal. 20 (1983), no. 6, 1153–1160. MR 723832, 10.1137/0720085
  • [8] M. Eiermann, W. Niethammer, and R. S. Varga, A study of semi-iterative methods for nonsymmetric systems of linear equations, Numer. Math. 47 (1985), no. 4, 505–533. MR 812617, 10.1007/BF01389454
  • [9] F. R. Gantmacher, The theory of matrices, Goz. Izdat. Lit., Moscow, 1954; English transl., Applications of the theory of matrices, Interscience, New York, 1959.
  • [10] Halim D. Kafeety, Carl D. Meyer, and William J. Stewart, A general framework for iterative aggregation/disaggregation methods for the numerical solution of Markov chains, Technical Report No. 06039101, Center for Research in Scientific Computation, North Carolina State University, Raleigh, North Carolina, November 1990. (See also the Proceedings of the Copper Mountain Conference on Iterative Methods (Copper Mountain, Colorado, April 9-14, 1992), Computational Mathematics Group, University of Colorado at Denver, 1992.)
  • [11] M. G. Krein and M. A. Rutman, Linear operators leaving a cone invariant in a Banach space, Uspekhi Mat. Nauk 3 (1948), no. 1, 3-95; English transl., Amer. Math. Soc. Transl. 26 (1950).
  • [12] Walter Ledermann and Steven Vajda (eds.), Handbook of applicable mathematics. Vol. IV, John Wiley & Sons, Ltd., Chichester, 1982. Analysis; A Wiley-Interscience Publication. MR 667016
  • [13] Vladimír Lelek and Ivo Marek, Data fitting under eigenvalue constraints, Proceedings of the 9th Conference on Problems and Methods in Mathematical Physics (9.TMP) (Karl-Marx-Stadt, 1988) Teubner-Texte Math., vol. 111, Teubner, Leipzig, 1989, pp. 159–166. MR 1087318
  • [14] Ivo Marek, Aggregation methods of computing stationary distributions of Markov processes, Numerical treatment of eigenvalue problems, Vol. 5 (Oberwolfach, 1990), Internat. Ser. Numer. Math., vol. 96, Birkhäuser, Basel, 1991, pp. 155–169. MR 1109102, 10.1007/978-3-0348-6332-2_12
  • [15] -, On square roots of M-operators, Linear Algebra Appl. (submitted).
  • [16] Ivo Marek and Daniel B. Szyld, Comparison theorems for weak splittings of bounded operators, Numer. Math. 58 (1990), no. 4, 387–397. MR 1077585, 10.1007/BF01385632
  • [17] Ivo Marek and Daniel B. Szyld, Splittings of 𝑀-operators: irreducibility and the index of the iteration operator, Numer. Funct. Anal. Optim. 11 (1990), no. 5-6, 529–553. MR 1079290, 10.1080/01630569008816387
  • [18] -, Iterative aggregation with inexact correction, Technical Report no. 91-52, Department of Mathematics, Temple University, May 1991.
  • [19] Ivo Marek and Karel Žitný, Equivalence of 𝐾-irreducibility concepts, Comment. Math. Univ. Carolin. 25 (1984), no. 1, 61–72. MR 749116
  • [20] M. Z. Nashed, Generalized inverses, normal solvability, and iteration for singular operator equations, Nonlinear Functional Anal. and Appl. (Proc. Advanced Sem., Math. Res. Center, Univ. of Wisconsin, Madison, Wis., 1970) Academic Press, New York, 1971, pp. 311–359. MR 0275246
  • [21] W. Niethammer and R. S. Varga, The analysis of 𝑘-step iterative methods for linear systems from summability theory, Numer. Math. 41 (1983), no. 2, 177–206. MR 703121, 10.1007/BF01390212
  • [22] Donald J. Rose, Convergent regular splittings for singular 𝑀-matrices, SIAM J. Algebraic Discrete Methods 5 (1984), no. 1, 133–144. MR 731863, 10.1137/0605015
  • [23] Uriel G. Rothblum, Algebraic eigenspaces of nonnegative matrices, Linear Algebra and Appl. 12 (1975), no. 3, 281–292. MR 0404298
  • [24] Uriel G. Rothblum, Convergence properties of powers of matrices with applications to iterative methods for solving linear systems, Extremal methods and systems analysis (Internat. Sympos., Univ. Texas, Austin, Tex., 1977) Lecture Notes in Econom. and Math. Systems, vol. 174, Springer, Berlin-New York, 1980, pp. 231–247. MR 563868
  • [25] Ikuko Sawashima, On spectral properties of some positive operators, Natur. Sci. Rep. Ochanomizu Univ. 15 (1964), 53–64. MR 0187096
  • [26] Paul J. Schweitzer, A survey of aggregation-disaggregation in large Markov chains, Numerical solution of Markov chains, Probab. Pure Appl., vol. 8, Dekker, New York, 1991, pp. 63–88. MR 1142109
  • [27] Kunio Tanabe, The conjugate gradient method for computing all the extremal stationary probability vectors of a stochastic matrix, Ann. Inst. Statist. Math. 37 (1985), no. 1, 173–187. MR 790385, 10.1007/BF02481090
  • [28] Angus E. Taylor, Introduction to functional analysis, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1958. MR 0098966
  • [29] Richard S. Varga, Factorization and normalized iterative methods, Boundary problems in differential equations, Univ. of Wisconsin Press, Madison, Wis., 1960, pp. 121–142. MR 0121977
  • [30] Richard S. Varga, Matrix iterative analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR 0158502

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65J10, 15A48, 47A50, 47B65, 60J10

Retrieve articles in all journals with MSC: 65J10, 15A48, 47A50, 47B65, 60J10


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1993-1192973-1
Keywords: $ \mathcal{K}$-stochastic operators, Markov type operators, stationary probability vectors, iterative methods, semi-iterative methods
Article copyright: © Copyright 1993 American Mathematical Society