大規(guī)模矩陣特征值及線性系統(tǒng)的Krylov子空間算法研究.pdf

1、大規(guī)模矩陣特征值及稀疏線性系統(tǒng)數(shù)值求解問題已成為許多科學(xué)、工程、工業(yè)模擬，以及金融等領(lǐng)域的核心問題，由于其求解時間在整個問題解決上占有相當(dāng)大的比重．因此，高效地解決這些大規(guī)模矩陣計算問題能夠很大程度上提高整個問題的求解效率．最近20多年來這些大規(guī)模矩陣計算問題的算法研究一直是計算數(shù)學(xué)的熱點，國際、國內(nèi)的研究十分活躍．其求解算法，特別是Krylov子空間類型的算法得到了長足的發(fā)展．然而，仍有許多問題尚待解決?；趩栴}的重要性及其長遠意義，

2、本文討論這些大規(guī)模矩陣計算問題的數(shù)值求解算法．一方面，本文研究了大規(guī)模矩陣特征值問題的數(shù)值求解算法，算法的收斂性、穩(wěn)定性等問題；另一方面，還討論了大規(guī)模稀疏線性系統(tǒng)的加速算法、預(yù)處理技術(shù)、以及相關(guān)的收斂性分析．全文共分八章．第一章分別介紹了大規(guī)模矩陣特征值和稀疏線性系統(tǒng)問題的來源、研究歷史、發(fā)展現(xiàn)狀以及解決這些問題的基本方法．第二章、第三章討論了大規(guī)模非對稱矩陣部分特征對的數(shù)值計算問題．其中，第二章提出了一種計算大規(guī)模矩陣部分內(nèi)部特征對

3、的Arnoldi類型的算法．分析了算法的收斂性，與調(diào)和Arnoldi算法之間的關(guān)系．最后給出數(shù)值算例．試驗對比表明；當(dāng)近似子空間空間維數(shù)較小時，本文的算法能夠得到更快的收斂速度；當(dāng)近似子空間維數(shù)逐漸增加時，兩種算法的收斂速度都明顯加快，子空間維數(shù)較大時，兩種算法的收斂效果相差不大．第三章討論了求解大規(guī)模矩陣特征值問題的一類帶壓縮向量的塊類型Arnoldi算法．每次重新啟動時，利用上一個循環(huán)得到的近似特征向量來構(gòu)造初始塊向量，在正交基向量

4、的構(gòu)造過程中采用‘非精確壓縮’．一方面，在新的求解子空間中算法可以包含已經(jīng)收斂的近似特征向量，另一方面，通過非精確壓縮，初始‘塊’的列數(shù)隨著近似特征對的收斂而減小，從而使得新的近似子空間對于尚未收斂的特征對更有利．因此，這種方法能夠克服單向量的Krylov子空間不能計算重特征值的缺陷，而且比傳統(tǒng)的塊Krylov子空間方法更穩(wěn)定，更有效．近似子空間的性質(zhì)分析表明這種方法漸進地具備添加特征向量重新啟動的Arnoldi算法的優(yōu)勢，隨著近似特征

5、對的收斂，每次重新啟動生成的近似子空間對未收斂的特征對越來越有利．最后給出數(shù)值試驗，結(jié)果表明本文的算法能夠克服塊的Krylov子空間不規(guī)則收斂的現(xiàn)象，具有非常光滑的收斂性質(zhì)． 第四至第七章討論的是大規(guī)模稀疏線性系統(tǒng)的求解問題．其中，第四章首先通過實驗發(fā)現(xiàn)添加近似特征向量重新啟動的GMRES(Generalized MinimumRESidual)算法(GMRES-E)每隔一步生成的殘向量角度往往很?。畯亩岢鲈贕MRES-E的基

6、礎(chǔ)上添加修正向量的一種雙重增廣重新啟動的GMRES算法(LGMRES-E)．?dāng)?shù)值試驗表明新的重新啟動方式可以有效的糾正殘向量經(jīng)常出現(xiàn)的跳躍角很小的現(xiàn)象，從而可以使每次重新啟動得到的近似子空間保持適當(dāng)?shù)恼恍?，一定程度上克服原來方法由于重新啟動所造成的近似子空間整體維數(shù)下降問題，同時由于添加近似特征向量，新方法也能夠有效地壓縮掉影響收斂速度的小特征值．?dāng)?shù)值試驗表明了這種雙重增廣方法對于系數(shù)矩陣具有少數(shù)幾個相對較小特征值的線性系統(tǒng)具有非常好

7、的效果．新方法可以加快GMRES-E的收斂速度． 第五章我們提出在GCRO-DR每次重新啟動時保留部分修正向量信息，并將其添加到新的求解子空間中．這種策略可以使前后近似求解子空間保持適當(dāng)?shù)木€性無關(guān)性，從而可以有效的縮短GCRO—DR經(jīng)常出現(xiàn)的收斂較慢的現(xiàn)象．當(dāng)只保留一個最新生成的修正向量時，分析表明，算法的改進是非常自然的，只需要極小的改動就能達到目的．當(dāng)需要添加的修正向量的個數(shù)大于1時，本章重點討論了一種非精確方法．它可以保證

8、在近似子空間維數(shù)相同時，改進后的算法與原算法的運算量相差不大．然而改進后的方法具有明顯的加速現(xiàn)象．我們對比了兩種方法在求解單個線性系統(tǒng)以及序列線性系統(tǒng)方面的收斂速度，討論了添加修正向量個數(shù)對于收斂性的影響．?dāng)?shù)值試驗表明新方法能夠有效加快GCRO-DR的收斂速度，在解決模擬機械疲勞斷裂問題產(chǎn)生的系列線性系統(tǒng)等問題上的數(shù)值試驗效果表明，新方法的收斂速度提高接近10％． 第六章討論了切頻率過濾分解與組合預(yù)處理技術(shù)．首先，我們觀察到傳統(tǒng)

9、的右側(cè)過濾分解同樣可以在滿足左側(cè)過濾條件下來完成．在此基礎(chǔ)上，本文提出了一種雙側(cè)切頻率過濾分解預(yù)處理子．在過濾向量的選取上采用ones來作為過濾向量．如此選取有以下幾個優(yōu)點，一方面，可以節(jié)省其他類似算法的前處理過程來計算過濾向量．另一方面，對于使用ones作為左側(cè)過濾向量所構(gòu)造的過濾預(yù)處理子，如果選取適當(dāng)?shù)某跏枷蛄浚敲搭A(yù)處理的Krylov子空間迭代算法能保證其殘向量的和始終為零，即所謂的材料均衡誤差為零的性質(zhì)．將切頻率過濾分解所構(gòu)造的

10、預(yù)處理子與傳統(tǒng)的ILU(0)預(yù)處理子以乘性方式相結(jié)合，我們討論了兩種組合預(yù)處理技術(shù)．譜分析表明組合預(yù)處理子能吸收兩個預(yù)處理子的優(yōu)點，使預(yù)處理矩陣的特征值很好的聚集在1附近．最后，對于一類非線性偏微分方程離散化產(chǎn)生的大規(guī)模稀疏線性系統(tǒng)，我們對比了幾種不同類型組合預(yù)處理子的試驗效果，數(shù)值結(jié)果表明了本文方法的穩(wěn)定性和有效性． 第七章討論了鞍點問題的預(yù)處理技術(shù)，基于對鞍點問題(1，1)塊的切頻率過濾分解和約束預(yù)處理子的結(jié)構(gòu)，本章討論了一

11、種切頻率過濾分解類型的預(yù)處理子．通過對Stokes問題及Oseen方程離散化產(chǎn)生的鞍點問題，我們分析了預(yù)處理子在網(wǎng)格精化，Reynolds數(shù)增加時的性態(tài)，數(shù)值結(jié)果表明：在內(nèi)迭代精度和Reynolds數(shù)不變的情形下，隨著網(wǎng)格精化，需要的迭代步數(shù)逐漸增加但變化不是很明顯．在矩陣網(wǎng)格單元及內(nèi)迭代精度不變的情形下，迭代步數(shù)基本不受Reynolds數(shù)變化的影響，這一性質(zhì)要比同類型的ILU預(yù)處理子要好很多．本章的后半部分，我們提出了一類推廣Schi

12、lders分解類型的預(yù)處理子．理論分析表明，預(yù)處理之后矩陣的譜性質(zhì)與Schilders分解類型的預(yù)條件子對標準鞍點問題預(yù)處理之后矩陣的譜性質(zhì)相同．因此，本文的預(yù)處理子是Schilders分解類型約束預(yù)處理子對于廣義鞍點問題的自然推廣．由于廣義鞍點問題非零(2，2)塊的出現(xiàn)，本文的預(yù)條件子在實際應(yīng)用時涉及到Schur補類型的計算．對于一類特殊類型的問題，本文討論了算法的一種非精確變形可以避免Schur補的計算，數(shù)值試驗還在準備中．

13、 最后一章提出了一種修正的切頻率過濾分解預(yù)處理子(MTFFD)，并對其進行了Fourier分析．用2維Poisson方程作為模型問題，通過Fourier分析確定了最優(yōu)修正階數(shù)以及最優(yōu)參數(shù)． Fourier分析結(jié)果表明MTFFD預(yù)處理之后的矩陣條件數(shù)為O(h-2/3)．這一結(jié)果表明MTFFD的性能應(yīng)該比BILU以及MBILU都要好．Fourier分析得到的結(jié)論都通過試驗進行了驗證．最后，通過數(shù)值算例表明MTFFD預(yù)處理子的效果比TFFD更