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

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

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

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

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

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

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