在科学计算和工程应用中,许多问题最终都归结为线性方程组的求解,因此研究线性方程组解的理论以及求解方法具有重要的理论意义和应用价值[1-4].如何快速有效地求得线性方程组的解是计算数学的一个基本问题,也是目前仍在继续研究的重要课题之一[5-16].
本文考虑M-矩阵线性方程组的求解
式中A ∈ Rn×n是非奇异的M-矩阵,b∈ Rn是给定的向量.这种类型的线性方程组在微分方程数值解、线性互补问题、Markov链以及物理学、生物学和经济学中都有着广泛的应用[2,4,17].例如,对于 Poisson方程第一边值问题,利用差分法离散化之后即得到一个系数矩阵为M-矩阵的线性方程组.在线性互补问题中,很多情况下的系数矩阵都是M-矩阵.在经济学中,投入产出分析对应的矩阵也是M-矩阵[17].
对于一般的线性方程组已有很多经典的解法,如Gauss消去法、平方根法、Jacobi迭代法、Gauss-Seidel迭代法、SOR、共轭梯度法、Krylov子空间方法[1-4]和 HSS 迭代法[18]等.而对于一些具有特殊性质和结构的方程组,也有很多学者进行了深入研究.本文利用M-矩阵的特点,针对M-矩阵线性方程组提出了一类迭代法.理论分析和数值实验表明,新方法是可行的,而且在一定情况下也是较为有效的.
首先简要介绍本文的符号记法及将要用到的一些预备知识.
Rm×n表示实数域上全体m×n的矩阵,Rn表示实数域上全体n维列向量,ρ(A)表示矩阵A的谱半径.n阶单位矩阵记为In,在没有混淆的情况下写为I.用||·||来表示一个给定的矩阵范数.
设A=(aij)∈ Rn×n,若A的每个元素都是非负的,则称 A为非负矩阵,记为 A ≥ 0.设 A=(aij)∈ Rn×n,若对于任意的i≠j都有aij≤0成立,则称A为Z-矩阵.一个Z-矩阵A若可以表示为A=sI-B,其中B为非负矩阵且s≥ ρ(B),则称该Z-矩阵为M-矩阵.特别地,当s>ρ(B)时,称A为非奇异的M-矩阵,当s=ρ(B)时,称A为奇异的M-矩阵.关于M-矩阵的详细内容可参考文献[17].
分裂迭代法是求解线性方程组(1)的最简单的一类迭代法.分裂迭代法的基本思路是,给定系数矩阵A的一个分裂
式中M是可逆的,代入式(1)得到原方程组的等价形式Mx=Nx+b,进而可以得到迭代法
式中M-1N称为分裂迭代法(2)的迭代矩阵.
如果对于任意给定的初始向量x0∈Rn,由式(2)生成的序列{xk}都收敛于方程组(1)的解 x*,则称迭代法(2)是收敛的.
引理1.1[19] 分裂迭代法(2)收敛当且仅当迭代矩阵M-1N的谱半径ρ(M-1N)<1.
引理 1.2[20] 设 ||·||是任意一个矩阵范数,则对任意的A∈Rn×n有![]()
本节提出一类非定常迭代法,以求解M-矩阵线性方程组,并给出该方法的收敛性分析.
设 A=(aij)∈ Rn×n为非奇异的 M-矩阵,则 A 存在自然的分裂
式中s>0,而B≥0是非负矩阵.事实上,不难验证只要选取
,令 B=sI-A 即可.于是基于上述分裂便可以得到如下的一类迭代法
式中x0∈Rn是任意给定的初始向量.
由于A是非奇异的M-矩阵,可知s>ρ(B).于是利用引理1.1,可得到如下的收敛性.
定理2.1 设线性方程组(1)的系数矩阵是非奇异的M-矩阵,则对于任意给定的初始向量,迭代法(4)都是收敛的.
在迭代法(4)中存在一个参数s.下面讨论参数s对迭代的影响,并给出最优参数的值.
定理2.2 迭代法(4)中的最优参数为![]()
![]()
证明 设A=s1I-B1=s2I-B2为矩阵A的2个分裂,其中 s1,
都是正数,且 s1 > s2,而B1,B2是非负矩阵.相应的迭代矩阵谱半径分别为![]()
由 B1=(s1-s2)I+B2,且 ρ(B1)=s1-s2+ ρ(B2),可得
因此,参数s越小,收敛越快.从而当
时,迭代法(4)收敛最快.证毕.
由于迭代法(4)的收敛速度与
相关,当ρ(B)<<s时,即矩阵远离奇异时,迭代收敛较快,而当ρ(B)接近s时,即矩阵接近奇异时,迭代收敛很慢.为了加速收敛,对其迭代格式进行改变,得到如下的非定常迭代
式中
,而
0为(4)的初始向量.不难验证上述非定常迭代法(5)第k步计算的结果相当于迭代法(4)第2k步计算的结果,因此(5)与(4)具有相同的收敛性.
定理2.3 设线性方程组(1)的系数矩阵为非奇异的M-矩阵,则迭代法(5)是收敛的,且具有二次收敛率.
证明 由迭代法(4)可得方程组的精确解为
式中
0为(4)的初始向量.直接验证可知非定常迭代法(5)得到的序列{xk} 满足
两边取范数,并利用引理1.2,可得
因此,序列{xk}是收敛的且具有二次收敛率.证毕.
尽管非定常迭代(5)相对于(4)运算量较大,但是上面的定理表明迭代收敛很快.因此是可行的.
本节将通过几个数值检验迭代法(4)与(5)的数值效果.实验中,所有的程序都用Matlab(R2012a)编写,并在个人笔记本电脑(2G CPU和8G内存)上运行.实验结果给出2种方法所需的迭代次数(IT)、CPU运行时间(CPU,s)以及残差(RES),其中残差定义为
.实验中,初始向量取为0向量,当残差满足RES<10-8时迭代终止.
例 3.1[19] 考虑M-矩阵线性方程组(1),其中
而n=m2,b=(1,1,…,1)T ∈ Rn.当m取不同值,2个迭代法得出的结果如表1所示.与迭代法(4)相比,迭代法(5)不仅迭代次数和运行时间都明显要少,而且求得解的精度也高.特别地,当系数矩阵的阶数增加时,迭代法(4)的迭代次数急剧增加,但迭代法(5)的迭代次数增加不明显.
表1 m取不同值时不同迭代公式对应的结果
注:IT表示迭代次数;CPU表示运行时间;RES表示残差.
?
例3.2 考虑M-矩阵线性方程组(1),其中A由下列命令生成
a=rand(n,n);A=diag(a*ones(n,1))-a+eye(n);而b=(1,1,…,1)T∈ Rn.对于阶数n的不同取值,表2中给出了实验结果.从表2中可见,随着系数矩阵阶数的增加,迭代法(4)的迭代次数与运行时间都急剧增加,但迭代法(5)的迭代次数和运行时间并没有明显的增加.
表2 n取不同值时不同迭代公式对应的结果
?
例3.3 考虑M-矩阵线性方程组(1),其中
ε>0是正数.当ε→ 0时,矩阵A接近奇异.对于参数ε的不同取值,实验结果见表3.当参数越来越小时,迭代法(4)的迭代次数急剧增加,但迭代法(5)的迭代次数并没有明显的增加.
表3 参数取不同值时不同迭代公式对应的结果
ε 1 0.1 0.01 0.001式(4)IT 46 378 3 694 36 851 RES 7.939 7×10-9 9.782 4×10-9 9.967 1×10-9 9.997 8×10-9式(5)IT 6 9 12 16 RES 5.372 4×10-12 1.416 1×10-11 1.342 2×10-9 0
由以上3个数值例子可见,迭代法(4)收敛较慢,特别当系数矩阵接近奇异时,收敛非常缓慢,而迭代法(5)始终收敛很快,且求得解的精度也比较高,因此迭代法(5)是较为有效的.
本文提出了一类非定常迭代法以求解M-矩阵线性方程组.理论分析表明该方法具有二次收敛率.数值实验表明,该方法是可行的,而且在一定情况下也是较为有效的.但是该方法在每步迭代中运算量较大,如何减少运算量并保持较快的收敛速度,还有待进一步的研究.另外,由于H-矩阵和M-矩阵具有很多相近的性质,本文的方法还可以推广到H-矩阵线性方程组.
[1] VARGA R S.Matrix iterative analysis[M].Berlin:Springer-Verlag,2000.
[2] MEYER C D.Matrix analysis and applied linear algebra[M].Philadelphia:SIAM,2000.
[3] DEMMEL J W.Applied numerical linear algebra[M].Philadelphia:SIAM,1997.
[4] SAAD Y.Iterative methods for sparse linear systems[M].北京:科学出版社,2009.
[5] 孙蕾.求解非对称线性方程组的不完全最小联合向后扰动法[J].高等学校计算数学学报,2016,38(3):269-288.
[6] 孙蕾.求解大型非对称线性方程组的不完全广义最小向后扰动法[J].数学进展,2016,45(6):939-954.
[7] 温瑞萍,李苏丹.迭代求解非Hermitian正定线性方程组的衍生多分裂方法[J].应用数学,2018,31(1):1-11.
[8] 张迎春,吕全义,肖曼玉.复线性方程组的预处理MCG算法[J].工程数学学报,2018,35(3):308-318.
[9] 潘春平,王红玉,曹文方.非Hermitian正定线性方程组的外推的HSS迭代方法[J].计算数学,2019,41(1):52-65.
[10] 房喜明,令锋,傅守忠.求解线性方程组的一般共轭梯度法[J].数学理论与应用,2019,39(2):62-71.
[11] 蔡静.严格次对角占优线性方程组迭代法的收敛性分析[J].华东师范大学学报(自然科学版),2019(2):1-6.
[12] 王福胜,高娟,赵媛璐,等.混合约束Minimax问题的基于序列线性方程组的模松弛SQP算法[J].应用数学学报,2019,42(2):242-253.
[13] 杜亦疏,殷俊锋,张科.求解大型稀疏线性方程组的贪婪距离随机Kaczmarz方法[J].同济大学学报(自然科学版),2020,48(8):1224-1231.
[14] 温瑞萍,段辉.H-矩阵线性方程组的一类预条件并行多分裂SOR迭代法[J].应用数学,2020,33(4):814-825.
[15] 王燕荣,陈云兰.一种改进的求解大型线性方程组的Jacobi迭代法[J].山东大学学报(理学版),2020,55(6):122-126.
[16] 刘瑞华,邹洋杨,谢挺.求解Hilbert矩阵线性方程组的SOR迭代预处理方法[J].高等数学研究,2020,23(1):60-63.
[17] BERMAN A,PLEMMONS R J.Nonnegative matrices in the mathematical sciences[M].New York:Academic Press,1994.
[18] BAI Z Z,GOLUB G H,NG M K.Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems[J].SIAM Journal on Matrix Analysis and Applications,2003,24:603-626.
[19] 徐树方,高立,张平文.数值线性代数[M].2版.北京:北京大学出版社,2013.
[20] 徐树方.控制论中的矩阵计算[M].北京:高等教育出版社,2011.
A class of non-stationary iterative method for M-matrix linear systems