线性方程组迭代法收敛性探析

【摘 要】线性方程组被广泛应用于工程技术以及物理等方面的求解。然而求解过程非常繁琐，因此，对线性方程组迭代法收敛性的研究就显得非常重要。首先，对线性方程组迭代法收敛性的研究意义进行了论述，对线性方程组迭代法收敛研究的发展进行了阐述，然后，对外推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～ ），男，陕西西安人，黄河交通学院基础教学部讲师，主要研究方向：应用数学。