求解鞍点问题的一种修正对称 SOR-like算法

沈栩竹,李红娟,李 杰

(1.云南大学数学与统计学院,云南昆明 650091;2.昆明理工大学冶金与能源工程学院,云南昆明 650093)

求解鞍点问题的一种修正对称 SOR-like算法

沈栩竹1,李红娟2,李 杰1

(1.云南大学数学与统计学院,云南昆明 650091;2.昆明理工大学冶金与能源工程学院,云南昆明 650093)

在 SOR-like迭代算法的基础上,通过选取预处理矩阵和待定参数来加速该迭代算法,构造了一种求解鞍点问题的修正对称 SOR-like迭代算法,简记为MSSOR-like算法,并研究了新算法的收敛性.数值实验表明新算法是可行且有效的.

鞍点问题;迭代法;SOR-like算法;收敛性

求解大型稀疏鞍点问题在工程和科学计算上有着极其广泛的应用.如计算流体力学中的 Stokes方程和电磁学Maxwell方程的有限元离散以及二阶椭圆方程问题的混合有限元方法[1-4].

本研究考虑如下鞍点问题

1 修正对称 SOR-like算法

为了表示上的方便,本文主要考虑具有如下形式的鞍点问题

2 收敛性分析

于是有如下引理:

引理 1 如果λ是迭代矩阵 M(ω,τ,α)的特征值,则λ≠1.

3 数值举例

下面给出以上算法的数值举例,定义如下:

所有的数值实验结果都是在 T1600 1.66GHz CPU,1G RAM Memory条件下获得的.在同一精度的条件下,通过选取合适的参数,将本文的MSSOR-like算法与文献[8]中提出的修正 SOR-like(MPSOR-like)迭代算法比较.选择预处理矩阵 P=A,Q=BTB为例.2种算法的参数,迭代次数 (IT)及占用 CPU的时间见表 1和表 2(表中m和n表示线性系统的大小).从表 1和表 2可以看出,MSSOR-like算法具有较少的迭代次数和较快的收敛速度.但是最优参数的确定还有待进一步的研究.总的来说,修正对称SOR-like算法是一种很有竞争力的算法,并且更具有一般性,特别是在选取合适的预处理矩阵和待定参数后,可以大大提高算法的收敛性.

表1 MPSOR-like迭代算法

表2 MSSOR-like算法

[1]BETTS J T.PracticalMethods forOptimal Control usingNonlinear Programming[M].Philadelphia:S IAM,2001.

[2]BREZZI F,FORT IN M.Mixed and Hybrid Finite ElementMethods[M].New York:Springer-Verlag,1991.

[3]G ILL P E,MURRAYW,WR IGHTM H.PracticalOpt imization[M].New York:Academic Press,1981.

[4]GLOW INSKIR.NumericalMethods forNonlinearVariational Problems[M].New York:Springer-Verlag,1984.

[5]GOLUB G H,WU X,YUAN J Y.SOR-like methods for augmented systems[J].B IT NumericalMathmatics,2001,41(1):71-85.

[6]WU Shi-liang,HUANG Ting-zhu,ZHAO Xi-le.A modified SSOR iterative method for augmented systems[J].Journal of Computational and AppliedMathematics,2009,228:424-433.

[7]BA I Z Z,WANG Z Q.On parameterized inexact Uzawa methods for generalized saddle point problems[J].Linear Algebra Appl,2008,428:2900-2932.

[8]沈海龙,邵新惠,张铁,等.求解鞍点问题的修正 SOR-like方法[J].东北大学学报:自然科学版,2009,6(6):905-908.

[9]YOUNGD M.Iterative solution of large linear systems[M].New York:Academic Press,1971.

OneModified SOR-likeMethod for Saddle Point Problems

SHEN Xu-zhu1,L IHong-juan2,L IJie1
(1.School ofMathematics and Statistics,Yunnan University,Kunming 650091,China;(2.Faculty ofMetallurgical and Energy Engineering,KunmingUniversity of Science and Technology,Kunming 650093,China)

Based on SOR-like iterative scheme,the pretreated matrix and undetermined parameterswere selected and used to accelerate it,and a modified symmetric SOR-like iterative algorithm for large sparse saddle point problems(MSSOR-like)was structured,and the convergence of this new method was provided.Numerical results showed that this new method was feasible and effective.

the saddle point problem;iteration method;SOR-like method;convergence

O 241 < class="emphasis_bold">文献标志码:A

A

1004-1729(2010)04-0298-04

2010-07-23

沈栩竹 (1984-),女,辽宁锦州人,云南大学数学与统计学院 2008级硕士研究生.