大稀疏鞍點線性系統(tǒng)的迭代解法.pdf

1、鞍點線性系統(tǒng)是一類對稱不定的線性系統(tǒng)，它來源于鞍點型偏微分方程問題、最優(yōu)化問題、最小二乘問題等研究領(lǐng)域.實際應(yīng)用中導(dǎo)出的這類系統(tǒng)通常都是大規(guī)模的，并且系數(shù)矩陣具有稀疏性，因此應(yīng)采用迭代法進行求解.然而，鞍點線性系統(tǒng)本身特殊的結(jié)構(gòu)特點使得一些著名的算法，諸如逐次超松弛迭代法(SOR)或共軛梯度法(CG)均失去效力.因此尋求解決大稀疏鞍點線性系統(tǒng)的有效的迭代解法具有重要的現(xiàn)實意義. 目前為人們所熟知的Uzawa算法和MINRES算法

2、是兩類求解鞍點線性系統(tǒng)的有效方法.Uzawa算法格式簡單，但收斂速度較慢.MINRES算法計算效率高，但計算格式比較復(fù)雜.尋求具有更簡單的計算格式或者更快收斂速度的迭代算法，成為熱門的研究課題. 經(jīng)典的SOR算法同樣具有格式簡單、存儲量小的特點，因而早為人們所關(guān)注.近年來有學(xué)者開始研究廣義化的SOR算法來求解鞍點線性系統(tǒng).李長軍等學(xué)者于1998年首次提出了一種廣義化的SOR算法：GSOR算法.Golub等學(xué)者于2001年提出了S

3、OR-like算法.這兩種算法本質(zhì)相同，因此我們將其統(tǒng)稱為廣義化SOR方法.這類算法具有同Uzawa算法一樣簡單的計算格式，并帶有一個預(yù)優(yōu)矩陣. 本文首先對SOR-like算法重新進行了深入的研究，采用比較初等的方法詳細地刻劃了SOR-like算法迭代矩陣譜半徑的基本特征；給出了SOR-like算法最優(yōu)迭代參數(shù)以及迭代矩陣譜半徑的顯式表達式；進一步證明了，通過選取合適的預(yù)優(yōu)矩陣，可以使SOR-like算法的迭代矩陣只含有實特征值

4、，從而可以采用Chebyshev多項式加速.這一結(jié)果是令人振奮的，豐富了D.M.Young的超松弛理論；同時我們還更正了Golub在2001年關(guān)于SOR-like算法的收斂性分析中出現(xiàn)的錯誤. 基于對SOR-like算法的理論分析，我們深入研究采用Chebyshev多項式對SOR-like算法進行加速，從而給出了GSOR-SI算法.理論分析和數(shù)值計算表明，這一算法具有和SOR-like算法相近的計算開銷，卻擁有比SOR-like

5、算法快得多的收斂速度. 針對鞍點線性系統(tǒng)的特有的結(jié)構(gòu)特點，我們提出兩種含有兩個迭代參數(shù)的廣義化SOR算法，即GAOR算法和TPGSOR算法.給出了TPGSOR算法的最優(yōu)參數(shù)的顯式表達式以及相應(yīng)的最優(yōu)迭代矩陣譜半徑的顯式表達式.TPGSOR算法的計算格式同SOR-like算法一樣簡單，但理論分析和實驗結(jié)果均表明它的收斂速度卻大大提高了. 我們研究將預(yù)優(yōu)共軛梯度算法(PCG)應(yīng)用于對鞍點線性系統(tǒng)的求解，并在理論上直接證明了：

6、PCG算法具有比Uzawa算法、SOR-like算法以及GSOR-SI算法更快的收斂速度.數(shù)值計算結(jié)果也進一步證明了理論分析的正確性. 對矩陣的特征值估計以及預(yù)優(yōu)矩陣的選取在實際應(yīng)用中具有重要的意義.本文討論了這一問題，并對一類廣為使用的預(yù)優(yōu)矩陣給出了合理的解釋. 本文將所有論及的數(shù)值方法應(yīng)用于數(shù)值求解定常Stokes方程.首先我們采用兩種混合有限元格式對定常Stokes方程進行離散，并編程導(dǎo)出了相應(yīng)的鞍點線性系統(tǒng)，即由

7、程序自動生成線性方程組的系數(shù)矩陣和右端項，然后應(yīng)用SOR-like算法、GSOR-SI算法、TPGSOR算法、PCG算法以及著名的MINRES算法和Uzawa算法(或預(yù)優(yōu)Uzawa算法)分別對所生成的線性方程組進行迭代求解.數(shù)值計算結(jié)果完全印證了本文的理論分析結(jié)論.PCG算法的收斂速度在6種算法中最快；TPGSOR算法和GSOR-SI算法的斂速接近于PCG算法，而TPGSOR算法和GSOR-SI算法的優(yōu)勢在于計算格式簡單，存儲量小，更適