鞍點問題和馬爾科夫鏈問題的高性能算法研究.pdf

1、科學(xué)與工程的很多重要領(lǐng)域如通訊網(wǎng)絡(luò)和輸送現(xiàn)象的模擬、經(jīng)濟管理和市場預(yù)測、高階微分方程求解、流體力學(xué)、計算電磁學(xué)、油藏模擬和最優(yōu)化問題等都離不開線性代數(shù)系統(tǒng)的求解。隨著科學(xué)技術(shù)的迅猛發(fā)展,人們對線性代數(shù)系統(tǒng)的求解在計算速度和計算精度方面的要求變得越來越高。因此,線性代數(shù)系統(tǒng)的求解方法研究一直都是科學(xué)與工程計算的核心之一,具有十分重要的理論意義和實際應(yīng)用價值。本文針對鞍點問題和馬爾科夫鏈問題產(chǎn)生的線性代數(shù)系統(tǒng),深入研究了直接法,矩陣分裂迭代

2、法, Krylov子空間方法和預(yù)處理技術(shù)等在求解相應(yīng)線性代數(shù)系統(tǒng)中的應(yīng)用,并構(gòu)造出了一些新的有效算法。全文共六章,分為四個部分:
　　研究了鞍點問題迭代求解預(yù)處理技術(shù)。首先提出了修正的對稱超松弛類(MSSOR-like)迭代法求解經(jīng)典鞍點問題,討論了該迭代法的收斂性,給出了最優(yōu)參數(shù)的選取范圍,數(shù)值實驗驗證了其有效性。其次,針對具有2×2塊結(jié)構(gòu)的奇異對稱鞍點問題,通過改變系數(shù)矩陣中(2,2)塊矩陣的值,構(gòu)造了修正的SSOR(MSSO

3、R)預(yù)處理子,研究了MSSOR預(yù)處理矩陣的譜性質(zhì)及其收斂性,數(shù)值實驗說明了MSSOR預(yù)處理子能有效加快迭代法的收斂速度.最后,針對對稱廣義鞍點問題產(chǎn)生的不定線性代數(shù)系統(tǒng),借用交替迭代法的思想,結(jié)合現(xiàn)有的塊對角預(yù)處理子和約束預(yù)處理子,建立了乘積預(yù)處理子,分析了該預(yù)處理矩陣的特征值分布情況,對應(yīng)特征向量的具體形式和最小多項式的最大次數(shù),數(shù)值實驗顯示該乘積預(yù)處理子在減少所需計算時間和迭代步數(shù)方面有著明顯的效果。
　　研究了矩陣分裂迭代法

4、在求解馬爾科夫鏈問題中的應(yīng)用。由于馬爾科夫鏈問題產(chǎn)生的線性代數(shù)系統(tǒng)通常是奇異的,以致適用于求解非奇異線性代數(shù)系統(tǒng)的很多計算方法不能直接應(yīng)用于該問題的求解。為了克服這一難點,本文首先給出一個定理說明存在一個非負數(shù)使得馬爾科夫鏈問題產(chǎn)生的線性方程組經(jīng)過修正之后具有正定性。然后基于矩陣分裂迭代法的思想,構(gòu)造了對稱與反對稱矩陣分裂(SSS)迭代法和三角與反對稱矩陣分裂(TSS)迭代法。這類迭代法包含兩個子系統(tǒng),本文從理論上詳細討論了SSS和TS

5、S迭代法的收斂性及其最優(yōu)參數(shù)選取情況。在實際計算中,如果利用直接法精確求解SSS和TSS迭代法中的兩個子系統(tǒng),則每個子系統(tǒng)的計算量與求解原系統(tǒng)相當(dāng),以致這里的兩步迭代失去了意義。為了加快兩個子系統(tǒng)的求解速度,本文發(fā)展了非精確的SSS和TSS迭代法,記為ISSS和ITSS迭代法。數(shù)值實驗說明了這些方法的有效性。
　　研究了求解馬爾科夫鏈問題的向量外推加速多級聚合算法。首先介紹了多級聚合算法和向量外推方法的相關(guān)原理,說明多級聚合算法的

6、核心部分在于如何有效地構(gòu)造限制和延伸算子。然后指出該算法在求解馬爾科夫鏈問題時存在的主要缺陷,即各層之間相互轉(zhuǎn)化所需要的限制和延伸算子依賴于最新近似解,使得每步迭代中都需要重新計算限制和延伸算子,從而耗費大量的計算時間,令人無法接受。因此,本文結(jié)合向量外推方法計算量小,所需輸入量少等優(yōu)點,構(gòu)造了新的向量外推加速多級聚合算法,數(shù)值實驗說明了該新算法在減少計算時間和迭代步數(shù)方面所取得的進步。
　　研究了求解非奇異線性方程組的兩個共軛方