《基於馬爾科夫鏈的線性系統求解問題的高效算法研究》是依託電子科技大學,由文春擔任醒目負責人的青年科學基金項目。
基本介紹
- 中文名：基於馬爾科夫鏈的線性系統求解問題的高效算法研究
- 依託單位：電子科技大學
- 項目類別：青年科學基金項目
- 項目負責人：文春
項目摘要,結題摘要,
項目摘要
馬爾科夫鏈由於其在生物學、管理學、金融經濟學等眾多領域的重大套用價值，受到國內外科研工作者的廣泛關注。馬爾科夫鏈的優勢在於能用馬爾科夫性描述和定義如隨機漫步、網頁排序、動態博弈等實際問題，並將這些問題歸結為線性系統的求解問題進行研究。本項目正是以基於馬爾科夫鏈的線性系統求解問題為研究對象，擬研究：(1) 改進和設計新的聚合技術，使輔助矩陣的構造更加合理，使各層係數矩陣的信息在粗格線與細格線的相互轉化過程中不會丟失；(2) 提出與問題相適應的疊代法與預處理技術，使Krylov子空間等疊代法的套用得到發展與推廣，進一步結合預處理技術，提高算法的性能，並做深入的理論分析和算法比較。
結題摘要
本項目研究了求解馬爾科夫鏈問題的自適應聚合多重格線法，同時研究了網頁排序問題的幾個數值方法及其改進。主要研究內容與結果如下： (1). 通過研究網頁連結圖的結構特徵以及網頁排序問題中轉移機率矩陣的數值性質，提出了一種消元算法。該算法通過對比轉移機率矩陣里各行的稀疏結構來選取一系列初等行變換以降低網頁排序系統的稠密度。同時也分析得出了該算法對於改變網頁排序系統特徵值分布的效果。數值實驗表明，該消元算法能有效地將網頁排序問題轉化為求解一個更簡單的線性系統。 (2). 通過進一步研究網頁排序問題係數矩陣的特殊性質，提出了一套低秩分解方案，得到了分塊矩陣的低秩分解表達式。並討論了一種基於該低秩分解表達式的預處理子。證明了該預處理子的可執行性並分析了其對於加速疊代求解過程的效果。數值實驗展示了這一整套預處理方案對於加速求解網頁排序問題的有效性。 (3). 分析了自適應聚合多重格線法中聚合塊的特性，結合Schwarz方法的相關理論構建了一種分塊鬆弛方案。討論了該分塊鬆弛方案在求解馬爾科夫鏈背景下的聚合多重格線法各層中的可執行性和收斂性。另外，網頁排序問題也可表述為求解馬爾科夫鏈線性系統，但此時係數矩陣通常是完全稠密的。針對此情況，本文給出了一些計算技巧使得所提出的分塊鬆弛方案在求解稠密網頁排序系統時避免直接計算有關稠密矩陣的操作。數值實驗驗證了上述基於聚合塊的分塊鬆弛方案對加速求解馬爾科夫鏈問題和網頁排序問題的有效性。 (4). 通過研究網頁排序問題的多步分裂疊代法，提出了改進的兩步矩陣分裂疊代法。文章中該方法被記為MPIO疊代法，其收斂性得到了具體的分析，並通過數值實驗，證實了該方法的有效性。 (5). 通過研究網頁排序問題的子空間方法，提出了加速的FOM方法。文章中進一步分析了FOM方法的求解奇異線性系統的行為，利用基於Ritz值的向量外推方法對FOM方法進行了加速，數值實驗說明了加速FOM方法的有效性。
