Remote Access Mathematics of Computation
Green Open Access

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

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 M-matrices, SIAM J. Matrix Anal. Appl. 9 (1988), 168-180. MR 938496 (89d:65034)
  • [2] George P. Barker and Robert J. Plemmons, Convergent iterations for computing stationary distributions of Markov chains, SIAM J. Algebraic Discrete Methods 7 (1986), 390-398. MR 844041 (87k:65034)
  • [3] V. A. Barker, Numerical solution of sparse singular systems of equations arising from ergodic Markov chains, Comm. Statist. Stochastic Models 5 (1989), 335-381. MR 1010533 (91a:65112)
  • [4] Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, Academic Press, New York, 1979. MR 544666 (82b:15013)
  • [5] Eugene B. Dynkin, Markov processes, Vols. I, II, Springer-Verlag, Berlin, 1965. MR 0193671 (33:1887)
  • [6] Michael Eiermann, Ivo Marek, and Wilhelm Niethammer, On the solution of singular linear systems of algebraic equations by semiiterative methods, Numer. Math. 53 (1988), 265-283. MR 948587 (89h:65049)
  • [7] Michael Eiermann and Wilhelm Niethammer, On the construction of semiiterative methods, SIAM J. Numer. Anal. 20 (1983), 1153-1160. MR 723832 (85f:65032)
  • [8] Michael Eiermann, Wilhelm Niethammer, and Richard S. Varga, A study of semiiterative methods for nonsymmetric systems of linear equations, Numer. Math. 47 (1985), 505-533. MR 812617 (87d:65034)
  • [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] W. Ledermann and Steven Vajda, eds., Handbook of applicable mathematics, Vol. IV. Analysis. Wiley Interscience, Chichester, New York, Brisbane, Toronto, and Singapore, 1982. MR 667016 (84f:00005)
  • [13] Vladimir Lelek and Ivo Marek, Data fitting under eigenvalue constraints, Proc. Ninth Tagung über Probleme und Methoden der Mathematischen Physik (F. Kuhnert and B. Silbermann, eds.), Karl Marx-Stadt, 1988, pp. 159-166. MR 1087318
  • [14] Ivo Marek, Aggregation methods of computing stationary distribution of Markov processes, Eigenvalue Problems and their Numerical Treatment (W. Velte, ed.), Proc. Conf. (Mathematisches Forschunginstitut Oberwolfach, February 26-March 2, 1990), Internat. Ser. Numer. Math. (ISNM), vol. 96, Birkhäuser, Basel, 1991, pp. 155-169. MR 1109102 (92g:65148)
  • [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), 387-397. MR 1077585 (92f:65070)
  • [17] -, Splittings of M-operators: Irreducibility and the index of the iteration operator, Numer. Funct. Anal. Optim. 11 (1990), 529-553. MR 1079290 (92f:65069)
  • [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 K-irreducibility concepts, Comment. Math. Univ. Carolinae 25 (1984), 61-72. MR 749116 (85k:47071)
  • [20] M. Z. Nashed, Generalized inverses, normal solvability and iteration for singular operator equations, Nonlinear Functional Analysis and Applications (M. Z. Nashed, ed.), Academic Press, New York, 1971, pp. 311-359. MR 0275246 (43:1003)
  • [21] Wilhelm Niethammer and Richard S. Varga, The analysis of k-step iterative methods for linear systems from summability theory, Numer. Math. 41 (1983), 177-206. MR 703121 (85a:65059)
  • [22] Donald J. Rose, Convergent regular splittings for singular M-matrices, SIAM J. Algebraic Discrete Methods 5 (1984), 133-144. MR 731863 (85h:65074)
  • [23] Uriel G. Rothblum, Algebraic eigenspaces of nonnegative matrices, Linear Algebra Appl. 12 (1975), 281-292. MR 0404298 (53:8100)
  • [24] -, Convergence properties of powers of matrices with applications to iterative methods for solving linear systems, Extremal Methods and Systems Analysis (Anthony V. Fiacco and Kenneth O. Kortanek, eds.), An International Symposium on the Occasion of Professor Abraham Charnes' Sixtieth Birthday (Austin, Texas, 1977), Lecture Notes in Econom. and Math. Systems, vol. 174, Springer Verlag, Berlin, Heidelberg, and New York, 1980, pp. 231-247. MR 563868 (83e:65066)
  • [25] Ikuko Sawashima, On spectral properties of some positive operators, Nat. Sci. Rep., Ochanomizu Univ. 15 (1964), 53-64. MR 0187096 (32:4550)
  • [26] Paul J. Schweitzer, A survey of aggregation-disaggregation in large Markov chains, Numerical Solution of Markov Chains (William J. Stewart, ed.), Marcel Dekker, New York, Basel, and Hong Kong, 1991, pp. 63-88. MR 1142109
  • [27] Kunio Tanabe, The conjugate gradient method for computing all extremal stationary probability vectors of a stochastic matrix, Ann. Inst. Statist. Math. B 37 (1985), 173-187. MR 790385 (86j:60155)
  • [28] Angus E. Taylor, Introduction to functional analysis, Wiley, New York, 1958. MR 0098966 (20:5411)
  • [29] Richard S. Varga, Factorization and normalized iterative methods, Boundary Problems in Differential Equations (Rudolph E. Langer, ed.), Univ. of Wisconsin Press, Madison, WI, 1960, pp. 121-142. MR 0121977 (22:12704)
  • [30] -, Matrix iterative analysis, Prentice-Hall, Englewood Cliffs, NJ, 1962. MR 0158502 (28:1725)

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

Keywords: $ \mathcal{K}$-stochastic operators, Markov type operators, stationary probability vectors, iterative methods, semi-iterative methods
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society