求解正定线性方程组的外推的PSS迭代方法

吴思婷; 鲍亮; 黄景宣

doi:10.14135/j.cnki.1006-3080.20210312001

求解正定线性方程组的外推的PSS迭代方法

doi: 10.14135/j.cnki.1006-3080.20210312001

华东理工大学数学学院，上海 200237

详细信息

作者简介:
吴思婷（1996-），女，浙江温州人，硕士生，主要研究方向：数值代数及其应用。E-mail：wusiting96@163.com

通讯作者:
鲍　亮，E-mail：lbao@ecust.edu.cn

中图分类号: O241.6
计量
- 文章访问数: 200
- HTML全文浏览量: 75
- PDF下载量: 8
- 被引次数: 0
出版历程
- 收稿日期: 2021-03-12
- 网络出版日期: 2021-06-29

An Extrapolated PSS Iterative Method for Positive Definite Linear Systems

School of Mathematics, East China University of Science and Technology, Shanghai 200237, China

摘要

摘要: 为了更高效地求解大型稀疏正定线性方程组，提出了一种外推的正定和反Hermitian迭代方法。新方法首先对系数矩阵进行正定和反Hermitian分裂(PSS)，再构造出了一种新的非对称二步迭代格式。同时理论分析了新方法的收敛性，并给出了新方法收敛的充要条件。数值实验表明，通过参数值的选择，新方法比PSS迭代方法和外推的Hermitian和反Hermitian分裂（EHSS）迭代方法具有更快的收敛速度和更小的迭代次数，选择合适的参数值时新方法的收敛效率可以大大提高。
- 正定线性方程组 /
- PSS迭代方法 /
- 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.
- positive definite linear systems /
- PSS iteration method /
- EHSS iteration method /
- spectral radius /
- convergence

HTML全文

图 1 例1中EPSS和PSS迭代方法的残量下降速度比较

Figure 1. Comparison of the residuals speed in EPSS and PSS for example 1

下载: 全尺寸图片幻灯片

图 2 例2取不同矩阵规模时，EPSS、PSS和EHSS迭代方法的残量下降速度比较

Figure 2. Comparison of the residuals speed in EPSS, PSS and EHSS for example 2 when matrix size is different

下载: 全尺寸图片幻灯片

图 3 例1取不同$qh$和最优ω时，EPSS和PSS迭代方法的谱半径与α的关系

Figure 3. Relationship between the parameter α and the spectral radius in EPSS and PSS for example 1 when $qh$ is differert and ω is optimal

下载: 全尺寸图片幻灯片

图 4 例1取不同$qh$时，EPSS迭代方法中参数$\alpha $和$\omega $与谱半径的关系

Figure 4. Relationship between the parameters $\alpha $,$\omega $ and the spectral radius in the EGHSS iterative method for example 1 when $qh$ is different

下载: 全尺寸图片幻灯片

表 1 例1 PSS和EPSS迭代方法谱半径，收敛迭代次数和时间

Table 1. Spectral radius, IT and CPU of PSS and EPSS iterative method for example 1

$qh$	$N$	PSS			EPSS
$qh$	$N$	$\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

下载: 导出CSV

表 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

下载: 导出CSV

参考文献(18)

[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.