An Extrapolated PSS Iterative Method for Positive Definite Linear Systems
-
摘要: 为了更高效地求解大型稀疏正定线性方程组,提出了一种外推的正定和反Hermitian迭代方法。新方法首先对系数矩阵进行正定和反Hermitian分裂(PSS),再构造出了一种新的非对称二步迭代格式。同时理论分析了新方法的收敛性,并给出了新方法收敛的充要条件。数值实验表明,通过参数值的选择,新方法比PSS迭代方法和外推的Hermitian和反Hermitian分裂(EHSS)迭代方法具有更快的收敛速度和更小的迭代次数,选择合适的参数值时新方法的收敛效率可以大大提高。Abstract: Positive definite linear systems arise in many areas of scientific computing and engineering applications, such as solid mechanics, dynamics, nonlinear programming and partial differential equations. It is very meaningful to explore how to efficiently solve the large scale sparse saddle point problem. This paper proposes an extrapolated positive definite and skew-Hermitian (EPSS) iterative method for solving large sparse positive definite linear systems. The new method first splits the coefficient matrix into positive definite matrix and skew-Hermitian matrix, next constructs a new non-symmetric two-step iterative scheme. The new method can not only solve non-Hermitian positive definite linear equations, but also be used for solving Hermitian positive definite linear equations, which greatly accelerates the convergence speed of the iterative method. Then theoretical analysis shows that the new method is convergent. And the necessary and sufficient conditions for the convergence of the new method are given.Moreover the spectral radius of the iterative matrix of the new method is smaller than that of the iterative matrix of the positive definite and skew-Hermitian (PSS) iterative method when selecting appropriate variables. After that numerical experiments are given to show that the new method is efficient and more competitive than PSS iteration method and the extrapolated Hermitian and skew-Hermitian (EHSS) iterative method. Finally, numerical experiments analyze the sensitivity of the parameters in the EPSS iterative method and find the approximate optimal parameters.
-
表 1 例1 PSS和EPSS迭代方法谱半径,收敛迭代次数和时间
Table 1. Spectral radius, IT and CPU of PSS and EPSS iterative method for example 1
$qh$ $N$ PSS EPSS $\rho $ IT CPU $\rho $ IT CPU 10 64 0.3583 36 0.0015 0.1973 23 0.0010 128 0.4355 52 0.0027 0.2268 37 0.0016 256 0.5623 73 0.0069 0.3782 47 0.0034 512 0.6696 102 0.0443 0.4925 65 0.0081 100 64 0.7094 100 0.0036 0.3084 14 0.0012 128 0.7609 139 0.0053 0.3214 15 0.0017 256 0.8126 193 0.0118 0.3238 19 0.0021 512 0.8610 268 0.1010 0.3240 28 0.0051 1000 64 0.7391 43 0.0057 0.1929 8 0.0010 128 0.8182 68 0.0069 0.2153 10 0.0015 256 0.9048 131 0.0221 0.2873 22 0.0019 512 0.9512 276 0.1134 0.2968 15 0.0043 表 2 例2 PSS、EPSS和EHSS迭代方法谱半径,收敛迭代次数以及时间(q=1000)
Table 2. Spectral radius, IT and CPU of PSS, EPSS and EHSS iterative method for example 2 when
$q = 1\;000$ N $\omega $ $\alpha $ $\rho $ IT CPU PSS 8 − 3.5 0.5329 22 0.0469 10 − 2.9 0.5825 25 0.1406 12 − 2.6 0.6270 30 0.4375 14 − 2.3 0.6626 33 0.9219 EPSS 8 0.1 3.9 0.5191 21 0.0156 10 0.1 3.3 0.5657 24 0.0781 12 0.1 2.9 0.6094 27 0.3594 14 0.1 2.6 0.6460 31 0.7969 EHSS 8 0.1 3.3 0.6269 33 0.0313 10 0.1 2.5 0.6508 33 0.1563 12 0.1 2.2 0.6869 37 0.4063 14 0.1 4.3 0.6978 38 1.0625 -
[1] ADAMS M F. Algebraic multigrid methods for constrained linear systems with applications to contact problems in solid mechanics[J]. Numerical Linear Algebra with Applications, 2004, 11(2/3): 275-300. [2] ARROW Z K, HURWICA L, UZAWA H. Studies in linear and non-linear programming[M]. Stanford: Stanford University Press, 1958. [3] BAI Z Z. Splitting iteration methods for non-Hermitian positive definite systems of linear equations[J]. Hokkaido Mathematical Journal, 2007, 36(4): 801-814. [4] YOUNG D M. Iterative Solutions of Large Linear Systems[M]. New York: Academic Press, 1971. [5] 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 & Applications, 2003, 98(1): 1-32. [6] BAI Z Z, GOLUB G H, LU L Z, et al. Block triangular and skew-Hermitian splitting methods for positive- definite linear systems[J]. Siam Journal on Scientific Computing, 2005, 26(3): 844-863. doi: 10.1137/S1064827503428114 [7] CAO Y, TAN W W, JIANG M Q. A generalization of the positive-definite and skew-Hermitian splitting iteration[J]. Numerical Algebra Control & Optimization, 2012, 2(4): 811-821. [8] 潘春萍, 王玉红, 曹文方. 非Hermitian正定线性方程组的外推的HSS迭代方法[J]. 计算数学, 2019, 41(1): 52-64. doi: 10.12286/jssx.2019.1.52 [9] BAI Z Z, GOLUB G H. On successive-overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iterations[J]. Numerical Linear Algebra with Applications, 2007, 19(4): 319-335. [10] BENZI M. A generalization of the Hermitian and skew-Hermitian splitting iteration[J]. SIAM Journal on Matrix Analysis and Applications., 2009, 31(2): 360-374. doi: 10.1137/080723181 [11] BAI Z Z, GOLUB G H, LI C K. Optimal Parameter in Hermitian and Skew-Hermitian Splitting Method for Certain Two-by-Two Block Matrices[M]. SIAM Journal on Scientific Computing, 2006, 28(2): 583-603. [12] LI W W, WANG X. A modified GPSS method for non-Hermitian positive definite linear systems[J]. Applied Mathematics & Computation, 2014, 234: 253-259. [13] YANG A L, AN J, WU Y J. A generalized preconditioned HSS method for non-Hermitian positive definite linear systems[J]. Applied Mathematics and Computation, 2010, 216(6): 1715-1722. doi: 10.1016/j.amc.2009.12.032 [14] BAI Z Z, GOLUB G H, LI C K. Convergence properties of preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite matrices[J]. Mathematics of Computation, 2007, 76(257): 287-298. doi: 10.1090/S0025-5718-06-01892-8 [15] WANG X, LI W W, MIAO L Z. On positive-definite and skew-Hermitian splitting iteration methods for continuous Sylvester equation AX+XB= C[J]. Computers & Mathematics with Applications: An International Journal, 2013, 66(11): 2352-2361. [16] 初鲁, 鲍亮, 董贝贝. 求解非Hermitian正定方程组的广义LHSS迭代法[J]. 浙江大学学报(理学版), 2018, 45(6): 694-706. [17] 蔡兆克, 鲍亮, 初鲁. 预条件平方Smith法求解连续Lyapunov方程[J]. 华东理工大学学报(自然科学版), 2016, 42(6): 881-886. [18] GOLUB G H, VAN LOAN C F. Matrix Computations[M]. Baltimore: The Johns Hopkins University Press, 1996. -