求解鞍點(diǎn)問題的一種修正對(duì)稱 SOR-like算法

沈栩竹,李紅娟,李 杰

(1.云南大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,云南昆明 650091;2.昆明理工大學(xué)冶金與能源工程學(xué)院,云南昆明 650093)

求解鞍點(diǎn)問題的一種修正對(duì)稱 SOR-like算法

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

(1.云南大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,云南昆明 650091;2.昆明理工大學(xué)冶金與能源工程學(xué)院,云南昆明 650093)

在 SOR-like迭代算法的基礎(chǔ)上,通過選取預(yù)處理矩陣和待定參數(shù)來加速該迭代算法,構(gòu)造了一種求解鞍點(diǎn)問題的修正對(duì)稱 SOR-like迭代算法,簡(jiǎn)記為MSSOR-like算法,并研究了新算法的收斂性.數(shù)值實(shí)驗(yàn)表明新算法是可行且有效的.

鞍點(diǎn)問題;迭代法;SOR-like算法;收斂性

求解大型稀疏鞍點(diǎn)問題在工程和科學(xué)計(jì)算上有著極其廣泛的應(yīng)用.如計(jì)算流體力學(xué)中的 Stokes方程和電磁學(xué)Maxwell方程的有限元離散以及二階橢圓方程問題的混合有限元方法[1-4].

本研究考慮如下鞍點(diǎn)問題

1 修正對(duì)稱 SOR-like算法

為了表示上的方便,本文主要考慮具有如下形式的鞍點(diǎn)問題

2 收斂性分析

于是有如下引理:

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

3 數(shù)值舉例

下面給出以上算法的數(shù)值舉例,定義如下:

所有的數(shù)值實(shí)驗(yàn)結(jié)果都是在 T1600 1.66GHz CPU,1G RAM Memory條件下獲得的.在同一精度的條件下,通過選取合適的參數(shù),將本文的MSSOR-like算法與文獻(xiàn)[8]中提出的修正 SOR-like(MPSOR-like)迭代算法比較.選擇預(yù)處理矩陣 P=A,Q=BTB為例.2種算法的參數(shù),迭代次數(shù) (IT)及占用 CPU的時(shí)間見表 1和表 2(表中m和n表示線性系統(tǒng)的大小).從表 1和表 2可以看出,MSSOR-like算法具有較少的迭代次數(shù)和較快的收斂速度.但是最優(yōu)參數(shù)的確定還有待進(jìn)一步的研究.總的來說,修正對(duì)稱SOR-like算法是一種很有競(jìng)爭(zhēng)力的算法,并且更具有一般性,特別是在選取合適的預(yù)處理矩陣和待定參數(shù)后,可以大大提高算法的收斂性.

表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]沈海龍,邵新惠,張鐵,等.求解鞍點(diǎn)問題的修正 SOR-like方法[J].東北大學(xué)學(xué)報(bào):自然科學(xué)版,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">文獻(xiàn)標(biāo)志碼:A

A

1004-1729(2010)04-0298-04

2010-07-23

沈栩竹 (1984-),女,遼寧錦州人,云南大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 2008級(jí)碩士研究生.