您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(理学版)》

《山东大学学报(理学版)》 ›› 2024, Vol. 59 ›› Issue (10): 1-9.doi: 10.6040/j.issn.1671-9352.0.2023.225

•   •    下一篇

一类复对称线性方程组的块三角分裂及其预处理迭代算法

王洋()   

  1. 吉林师范大学数学与计算机学院, 吉林 四平 136100
  • 收稿日期:2023-05-19 出版日期:2024-10-20 发布日期:2024-10-10
  • 作者简介:王洋(1982—), 女, 副教授, 硕士生导师, 博士, 研究方向为数值代数及其应用. E-mail: yyang3721@163.com
  • 基金资助:
    吉林省社会科学基金资助项目(2021B136)

Block triangular splitting and its preconditioning iterative algorithms for a class of complex symmetric linear systems

Yang WANG()   

  1. College of Mathematics and Computer, Jilin Normal University, Siping 136100, Jilin, China
  • Received:2023-05-19 Online:2024-10-20 Published:2024-10-10

摘要:

基于2×2块矩阵的块三角分裂, 提出求解复对称线性方程组的块三角分裂(BTS)迭代方法及其预处理迭代方法(PBTS)。理论分析表明, 在迭代参数α满足一定的条件下, BTS和PBTS迭代方法是收敛性的, 给出两类方法迭代格式中理论最优参数的计算方法。数值实验结果证明BTS迭代方法和PBTS迭代方法的有效性和优越性。

关键词: 复对称线性方程组, 收敛性分析, 块三角分裂, 预处理

Abstract:

Based on block triangular splitting for block 2×2 matrix, the block triangular splitting(BTS) iteration method and the preconditioned block triangular splitting (PBTS) iteration method for a class of complex symmetric linear system are proposed. Theoretical analysis shows that the BTS and PBTS methods converge under certain conditions. The optimal iteration parameters of these two methods are obtained. Numerical experiments demonstrate the effectiveness and superiority of the BTS method and the PBTS iterative methods.

Key words: complex symmetric linear system, convergence analysis, block triangular splitting, preconditioning

中图分类号: 

  • O242.2

图1

例1中迭代矩阵谱半径的比较"

图2

例2中迭代矩阵谱半径的比较"

图3

例3中迭代矩阵谱半径的比较"

表1

例1中6种迭代方法的理论最优参数值"

算法 n×n 8×8 16×16 32×32 64×64
GSOR αopt 0.6168 0.5516 0.4967 0.4590
SBTS αopt 6.5880/0.5411 8.4153/0.5316 10.6630/0.5250 12.7600/0.5204
NSBTS αopt 3.5645 4.4735 5.5938 6.6402
PGSOR αopt 0.9944 0.9908 0.9877 0.9855
ω* 0.7017 0.6578 0.6239 0.6025
PSBTS αopt 1.1753/0.8702 1.2344/0.8404 1.1866/0.8641 1.2050/0.8544
ω* 0.7018 0.6577 0.6239 0.6025
PNSBTS αopt 1.0116 1.0187 1.0253 1.0298
ω* 0.7018 0.6577 0.6239 0.6025

表2

例2中6种迭代方法的理论最优参数值"

算法 n×n 8×8 16×16 32×32 64×64
GSOR αopt 0.9636 0.9083 0.7764 0.5661
SBTS αopt 1.3747/0.7858 1.7470/0.7005 2.8820/0.6050 6.8786/0.5319
NSBTS αopt 1.0803 1.2238 1.7435 3.7080
PGSOR αopt 0.9937 0.9820 0.9556 0.9183
ω* 4.5036 3.0020 1.9780 1.4366
PSBTS αopt 1.1278/0.8982 1.2339/0.8406 1.4284/0.7693 1.6760/0.7126
ω* 4.5036 3.0020 1.9783 1.4366
PNSBTS αopt 1.0256 1.0373 1.0988 1.1943
ω* 4.5036 3.0020 1.9783 1.4366

表3

例3中6种迭代方法的理论最优参数值"

算法 n×n 8×8 16×16 32×32 64×64
GSOR αopt 0.4507 0.4553 0.4567 0.4571
SBTS αopt 12.3030/0.5212 11.9860/0.5217 11.8980/0.5219 11.8749/0.5219
NSBTS αopt 6.412 6.2540 6.2101 6.1984
PGSOR αopt 0.9035 0.8978 0.8962 0.8957
ω* 1.2536 1.3081 1.3236 1.3278
PSBTS αopt 1.7784/0.6956 1.8194/0.6894 1.8309/0.6878 1.8339/0.6874
ω* 1.2536 1.3081 1.3236 1.3278
PNSBTS αopt 1.4727 1.5072 1.2594 1.2607
ω* 1.2536 1.3081 1.3236 1.3278

表4

例1迭代步数(IT)迭代时间(CPU)的比较"

算法 n×n 8×8 16×16 32×32 64×64
GSOR IT/CPU 14/0.005 15/0.023 16/0.047 16/0.215
SBTS IT/CPU 13/0.004 17/0.020 20/0.112 20/0.508
NSBTS IT/CPU 13/0.007 17/0.020 20/0.054 20/0.267
PGSOR IT/CPU 3/0.001 3/0.005 3/0.008 3/0.040
PSBTS IT/CPU 3/0.003 3/0.008 3/0.020 3/0.056
PNSBTS IT/CPU 3/0.001 3/0.002 3/0.009 3/0.042

表5

例2迭代步数(IT)迭代时间(CPU)的比较"

算法 n×n 8×8 16×16 32×32 64×64
GSOR IT/CPU 7/0.003 9/0.008 14/0.068 26/0.546
SBTS IT/CPU 7/0.004 11/0.016 22/0.238 60/2.652
NSBTS IT/CPU 7/0.003 11/0.009 22/0.100 60/1.310
PGSOR IT/CPU 5/0.003 6/0.006 8/0.044 9/0.168
PSBTS IT/CPU 6/0.004 6/0.014 8/0.075 10/0.427
PNSBTS IT/CPU 6/0.002 6/0.004 8/0.037 10/0.236

表6

例3迭代步数(IT)迭代时间(CPU)的比较"

算法 n×n 8×8 16×16 32×32 64×64
GSOR IT/CPU 34/0.007 33/0.020 31/0.086 30/0.362
SBTS IT/CPU 95/0.035 92/0.127 93/0.476 96/2.281
NSBTS IT/CPU 96/0.026 93/0.056 93/0.254 95/1.141
PGSOR IT/CPU 9/0.002 9/0.012 9/0.035 9/0.114
PSBTS IT/CPU 10/0.006 10/0.027 11/0.065 11/0.267
PNSBTS IT/CPU 10/0.003 10/0.010 11/0.030 12/0.145
1 SOMMERFELD A . Partial differential equations[M]. New York: Academic Press, 1949: 1- 10.
2 ARRIDGE S R . Optical tomography in medical imaging[J]. Inverse Problems, 1999, 15 (2): 41- 93.
doi: 10.1088/0266-5611/15/2/022
3 HIPTMAIR R . Finite elements in computational electromagnetism[J]. Acta Numerica, 2002, 11, 237- 339.
doi: 10.1017/S0962492902000041
4 ARANSON I S , KRAMER L . The world of the complex Ginzburg-Landau equation[J]. Reviews of Modern Physics, 2002, 74 (1): 99- 143.
doi: 10.1103/RevModPhys.74.99
5 KURAMOTO Y . Chemical oscillations, waves, and turbulence[M]. New York: Dover Publications, Inc, 2003: 89- 140.
6 SAAD Y , SCHULTZ M H . GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems[J]. SIAM Journal on Scientific and Statistical Computing, 1986, 7 (3): 856- 869.
doi: 10.1137/0907058
7 FREUND R W , NACHTIGAL N M . QMR: a quasi-minimal residual method for non-Hermitian linear systems[J]. Numerische Mathematik, 1991, 60 (1): 315- 339.
doi: 10.1007/BF01385726
8 AXELSSON O , KHCHEROV A . Real valued iterative methods for solving complex symmetric linear systems[J]. Numerical Linear Algebra with Applications, 2000, 7 (4): 197- 218.
doi: 10.1002/1099-1506(200005)7:4<197::AID-NLA194>3.0.CO;2-S
9 AXELSSON O , NEYTCHEVA M , AHMAD B . A comparison of iterative methods to solve complex valued linear algebraic systems[J]. Numerical Algorithms, 2014, 66 (4): 811- 841.
doi: 10.1007/s11075-013-9764-1
10 AXELSSON O , BAI Z Z , QIU S X . A class of nested iteration schemes for linear systems with a coefficient matrix with a dominant positive definite symmetric part[J]. Numerical Algorithms, 2004, 35, 351- 372.
doi: 10.1023/B:NUMA.0000021766.70028.66
11 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.
doi: 10.1137/S0895479801395458
12 BAI Z Z , BENZI M , CHEN F . Modified HSS iteration methods for a class of complex symmetric linear systems[J]. Computing, 2010, 87 (3/4): 93- 111.
13 BAI Z Z , BENZI M , CHEN F . On preconditioned MHSS iteration methods for complex symmetric linear systems[J]. Numerical Algorithms, 2011, 56, 297- 317.
doi: 10.1007/s11075-010-9441-6
14 BAI Z Z , BENZI M , CHEN F , et al. 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.
doi: 10.1093/imanum/drs001
15 SALKUYEH D K , HEZARI D , EDALATPOUR V . Generalized successive over-relaxation iterative method for a class of complex symmetric linear system of equations[J]. International Journal of Computer Mathematics, 2015, 92 (4): 802- 815.
doi: 10.1080/00207160.2014.912753
16 HEZARI D , EDALATPOUR V , SALKUYEH D K . Preconditioned GSOR iterative method for a class of complex symmetric linear system of linear equations[J]. Numerical Linear Algebra with Applications, 2015, 22 (4): 761- 776.
doi: 10.1002/nla.1987
17 LI Xian , WEI Hongzhang , WU Yujiang . On symmetric block triangular splitting iteration method for a class of complex symmetric system of linear equations[J]. Applied Mathematics Letters, 2018, 79, 131- 137.
doi: 10.1016/j.aml.2017.12.008
18 ZHANG Jianhua , WANG Zewen , ZHAO Jing . Preconditioned symmetric block triangular splitting iteration method for a class of complex symmetric system of linear equations[J]. Applied Mathematics Letters, 2018, 86, 95- 102.
doi: 10.1016/j.aml.2018.06.024
19 ZHENG Qingqing , MA Changfeng . A class of triangular splitting methods for saddle point problems[J]. Journal of Computational and Applied Mathematics, 2016, 298, 13- 23.
doi: 10.1016/j.cam.2015.11.026
20 LI Jingtao , MA Changfeng . The parameterized upper and lower triangular splitting methods for saddle point problems[J]. Numerical Algorithms, 2017, 76, 413- 425.
doi: 10.1007/s11075-017-0263-7
21 BAI Z Z . On preconditioned iteration methods for complex linear systems[J]. Journal of Engineering Mathematics, 2015, 93, 41- 60.
doi: 10.1007/s10665-013-9670-5
22 LIANG Zhaozheng , ZHANG Guofeng . On SSOR iteration method for a class of block two-by-two linear systems[J]. Numerical Algorithms, 2016, 71, 655- 671.
doi: 10.1007/s11075-015-0015-5
23 WU Yujiang , LI Xu , YUAN Jinyun . A non-alternating preconditioned HSS iteration method for non-Hermitian positive definite linear systems[J]. Computational and Applied Mathematics, 2017, 36 (1): 367- 381.
doi: 10.1007/s40314-015-0231-6
24 BENZI M , BERTACCINI D . Block preconditioning of real-valued iterative algorithms for complex linear systems[J]. IMA Journal of Numerical Analysis, 2008, 28 (3): 598- 618.
25 LI Xu , YANG Aili , WU Yujiang . Lopsided PMHSS iteration method for a class of complex symmetric linear systems[J]. Numerical Algorithms, 2014, 66 (3): 555- 568.
doi: 10.1007/s11075-013-9748-1
26 ZHENG Qingqing , LU Linzhang . A shift-splitting preconditioned for a class of block two-by-two linear systems[J]. Applied Math Letters, 2016, 66 (3): 54- 60.
27 王洋, 赵彦军, 冯毅夫. 基于超松弛迭代的MHSS加速方法[J]. 山东大学学报(理学版), 2016, 51 (8): 61- 65.
doi: 10.6040/j.issn.1671-9352.0.2015.402
WANG Yang , ZHAO Yanjun , FENG Yifu . On successive-overrelaxation acceleration of MHSS iteration[J]. Journal of Shandong University (Natural Science), 2016, 51 (8): 61- 65.
doi: 10.6040/j.issn.1671-9352.0.2015.402
[1] 王静红,梁丽娜,李昊康,周易. 基于注意力网络特征的社区发现算法[J]. 《山东大学学报(理学版)》, 2021, 56(9): 1-12,20.
[2] 郑荔平,胡敏杰,杨红和,林耀进. 基于粗糙集的协同过滤算法研究[J]. 《山东大学学报(理学版)》, 2019, 54(2): 41-50.
[3] 陈一鸣, 柯小红, 韩小宁, 孙艳楠, 刘立卿. 小波法求解分数阶微分方程组及其收敛性分析[J]. 山东大学学报(理学版), 2015, 50(02): 67-74.
[4] 王洋1,付军1,马维元2. 非埃尔米特正定线性系统的预条件NSS方法[J]. J4, 2012, 47(6): 57-62.
[5] 张建松1,牛海峰2. 多孔介质中可压缩混溶驱动问题的新型流线-扩散混合元方法[J]. J4, 2011, 46(12): 6-12.
[6] 高广花,王同科. 两点边值问题基于三次样条插值的高精度有限体积元方法[J]. J4, 2009, 44(2): 45-51.
[7] 郭 会,林 超 . 对流占优Sobolev方程的最小二乘特征混合有限元方法[J]. J4, 2008, 43(9): 45-50 .
[8] 郭 会 . 对流占优扩散方程的最小二乘特征混合有限元方法[J]. J4, 2008, 43(8): 6-10 .
[9] 张建松,羊丹平* . 混合边界条件下电热问题的数值分析[J]. J4, 2007, 42(8): 1-08 .
[10] 张建松,羊丹平 . 多孔介质中可压缩驱动问题的全离散分裂正定混合元方法[J]. J4, 2006, 41(1): 1-10 .
[11] 张建松,羊丹平 . 多孔介质中可压缩驱动问题的全离散分裂正定混合元方法[J]. J4, 2006, 41(1): 1-10 .
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 邹国平1,马儒宁1,丁军娣2,钟宝江3. 基于显著性加权颜色和纹理的图像检索[J]. J4, 2010, 45(7): 81 -85 .
[2] 陈 莉 . 不确定奇异系统的鲁棒故障诊断滤波器设计[J]. J4, 2007, 42(7): 62 -65 .
[3] 丁超1,2, 元昌安1,3*, 覃晓1,3. 基于GEP的多数据流预测算法[J]. J4, 2010, 45(7): 50 -54 .
[4] 张德瑜,翟文广 . 关于整数n的k次补数[J]. J4, 2006, 41(5): 4 -07 .
[5] 曾文赋1,黄添强1,2,李凯1,余养强1,郭躬德1,2. 基于调和平均测地线核的局部线性嵌入算法[J]. J4, 2010, 45(7): 55 -59 .
[6] 易超群,李建平,朱成文. 一种基于分类精度的特征选择支持向量机[J]. J4, 2010, 45(7): 119 -121 .
[7] 孙亮吉,吉国兴 . 上三角形矩阵代数上的Jordan(α,β)-导子和广义Jordan(α,β)-导子[J]. J4, 2007, 42(10): 100 -105 .
[8] 杨建, 张建平,程新路, 杨向东. 类铍离子 1s22s2p 3P0,能级之间的磁偶极跃迁[J]. J4, 2009, 44(11): 29 -34 .
[9] 房用,慕宗昭,王月海,鲍玉海,孙蕾 . 个杨树无性系蒸腾特性及其影响因子研究[J]. J4, 2006, 41(6): 168 -172 .
[10] 吴大千,杜 宁,王 炜,翟 雯,王玉芳,王仁卿,张治国* . 昆嵛山森林群落下灌草层结构与多样性研究[J]. J4, 2007, 42(1): 83 -88 .