求解非厄尔米特正定线性系统的SSI-SS迭代方法.pdf

第 44 卷第 3 期 温 州 大 学 学 报（自 然 科 学 版）2023 年 8 月 Vol.44 No.3 Journal of Wenzhou University(Natural Science Edition)Aug.2023 求解非厄尔米特正定线性系统的 SSI-SS 迭代方法 王 虹(温州大学数理学院，浙江温州 325035)摘 要：基于耦合的思想，提出一个新的 SSI-SS 迭代法来求解非厄尔米特正定线性系统从理论上证明了该方法的收敛性，并给出了其最优参数的选取与 SHSS-SS 方法相比，该方法的迭代矩阵的谱半径上界更小最后通过数值结果验证了该方法的数值有效性 关键词：非厄尔米特正定；SSI-SS 迭代方法；耦合；收敛速度 中图分类号：O241.6 文献标志码：A 文章编号：1674-3563(2023)03-0020-07 DOI：10.20108/j.wzun.2022.05.03.0001 本文的 PDF 文件可以从 https:/ 获得 本文主要考虑求解非厄尔米特正定线性系统 Axb=，（1）其中n nAC是一个非厄尔米特正定矩阵，即*2AA+是一个厄尔米特正定矩阵，*A为A的共轭转置，,nx bC这种形式的线性系统广泛应用于科学计算和工程领域中1-3近年来学者们研究问题（1）的兴趣激增，针对这类线性系统提出了许多求解技术 基于矩阵的厄尔米特和斜厄尔米特（Hermitian and Skew-Hermitian Splitting,HSS）分裂：AHS=+，其中*1()2HAA=+，*1()2SAA=，Bai 等人提出了 HSS 迭代法4之后，Li等人5提出了单步的 HSS（Single-step HSS,SHSS）迭代法，给出了相应的迭代格式（()kx表示第k步迭代的近似解，下同）：(1)()()()kkIH xIS xb+=+，0,1,2,.k=（2）并讨论了 SHSS 迭代法的收敛性质，给出了相应的最优参数Wang 等人6在此基础上提出了 SSI（Single-Step Iteration）迭代法，其迭代格式为：(1)()()()kkPH xPS xb+=+，0,1,2,.k=（3）其中P是任意给定的厄尔米特正定矩阵文献7中，Bai 等人提出了 SS（Shift-Splitting）迭代法：(1)()()()2kkIA xIA xb+=+，0,1,2,.k=（4）其中为一正参数在文献8中，Li 和 Wu 等人为了加快 SHSS 的收敛速度，将此迭代法与 SS 收稿日期：2022-05-03 作者简介：王虹(1997)，女，浙江嘉兴人，硕士研究生，研究方向：计算数学 王虹：求解非厄尔米特正定线性系统的 SSI-SS 迭代方法 21 迭代法进行耦合，提出了 SHSS-SS 迭代法：1()()21()(1)2()()()()2kkkkIH xIS xbIA xIA xb+=+=+，0,1,2,.k=（5）其中为一正参数，I是单位矩阵 本文将在 SHSS-SS 的基础上讨论更一般的 SSI-SS 耦合方法 1 SSI-SS 迭代法 SSI-SS 迭代方法(0)x为一给定的初始迭代向量，对于0,1,2,.k=直到()kx收敛，通过下面式子来计算(1)kx+：1()()21()(1)2()()()()2kkkkPH xPS xbPA xPA xb+=+=+，（6）其中P是一个任意给定的厄尔米特正定矩阵 消除上述迭代的中间向量1()2kx+，进而可得到单步迭代格式：(1)()kkxMxNb+=+，0,1,2,k=（7）其中，11()()()()MPAPA PHPS=+，11111()()()2()()(3)()NPAPA PHPAPAPHSPH=+=+为得到该方法的收敛条件，下面讨论迭代矩阵M的谱半径()M 引理 1 若,a b mR+，当ab时，有bbmaam+；当ab+证明：当ab时，()0()bbmba maama am+=+，于是bbmaam+同理可得，当ab+证毕 定理 1 假设n nAC是一个非厄尔米特正定矩阵，*1()2HAA=+，*1()2SAA=，且P是一个厄尔米特正定矩阵，则迭代矩阵M的谱半径()M有上界 2max1min11m+=+（8）另外，()H表示H的特征值集合，()S表示S的奇异值集合，min是H的最小特征值，maxm是S的最大奇异值，其中1122HPHP=，1122SPSP=，1122APAP=证明：由迭代矩阵11()()()()MPAPA PHPS=+，可得：温州大学学报（自然科学版）(2023)第 44 卷第 3 期 22 111()()()()PAPAPAPPPA+=+=111()()IP AIP A+=111111111122222222()()=()()PIPAPIPAPPPIAIA P+同理，111122()()()()PHPSPIHIS P+=+，则 11()()()()()MIAIA IHIS=+令*x Hxtx x=，根据引理 1 可得：*21*200*2*2*00*()()()()()maxmax()()()1 21 2maxmax1 21 2xxxxx IA IA xx xxAA xx AA xIAIAx IA IA xx xxAA xx AA xx Hxx AA xx HxAx xx xx xx Hxx Hxx AA xAx xx xx x+=+22 令22221 2()1 2tAf ttA+=+，由222224(1)()0(12)Af ttA+=+可知，()f t关于t单调递减，故 22min1222min21 2()()112AIAIAA+另外，11222()()()()IHISIHIS+=2max2()()min11maxmax111iiiHSimmm+=+，因此有：2max1122min1()()()()()1MIAIAIHISm+证毕 由于n nAC是非厄尔米特正定矩阵，由2maxmin1()1Mm+可知，当2maxmin111m+，即22maxminmin12m时，该方法收敛 2 特殊情形PH=的讨论 特别地，当PH=，且为一正参数，该方法的迭代矩阵变为：11()()()()THAHAHHHS=+，（9）王虹：求解非厄尔米特正定线性系统的 SSI-SS 迭代方法 23 此时，1HI=，1HSS=，1122HSHSH=可得到类似定理 1 的结论 定理 2 若A是非厄尔米特正定矩阵，则迭代矩阵T的谱半径()T有上界 22max()()1Hm+=+，（10）其中maxHm是HS的最大奇异值，且 1）若max1Hm，则()1，该迭代方法收敛；2）若max1Hm，则()1 定理 3 若定理 2 的条件满足，则极小化谱半径上界()的最优参数*为：22max2*max()=argmin()1HHmm+=+，（11）max2maxmin()1()HHm m=+（12）证明：将谱半径的上界()对进行求导，得到2max222max()()(1)()HHm m=+，于是，当2max()Hm时，()0，此时()关于单调递增；当2max()Hm时，()0，此时()关于单调递减因此，当2*max()Hm=时，*()为最小值，且经过简单计算该最小值为max*2max()1()HHm m=+证毕 注：当PI=时，本文中的迭代方法退化为 SHSS-SS 迭代法（5），并可得到其迭代矩阵的谱半径上界在经过极小化后的最小值为：maxmaxmin222minmaxmaxmin()1nnn=+，（13）其中minn是H的最小特征值，max是S的最大奇异值（详见文献8）令2()1xf xx=+，可知()f x关于x单调递增又由 1111max2222max22min222HHSHSHHSHmn=，（14）温州大学学报（自然科学版）(2023)第 44 卷第 3 期 24 有*()()因此，SSI-SS 迭代方法的迭代矩阵的谱半径上界比原方法 SHSS-SS 的迭代矩阵的谱半径上界小，从而 SSI-SS 方法收敛速度更快 3 数值实验 根据上面的理论分析，下面通过一些数值实验来验证 SSI-SS 迭代法求解系统（1）的有效性 所有的数值实验将在 MATALB（R2017a）环境中实现 在下面实验中，取向量(0)*(0,0,.,0)x=为初始迭代向量，其中*表示相对应的最优参数，IT 代表总迭代步数（单位：次），CPU 代表算法达到收敛时所需要的总运行时间（单位：秒），RES 代表相对残差，设置停机准则为82210bAxb，或者迭代次数超过 400 算例 19 考虑二维对流-扩散方程 xxyyxyuuuug+=，其中，g是一给定的函数，u满足 Dirichlet 型边界条件 在0,1 0,1上采用五点中心差分离散，可以得到系统（1）的系数矩阵 ATIIT=+，其中，11hm=+，表示 Kronecker 积，I是单位矩阵，T是一个三对角矩阵，tridiag(1T=,2,1)eeRR+，并且2ehR=是网格 Reynolds 数，其系数矩阵A的维数为2nm=表 1 中列出了不同的迭代方法在8,16,32,64m=时的最优参数选取在 HSS 方法中，取*minmax=，其中min和max分别表示H的最小、最大特征值；SHSS 与 SHSS-SS 两个方法的最优参数选取相同，都为2max*minn=，其中minn是H的最小特征值，max是S的最大奇异值；在 CRI（Combination Method of Real Part and Imaginary Part）方法10中，最优参数恒取*1=；本文中讨论的迭代方法 SSI-SS 按（11）式选取最优参数 各种迭代法的实验结果见表 2结果表明，SSI-SS 方法所需的迭代步数明显比其他方法所需的少，并且 CPU 运行的时间也比较短 表 1 HSS、SHSS、CRI、SHSS-SS 和 SSI-SS 迭代法的最优参数的选取 迭代法 参数*m=8 m=16 m=32 m=64 HSS 1.368 0.735 0.380 0.193 SHSS 0.181 0.196 0.201 0.202 CRI 1 1 1 1 SHSS-SS 0.181 0.196 0.201 0.202 SSI-SS 0.023 0.024 0.025 0.025 王虹：求解非厄尔米特正定线性系统的 SSI-SS 迭代方法 25 4 结 语 本文基于将两个迭代方法耦合的思路，将 SSI 与 SS 迭代法进行耦合，重新得到一个新的迭代方法从理论上证明了该方法的收敛性，与 SHSS-SS 相比，该迭代方法的迭代矩阵的谱半径上界更小，因此收敛速度更快，数值算例也验证了新方法的优越性 参考文献 1 Bai Z Z.Block Alternating Splitting Implicit Iteration Methods for Saddlepoint Problems from Timeharmonic Eddy Current Models J.Numerical Linear Algebra with Applications,2012,19(6):914-936.2 Saad Y.Iterative Methods for Sparse Linear Systems M.Philadelphia:Society for Industrial and Applied Mathematics,2003:103-125.3 Noormohammadi Pour H,Sadeghi Goughery H.New Hermitian and Skew-Hermitian Splitting Methods for Non-Hermitian Positive-definite Linear Systems J.Numerical Algorithms,2015,69(1):207-225.4 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(3):603-626.5 Li C X,Wu S L.A Single-step HSS Method for Non-Hermitian Positive Definite Linear Systems J.Applied Mathematics Letters,2015,44:26-29.6 Wang X,Xiao X Y,Zheng Q Q.A Single-step Iteration Method for Non-Hermitian Positive Definite Linear Systems J.Journal of Computational and Applied Mathematics,2019,346:471-482.7 Bai Z Z,Yin J F,Su Y.A Shift-Splitting Preconditioner for Non-Hermitian Positive Definite Matrices J.Journal of 表 2 HSS、SHSS、CRI、SHSS-SS 和 SSI-SS 迭代法的实验结果 方法 项目 实验结果 m=8 m=16 m=32 m=64 HSS IT 48 88 172 345 CPU 0.003 7 0.010 9 0.689 9 16.438 2 RES 7.46e-9 8.53e-9 9.08e-9 9.94e-9 SHSS IT 19 53 173 CPU 0.003 6 0.007 5 0.575 3 RES 8.94e-9 9.25e-9 9.49e-9 CRI IT 19 18 17 14 CPU 0.005 8 0.012 2 0.034 8 0.145 9 RES 8.53e-10 3.49e-10 6.88e-11 5.34e-11 SHSS-SS IT 9 16 56 202 CPU 0.002 4 0.003 7 0.204 9 8.810 8 RES 1.77e-9 5.76e-9 9.48e-9 9.80e-9 SSI-SS IT 9 8 7 7 CPU 0.002 0 0.002 5 0.028 4 0.317 9 RES 3.27e-9 6.36e-9 8.74e-9 1.66e-9 注:表中“”表示该情况下不收敛或者迭代步数超过 400.温州大学学报（自然科学版）(2023)第 44 卷第 3 期 26 Computational Mathematics,2006,24(4):539-552.8 Li C X,Wu S L.A SHSS-SS Iteration Method for Non-Hermitian Positive Definite Linear Systems J.Results in Applied Mathematics,2022,13:100225.9 Huang Y M.A Practical Formula for Computing Optimal Parameters in the HSS Iteration Methods J.Journal of Computational and Applied Mathematics,2014,255:142-149.10 Wang T,Zheng Q Q,Lu L Z.A New Iteration Method for a Class of Complex Symmetric Linear Systems J.Journal of Computational and Applied Mathematics,2017,325:188-197.(编辑：王一芳)SSI-SS Iterative Method for Solving Non-Hermitian Positive Definite Linear System WANG Hong(College of Mathematics and Physics,Wenzhou University,Wenzhou,China 325035)Abstract:Based on the idea of coupling,this paper proposed a new SSI-SS iterative method to solve non-Hermitian positive definite linear systems.This paper theoretically proved the convergence of this method and gave the selection of its optimal parameters.Compared with the SHSS-SS method,this method has a smaller upper bound of the spectral radius of the iterative matrix.Finally,the numerical results verified the numerical effectiveness of the method.Key words:Non-Hermitian Positive Definite;SSI-SS Iterative Method;Coupling;Convergence Speed (英文审校：黄璐)