一类求解鞍点问题的推广的GSOR迭代法

【前言】一类求解鞍点问题的推广的GSOR迭代法由文秘帮小编整理而成，但愿对你的学习工作带来帮助。Ax=b,A 非奇异,x,b(1)的解,求解方法可分为两大类:直接法和迭代法。由于直接解法在进行矩阵分解时常引入大量填充元,导致存储量与计算量很大,而且当系数矩阵条件数很大时,直接法稳定性差。为利用系数矩阵的稀疏结构以尽可能减少存储空间和计算开销,迭代算法成为求解(1)...

摘要:为了快速有效地求解大型稀疏鞍点问题,在SOR-like迭代算法的基础上,通过引入新的待定参数对原有迭代算法进行加速的思想,构造了一种解鞍点问题的具有多个待定参数的一般加速超松弛迭代算法,并给出了该算法收敛性的条件。数值例子表明:通过参数值的选择,新算法比SOR-like和GSOR算法都具有更快的收敛速度和更小的迭代次数,选择了合适的参数值后,可以大大提高算法的收敛效率。

关键词:鞍点问题;迭代法;SOR-like方法;GSOR方法

中图分类号:O241.6 文献标识码:A文章编号:1007-9599 (2010) 01-0000-02

一、引言

许多物理应用问题求解的核心是:如何高效求解大型稀疏线性方程组

Ax=b,A 非奇异,x,b(1)的解,求解方法可分为两大类:直接法和迭代法。由于直接解法在进行矩阵分解时常引入大量填充元,导致存储量与计算量很大,而且当系数矩阵条件数很大时,直接法稳定性差。为利用系数矩阵的稀疏结构以尽可能减少存储空间和计算开销,迭代算法成为求解(1)的主要方法,但迭代法也存在不收敛与收敛速度慢的问题,而且不同的迭代法适用于不同的线性系统。因此,为不同的大型稀疏线性系统找到合适的迭代算法成为重要的研究课题。大型稀疏鞍点问题的求解在很多应用领域都出现过,并且非常重要.如计算流体力学中的Stokes方程和电磁学Maxwell方程的有限元离散以及二阶椭圆方程问题的混合有限元方法,带有限制条件的二次优化问题,线性弹性力学问题,图像处理问题,最小二乘问题等[1,2]。

本文主要考虑具有如下形式的鞍点问题:

其中A∈Rm×m为对称正定矩阵(SPD),B∈Rm×n为列满秩矩阵,即rank(B)=n ,向量x,p∈Rm,向量y,q∈Rn(这里我们假定m≥n)。BT是B的转置矩阵。p,q是已知向量。在这样的假设下,鞍点问题(2)有唯一解[1]。

上面的线性方程组来源于下面的线性约束二次优化问题:

二、推广的gsor迭代算法

在求解Stokes方程,Navier-Stokes方程和Oseen方程等问题时,我们也通常会遇到求解鞍点问题。因此,如何快速有效的求解鞍点问题就变得非常关键,目前成为许多学者研究的热点。当前已经存在很多方法求解鞍点问题,其中包括直接法、Krylov子空间方法[3]、Uzawa算法、SOR-like算法、HSS算法等[5,6,8,9,12]。经典的SOR 迭代[4,10,11,]是非常简单而有效的方法之一,并且在工程计算中有着广泛的应用。然而鞍点问题(2)的特点使SOR算法难以直接应用。Golub等人通过对系数矩阵进行适当的分解,构造出了一种SOR-like迭代方法[6],在此基础上白中治等人通过引入新的参数,构造出了一种GSOR迭代算法[8],本文通过引人三个松弛参数提出了一种推广的GSOR迭代算法。为了表示上的方便,我们将方程组(2)等价表示为:

三、算法的收敛性分析

引理1.[7]实二次方程 的两个根的模均小于1当且仅当 。

定理1.设A∈Rm×m,Q∈Rn×n是对称正定矩阵,B∈Rm×n为列满秩矩阵。令 分别为J=Q-1BTA-1B的最小和最大特征值。若ω满足0

参考文献:

[1]M.Benzi,Golub,G.H.and J.Liesen,numerical solution of saddle point problems,Acta Numerica,14(2005),1-137

[2]Li,C.-J.,Li,B.-J.,Evans,D.J.:A generalized successive overrelaxation method for least squares problems.BIT 38,347-356(1998)

[3]Golub,G.H.,Van Loan,C.F.:Matrix Computations.3rd Edition,The Johns Hopkins University Press,Baltimore and London,1996

[4]Axelsson,O.:Iterative Solution Methods.Cambridge University Press,Cambridge,1994

[5]J.H.Bramble,J.E.Pasciak,and A.T.Vassilev,Analysis of the inexact Uzawa algorithm for saddle point problem.SIAM J.Numer.Anal.,vol.34,No.3,1072-1092(1997)

[6]Golub,G.H.,Wu,X.,Yuan,J.-Y.:SOR-like methods for augmented systems.BIT 41,71-85(2001)

[7]Young,D.M.:Iterative Solutions of Large Linear Systems.Academic Press,New York,1971

[8]Bai,Z.-Z.,B.N.Parlett.,Z.-Q.Wang.:On generalized successive Overrelaxationmethods for augmented linear systems.Numer.Math.(2005)102:1-38

[9]G.F.Zhang,Q.H.Lu,On generalized SSOR method for augmented systems,Accepted manuscript,put.Appl.Math.(2007)

[10]曹志浩.数值线性代数,复旦大学出版社,1996

[11]曹志浩.变分迭代法,科学出版社,2005

[12]邵新慧等.求解鞍点问题的一般加速超松弛方法,数值计算与计算机应用.4,241-248(2006)