黄金比例分割法确定对称逐次超松弛迭代法的最佳松弛因子

1、黄金比例分割法确定对称逐次超松弛迭代法的最佳松弛因子/. -1- 黄金比例分割法确定对称逐次超松弛迭代法的最佳松弛因子 张德宣，杜成斌，孙立国 河海大学工程力学系，南京 (210098) 摘 要：本文提出了将黄金分割法确定松弛因子与对称逐次超松弛法的改进迭代格式相结合的迭代算法。算法应用黄金比例分割法确定最佳松弛因子，成功的将其与运行速度和效率很高的对称逐次超松弛法的改进迭代格式相结合，并给出了迭代收敛性证明，编写了相应的程序，对一实际结构进行的算例计算表明，与大型商业软件的计算结果相比较，本文所提算法具有精度高，收敛快的优点。 关键词：黄金分割；对称逐次超松弛法；松弛因子

2、1引言 线性代数方程组 bAx = (其中A为非奇异系数矩阵,b为列向量)的迭代解法通常有Jacobi迭代法,Gauss Seidel迭代法和对称逐次超松弛迭代（SSOR）法三种，此外还有USAOR1迭代法，USSOR2迭代法等。 但是当结构的自由度达到较大的数目（如10000个自由度以上），Jacobi法和Gauss Seidel法存在着运算速率很慢这一明显缺点，而且这些迭代方法的结果的精度不能保证。因此本文针对运算速率很高的对称逐次超松弛法的改进迭代格式提出了用黄金分割法确定松弛因子的思路，编写了黄金分割计算松弛因子与相应的迭代法相结合的程序，实际算例表明，本文方法可提高求解大型线性方程组

3、的求解效率和精度。 2SSOR-PCG法改进的迭代格式 SSOR法在每步迭代中，需计算系数矩阵与方向向量的乘积，下面引用了该法的改进迭代格式，避免了该乘积的计算，比原迭代格式节省计算量850。 SSOR法的改进迭代格式3为： 置初值 0, 0000010000 =?=?= ? kzWdVyzgWyRKg T ， (1) R： ( )kk Vyy ,= 式中 ( ， )为内积表示，下同。 如果 ，则停止，否则 /. -2- ?+=+?=?+=+=?=+?+?+RkkzWdzVyzVyyVyyVdzWdyydVdzdVyykTkkkkkkkkkkkkkkkkkkkkkkkkkk转

4、到,1,),/(),(),(,),2,/(),(111111111 (2) 从迭代格式可见，由于V是对角阵，计算Vy和Vd为2n次乘法运算。改进的迭代格式由于避免了计算Ad，比原迭代格式可省 ( )nra 2? 次乘法运算， ar 为A的各行非零元素的平均个数。因此， 3=ar 是改进迭代格式节省计算量约8； 62 >>ar 时，可节省计算量约50，各迭代步计算量接近CG（共轭梯度）法的计算量。 3松弛因子的选取 本文采用上述对称逐次超松弛法的改进迭代格式求解大型线性方程组，将黄金分割法确定松弛因子与之相结合，松弛因子的取值对迭代公式的收敛速度影响很大，它的好坏直接影响到收敛的快慢

5、。为了保证迭代过程的收敛，取 21 << ，但是在1和2之间仍然有很多的取值，究竟如何取值，目前并没有统一的规定，一般是将的取值区间(1,2)进行M等分，松弛因子分别取 M/11+ , M/21+ , , MM /)1(1 ?+ ,然后分别代入迭代公式求解的同时比较出最少的迭代次数，这样就得到了最佳的值。但是这种方法如果要得到比较精确的值，M的取值就要变大，如果要在程序中实现，就导致计算量增加很多，运算时间就会延长许多，是很不经济的。 黄金分割比例法是一种经典的算法，本文即采用此种方法来确定最佳松弛因子，其具体步骤和主要思想如下： (1)利用优选法思想,在(1,2)之间选取四个点，

6、即： dot1=1，dot2=dot4-0.618(dot4-dot1)，dot3=dot1+0.618(dot4-dot1)，dot4=2 。 (2)分别取dot2与 dot3作为松弛因子代入迭代程序，比较出最少的迭代次数，如果dot2对应的迭代次数少，则选取(dot1, dot2)作为收敛区间，如果是dot3对应的迭代次数少，则选取(dot3, dot4)作为收敛区间。 (3)在所选取的收敛区间里循环进行上述的两个步骤，直到选取出迭代次数最少时所对应的最佳松弛因子。 通过本文中所采用的算例验证，本文方法确定松弛因子的加速效果是明显的，计算的时间相对较短。在SSOR法改进迭代格式中采用黄金比

7、例分割的综合算法就可以根据不同的具体工程问题确定最佳松弛因子，该算法简单明了，而且效果显著，大大节省了选取最佳松弛因子的时间，提高了大型有限元方程组计算的收敛速度。 4收敛性证明 定义14 设A nnC ? ， n , 21 L 为A的特征值，我们称 /. -3- iiA max)( = (3) 为A的谱半径。 定义25 由 1)(0 << B ，且误差向量 ?= xx kk )()( 满足 )0( kk B= ，推出欲使初始误差缩小 s?10 所需最小迭代次数为)(ln10lnBsk ? ，称 )(ln)( BBR ?= 为迭代法收敛速度。 定义36 nnija

8、A = )( ，如果A的元素满足 =nijjijij aa1),2,1,( nji L= ，称A为对角占优矩阵，记为 0DA ；而当 =>nijjijij aa1),2,1,( nji L= 时，称A为严格对角占优矩阵，记为DA 。 引理17 设有等价的方程组 fBxxbAx +=?= (4) 构造的一阶定常迭代法 fBxx kk +=+ )()1( (5) 对于任意选取的初始向量 )0(x ，迭代法收敛的充要条件是迭代矩阵B的谱半径 1)( <B 。 定理1 设 bAx = ，本文采用改进的SSOR迭代法收敛的充分条件为： (1) nnRA 为严格对角占优矩阵，且 ULDA ?=

9、 （D为单位对角阵，L为单位下三角阵，U为单位上三角阵）； (2) 21 << ； (3) 取 IkD = ，当 )21,0(nk 时； 则本文采用改进的SSOR迭代法收敛。 证明：本文所采用的SSOR-PCG法改进的迭代格式所采用的迭代矩阵为： )1()()( 11 UILIACDIL L +?=?= ? (6) 采用反证法，假设为 L 的任一特征值，且 1 ，则 =? LI LLILI ? ? )()( 1 UILILI ?= ? )1()()( 1 ULILI ?+?= ? )1()( 1 0)1(1 =?+?= ? ULILI (7) 由于 ULDA ?= 为严格对角占优矩

10、阵，所以 0?= ULDA ，由于 LI ? 也为对角阵，从而 01 ? ?LI 。 分析式（7）后半部分，并由 1 可得 /. -4- +=?=?= +=?+?+?nijijiijijiiiiijnijijiijiiii aaIaaI11111 1)1()1( )()1()()1(1,11 111 1 =?= +=?= +=+?+?>+?+?>njiijnijijiijiijiiiiijnijijiijiiii aaaIaaI = ? ?+?=? ?+?=?+?>niiininiiniiininiiiiiii akkakaI111)1()1(1)1(由 2

11、1 << ，进而 01 >?i ，又由 )21,0(nk ，推得 01 >? ink ，于是可以得出 =? ?+? niiiniinakk10)1()1( ，此式表明 ( ) ULI ?+?1 也是严格对角占优矩阵，其行列式 0)1( ?+? ULI ，这与式（7）矛盾，故 L 的特征值均有 1< ，结合定义1可知谱半径 1)( < L ，则该迭代方法收敛。 本文论证出了改进的SSOR迭代法收敛的一个充分条件，而由引理1并结合定义2可知，迭代次数与收敛速度成反比，即 )(B 越小，迭代收敛速度R(B)越快。而一般来说迭代矩阵B的谱半径 )(B 对极为敏感，但

12、是究竟是取值大能减少迭代次数，还是取值小可以减少迭代次数，这并无规律，完全取决于计算当时的情况，如结构划分单元的多少及计算精度等因素都有一定的关系。 5算例 设一悬臂梁长20m，高5m,厚1m, 如图1所示。材料弹性模量E2.1E7，泊松比 =0.167,不计自重，上表面受1000 N/m 的均布荷载。网格划分为平面四节点单元，长度方向200等分，高度方向50等分，则节点总数为10251，单元总数为10000。 图1 悬臂梁网格剖分示意图 表1为本文算法与大型商业软件MARC计算的节点位移比较，表2为两者运算时间的比较（采用的计算机配置为：Pentium(R) D CPU 2.80 GHz ,

13、 1.00 GB 内存）。 /. -5- 表1 本文算法与MARC计算节点位移比较 节 点 方 向 MARC 解 本文算法解 误 差 x -0.315654E-03 -0.315041E-03 0.194 2 y -0.151406E-03 -0.151282E-03 0.082 x -0.130349E-01 -0.130269E-01 0.061 101 y -0.354377E-01 -0.353946E-01 0.343 x -0.148028E-01 -0.147813E-01 0.145 201 y -0.942368E-01 -0.942186E-01 0.01

14、9 x 0.431350E-04 0.432271E-04 0.213 5126 y -0.353197E-01 -0.352766E-01 0.122 x 0.329006E-03 0.328835E-03 0.052 10052 y -0.168963E-03 -0.168703E-03 0.154 x 0.131212E-01 0.131073E-01 0.106 10151 y -0.355535E-01 -0.355067E-01 0.132 x 0.149818E-01 0.149659E-01 0.106 10251 y -0.943525E-01 -0.943297E-01 0

15、.024 注：表中节点位置参见图1. 表2 二者运算时间比较 Marc计算 本文算法计算 运行时间 1分32秒 17秒 通过所列的表1和表2观察可以发现，本文算法所求出的位移与大型商业软件MARC相比较精度误差很小，具有较高的精度，且在保证精度的基础上计算时间也大大缩短，有很高的利用价值。本文算例所生成并取用的最佳松弛因子 =1.729475，而通常算法要想得到精确的松弛因子，只能将松弛因子进行M 等分再依次代入，依据迭代次数的多少选取出最佳松弛因子，累加起来就是一个非常巨额的计算时间，是很不现实的。而根据本文算法编写的程序，由于包含了黄金比例分割法计算最佳松弛因子的子程序，可以精确的计算出最

16、佳松弛因子，效果显著，大大节省了选取最佳松弛因子的时间，进而提高了大型方程组计算的收敛速度与结果精度，具有非常强的经济实用性。 6结论 本文提出的黄金分割求解最佳松弛因子结合SSOR法的改进格式的综合算法，不仅计算公式简单,编程易于实现，而且计算结果与大型商业软件求解结果相比，精度较高，速度也大大提高,适宜用于求解大型稀疏线性方程组。 参考文献 1 Ruiming Li,Dian Zhou. A note on the eigenvalue relationship for USAOR iterative method applied to p-cyclic matricesJ, Journa

17、l of Computational and Applied Mathematics, 2004,169: 213-225. 2 M. Madalena Martins. An Error Bound for the SSOR and USSOR MethodsJ, Lineab Algebra and Its Applici- -tions,1996,232:131-147 . 3 林绍忠. 对称逐步超松弛预处理共轭梯度法的改进迭代格式J, 数值计算与计算机应用,1997,4:266-270. 4 方保熔,周继东,李医民. 矩阵论 M. 清华大学出版社,2004. 5 李庆扬,王能超,易大义

18、. 数值分析 M. 清华大学出版社,2005. 6 陈景良,陈向晖. 特殊矩阵 M. 清华大学出版社,2001. 7 冉瑞生,杨 鹏,黄廷祝. 非奇H矩阵判别条件的推广J. 电子科技大学学报33(1):102-104. /. -6- The optimal relaxation factor of the symmetry successive overre-laxation iterative method determination from the golden-section method Zhang dexuan，Du chengbin，Sun liguo Depa

19、rtment of Engineering Mechanics,Hohai University,Nanjing,PRC.(210098) Abstract This article proposed the combined iterative method about the golden-section method detemined the re- -laxation factor and the improved iterative form of the symmetry successive overrelaxation method.this method applied t

20、he golden-section method to determined the optimal relaxation factor successful com- -bined this method with the improved iterative form of the symmetry successive overrelaxation method whose run speed is fast and efficiency is high,also proved the convergence of the iteration method and correspondi

21、ng program is developed. the calculation with one practical structure showed that compared with the results of the large commercial soft- -ware,the method in this paper has the advantages of a ac- -curacy and fast convergence. Keywords: golden-section, the symmetry successive overrelaxation method,

22、the relaxation factor. 作者简介：张德宣，男，1983年生，硕士研究生，主要研究方向结构动力学与工程有限元仿真。 << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /All /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated 050SWOP05

23、1 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Warning /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJDFFile false /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /ColorCon

24、versionStrategy /LeaveColorUnchanged /DoThumbnails false /EmbedAllFonts true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /

25、PreserveCopyPage true /PreserveEPSInfo true /PreserveHalftoneInfo false /PreserveOPIComments false /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed true /NeverEmbed true /AntiAlia

26、sColorImages false /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDi

27、ct << /QFactor 0.15 /HSamples 1 1 1 1 /VSamples 1 1 1 1 >> /ColorImageDict << /QFactor 0.15 /HSamples 1 1 1 1 /VSamples 1 1 1 1 >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeig

28、ht 256 /Quality 30 >> /AntiAliasGrayImages false /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStra

29、tegy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples 1 1 1 1 /VSamples 1 1 1 1 >> /GrayImageDict << /QFactor 0.15 /HSamples 1 1 1 1 /VSamples 1 1 1 1 >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /

30、TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict <<

31、; /K -1 >> /AllowPSXObjects false /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset 0.00000 0.00000 0.00000 0.00000 /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset 0.00000 0.00000 0.00000 0.00000 /PDFXOutputInten

32、tProfile () /PDFXOutputCondition () /PDFXRegistryName (/.) /PDFXTrapped /Unknown /Description << /FRA <FEFF004f007000740069006f006e00730020007000650072006d0065007400740061006e007400200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e0074007300200050004

33、4004600200064006f007400e900730020006400270075006e00650020007200e90073006f006c007500740069006f006e002000e9006c0065007600e9006500200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200061006d00e9006c0069006f007200e90065002e00200049006

34、c002000650073007400200070006f0073007300690062006c0065002000640027006f00750076007200690072002000630065007300200064006f00630075006d0065006e007400730020005000440046002000640061006e00730020004100630072006f0062006100740020006500740020005200650061006400650072002c002000760065007200730069006f006e00200020003

35、5002e00300020006f007500200075006c007400e9007200690065007500720065002e> /ENU (Use these settings to create PDF documents with higher image resolution for improved printing quality. The PDF documents can be opened with Acrobat and Reader 5.0 and later.) /JPN <FEFF3053306e8a2d5b9a306f30019ad889e3

36、50cf5ea6753b50cf3092542b308000200050004400460020658766f830924f5c62103059308b3068304d306b4f7f75283057307e30593002537052376642306e753b8cea3092670059279650306b4fdd306430533068304c3067304d307e305930023053306e8a2d5b9a30674f5c62103057305f00200050004400460020658766f8306f0020004100630072006f0062006100740020

37、304a30883073002000520065006100640065007200200035002e003000204ee85964d30678868793a3067304d307e30593002> /DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0

38、065006e00200076006f006e0020005000440046002d0044006f006b0075006d0065006e00740065006e0020006d00690074002000650069006e006500720020006800f60068006500720065006e002000420069006c0064006100750066006c00f600730075006e0067002c00200075006d002000650069006e006500200076006500720062006500730073006500720074006500200

39、0420069006c0064007100750061006c0069007400e400740020007a0075002000650072007a00690065006c0065006e002e00200044006900650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f0062006100740020006f0064006500720020006d00690074002000640065006d0

40、02000520065006100640065007200200035002e003000200075006e00640020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e> /PTB <FEFF005500740069006c0069007a006500200065007300740061007300200063006f006e00660069006700750072006100e700f50065007300200070006100720061002

41、00063007200690061007200200064006f00630075006d0065006e0074006f0073002000500044004600200063006f006d00200075006d00610020007200650073006f006c007500e700e3006f00200064006500200069006d006100670065006d0020007300750070006500720069006f0072002000700061007200610020006f006200740065007200200075006d006100200071007

42、50061006c0069006400610064006500200064006500200069006d0070007200650073007300e3006f0020006d0065006c0068006f0072002e0020004f007300200064006f00630075006d0065006e0074006f0073002000500044004600200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006

43、f006200610074002c002000520065006100640065007200200035002e0030002000650020007300750070006500720069006f0072002e> /DAN <FEFF004200720075006700200064006900730073006500200069006e0064007300740069006c006c0069006e006700650072002000740069006c0020006100740020006f00700072006500740074006500200050004400460

44、02d0064006f006b0075006d0065006e0074006500720020006d006500640020006800f8006a006500720065002000620069006c006c00650064006f0070006c00f80073006e0069006e006700200066006f00720020006100740020006600e50020006200650064007200650020007500640073006b00720069006600740073006b00760061006c0069007400650074002e002000500

45、0440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e006500730020006d006500640020004100630072006f0062006100740020006f0067002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /NLD <FEFF004700650062007200750069006b002000640065007a006

46、500200069006e007300740065006c006c0069006e00670065006e0020006f006d0020005000440046002d0064006f00630075006d0065006e00740065006e0020007400650020006d0061006b0065006e0020006d00650074002000650065006e00200068006f0067006500720065002000610066006200650065006c00640069006e00670073007200650073006f006c00750074006

47、9006500200076006f006f0072002000650065006e0020006200650074006500720065002000610066006400720075006b006b00770061006c00690074006500690074002e0020004400650020005000440046002d0064006f00630075006d0065006e00740065006e0020006b0075006e006e0065006e00200077006f007200640065006e002000670065006f00700065006e0064002

48、0006d006500740020004100630072006f00620061007400200065006e002000520065006100640065007200200035002e003000200065006e00200068006f006700650072002e> /ESP <FEFF0055007300650020006500730074006100730020006f007000630069006f006e006500730020007000610072006100200063007200650061007200200064006f00630075006d0

49、065006e0074006f0073002000500044004600200063006f006e0020006d00610079006f00720020007200650073006f006c00750063006900f3006e00200064006500200069006d006100670065006e00200070006100720061002000610075006d0065006e0074006100720020006c0061002000630061006c006900640061006400200061006c00200069006d007000720069006d0

50、0690072002e0020004c006f007300200064006f00630075006d0065006e0074006f00730020005000440046002000730065002000700075006500640065006e00200061006200720069007200200063006f006e0020004100630072006f00620061007400200079002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e006500730

51、0200070006f00730074006500720069006f007200650073002e> /SUO <FEFF004e00e4006900640065006e002000610073006500740075007300740065006e0020006100760075006c006c006100200076006f0069006400610061006e0020006c0075006f006400610020005000440046002d0061007300690061006b00690072006a006f006a0061002c0020006a006f006

52、900640065006e002000740075006c006f0073007400750073006c00610061007400750020006f006e0020006b006f0072006b006500610020006a00610020006b007500760061006e0020007400610072006b006b007500750073002000730075007500720069002e0020005000440046002d0061007300690061006b00690072006a0061007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f006200610074002d0020006a0061002000410063007200