登录  /  注册

随机矩阵( stochastic matrix)

坏嘻嘻
发布: 2018-09-14 10:53:13
原创
3314人浏览过

本文实例讲述了随机矩阵。分享给大家供大家参考,具体如下:

随机矩阵(stochastic matrix)

      最近一个月来一直在看Google排序的核心算法---PageRank排序算法[1][2],在多篇论文中涉及到图论、马尔可夫链的相关性质说明与应用[3][4][5],而最为关键,一直让我迷惑的一句话是"A stochastic matrix has principal/primary eigenvalue 1"[3][4][5][6][7][8]。可能对于系统学习过矩阵理论的人,它很平淡,不值得单独拿出来讨论或者说明。而我在此不得不承认自己的无知。尽管在高等代数中学习过关于矩阵性质的一些讨论,但从来没有接触过所谓的随机矩阵(Stochastic Matrix),更不要说其性质了。于是,我从网上努力的寻找相关文献,但结果不是特别理想,并没有关于随机矩阵的详细介绍以及相关性质的证明。我想也许一方面是我搜索技术还不成熟,或者是搜索的关键词不准确,亦或者是网上关于它的资料本就很缺乏。在这里我想将最近搜集的相关资料拿出来整理一下思路,以备将来之用,也是对自己学习的一个真实记录和督促。

 随机矩阵实际上是非负矩阵(Nonnegative matrix)的一类,而非负矩阵是指矩阵元素都是非负(Nonnegative)的,当然非负要与正矩阵(Positive matrix)进行细微的区分。非负矩阵在计算数学、图论、线性规划、自动控制等领域有着广泛的应用,对其特征值,尤其是最大特征值(注意这里的最大是从模的角度或者说是绝对值概念上的最大)特征值,也就是矩阵的主特征值(principal/primary eigenvalue)的估计有很重要的意义[9]。

       随机矩阵说来如此之重要,那么到底什么样的矩阵才是随机矩阵呢?假如随便给你一个非负矩阵,该如何判定它是否属于随机矩阵呢?

       随机矩阵实际上应当分成行随机矩阵(Row stochastic matrix)和列随机矩阵(Column stochastic matrix)。行随机矩阵是指方阵的行和等于1;而列随机矩阵就是其列和等于1的非负矩阵。那么同时满足行和列和都是1的非负矩阵就是双随机矩阵(Double stochastic matrix),单位矩阵就是一种双随机矩阵。从研究的角度,其实只要研究行矩阵的性质即可,毕竟列随机矩阵只是行随机矩阵的转置矩阵。因此以下的讨论完全从行随机矩阵出发。

       既然随机矩阵A行和为1,那么假设e=(1,1,...,1),则e的转置向量e',即是矩阵的一个特征向量,对应于A的特征值1。这样对于证明随机矩阵的主特征值是1还有一定的距离。假设A的n个特征值为λ(i),其中i=1,2,...,n;若要证明性质成立,则必须证明|λ(i)|

       于是我又查找了相关资料,并在“数学博士论坛”发帖请教,得到的回复是要证明它,粗略地讲利用圆盘定理即可,若要精细的证明还要利用Perron-Frobenius Theorm[9][10][11][12]。一个个新的概念和方法出现在面前,看来需要系统的学习数值方法、数值计算理论。查找到的资料[10]表明任何矩阵的谱半径都不大于该矩阵任意诱导矩阵范数,而随机矩阵的L1-Norm值是1,那么谱半径(是主特征值的等价说法)不大于1,而由于1是A的一个特征值,那么就不可能出现绝对值大于1的特征值了:1确实是随机矩阵A的主特征值。

   那么对上述性质的证明就等价于证明资料[10]中的结论了。

    其实,“任意复数域上的矩阵的谱半径不大于其任意一种诱导范数”只是矩阵的一个基本的性质。其具体证明见下图:

     18091619-08cd09913b9c44229a69507e2c9c3480.gif

   根据以上的证明结果可知,对任意的行随机矩阵,其谱半径是1,即最大特征值是1得证。

   由此可知,其实矩阵的一个小小的性质对于没有系统学习过矩阵理论的人有时确实是一个难题。要入行,就当懂行规,要入门,就当精通门路。

   随机矩阵的主特征值以及second largest eigenvalue的比值是幂法收敛速度的一个基本的衡量标准。PageRank的计算有多种方式,而对此的研究也是不计其数,当然最传统的还是利用幂法来确定抓取入库的各网页的PageRank值。由于web网页的数量巨大,针对幂法收敛速度的考虑就不是多余无用的分析。而两特征值的“谱隙”(Eigengap)主要用来衡量利用幂法求解得到的PR值的稳定性的。由此看来,特征值分析对于理解PageRank算法起到关键作用。

相关推荐:

php版螺旋矩阵(由里到外)

PHP实现N*M的字符矩阵90度旋转

以上就是随机矩阵( stochastic matrix)的详细内容,更多请关注php中文网其它相关文章!

智能AI问答
PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
相关标签:
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号