半正定线性系统广义非定常多分裂二阶段迭代方法的收敛性
时间：2023-05-30 13:20:16 来源：雅意学习网 本文已影响 人 
崔艳星, 王川龙, 江文胜
(1. 长治学院数学系，长治 046000; 2. 太原师范学院数学系，太原 030619;3. 中国海洋大学物理海洋教育部重点实验室，青岛 266003)
奇异半正定系统的数值解法有广泛且重要的应用，一般情况下，有限元或有限差分方法产生的代数系统是稀疏正定或半正定线性方程组。上述问题可以归结为稀疏线性方程组的求解问题
其中b ∈R(A),A ∈Rn×n为对称正定或半正定矩阵。
稀疏线性方程组一般用矩阵的分裂迭代法[1–3]求解，该方法把A分裂为一个非奇异矩阵M和另一同阶矩阵N的差，并且构造出相应的收敛迭代格式。作为上述算法的推广，O’Leary 和White 首先给出了矩阵多分裂算法[4]，并且讨论了它的收敛性，该算法实现了在并行计算机上求解线性系统。另外的一些学者也对矩阵多分裂算法展开研究，获得了不同类型分裂下的收敛性定理[5–6]。
Lee 等构造了半正定线性方程组分裂迭代算法[7]，并且在一组简便条件下证明了它为半范数收敛的。该算法把A分裂为奇异矩阵M和矩阵N的差，进一步丰富了分裂迭代算法。在此基础上，Cui 等构造了半正定线性系统的多分裂迭代算法[8]，并证明了其收敛性。受此启发，Cui 等给出了半正定线性系统广义并行多分裂迭代算法[9]，其迭代格式为
其中Ej(j= 1,2,···,J)是和为单位矩阵I的非负权重矩阵序列。在定常情形下，该算法的商收敛和收敛是等价的。在非定常情形下，该算法是半范数收敛，进而是商收敛的。
为了便于对A进行预处理，二阶段迭代算法先分解A为矩阵M和矩阵N的差，而后分解M为B和C的差。作为求解线性方程组迭代解法的一类改进，如此构造出的二阶段迭代方法[1,10]受到人们的广泛重视，其迭代格式如下
内层迭代次数充分大时，Frommer 和Szyld 讨论了非定常二阶段迭代方法的收敛条件[11]。内外层分裂为特定分裂时，他们进一步研究了分块矩阵两阶段迭代方法的收敛定理[12]。系数矩阵是H-矩阵和单调矩阵时，Bai 在一个约束条件下给出了多分裂二阶段迭代算的收敛定理[13]。依据系数矩阵的不同，学者们给出了其它多分裂二阶段多分裂算法[14–17]。上述算法可以解决一些区块链实用模型[18–20]的求解，从而丰富了该类算法的应用范围。
为了更高效的求解稀疏线性方程组，本文给出了一种带有预处理项非定常多分裂二阶段迭代方法。高自由度的预处理矩阵通过对第二阶段分裂的预处理决定了该方法拥有较好的收敛性，数值实验表明该非定常多分裂二阶段迭代方法比传统的计算方法拥有更高的执行效率。
Rn、Rn×n、AT、N(A)和R(A)分别代表n维实向量空间，n×n实矩阵空间，A的转置，A的零空间和矩阵A值域。当A为奇异矩阵时，A†称为A的广义逆，那么P=A†A为N(A)的正交补。x**=A†b称为奇异线性系统(1)的最小二乘解[2]，如果极限Tk(k →∞)存在，那么我们称矩阵T收敛[1]。
下列概念是研究半正定系统算法收敛性的基石。
定义1[1,21]设P=A†A,∀x(0)∈Rn，若迭代序列{xk}收敛到(1)的解x*，则该迭代格式收敛；
若迭代序列{Pxk}收敛到解x**=A†b，则该迭代格式商收敛。
定义2[3]设A和T分别是n阶对称半正定矩阵和n阶矩阵。若
则称‖·‖A是矩阵T的一个半范数。
定义3[3,7]设A和T分别是n阶对称半正定矩阵和n阶矩阵。若迭代格式xk+1=Txk中T满足‖T‖A ＜1，那么该迭代格式是半范数收敛的。
引理1[7]设A和M分别是n阶对称半正定矩阵和n阶矩阵。若R(A)⊂R(M)，则有MM†A=A成立。
我们构造半正定线性系统(1)的广义二阶段多分裂如下
M为对称半正定矩阵，且满足R(A)⊂R(M)。这里的广义有二层含义：第一层广义体现在矩阵序列Rj(j= 1,2,···,J)对M进行进行了预处理；
第二层广义体现在Rj(j=1,2,···,J)选取的高自由度。
基于(4)式的第一阶段分裂A=M-N，稀疏线性方程组(1)可以改写为
Mx=Nx+b.
根据矩阵M的特征，等式的两边同乘上预处理矩阵Rj(j= 1,2,···,J)，并使用方程(1)的第二阶段分裂，可得
x=(I-RjM)x+RjNx+Rjb.
由此，我们可以构建相应的迭代格式求解半正定线性系统(1)。
算法1广义非定常多分裂二阶段迭代算法
步骤1构建多分裂。建立系数矩阵A的第一层分裂的分裂矩阵M和N，任取长度为J的预处理矩阵序列Rj(j= 1,2,···,J)，建立系数矩阵A的第二层分裂的分裂矩阵I和I-RjM。
步骤2构建迭代序列{xk}。给定任意初值x(0)，以yj,0=x(k)为内层循环初值，根据迭代格式
yj,l=(I-RjM)yj,l-1+RjNyj,0+Rjb,
计算内层迭代终值yj,μj。把该值通过加权求和公式
求得x(k+1)。
步骤3算法终止条件判断。若‖x(k+1)-x(k)‖＞eps，则转到步骤2。否则，转到步骤4。
步骤4输出结果。即求解了稀疏线性方程组(1)并输出计算解。
现在，我在这个城市已经生活了3个年头，有了自己的朋友圈，朋友间聚会的时候我有一次把这个故事说给了大家听，我说我刚来的时候是如何不合群，幸好当时有一个好邻居，她身材高挑，人也很好，经常喜欢戴一副墨镜，很酷，她对我很是照顾，只不过后来，她就利用了我。朋友们很惊奇，我就说了那一年发生的事情。有人说，以后遇到这种人，一定不要轻信，满嘴谎言。还有人说，我们公司两年前来了一个女人，也是整天戴着墨镜，和你描述的很像呢。
算法1可使用逻辑语言结构化表示为：
其中eps 是预先设定的精度，内层迭代次数μj与相应的次外层迭代序号j相关，消去内层迭代变量yj,l，外层迭代变量为
根据引理1，上式可以改写为
为方便讨论算法的收敛性，算法1 可以改写成更加紧凑的迭代格式。
引理2若A和M分别是n阶对称半正定矩阵和n阶矩阵且满足R(A)⊂R(M)，则广义多分裂两阶段迭代算法1 的迭代格式为
证明 根据(5)式～(7)式，只需证明下式
成立。因为AA†A=A，所以AA†b=b,b ∈R(A)。因此
根据(9)式，只需证明下式
成立。因为
所以(8)式成立。
算法1的收敛性由下面的定理刻画。
定理1若A和M分别是n阶对称半正定矩阵和n阶矩阵，+Rj-MRj(j=1,2,···,J)在R(M)上对称正定且满足R(A)⊂R(M)，若
则存在一个与K有关的正数η，使得μj ＞K时，有
成立，并且迭代格式(8)收敛，进而商收敛。
证明
因此，存在一个与K有关的正数η，使得迭代次数μj ＞K(j=1,2,···,J)时，有
这时，迭代格式(8)的迭代矩阵满足
根据引理2，得
因此
根据定义2，可得
再由引理1，可得
所以
根据定义1，迭代格式(8)也是商收敛的。
Wen 等利用一个系数矩阵为三对角矩阵的算例验证了具有任意权矩阵的多分裂迭代算法的有效性[22]，其中系数矩阵来源于复对称线性系统[23]的虚部矩阵。
为了体现算法1 的普适性，本节求解1 000 阶稀疏线性方程组Ax=b，其中系数矩阵A为五对角矩阵
为验证算法的有效性，我们分别利用Jacobi 迭代法[3]、Gauss-Seidel迭代法(G-S 迭代法)[3]和算法1 计算该数值算例。实验中，eps 统一设定为10-6。我们取初始值为零向量，两相邻迭代解的残差小于eps 时迭代终止。算法1 中，N是与A同阶的单位向量，计算结果见表1。
表1 Jacobi 迭代、G-S 迭代及算法1 计算结果比较
数值对比实验表明，与经典的Jacobi 迭代法和G-S 迭代法相比，算法1 的执行效率更高。一方面，算法1 的迭代次数约为Jacobi 迭代法和G-S 迭代法的37%和65%。另一方面，算法1 的CPU 占用时间约为Jacobi 迭代法和G-S 迭代法的34%和62%。用迭代次数和CPU 占用时间来衡量，算法1 的执行效率都优于Jacobi 迭代法和G-S 迭代法。这说明算法1 是求解方程(1)的一个应用前景好的数值算法。
基于预处理的广义二阶段多分裂，本文给出了广义非定常多分裂二阶段迭代算法。当J个预处理矩阵Rj满足+Rj-MRj在R(M)上对称正定且R(A)⊂R(M)时，半正定线性系统广义非定常多分裂二阶段迭代方法是收敛的，并且是商收敛的。数值算例表明了该算法的有效性和实用性。
猜你喜欢 迭代法线性方程组收敛性 迭代法求解一类函数方程的再研究中等数学(2022年8期)2022-10-24一类整系数齐次线性方程组的整数解存在性问题中等数学(2022年6期)2022-08-29齐次线性方程组解的结构问题的教学设计数学学习与研究(2022年17期)2022-08-16求解非线性方程组的Newton迭代与Newton-Kazcmarz迭代的吸引域南京大学学报(数学半年刊)(2021年2期)2021-04-19求解非线性方程的4阶收敛的无导数迭代法*哈尔滨师范大学自然科学学报(2020年4期)2020-03-08Cramer法则推论的几个应用数学学习与研究(2018年3期)2018-03-14改进的布洛依登算法哈尔滨理工大学学报(2017年6期)2018-01-09多种迭代法适用范围的思考与新型迭代法科学家(2017年13期)2017-08-11西部地区金融发展水平的收敛性分析商业经济研究(2016年14期)2016-09-14我国省域经济空间收敛性研究科教导刊·电子版(2016年16期)2016-07-18
