求解复对称线性系统的IBS迭代方法.pdf

第 44 卷第 3 期 温 州 大 学 学 报（自 然 科 学 版）2023 年 8 月 Vol.44 No.3 Journal of Wenzhou University(Natural Science Edition)Aug.2023 求解复对称线性系统的 IBS 迭代方法 朱亚楠(温州大学数理学院，浙江温州 325035)摘 要：提出一种改进的块分裂（IBS）迭代法，用于求解一类由复对称线性系统演化而来的 22 块实值线性系统对 IBS 迭代法进行收敛性分析，给出使迭代矩阵谱半径极小化的最优参数选择方法，数值实验结果进一步验证了 IBS 迭代方法的数值有效性 关键词：复对称线性系统；IBS 迭代方法；参数；收敛 中图分类号：O241.6 文献标志码：A 文章编号：1674-3563(2023)03-0027-10 DOI：10.20108/j.wzun.202210001 本文的 PDF 文件可以从 https:/ 获得 本文主要考虑复对称线性系统问题：(i)AxWT xb=+=，（1）其中，nnRTW、均为对称矩阵，,nx bC，i1=为虚数单位 易知，复线性系统（1）可以等价地写为如下 22 块实值线性系统：WTufBzbTWvg =，（2）其中，ixuv=+，ibfg=+，,nu v f gR，2nbR这种形式的复对称线性系统广泛应 用于科学计算和工程应用中的许多实际问题，例如电磁学、波传播、量子力学、分子散射、结构动力学等问题，关于更多细节参见文献1-3 近年来，相关学者对问题（1）提出了许多求解技术基于系统（1）中A的厄尔米特和斜厄 尔米特（Hermitian and Skew-Hermitian Splitting,HSS）分裂：A=H+S，其中2A+AH=W，i2AAST=，Bai 等在文献4中最先建立了 HSS 迭代法在 HSS 迭代法的每个步骤中，都 需要求解一个偏移的 HSS 线性系统为了解决该问题，Bai 等在文献5中提出了一种修正的 HSS（Modified Hermitian and Skew-Hermitian Splitting,MHSS）迭代法，在文献6中提出了预处理MHSS（Preconditioned Modified Hermitian and Skew-Hermitian Splitting,PMHSS）迭代法求解线性系统（1），在文献7中将 PMHSS 迭代法的分裂思想用于求解实值线性系统（2）随后，Hezari等在文献8中建立了广义逐次超松弛（Generalized Successive Overrelaxation,GSOR）迭代法，给出了最优参数，提高了迭代收敛的速度文献9提出了新的块分裂（New Block Splitting,NBS）收稿日期：2022-10-08 作者简介：朱亚楠(1998)，女，山东济宁人，硕士研究生，研究方向：计算数学 温州大学学报（自然科学版）(2023)第 44 卷第 3 期 28 迭代法，该方法提出如下形式的预处理矩阵：0IIPI=，（3）并得到最优参数=1本文考虑下述预处理矩阵：0IIPI=，（4）通过一个矩阵块三角分裂，添加一个加速参数后，得到改进的块分裂（Improved Block Splitting,IBS）迭代法，以期提高迭代方法的收敛速度本文中()表示矩阵或向量的共轭转置，T()表示矩阵或向量的转置 1 IBS 迭代法 基于文献9的预处理思想，在（2）式的两边同时左乘块矩阵0IIPI=，得：WTWTufgPBzTWvg+=（5）令0uIIdvIe =，有：0WTWTIIdfgTWIeg+=（6）进一步把（6）式写成：2dWTWdfgAeTWTeg+=+（7）考虑分裂：2002()()()0(1)()WTWWTWMNTWTTWTWT+=+，（8）其中是一个正实数由此分裂得到如下迭代格式，也即 IBS 迭代：(1)()1(1)()()()kkkkddfgMgee+=+，（9）其中迭代矩阵1()()()MN=为：1111002()()0(1)()02().120()()WTWTWTWTWTWIWTT WTW+=+（10）上述迭代格式可以写成如下算法 朱亚楠：求解复对称线性系统的 IBS 迭代方法 29 IBS 迭代法算法：给定任意初始向量(0)ndR，(0)neR，按如下迭代过程计算直至迭代序列()()0(,)k Tk TTkde=收敛到系统（1）的精确解：1()(1)(1)()(1)(1)(1)(1)(1)()2()(1)()=,=kkkkkkkkkkWT dWefgWT eTdWT egudeve+=+=+（）（11）2 IBS 方法的收敛性分析 定理 1 设nnRTW,分别是对称正定阵和对称正半定阵，是一正常数，则：（1）迭代矩阵()的特征值取值如下：0=，2211(1)kkuu+=+，1,2,.,kn=，（12）其中，10.knuuu是矩阵1122SWTW=的特征值（2）谱半径()1，当且仅当的取值范围如下：1）若1nu+；（13）2）若11u 时，2212(1)nnuu+；（14）3）若 1 介于1u与nu之内，即存在整数k，使得110.1.kknuuuu+时，22122111max,2(1)2(1)nnuuuu+（15）（3）迭代矩阵()的谱半径满足：1）若1nu 时，22122111()max 1,1(1)(1)nnuuuu+=+；（16）2）若 1 介于1u与nu之内，即存在整数k，使得110.1.kknuuuu+时，221221111()max 1,1,1(1)(1)2nnuuuu+=+（17）证明：由（10）式有：11102()()=120()()WTWIWTT WTW+=+温州大学学报（自然科学版）(2023)第 44 卷第 3 期 30 11111222211111111112222222202()=120()()WIWTWWIWIWTWWTWIWTWW+11111222211111111112222222202()00120()()00IWTWWWIIWTWWTWIWTWWW+，即()相似于下述矩阵()，11102()()120()()ISIISS IS+=+，（18）其中1122SWTW=，故矩阵()与()有相同的特征值设矩阵S的特征值分解为TSUU=S，其中nnRU是一个正交矩阵，12diag(,)nu uuS=令：T1T00UPU=（19）记：1T111T1111102()00()()=12000()()02().120()()ISUUPPUUIISS ISIIII+=+S+SS+S（20）由于()、()与()有相同的特征值，注意到1112()()III+SS+S为对角阵且主对角元为2222111(1)(1)kkkkuuuu+=+，1,2,.,kn=，故()的特征值为：0，2211,1,2,.,(1)kkuknu+=+（21）故定理 1 中的结论（1）得证下证定理 1 中的结论（2），由（21）式知：222211()1111 11(1)(1)kkkkuuuu+，22111(1)kkuu+显然成立 接下来考虑2211 1(1)kkuu+令221()2(1)uf uu+=+，1,nuu u，则有2243d()1 2(1)2(1)(1)1d2(1)(1)f uuuuuuuuu+=+朱亚楠：求解复对称线性系统的 IBS 迭代方法 31 分三种情况进行讨论 1）若1nu 时，此时d()0df uu+2）若11u 时，此时d()0df uu，()f u关于u单调递增，此时2211max()2(1)nkk nnuf uu+=+，得2212(1)nnuu+3）若 1 介于1u与nu之内，即存在整数k，使得110.1.kknuuuu+时，()f u分别在1,1u和1,nu单调递减和单调递增，此时221221111max()2(1)2(1)nkk nnuuf uuu+=+，得22122111max2(1)2(1)nnuuuu+，故定理 1 中的结论（2）得证，下证定理 1 中的结论（3）令221()1(1)us uu+=+，0,)u+，3ds()2(1)d(1)uuuu=+分两种情况进行讨论 1）当1nu，()s u单调递增，则迭代矩阵()的谱半径为：22122111()max 1,1(1)(1)nnuuuu+=+同理，当11u，ds()0duu，()s u单调递减，迭代矩阵()的谱半径也为（16）式 2）当110.1.kknuuuu+时，()s u分别在1,1u和1,nu单调递增和单调递减，于是()s u在1u=处有最大值1(1)12s=，迭代矩阵()的谱半径为：221221111()max 1,1,1(1)(1)2nnuuuu+=+综合上述 1）和 2）两种情况知迭代矩阵的谱半径为：2211n221221122111max 1,1,1+=+或 定理 1 得证 温州大学学报（自然科学版）(2023)第 44 卷第 3 期 32 定理 1 给出了 IBS 迭代法的收敛条件，下面讨论使()极小化的最优参数以及相应的最优收敛因子 定理 2 设nnRTW,分别是对称正定与对称正半定的，矩阵1122SWTW=的特征值为10.knuuu，则极小化()的最优参数及相应的最优收敛因子为：（1）若1nu 时，222211221(1)(1)(1)(1)2(1)(1)nnnuuuuuu+=+，（22）相应最优收敛因子为：2222112222112222111222211(1)(1)(1)(1),+（23）（2）若 1 介于1u与nu之内，即存在整数k，使得110.1.kknuuuu+时，221112122122(1)(1)1,4(1)2(1)(1)1,4(1)nnnnnuuuuuuuuuu+=+，（24）相应最优收敛因子为：221112211221222(1)(1)1,2(1)(1)()2(1)(1)1,2(1)(1)nnnnnnuuuuuuuuuuuu+=+（25）证明：1）若1nu+，所以()us关于单调递增，()us关于单调递减，从而函数()us关于先减后增，如图 1，由图 1 可知当交点纵坐标最大值时相应横坐标即为最优的 计算2212211+1+1=1(1+)(1+)nnuuuu，得222211221(1)(1)(1)(1)=2(1)(1)nnnuuuuuu+朱亚楠：求解复对称线性系统的 IBS 迭代方法 33 图 1 ()us的图像 把带入221()1(1)nnuu+=+，得到相应的最优收敛因子：222211222211(1)(1)(1)(1)()(1)(1)(1)(1)nnnnuuuuuuuu+=+同理，若11u 时，的选取也如（22）式，把带入21211()1(1)uu+=+，得到相应的最优收敛因子：222211222211(1)(1)(1)(1)()(1)(1)(1)(1)nnnnuuuuuuuu+=+2）若 1 介于1u与nu之内，即存在整数k，使得110.1.kknuuuu+时，221221111argmin()argminmax 1,1,1(1)(1)2nnuuuu+=+，由定理 2 中结论 1）知()us关于单调递增，()us关于单调递减，()nus、1()us和1()s图像有两种情况 当11nuu，即2212211+1+11(1+)(1+)nnuuuu，也即1()()nuuss，见图 2 由图 2 可以看出，1()us的图像在()nus的图像上方，可知交点纵坐标取得最大值时相应横坐标为最优参数，计算21211+11=12(1+)uu，得2211212(1)(1)4(1)uuu+=+，把带入1()12=，得到相应的最优收敛因子：221122112(1)(1)()2(1)(1)uuuu+=+当11nuu，即2212211+1+11(1+)(1+)nnuuuu，也即1()()nuuss，见图 3 温州大学学报（自然科学版）(2023)第 44 卷第 3 期 34 图 2 ()us的图像（11nuu）图 3 ()us的图像（11nuu）由图 3 可以看出，()nus的图像在1()us的图像上方，可知交点纵坐标取得最大值时相应横坐标为最优参数，计算221+11=12(1+)nnuu，2222(1)(1)4(1)nnnuuu+=+，把带入1()12=，得到相应的最优收敛因子22222(1)(1)()2(1)(1)nnnnuuuu+=+定理 2 得证 3 数值实验 通过数值实验来证明 IBS 迭代法的有效性 本文中的所有实验都在电脑内存为 16.0 GB，CPU型号为Intel(R)Core(TM)i5-10500 CPU3.10GHz 3.10 GHz，操作系统为Windows 10的MATLAB（R2021a）上完成选取零向量(0)T(0)TT(),()xy12 nR为初始向量，设线性系统的精确解为()T()TT(),()xy 12 nRIT为求解问题的迭代算法达到收敛时的总迭代步数（单位：次），CPU(s)为求解问题的迭代算法达到收敛时所需要的总运行时间（单位：秒），RES为相对残差，()kx为当前的迭代残量，则停机准则为：()622RES10kbAxb=，或者迭代次数超过 400 例 15 考虑如下复对称线性系统方程：3333()i()KIKI ub+=，（26）其中，为时间步长，K为单位正方形0,1 0,1内、均匀网格h h上、具有齐次狄利克雷边界条件的负拉普拉斯算子L=的五点中心差分阵，11hm=+，矩阵nnRK拥有如下张量积形式2nm=：IVVIKmm+=（其中I是单位阵），2tridiag(1,2,1)m mmVhR=，表示克罗内克积 数值实验选取右端向量为2(1 i),1,2,.,(1)jjbjnj=+，i1=为虚数单位 在进行实验时令h=，并在方程组两边同时乘以2h正规化系数矩阵和右端向量 表 1 是关于 IBS、朱亚楠：求解复对称线性系统的 IBS 迭代方法 35 NBS、PMHSS 和 HSS 迭代法的实验参数选取，取法分别按照本文定理 2、文献9、文献6和文献4，表 2 为实验结果 表 1 IBS、NBS、PMHSS 和 HSS 的实验参数选取 迭代法 mm 88 1616 3232 6464 9696 IBS 0.528 2 0.543 4 0.558 0 0.568 7 0.573 1 NBS 1 1 1 1 1 PMHSS 1.737 4 1.068 8 0.673 4 0.440 2 0.348 6 HSS 1.737 4 1.068 8 0.673 4 0.440 2 0.348 6 表 2 IBS、NBS、PMHSS 和 HSS 的实验结果 迭代法 项目 mm 88 1616 3232 6464 9696 IBS IT 6 7 8 8 8 CPU(s)0.003 7 0.004 5 0.007 7 0.049 1 0.139 7 RES(1e-08)2.942 3 1.173 3 0.366 9 0.582 5 0.584 0 NBS IT 21 21 21 21 21 CPU(s)0.004 9 0.007 2 0.016 9 0.121 6 0.394 5 RES(1e-08)3.501 8 2.410 9 1.439 7 0.786 6 0.539 3 PMHSS IT 30 40 59 88 109 CPU(s)0.005 2 0.006 5 0.022 5 0.230 0 1.057 1 RES(1e-08)6.558 0 4.274 6 2.409 0 1.102 1 0.782 8 HSS IT 24 39 63 97 122 CPU(s)0.004 4 0.005 1 0.023 1 0.270 7 1.234 3 RES(1e-07)5.547 1 7.494 1 7.213 8 7.240 2 7.734 5 4 结 论 本文基于 NBS 迭代方法提出了一种 IBS 迭代方法，并证明了它的收敛性在适当的收敛条件下，给出了该方法的最优迭代参数和相应的最优收敛因子数值实验表明，在求解线性方程组（1）时，该方法优于 NBS、PMHSS、HSS 等迭代方法 参考文献 1 Feriani A,Perotti F,Simoncini V.Iterative System Solvers for the Frequency Analysis of Linear Mechanical Systems J.Computer Methods in Applied Mechanics and Engineering,2000,190(13/14):1719-1739.2 Howle V E,Vavasis S A.An Iterative Method for Solving Complex-Symmetric Systems Arising in Electrical Power Modeling J.SIAM Journal on Matrix Analysis and Aapplications,2005,26(4):1150-1178.3 Saad Y.Iterative Methods for Sparse Linear Systems M.Philadelphia:Society for Industrial and Applied Mathematics,2003:45-59.4 Bai Z Z,Golub G H,Ng M K.Hermitian and Skew-Hermitian Splitting Methods for Non-Hermitian Positive Definite 温州大学学报（自然科学版）(2023)第 44 卷第 3 期 36 Linear Systems J.SIAM Journal on Matrix Analysis and Applications,2003,24(3):603-626.5 Bai Z Z,Benzi M,Chen F.Modified HSS Iteration Methods for a Class of Complex Symmetric Linear Systems J.Computing,2010,87(3):93-111.6 Bai Z Z,Benzi M,Chen F.On Preconditioned MHSS Iteration Methods for Complex Symmetric Linear Systems J.Numerical Algorithms,2011,56(2):297-317.7 Bai Z Z,Benzi M,Chen F.Preconditioned MHSS Iteration Methods for a Class of Block Two-by-two Linear Systems with Applications to Distributed Control Problems J.IMA Journal of Numerical Analysis,2013,33(1):343-369.8 Salkuyeh D K,Hezari D,Edalatpour V.Generalized Successive Overrelaxation Iterative Method for a Class of Complex Symmetric Linear System of Equations J.International Journal of Computer Mathematics,2015,92(4):802-815.9 Huang Z G.Efficient Block Splitting Iteration Methods for Solving a Class of Complex Symmetric Linear Systems J.Journal of Computational and Applied Mathematics,2021,395:113574.(编辑：封毅)IBS Iteration Method for Solving Complex Symmetric Linear Systems ZHU Yanan(College of Mathematics and Physics,Wenzhou University,Wenzhou,China 325035)Abstract:An improved block splitting(IBS)iteration method is proposed for solving a class of block two-by-two real linear systems which arises from complex symmetric linear systems.We give the convergence analysis for the IBS iteration method and obtain the optimal iteration parameter which minimizes the spectral radius of the iteration matrix.Numerical results demonstrate the effectiveness of the IBS iteration method.Key words:Complex Symmetric Linear Systems;IBS Iteration Method;Optimal Parameter;Convergence (英文审校：黄璐)