马尔科夫链与网页排序问题的数值算法研究

发布时间：2017-03-29 18:01

  本文关键词：马尔科夫链与网页排序问题的数值算法研究，由笔耕文化传播整理发布。

【摘要】：本文针对由离散时间马尔科夫链产生的线性代数系统和一般线性代数系统的数值求解问题,深入研究其迭代、加速和预处理等求解方法,并将这些新方法应用到网页排序问题求解中。研究了利用广义极小残量法求解大规模线性代数系统的问题,通过引入向量外推法改进迭代循环时的初值,达到加速的效果。然后研究了马尔科夫链问题求解的外推加速极小残量法。数值实验验证了加速算法能提高广义极小残量法的鲁棒性,并在计算时间和迭代次数等方面具有明显的加速效果。研究了马尔科夫链问题求解的代数多重网格法。鉴于在插值算子、限制算子和各层迭代矩阵的构造所需时间不可小觑,本文引入外推加速策略,通过对最细层的加速,改进了各层循环的初值,数值效果好。之后将这种新的加速的代数多重网格法用于网页排序问题求解,数值实验和比较结果验证了所提出的新算法具有比传统的网页排序算法更好的性能。研究了网页排序算法转化为线性代数系统求解的问题。针对阻尼因子接近1时重启的GMRES方法可能在该迭代系统中出现不收敛或崩溃的情形,提出了多项式右预处理策略,并给出了改进的新算法。随后,提出并证明了新算法的收敛性定理。另外,在预处理基础上进行了混合策略的加速并给出了相应算法。数值实验部分,首先验证了预处理技术能显著改善系数矩阵特征值的分布,同时从求解所需迭代次数、CPU时间等方面验证了预处理技术改进了算法的收敛性,提高了收敛速度。针对经典PageRank算法缺憾 平均分配权威值导致的搜索网页排序质量下降和可能引起的商业投机行为及网页作弊问题,本文提出了三种改进策略将网页的权威值按不同权重分配给它所外链接的网页,然后给出了基于链接的加权网页排序新算法,最后通过数值实验对新算法的有效性进行了验证。研究了线性代数系统的预处理问题,包括交替迭代和新型预处理子等的Gauss-Seidel预处理方法。从理论角度分析了预处理在改进收敛性方面的效果,数值实验进行了验证。
【关键词】：马尔科夫链 网页排序 线性代数系统 向量外推法 预处理
【学位授予单位】：电子科技大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O211.62;O241.8
【目录】：

• 摘要5-6
• ABSTRACT6-11
• 第一章 绪论11-20
• 1.1 研究背景和意义11-15
• 1.1.1 线性代数系统的求解11-12
• 1.1.2 马尔科夫链问题及网页排序问题的计算12-15
• 1.2 主要方法简介15-17
• 1.2.1 Krylov子空间方法15-16
• 1.2.2 预处理技术16-17
• 1.3 本文的主要工作和创新点17-18
• 1.4 本文的章节安排18-20
• 第二章 求解线性代数系统和马尔科夫链问题的外推加速广义极小残量法20-39
• 2.1 引言20-22
• 2.2 GMRES算法的向量外推加速策略22-30
• 2.2.1 向量外推法简介22-25
• 2.2.2 外推加速的GMRES算法25-27
• 2.2.3 数值实验27-30
• 2.3 求解马尔科夫链问题的外推加速GMRES方法30-37
• 2.3.1 马尔科夫链问题的外推加速GMRES算法30-33
• 2.3.2 数值实验33-37
• 2.4 本章小结37-39
• 第三章 代数多重网格方法及其应用39-53
• 3.1 引言39-42
• 3.2 AMG方法的加速及其在求解马尔科夫链问题中的应用42-47
• 3.2.1 求解马尔科夫链问题的AMG算法42-44
• 3.2.2 外推加速的代数多重网格法44-45
• 3.2.3 数值实验45-47
• 3.3 求解PageRank问题的代数多重网格法47-52
• 3.3.1 网页排序新算法的提出47-50
• 3.3.2 数值实验50-52
• 3.4 本章小结52-53
• 第四章 PageRank问题求解的多项式预处理和混合加速策略53-66
• 4.1 引言53-55
• 4.2 PageRank问题求解的多项式预处理55-59
• 4.2.1 算法提出55-56
• 4.2.2 收敛性分析56-57
• 4.2.3 数值实验57-59
• 4.3 PageRank问题求解的混合加速策略59-65
• 4.3.1 混合加速算法的提出59-61
• 4.3.2 数值实验61-65
• 4.4 本章小结65-66
• 第五章 基于链接的加权PageRank算法66-78
• 5.1 引言66-67
• 5.2 PageRank计算的加权策略及算法67-71
• 5.2.1 PageRank算法改进策略I68-70
• 5.2.2 PageRank算法改进策略II70
• 5.2.3 PageRank算法混合加权策略70-71
• 5.3 数值实验71-76
• 5.4 本章小结76-78
• 第六章 线性代数系统的预处理技术78-96
• 6.1 引言78-81
• 6.2 交替Gauss-Seidel预处理迭代81-86
• 6.2.1 预处理子的构建81-82
• 6.2.2 收敛性分析82-86
• 6.3 I+C+S型Gauss-Seidel预处理迭代86-89
• 6.4 数值实验89-92
• 6.5 本章小结92-96
• 第七章 总结与展望96-98
• 7.1 总结96
• 7.2 展望96-98
• 致谢98-99
• 参考文献99-109
• 攻博期间取得的研究成果109-110

  本文关键词：马尔科夫链与网页排序问题的数值算法研究，，由笔耕文化传播整理发布。

本文编号：275053