線性方程組迭代法收斂性探析

【摘 要】線性方程組被廣泛應(yīng)用于工程技術(shù)以及物理等方面的求解。然而求解過程非常繁瑣，因此，對線性方程組迭代法收斂性的研究就顯得非常重要。首先，對線性方程組迭代法收斂性的研究意義進行了論述，對線性方程組迭代法收斂研究的發(fā)展進行了闡述，然后，對外推Gauss-Seidel迭代法收斂性進行了闡述，分析了外推Gauss-Seidel與H-矩陣的關(guān)系，同時，最后給出了算例分析。

【關(guān)鍵詞】線性方程組；Gauss-Seide；收斂性

當(dāng)前，科學(xué)技術(shù)發(fā)展迅猛，與此同時，計算機科學(xué)突飛猛進，在工程技術(shù)以及物理等中存在眾多的問題都可以歸結(jié)為對線性方程組求解問題。但是，對大型線性方程組進行求解的過程中，求解時間長、計算量大，計算復(fù)雜，求解過程中需要非常大的存儲等，都是人們需要面臨的問題，所以，構(gòu)建計算量比較小，同時數(shù)值比較穩(wěn)定的算法是國內(nèi)外學(xué)者研究的重點與熱點。因為迭代法節(jié)省內(nèi)容，容易實現(xiàn)并行處理，求解的速度比較快，因此，成為解決線性方程組的重要方法，而對于迭代法收斂性進行探索，對線性方程組的求解具有非常重要的意義。

一、線性方程組迭代法收斂性研究的意義及發(fā)展

1.線性方程組迭代法收斂性研究的意義

當(dāng)前科學(xué)技術(shù)發(fā)展迅猛，計算機科學(xué)技術(shù)突飛猛進，在理論研究與科學(xué)實驗以后，出現(xiàn)了科學(xué)計算已經(jīng)成為了研究領(lǐng)域的第三大計算工具。在工程領(lǐng)域、物理學(xué)領(lǐng)域中的很多問題，包括模擬電路的求解、熱力學(xué)問題的求解、流體力學(xué)問題的求解等，都需要對大型線性方程組進行求解。同時，偏微分方程等屬性領(lǐng)域的問題的求解一般也是領(lǐng)域差分方法、有限元方法以及區(qū)域分解方法等進行離散化，從而向線性方程組轉(zhuǎn)化進行求解。所以，從某種意義上講，科學(xué)與工程計算中的一個基本問題就是對于大型的稀疏線性方程組的求解。然而，在工程實際問題中，由于影響因素較多，使得稀疏線性方程一般都非常復(fù)雜，因此，大型稀疏線性方程組求解過程非常繁瑣，計算難度高等阻礙著實際問題的解決。迭代法可以實現(xiàn)并行處理，具有較快的求解速度，同時節(jié)省內(nèi)存，因此，對于實際問題的解決具有非常重要的意義。

2.線性方程組迭代法收斂研究的發(fā)展

直接法與迭代法是進行線性方程組求解的主要方法。二十世紀的六十年代到七十年代期間，是直接法研究的主要時期，直接法是利用Gauss消元法、LU分解法等變換方程組的系數(shù)矩陣，把線性方程組轉(zhuǎn)換成為三對角或者是三角的形式進行求解，之后利用追趕的方法或者是回代的方法對原方程組的解進行求解。直接法當(dāng)在對舍入誤差不計的情況下，能夠獲得準確解，然而，其不足是如果系數(shù)矩陣具有很大的條件數(shù)的時候，通過舍入誤差的方法，無疑使得求的解和方程的實際的解相比較，具有很大的誤差，另外，直接法通常需要很大的內(nèi)存，需要較長的計算時間，因此，線性方程組求解的熱點已經(jīng)轉(zhuǎn)變?yōu)榈ㄟM行去求解。迭代法指的是基于解的近似值入手，對于具有無窮序列進行構(gòu)建，從而對于精確解進行逼近，這樣能夠使得在比較短的時間內(nèi)就能夠得到比較準確的解，使得方程的解的求解的速度得到有效的提高。同時，迭代法能夠?qū)τ谙禂?shù)矩陣稀疏性進行有效的利用與保持，使得內(nèi)存節(jié)省，另外，迭代法可實現(xiàn)并行處理，實現(xiàn)并行計算，因此，迭代法已經(jīng)成為當(dāng)前研究的熱點。

3.迭代法的分類

對于迭代法而言，具有很多的種類，通?？梢苑殖啥ǔ５ㄒ约胺嵌ǔ５?。對于方程組的求解而言，收斂速度以及收斂性無疑是核心，不能應(yīng)用不收斂的迭代法。如果收斂速度慢，一方面計算時間比較長，另外一方面計算的結(jié)果有可能不能滿足需要，所以，對于迭代法進行研究的目的，就是尋找收斂速度比較快的方法。

Jacobi迭代法、Gauss-seidel迭代法、AOR迭代法以及SOR迭代法都是較為經(jīng)典的定常迭代法。上述方法都可以利用矩陣的分裂獲得，實際上，就大型線性方程組而言，

Ax=b

當(dāng)一次分裂系數(shù)矩陣時，也就是A=M-N，這其中，M是非奇異矩陣，那么，可以得到以下的迭代格式：

x（k+1）=M-1Nx（k）+M-1b，k=0，1，2…

上面的式子中，迭代矩陣是M-1N，而給定的初始的迭代值是x（0）。對于M取不一樣的矩陣就那個獲得不同的迭代法。

在定常迭代法中，進行每一次的迭代之后，都要進行分裂，從而可以獲得交替迭代法。交替迭代法的格式如下：

交替迭代法同樣是一種比較廣泛的迭代法。根據(jù)經(jīng)典的迭代法對對稱型迭代法進行構(gòu)建。學(xué)者Aitken提出了對稱的Gauss-seidel方法，而學(xué)者Sheldon則指出SSOR方法同樣是交替迭代法中的一種。學(xué)者Climent等人，對經(jīng)典交替方法進行了推廣，從而獲得了非定常的交替迭代法、并行交替迭代法以及廣義的交替迭代法，同時，Climent等人對于單調(diào)矩陣進行了分析，對對稱正定矩陣其相應(yīng)迭代法收斂性也進行了分析研究。

國內(nèi)外學(xué)者一方面對于迭代法收斂性進行研究，另外一方面對于迭代法的相互之間的關(guān)系以及收斂的速度進行了研究，學(xué)者們基于對方程組系數(shù)矩陣的分類，對于不同矩陣類迭代法的求解進行了研究，比如研究非負矩陣、L-矩陣、M-矩陣以及H-矩陣等。學(xué)者Neumann等人對于減小相容線性方程組非負的迭代矩陣的普半徑的求解方法進行了研究，對于加速迭代方法的收斂性進行研究。

迭代法的研究不斷的發(fā)展，學(xué)者提出了two-stage iterative methods，即二級迭代法。二級迭代法通過內(nèi)、外迭代構(gòu)成，因此，也被叫做inner-outer迭代法，即內(nèi)外迭代法，或者是nested迭代法或嵌套迭代法。二級迭代法求解的思路是，對于單步的定常格式的迭代，再通過一次迭代法對于其近似解進行求解，也就是M=F-G，實現(xiàn)s（k）次內(nèi)迭代，從而獲得以下的二級的迭代方式：

上式中的迭代矩陣如下：

其中，s（k）是內(nèi)迭代次數(shù)。而其中的內(nèi)分裂是M=F-G，而外分裂是A=M-N，內(nèi)迭代次數(shù)是s（k），外迭代次數(shù)是k。當(dāng)對于全部的外迭代次數(shù)，內(nèi)迭代次數(shù)都不變的時候，也就是說，當(dāng)s（k）=s（k=0，1，2，…）的時候，二級迭代法就被叫做是定常迭代法。如果，對于全部的外迭代次數(shù)，內(nèi)迭代次數(shù)是變化的，那么二級迭代法就叫做是非定常迭代法。二級迭代法重點是對離散化的偏微分方程組進行求解。進一步改進了傳統(tǒng)的分裂迭代法。通過內(nèi)迭代法對于相對來說比較簡單的外迭代方程組進行求解，不求解方程組的準確的解，而是對于整個方程組的近似的解進行求解，事實上，內(nèi)迭代法對于方程組近似解的求解提供了一種非常好的方法。對于二級迭代法，很多文獻都進行了論述，OLeary以及White等學(xué)者對于線性方程組多重迭代求解的方法進行了研究，同時，研究分析了單調(diào)矩陣以及對稱的正定矩陣的收斂性?；诙壍ǖ那疤嵯?，對于交替二級迭代法進行了研究，并且對于系數(shù)矩陣是M-矩陣、對稱正定矩陣的收斂性進行了研究。

研究收斂性并且進行改善是線性方程組求解的前提，同時，為了加快收斂速度，需要對方程組自身進行處理，通過預(yù)處理使得方程組的收斂性得到改善，從而加快了收斂的速度。

二、外推Gauss-Seidel迭代法收斂性

假設(shè)A=D-L-U，

A的對角是D，-L，-U，當(dāng)A是嚴格的上三角和嚴格下三角矩陣時，那么A的Gauss-Seidel迭代法就是基于A=（D-L）-U獲得的，（令M=D-L，N-U）），那么，其迭代的格式如下：

式中，Gh=（1-h）I+Gh是外推Gauss-Seidel的迭代矩陣，外推系數(shù)用h表示。

外推迭代法能夠收斂的充要條件是：

①，并且，存在

或者是存在

②，并且，存在

xj+yij，j=1，2，…，n，作為原迭代矩陣T全體特征值，Th=（1-h）I+Th是其對應(yīng)外推迭代矩陣。

基于Jacobi迭代法的H-矩陣等價條件如下：

假設(shè)，當(dāng)期滿足條件，時，那么，A就是H-矩陣當(dāng)且僅當(dāng)對于任何

式中，是P的Jacobi迭代矩陣譜半徑，A的等模矩陣集合用表示。

下面對Gauss-Seidle迭代法收斂性進行探討。

假設(shè)，方陣。當(dāng)存在，那么可以得到以下結(jié)論：

①如果ρ（B）<1，那么，0≤ρ（i-e）-1F≤ρ（B）<1

②如果ρ（B）=1，那么

③如果ρ（B）>1，那么

就L-矩陣來說，構(gòu)建Gauss-Seidle迭代矩陣譜半徑和Jacobi迭代矩陣譜半徑關(guān)系，從而獲得Gauss-Seidle收斂結(jié)論如下：

假設(shè)A是L-矩陣，當(dāng)，，那么存在以下結(jié)論：

①如果ρ（J）<1，那么1-h≤ρ（G（h））≤（1-h）+hρ（J）<1

②如果ρ（J）=1，那么ρ（Gh）=ρ（J）=1

③如果ρ（J）>1，那么，ρ（Gh）≥（1-h）+hρ（J）>1

其證明的過程如下：

由于

假設(shè)，，那么

，同時，。

因為，A是L-矩陣，因此，

根據(jù)上文的結(jié)論，

如果ρ（J）<1，那么1-h≤ρ（G（h））≤（1-h）+hρ（J）

<1；如果ρ（J）=1，那么ρ（Gh）=ρ（J）=1；如果ρ（J）>1，那么，ρ（Gh）≥（1-h）+hρ（J）>1。

因為，Gh=（1-H）I+Gh以及0

①如果ρ（J）<1，那么1-h≤ρ（G（h））≤（1-h）+hρ（J）<1

②如果ρ（J）=1，那么ρ（Gh）=ρ（J）=1

③如果ρ（J）>1，那么，ρ（Gh）≥（1-h）+hρ（J）>1

由此可見，0

三、外推Gauss-Seidle與H-矩陣關(guān)系

為了探究外推Gauss-Seidle與H-矩陣的關(guān)系，給出以下定理：

假設(shè)是H-矩陣，同時就任何i，存在，那么

①如果，那么

②如果，那么

上面J是A的Jacobi迭代矩陣。

下面給出證明，假設(shè)A不可約，根據(jù)A是H-矩陣，則A的最優(yōu)尺度矩陣

嚴格對角占優(yōu)，同時存在

式中，對于主對角線以下的第i行元素求和以及主對角線以上第i行元素求和分別用表示。

①如果，那么

②如果，那么

由此可以得到Gauss-Seidel與H-矩陣的關(guān)系，從而獲得H-矩陣在收斂范圍內(nèi)Gauss-Seidel迭代矩陣譜半徑上屆值。

四、實例分析

假設(shè)：

A是非奇異H-矩陣，存在，從而表明了，根據(jù)前文的結(jié)論，存在如果，也就是當(dāng)時，，如果h=0.2，h=1.26，那么，通過計算可以得到，都比1小，也就表明了對應(yīng)的Gauss-Seidle迭代法收斂。

五、結(jié)束語

對Gauss-Seidel迭代法收斂性進行了探討，對H-矩陣與Gauss-Seidel迭代法收斂性關(guān)系進行了分析，獲得了Gauss-Seidel迭代法收斂性收斂性結(jié)論，同時給出了實際算例，為H-矩陣有關(guān)理論的發(fā)展提供借鑒。

參考文獻：

[1]王麗，孫明軍，宋永忠.解非埃爾米特線性方程組的外推迭代法的收斂性[J].南京師范大學(xué)學(xué)報.2007（1）30：1-5

[2]胡家贛.線性代數(shù)方程組的迭代解法[M].科學(xué)出版社.1997

[3]薛秋芳，高興寶，劉曉光.H-矩陣基于外推Gauss-Seidel迭代法的幾個等價條件[J].山東大學(xué)學(xué)報.2013（4）48：65-71

[4]Aitken A C. On the iterative solution of a system of linear equations[J]. Proceedings of the Royal Society of Edinburgh， Sec， A， 1950，63，52-60.

[5]Sheldon J W. On the numerical solution of elliptic differential equations[J]. Mathematical Tables and Other Aids to Computation， 1955，9， 101-112

[6]Climent J J， Perea C， Tortosa L， et al. Convergence theorems for parallel alternating iterative methods[J]. Applied Mathematics and Computation，2004，148（2）： 497-517.

[7]Neumann M，Plemmons R J. Convergent nonnegative matrices ￡md iterative methods for consistent linear systems [J]. Numerische Mathematik， 1978，31（3）： 265-279.

[8]OLeary D P，White R E. Multisplittings of matrices and parallel solution for Liearsystems[J]. SIAM J. Algebra Diseret Methods， 1985，6： 630-640.

作者簡介：

劉講軍（1981～ ），男，陜西西安人，黃河交通學(xué)院基礎(chǔ)教學(xué)部講師，主要研究方向：應(yīng)用數(shù)學(xué)。