本文關(guān)鍵詞：馬爾科夫鏈與網(wǎng)頁排序問題的數(shù)值算法研究，由筆耕文化傳播整理發(fā)布。

【摘要】：本文針對由離散時間馬爾科夫鏈產(chǎn)生的線性代數(shù)系統(tǒng)和一般線性代數(shù)系統(tǒng)的數(shù)值求解問題,深入研究其迭代、加速和預(yù)處理等求解方法,并將這些新方法應(yīng)用到網(wǎng)頁排序問題求解中。研究了利用廣義極小殘量法求解大規(guī)模線性代數(shù)系統(tǒng)的問題,通過引入向量外推法改進迭代循環(huán)時的初值,達到加速的效果。然后研究了馬爾科夫鏈問題求解的外推加速極小殘量法。數(shù)值實驗驗證了加速算法能提高廣義極小殘量法的魯棒性,并在計算時間和迭代次數(shù)等方面具有明顯的加速效果。研究了馬爾科夫鏈問題求解的代數(shù)多重網(wǎng)格法。鑒于在插值算子、限制算子和各層迭代矩陣的構(gòu)造所需時間不可小覷,本文引入外推加速策略,通過對最細(xì)層的加速,改進了各層循環(huán)的初值,數(shù)值效果好。之后將這種新的加速的代數(shù)多重網(wǎng)格法用于網(wǎng)頁排序問題求解,數(shù)值實驗和比較結(jié)果驗證了所提出的新算法具有比傳統(tǒng)的網(wǎng)頁排序算法更好的性能。研究了網(wǎng)頁排序算法轉(zhuǎn)化為線性代數(shù)系統(tǒng)求解的問題。針對阻尼因子接近1時重啟的GMRES方法可能在該迭代系統(tǒng)中出現(xiàn)不收斂或崩潰的情形,提出了多項式右預(yù)處理策略,并給出了改進的新算法。隨后,提出并證明了新算法的收斂性定理。另外,在預(yù)處理基礎(chǔ)上進行了混合策略的加速并給出了相應(yīng)算法。數(shù)值實驗部分,首先驗證了預(yù)處理技術(shù)能顯著改善系數(shù)矩陣特征值的分布,同時從求解所需迭代次數(shù)、CPU時間等方面驗證了預(yù)處理技術(shù)改進了算法的收斂性,提高了收斂速度。針對經(jīng)典PageRank算法缺憾 平均分配權(quán)威值導(dǎo)致的搜索網(wǎng)頁排序質(zhì)量下降和可能引起的商業(yè)投機行為及網(wǎng)頁作弊問題,本文提出了三種改進策略將網(wǎng)頁的權(quán)威值按不同權(quán)重分配給它所外鏈接的網(wǎng)頁,然后給出了基于鏈接的加權(quán)網(wǎng)頁排序新算法,最后通過數(shù)值實驗對新算法的有效性進行了驗證。研究了線性代數(shù)系統(tǒng)的預(yù)處理問題,包括交替迭代和新型預(yù)處理子等的Gauss-Seidel預(yù)處理方法。從理論角度分析了預(yù)處理在改進收斂性方面的效果,數(shù)值實驗進行了驗證。
【關(guān)鍵詞】：馬爾科夫鏈 網(wǎng)頁排序 線性代數(shù)系統(tǒng) 向量外推法 預(yù)處理
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：O211.62;O241.8
【目錄】：

• 摘要5-6
• ABSTRACT6-11
• 第一章 緒論11-20
• 1.1 研究背景和意義11-15
• 1.1.1 線性代數(shù)系統(tǒng)的求解11-12
• 1.1.2 馬爾科夫鏈問題及網(wǎng)頁排序問題的計算12-15
• 1.2 主要方法簡介15-17
• 1.2.1 Krylov子空間方法15-16
• 1.2.2 預(yù)處理技術(shù)16-17
• 1.3 本文的主要工作和創(chuàng)新點17-18
• 1.4 本文的章節(jié)安排18-20
• 第二章 求解線性代數(shù)系統(tǒng)和馬爾科夫鏈問題的外推加速廣義極小殘量法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 數(shù)值實驗27-30
• 2.3 求解馬爾科夫鏈問題的外推加速GMRES方法30-37
• 2.3.1 馬爾科夫鏈問題的外推加速GMRES算法30-33
• 2.3.2 數(shù)值實驗33-37
• 2.4 本章小結(jié)37-39
• 第三章 代數(shù)多重網(wǎng)格方法及其應(yīng)用39-53
• 3.1 引言39-42
• 3.2 AMG方法的加速及其在求解馬爾科夫鏈問題中的應(yīng)用42-47
• 3.2.1 求解馬爾科夫鏈問題的AMG算法42-44
• 3.2.2 外推加速的代數(shù)多重網(wǎng)格法44-45
• 3.2.3 數(shù)值實驗45-47
• 3.3 求解PageRank問題的代數(shù)多重網(wǎng)格法47-52
• 3.3.1 網(wǎng)頁排序新算法的提出47-50
• 3.3.2 數(shù)值實驗50-52
• 3.4 本章小結(jié)52-53
• 第四章 PageRank問題求解的多項式預(yù)處理和混合加速策略53-66
• 4.1 引言53-55
• 4.2 PageRank問題求解的多項式預(yù)處理55-59
• 4.2.1 算法提出55-56
• 4.2.2 收斂性分析56-57
• 4.2.3 數(shù)值實驗57-59
• 4.3 PageRank問題求解的混合加速策略59-65
• 4.3.1 混合加速算法的提出59-61
• 4.3.2 數(shù)值實驗61-65
• 4.4 本章小結(jié)65-66
• 第五章 基于鏈接的加權(quán)PageRank算法66-78
• 5.1 引言66-67
• 5.2 PageRank計算的加權(quán)策略及算法67-71
• 5.2.1 PageRank算法改進策略I68-70
• 5.2.2 PageRank算法改進策略II70
• 5.2.3 PageRank算法混合加權(quán)策略70-71
• 5.3 數(shù)值實驗71-76
• 5.4 本章小結(jié)76-78
• 第六章 線性代數(shù)系統(tǒng)的預(yù)處理技術(shù)78-96
• 6.1 引言78-81
• 6.2 交替Gauss-Seidel預(yù)處理迭代81-86
• 6.2.1 預(yù)處理子的構(gòu)建81-82
• 6.2.2 收斂性分析82-86
• 6.3 I+C+S型Gauss-Seidel預(yù)處理迭代86-89
• 6.4 數(shù)值實驗89-92
• 6.5 本章小結(jié)92-96
• 第七章 總結(jié)與展望96-98
• 7.1 總結(jié)96
• 7.2 展望96-98
• 致謝98-99
• 參考文獻99-109
• 攻博期間取得的研究成果109-110

  本文關(guān)鍵詞：馬爾科夫鏈與網(wǎng)頁排序問題的數(shù)值算法研究，，由筆耕文化傳播整理發(fā)布。

本文編號：275053