On a direct method for the solution of nearly uncoupled Markov chains

DOI10.1007/BF01385767MaRDI QIDQ911215zbMATH OpenFDO

Authors N. E. Zubov

Publication date 1991

Published in Numerische Mathematik (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/133536

zbMATH Keywords

condition numbersdiagonal pivotingdirect methodGaussian eliminationLU decompositionnearly uncoupled Markov chainsrounding errors

Mathematics Subject Classification ID

Stochastic matrices (15B51) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Direct numerical methods for linear systems and matrix inversion (65F05) Roundoff error (65G50)

Review text

This note is concerned with the accuracy of the solution of nearly uncoupled Markov chains by a direct method based on the LU decomposition. It is shown that plain Gaussian elimination may fail in the presence of rounding errors. A modification of Gaussian elimination with diagonal pivoting and correction of small pivots is proposed and analyzed. It is shown that the accuracy of the solution is affected by two condition numbers associate with aggregation and the coupling respectively.

Recommendations

• Perturbation results for nearly uncoupled Markov chains with applications to iterative methods
• scientific article; zbMATH DE number 663840
• On the Sensitivity of the Solution of Nearly Uncoupled Markov Chains
• Iterative aggregation/disaggregation techniques for nearly uncoupled markov chains
• Comparison of Some Direct Methods for Computing Stationary Distributions of Markov Chains

Cites work

• Comparison of Some Direct Methods for Computing Stationary Distributions of Markov Chains
• Computable Error Bounds for Aggregated Markov Chains
• scientific article; zbMATH DE number 3760340 (Why is no real title available?)
• scientific article; zbMATH DE number 19231 (Why is no real title available?)
• scientific article; zbMATH DE number 3473182 (Why is no real title available?)
• scientific article; zbMATH DE number 3408799 (Why is no real title available?)
• LU decomposition of M-matrices by elimination without pivoting
• On the Smallest Positive Singular Value of a Singular M-Matrix with Applications to Ergodic Markov Chains
• Regenerative Analysis and Steady State Distributions for Markov Chains
• Solution of Homogeneous Systems of Linear Equations Arising from Compartmental Models

Cited in

(12)

• Optimizing steady state Markov chains by state reduction
• Perturbation results for nearly uncoupled Markov chains with applications to iterative methods
• Entrywise perturbation theory and error analysis for Markov chains
• A direct projection method for Markov chains
• A combinatorial approach to nearly uncoupled Markov chains. I: Reversible Markov chains
• Asymptotic expansions for stationary distributions of perturbed semi-Markov processes
• Error Bounds for the Computation of Null Vectors with Applications to Markov Chains
• On the Sensitivity of the Solution of Nearly Uncoupled Markov Chains
• Influence of Preconditioning and Blocking on Accuracy in Solving Markovian Models
• Comparison of Some Direct Methods for Computing Stationary Distributions of Markov Chains
• Uncoupling Measures and Eigenvalues of Stochastic Matrices
• An iterative aggregation/disaggregation procedure for modelling the long-term behaviour of continuous-time evanescent random processes

This page was built for publication: On a direct method for the solution of nearly uncoupled Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911215)