英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
《信息与计算科学》专业
本科毕业论文
外文资料翻译
原文名称Xie-Ma2018_Article_ARelaxedTwo-stepSplittingItera
原文作者 Ya-Jun Xie1 · Chang-Feng Ma2
原文出版物copy; SBMAC - Sociedade Brasileira de Matemaacute;tica Aplicada e Computacional 2016
计算PageRank的松弛两步分裂迭代法
谢亚军1马长风2·
接收日期：2015年11月18日/修订日期：2016年3月21日/接受日期：2016年4月1日/
在线发布：2016年4月21日
copy;SBMAC-巴西材料协会2016
摘要：本文通过引入一个新的松弛参数，扩展了两步矩阵分裂迭代法。其主要思想是基于Gleich等人（J Sci Comput 32（1）：349–371，2010）和Bai（Numer Algebra Cont Optim 2（4）：855–862，2012）提出的求解PageRank问题的内外迭代和Gu等人（Appl Math Comput 271:337–343，2015）提出的两步分裂迭代。理论分析结果表明，该方法是有效的。数值实验表明，该方法的收敛性能优于现有方法。
关键词：两步分裂迭代·内外迭代·松弛参数·PageRank·数值试验
数学学科分类：65F10·65F30型
1 介绍
考虑特征值问题的解，其形式如下：
通讯员:金云园。
该项目得到了国家自然科学基金（11071041、11201074）、福建省自然科学基金（2016J01005、2015J01578）、福建省高校优秀青年培养计划（15kxtz13、2015）的资助。
马长峰邮箱：macf@fjnu.edu.cn
1 福建江夏大学数学与物理系，福州350108，中国
2 福建师范大学数学与计算机学院，福州350117，中国
如果P是具有适当维数的列随机矩阵，即其条目为非负实数，且其所有列之和为一。alpha;isin;（0,1）表示阻尼因子，它决定了给定给Web链接图的权重。e是一个包含所有1的列向量，v是一个个性化向量或隐形传态向量。x是要确定的特征向量。
当没有人根据网页的图形来确定网页的重要性时，就会出现所谓的页面rank问题，即abvelinearsystem（1.1）。PageRank可以看作是马尔可夫链的平稳分布（Langville和Meyer 2005）。随着互联网的飞速发展，PageRank作为搜索引擎技术的一部分已经被Google广泛利用。虽然Google所采用的精确排序技术和计算方法已经逐渐得到改进，但PageRank方法仍然受到人们的广泛关注，成为近年来科学与工程计算领域的一个热点问题。
目前求解模型（1.1）的方法可分为直接法和迭代法。直接法往往需要大量的填充元素存储，特别是当系数矩阵和条件数很大时，直接法的稳定性较差。针对矩阵P的稀疏性，可以利用矩阵P的稀疏结构来减少存储空间和计算量。迭代法已成为求解特征值问题的一种常用方法。Sauer开发了计算PageRank的幂方法，因为它收敛于每一个非负起始向量的选择（Sauer 2005）。但是，当阻尼因子alpha;较大时，功率法容易导致收敛效率较低。提出了一种外推方法，通过计算并减去第二和第三特征向量的贡献估计来加速收敛（Kamvar等人，2003）。Kamvar等人（2004）还提出了一种改进PageRank计算的自适应方法，即每次迭代都不重新计算收敛的页面的PageRank。PageRanktype算法用于Web搜索以外的应用领域（Morrison et al.2005）。Capizzano考虑了Google矩阵的Jordan标准形式，这是PageRank计算的一个潜在贡献（Capizzano 2005）。Krylov子空间方法最近也被考虑。Jia提出了重新启动的改进Arnoldi方法（Jia 1997），它可以看作是Golub等人（2006）提出的Arnoldi型算法的变体。已经给出了许多方法；参见书（Langville and Meyer 2006），该书对PageRank问题进行了更全面的描述，论文（Bai et al.2004，1996；Bai 2012；Berkhin 2005；Gleich et al.2010；Langville and Meyer 2005，2006；Page et al.1999；Yin et al.2012；Golub and Van Loan 1996；Wu and Wei 2007；Kamvar et al.2007）al.2003；Huang and Ma 2015；Fan and Simpson 2015；Skardal et al.2015），其中包含许多额外的结果和有用的参考，以及包括马尔可夫链概述的书（Stewart 1994）。
Gu et al.（2015）基于Gleich et al.in（2010）和Bai in（2012）提出的内部-外部迭代（IOI）方法，开发了一种用于计算PageRank的两步矩阵分裂迭代（TSS）。受这些工作的启发，本文构造了一种新的计算PageRank的松弛两步分裂迭代法（RTSS），它是一种更有效、更灵活的方法。
论文的其余部分组织如下。在第2部分中，首先简要回顾了内外迭代法和两步矩阵分裂迭代法。另外，考虑一种新的计算PageRank（1.1）的放松两步分裂迭代方法。在第3部分，详细分析了算法的收敛性。第4部分，数值实验表明，该方法是有效的。最后，我们在以第五部分的一些结论结束论文。
2 RTSS方法
在本节中，我们将回顾计算PageRank问题的内-外迭代和两步矩阵分裂迭代方法。
很明显，特征向量问题（1.1）等价于求解下列线性系统
在这里，我用上下文中清楚的对应维度表示单位矩阵。
由（2.1）可知，阻尼参数alpha;越小，问题越容易解决。鉴于这一考虑，Gleich等人提出了求解系统的内外迭代方法（2.1）（Gleich等人，2010）。现在，我们简要回顾一下这种方法。
（2.1）的系数矩阵可以写成：
其中M1 = I minus; beta; P, N1 = (alpha; minus; beta;)P。然后，给出（2.1）的不动点方程
所以平稳外迭代格式
其中0lt;beta;lt;alpha;。此外，内部Richardson迭代
被认为加速了外部迭代，其中f = (alpha; minus; beta;)Pxk (1 minus; alpha;)v, j = 0, 1, 2 ...,l minus; 1, y0 = xk第l步内解y被指定为下一个新的xk 1，内-外迭代法如下算法2.1所示。
算法2.1（内-外迭代法）
第1步输入P，alpha;，beta;，v，tau;，eta;。计算x0 = v, z0 = Px0。设置k := 0。
第2步如果,更新
否则，转至步骤3.
第3步更新
直到,转到步骤4.
第4步设置k：=k 1，返回步骤2。
Gu等人在内外迭代法的基础上，提出了PageRank的两步分裂迭代法（TSS），它与幂法和Richardson迭代法密切相关。
如下面的算法2.2所示
算法2.2（两步分裂迭代法）
第1步输入P , alpha;, beta;, v, tau;, eta;。计算x0 = v, z0 = Px0. Set k := 0设置k:=0。
第2步如果更新
否则，转至步骤3.
第3步更新
直到转到步骤4.
第4步设置k：=k 1，返回步骤2。
实际上，在算法2.1中IOI方法的第2步计算向量f之前，考虑了迭代更新（2.3）。结果表明，TSS方法比IOI方法具有更好的性能。受Gleich等人（2010）、Gu等人（2015）的启发，我们通过引入一个新的松弛参数gamma;来进一步考虑这些方法，它可以在一定程度上加速TSS方法。特别地，TSS方法只涉及平稳外迭代格式，即内迭代必须是精确迭代。在算法2.2中，内环是一个不精确的迭代。Gu等人（2015）的定理2证明了TSS方法的收敛性；然而，导致算法2.2的内环是一个非平稳迭代，这一点被忽略了。因此，在本文中，我们将详细讨论这一情况。
现在，我们考虑系数矩阵A，如下所示：
其中M2 = gamma; I minus; beta; P, N2 = (gamma; minus; 1)I (alpha; minus; beta;) P,gamma; gt; 0。算法2.3描述了松弛的两步分裂迭代。
算法2.3（松弛两步分裂迭代法）
第1步输入P, alpha;, beta;, gamma;, v, tau;, eta;。计算x0 = v, z0 = Px0= 0。设置k:=0。
第2步如果更新
否则，转至步骤3.
第3步更新
直到转到步骤4.
第4步设置k：=k 1，返回步骤2。
备注2.1事实上，如果我们设置gamma;=1，则RTSS被简化为TSS，因此RTSS方法是TSS方法的一个推广版本。RTSS松弛参数gamma;的灵活选择比TSS方法具有更好的收敛性能，这在我们的数值试验部分可以看到。
备注2.2算法2.3由平稳迭代格式生成，因此可以扩展到研究绝对值方程（AVE）Ax |x |=b（Mangasarian and Meyer 2006；Rohn 2012；Moosaei et al.2015；Yong 2016；Yong et al.2011），也可以用平稳方程的形式表示。AVE的重要性源于这样一个事实：二次规划、线性规划、双矩阵对策和许多其他问题都可以归结为一个线性互补问题（LCP）（Cottle and Dantzig 1968；Cottle et al.1992），它等价于AVE。此外，我们知道AVE是NP难的。在（Mangasarian 2007）中，通过将NP难背包可行性问题对应的LCP降到平均值，证明了这一点。在适当的假设条件下，如系数矩阵A的奇异值超过1时，可以使用一些有效的方法来解决该问题，如广义牛顿法。在今后的工作中，我们将致力于用本文提出的方法或改进的方法来研究AVE。
3 收敛性
在本节中，我们将详细讨论算法2.3的收敛性。为此，
我们将算法2.3重写如下：
定理3.1Let参数0 lt;beta;lt;alpha;lt;gamma;le;1和1minus;alpha;lt;gamma;，mk是内环
第k次外部迭代的数字。算法2
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[262208]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
