最速下降法的若干重要改进_吴锋

第35卷第4期

2010年8月

文章编号:1001-7445(2010)04-0596-05广西大学学报:自然科学版JournalofGuangxiUniversity:NatSciEdVo.l35No.4Aug.2010

最速下降法的若干重要改进

吴 锋,李秀梅,朱旭辉,黄哲华1121

(11广西大学土木建筑工程学院,广西南宁530004;

21中铁二院工程集团有限责任公司南宁分院,广西南宁530004)

摘要:为了研究结构工程分析中线性方程组解法,基于变分迭代法的思路和简化拉氏乘子的识别,构造了线性

方程组求解的一种迭代格式)))改进型最速下降法。为了提高改进型最速下降法的计算效率,引入松弛因子

和预处理技术两种手段,同时把松弛因子引入原来的最速下降法中,使传统的最速下降法也具有了实用性和

较好的收敛速度。设计两个算例分别验证了改进型最速下降法引入松弛因子和预处理两种手段以及对最速

下降法引入松弛因子这三种算法的效率和稳定性,对于算例1,三种方法与传统高斯-赛德尔方法相比计算效

率分别提高了444倍、533倍和444倍,与传统超松弛迭代法相比分别提高了2813倍、3412倍和2813倍;算例

2是个病态矩阵,传统的高斯-赛德尔方法和超松弛迭代法均计算不出结果。三种方法与最速下降法相比计

算效率分别提高了2916倍、3812倍和2018倍。算例数值结果表明,改进型最速下降法极大地提高了方程组

的求解效率和稳定性,值得推广。

关键词:最速下降法;迭代格式;结构工程;变分迭代法;松弛因子;线性方程组

中图分类号:TU13;O24116 文献标识码:A

Someimportantimprovementforthegradientmethod

WUFeng,LIXiu-mei,ZHUXu-hui,HUANGZhe-hua1121

(11CollegeofCivilandArchitectureEngineering,GuangxiUniversity,Nanning530004,China;

21NanningBranchofChinaRailwayEryuanEngineeringGroupCo.Ltd,Nanning530004,China)

Abstract:Solvingsystemsoflinearequationsplaysanimportantroleinstructuralanalysis1Basing

ontheideasofvariationiterationmethodandthedeterminationofsimplifiedLagrangemultiplier,an

iterationmethodforsolvinglinearequations,namedmodifiedgradientmethod(MGM)wasproposed

inthispaper1InordertoimprovecomputationalefficiencyofMGM,anover-relaxationparameter

andapreconditioningtechniquewereintroduced,respectively1Theover-relaxationparameterwas

alsointroducedtothegradientmethod,whichcanimprovepracticabilityandefficiencyofthetrad-i

tionalgradientmethod(GM)1Twonumericalexamplesareemployedtoshowthecomputationalper-

formanceofthethreeschemes,whichareMGMassociatedwithover-relaxationparameter,MGMas-

sociatedwithpreconditioningtechniqueandGMassociatedwithover-relaxationparameter1ForEx-

ample1,thecomputationalefficiencyofthethreeproposedschemesisimprovedby444,533,444

timesoftheGauss-Seidelmethod(GSDL),respectively,and2813,3412,2813timesofthesucces-

siveover-relaxationiterativemethod(SOR),respectively;ForExample2,whichinvolvedail-l

收稿日期:2010-01-07;修订日期:2010-05-20

基金项目:国家自然科学基金资助项目(19872001);广西科学研究与技术开发项目(桂科攻0861001-12);广西研究

生教育创新计划资助项目(105930903071)。

通讯联系人:李秀梅(1968-),女,辽宁葫芦岛人,广西大学副教授,博士;E-mai:llixiumei_gx@http://www.77cn.com.cn。

conditionedmatrix,thecomputationalefficiencyofthethreeproposedschemesisimprovedby2916,

3818,2018timesofGM,respectively,whileGSDLandSORcannotleadtoaccuratesolution1Nu-

mericalresultsshowthatthesemodifiediterationschemeshavemoreadvantagesinefficiencyand

stabilityforsolvinglargelinearsystems1

Keywords:gradientmethod;iterationscheme;structuralengineering;variationiterationmethod;

overrelaxationparameter;linearequations

线性方程组的求解在结构分析中非常重要,常用的方法有直接解法和迭代解法[1-11]。直接法一般可分为消元法和三角分解法两类;而迭代法常用的有JIM(JacobiIterationMethod)、GSDL(Gauss-SeidelIterationMethod)、SOR(SuccessiveOverrelaxation)、GM(GradientMethod)、CG(ConjugateGradient)等。前三种方法属于定常迭代法,即其迭代系数或矩阵是恒定的,后两种方法属于非定常迭代法,其迭代系数

[1-3]随迭代步数的增长而有规律或无规律地变化。迭代算法一般都属于Krylov子空间算法,具有存储

量小、程序结构简单、精度可控制、并行性能好等优点,在大型工程结构分析中广为应用。SOR法和CG法被认为是求解大型稀疏线性方程组的最有效方法,一直是研究的热点。GM法(常被称为最速下降法或梯度法)在迭代法的发展历史上有着特殊的作用,虽然该方法公认几乎不能用于实际计算中,但是基于该方法发展出的CG法却是求解大型稀疏矩阵方程组的最有效方法之一。变分迭代法最初来自量子力学,文献[4]把它引入线性方程组的求解之中,因该方法需要识别拉氏乘子,这一步很繁琐,实际应用还不多。

本文对传统的最速下降法(GM)做了若干改进。首先基于变分迭代法的思想,采用近似的拉氏乘子,导出一个与GM很相似的迭代格式,但比GM的收敛速度快得多,因此本文称之为MGM(ModifiedGradientMethod),可视为对最速下降法的改进。仿照SOR法的做法,分别在MGM和GM的算法中引入松弛因子X,得到了OMGM(OverrelaxationModifiedGradientMethod)和OGM(OverrelaxationGradientMethod)算法的迭代格式,不但提高了收敛速度,也使GM的工程应用成为可能。最后通过预处理技术,进一步提高了OMGM的计算效率,并给出了该算法的计算步骤。

1 算法描述

为了介绍本文算法的具体细节,首先介绍GM和变分迭代法。对于如下线性方程组:

Ax=b,(1)

其中A为对称正定矩阵,式(1)对应的二次函数为:

1TTU(x)=xAx-bx。(2)2

111 最速下降法(GM)格式

如用GM迭代求解式(1),由xn求xn+1时,xn+1应在U(xn)的负梯度方向寻找并使U(x)取得最小值,GM的迭代格式为:

xn+1=xn+anrn,(3)

其中rn=b-Axn为xn的残差,也就是U(xn)的负梯度Uc(xn),这也是GM名字的由来,系数an可根据U(xn+1)取最小值来确定:

5U(xn+1)TT=anrnArn-rnrn=0。5an

由式(4)解出an:

rnrnan=T。rnArn

112 变分迭代法的思路

如用变分迭代法求解式(1),则首先构造与式(1)对应的一次函数:T[4](4)(5)

f(x)=b-Ax。

设xn为f(x)=0的近似解,为此按下式取xn的校正近似值:

xn+1=xn+Knf(xn),

式中,Kn为拉氏乘子,Knf(xn)为校正项。根据变分迭代法

(7)微分可得:

Kn=

-1[4](6)(7)5xn+1=0,对式n(8)的思想,确定Kn的原则是使-1。fc(xn)-1-1 对式(6)取导数可知K,即:K,但A是很难求的,这也不是迭代法的做法。n的精确解为An=A

文献[4]构造A的一个近似逆矩阵来确定Kn,但这种做法仍然相当复杂。

113 改进的最速下降法(MGM)格式

本文为式(8)的K(xn)其实函数是f(x)在xn处的斜率,因此可以n构造另外一种近似。考虑到fc

用(xn,f(xn))和(xn-1,f(xn-1))两点的割线斜率近似代替,因此有 …… 此处隐藏：7183字，全部文档内容请下载后查看。喜欢就下载吧 ……