马尔科夫链问题中的Bi-CG与Bi-CR共轭方向算法对比

62 浏览量更新于2024-07-16 收藏 203KB PDF 举报

本文探讨了"比较应用于马尔科夫链问题的两个共轭方向算法"，由文春和黄廷祝两位作者在电子科技大学数学科学学院撰写。他们的研究受到了Sogabe、Sugihara和Zhang在2009年发表在《计算应用数学》(Journal of Computational and Applied Mathematics)上的工作启发，该文献扩展了共轭残差法在非对称线性系统中的应用。文章的核心焦点在于介绍和比较Bi-CG（双共轭梯度）算法和Bi-CR（双共轭残差）算法，这两种方法都是在共轭梯度方法的基础上发展出来的。共轭梯度算法是一种有效的求解线性系统的方法，特别适用于处理对称正定矩阵。然而，当面临非对称线性系统时，传统的共轭梯度方法可能不再适用。Bi-CG和Bi-CR算法作为其变种，旨在解决这类问题，通过在Krylov子空间内构造适当的搜索方向来逼近解。Krylov子空间是矩阵与向量的迭代乘积构成的空间，对于求解大型线性系统的最优化问题具有重要意义。在本文中，作者试图将这些算法扩展到不可约马尔科夫链的问题上，马尔科夫链是一种随机过程，其状态之间的转移遵循一定的概率规则。平稳概率分布是马尔科夫链的一个关键概念，它描述了在无限时间后，链处于各个状态的概率分布。通过数值实验，作者展示了Bi-CG和Bi-CR算法在实际马尔科夫链问题上的有效性，并对它们的性能进行了对比分析。关键词包括Krylov子空间方法、共轭方向算法、马尔科夫链以及平稳概率分布，这些都是文章讨论的核心内容。文章的中图分类号指向了60J22（概率论与数理统计-应用概率）和65C40（计算数学-数值分析-线性代数），表明了研究内容的理论背景和应用领域。本文的主要贡献在于扩展了共轭方向方法在非对称线性系统及马尔科夫链问题中的应用，提供了两种新算法的详细描述，并通过实例验证了它们在求解相关问题上的实用性和优势。这对于理解和改进数值求解复杂动态系统的算法具有重要的学术价值。

˖ڍመ᝶஠ڙጲ

http://www.paper.edu.cn

The remainder of the paper is organized as follows. In Section 2, Markov chain modellings

are brieﬂy introduced. In Section 3, the Bi-CR and Bi-CG methods, with applications to

Markov chains, are given according to [18]. In Section 4, numerical experiments on several

Markov chains are made and a comparative analysis between the Bi-CR and Bi-CG methods

is given. Finally, conclusions are summarized in Section 5.

Throughout this paper, the following notations will be used:

: the transpose of the matrix A ∈ R

n×n

;

(x, y): the dot product given by x

y with x, y ∈ R

;

R(A): the range space of the matrix A;

N (A): the null space of the matrix A;

(A, r): the Krylov subspace generated by a vector r, i.e., K

(A, r) = span{r, Ar, ..., A

n−1

r};

k = index(A): the smallest nonnegative integer k with R(A

) = R(A

k+1

1 Markov chain modellings

In this section, Markov chain modellings which represent a class of singular systems are

brieﬂy introduced and certain related properties are presented.

Markov chains are one of the most important kinds of models in simulation. Generally s-

peaking, Markov chains are divided into discrete-time Markov chains (DTMCs) and continuous-

time Markov chains (CTMCs) [21] [22]. For a ﬁnite and irreducible Markov chain, there exists

a unique stationary probability distribution π whose elements are strictly greater than zero. If

the Markov chain is a DTMC, then it has

πP = π, π > 0, πe = 1, (2)

where P ∈ R

n×n

is a transition probability matrix, and e is a column vector with all elements

as one. This problem can be considered as an eigenvalue problem. If the Markov chain is a

CTMC, then we have

πQ = 0, π > 0, πe = 1, (3)

where Q ∈ R

n×n

is an inﬁnitesimal generator, and e is a column vector as above.

Observe that both the equations (2) and (3) may be put into the same form. Let I ∈ R

n×n

be an identity matrix, then the equations (2) may be rewritten as π(P − I) = 0, which has the

same form with (3). On the other hand, we may discrete a CTMC. From (3), we can have

π(Q△T + I) = π, π > 0, πe = 1, (4)

which has the same form with (2). In the discreted Markov chain, transitions take place at

interval △T , where △T is chosen suﬃciently small such that the probability of two transitions

- 3 -

剩余14页未读，继续阅读

weixin_38696339

粉丝: 4
资源: 908

马尔科夫链问题中的Bi-CG与Bi-CR共轭方向算法对比

A comparison of single-cell trajectory inference methods.pdf

A comparison of GPS-TEC with IRI-TEC at low latitudes in China in 2006

Transformation from hadronic to quark matter in neutron stars: a comparison of two scenarios

Measuring academic Self-Concept in children: A comparison of two scales

A statistical comparison of two recent musical aptitude tests

A comparison of the Vane Kindergarten Test with the WPPSI and a measure of Self-Control

School psychological services: An empirical comparison of two models

A comparison of three different measures of intelligence with preschool children identified at-risk

A Survey and Comparison of Time-Delay Estimation Methods in Linear Systems

Performance comparison of two on-demand routing protocols for ad hoc networks.pdf

最新资源