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

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

【關鍵詞】線性方程組；Gauss-Seide；收斂性

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

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

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

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

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

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

3.迭代法的分類

對于迭代法而言，具有很多的種類，通常可以分成定常迭代法以及非定常迭代法。對于方程組的求解而言，收斂速度以及收斂性無疑是核心，不能應用不收斂的迭代法。如果收斂速度慢，一方面計算時間比較長，另外一方面計算的結果有可能不能滿足需要，所以，對于迭代法進行研究的目的，就是尋找收斂速度比較快的方法。

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

Ax=b

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

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

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

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

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

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

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

上式中的迭代矩陣如下：

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

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

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

假設A=D-L-U，

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

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

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

①，并且，存在

或者是存在

②，并且，存在

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

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

假設，當期滿足條件，時，那么，A就是H-矩陣當且僅當對于任何

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

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

假設，方陣。當存在，那么可以得到以下結論：

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

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

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

就L-矩陣來說，構建Gauss-Seidle迭代矩陣譜半徑和Jacobi迭代矩陣譜半徑關系，從而獲得Gauss-Seidle收斂結論如下：

假設A是L-矩陣，當，，那么存在以下結論：

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

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

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

其證明的過程如下：

由于

假設，，那么

，同時，。

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

根據上文的結論，

如果ρ（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-矩陣關系

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

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

①如果，那么

②如果，那么

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

下面給出證明，假設A不可約，根據A是H-矩陣，則A的最優尺度矩陣

嚴格對角占優，同時存在

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

①如果，那么

②如果，那么

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

四、實例分析

假設：

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

五、結束語

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

參考文獻：

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

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

[3]薛秋芳，高興寶，劉曉光.H-矩陣基于外推Gauss-Seidel迭代法的幾個等價條件[J].山東大學學報.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～ ），男，陜西西安人，黃河交通學院基礎教學部講師，主要研究方向：應用數學。