（应用数学专业论文）求解对称非线性方程组的一种修正共轭梯度法.pdf

am o d i f i e dc o n j u g a t eg r a d i e n tm e t h o df o rs y m m e t r i cn o n l i n e a r e q u a t i o n s b y z o uz h i w e i b e ( w u h a nu n i v e r s i t y ) 2 0 0 5 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o r t h ed e g r e eo f m a s t e ro fs c i e n c e l n a p p l i e dm a t h e m a t i c s i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rl id o n g h u i n o v e m b e r ，2 0 10 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特另t l d n 以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 名译南 日期：叫眸2 月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密回。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 日期：夕p 哞二月7 日 b 3 攀q 每f 乒7 、j 求解对称非线性方程纽的一种修正芪轭梯度法 摘要 求解非线性方程组的数值算法是一个重要研究课题在已有的求解非线性方 程组的数值算法中，牛顿法是一种下降算法，在一定的条件下该算法具有全局收 敛性和超线性收敛性然而牛顿法是一种利用导数的算法，求解非线性方程组的 无导数算法如拟牛顿法、谱梯度算法等一般不是下降算法，研究求解非线性方程 组的无导数下降算法是一个重要而难度较大的课题本文在g u 等人提出的求解 对称非线性方程组的一种下降拟牛顿型算法的基础上提出求解对称非线性方程组 的一种具有下降性质的共轭梯度算法，在算法中借助于求解无约束最优化问题的 c d 共轭梯度法的思想所提出的算法具有如下优点：1 算法的每次迭代都能产生 使得方程组模函数下降的充分下降方向；2 算法不需要计算函数的导数；3 在较 弱的条件下算法具有全局收敛性；4 该算法继承了共轭梯度法存储量少的优点， 因此可用于求解大规模对称非线性方程组我们还通过数值实验对所提出的算法 进行数值检验我们首先验证算法的全局收敛性，在此基础上，进一步检验算法 用于求解对称非线性方程组的数值效果结果表明，本文提出的算法是求解大规 模对称非线性方程组的一种有效方法 关键词：对称非线性方程组；无导数线性搜索；共轭梯度法；全局收敛性 硕士学位论文 a b s t r a c t t h es t u d yi nt h en u m e r i c a lm e t h o d sf o r s o l v i n gn o n l i n e a re q u a t i o n si sa n i m p o r t a n tr e s e a r c ht o p i ca n dh a sr e c e i v e dm u c ha t t e n t i o n a m o n ge x i s t i n gm e t h o d s ， n e w t o n sm e t h o di sad e s c e n tm e t h o di nt h es e n s et h a tt h ed i r e c t i o n sg e n e r a t e db vt h e m e t h o da r ed e s c e n tf o rt h en o r mf u n c t i o n u n d e rs u i t a b l e c o n d i t i o n s ，n e 、t o n ，s m e t h o di s g l o b a l l ya n ds u p e r l i n e a r l yc o n v e r g e n t h o w e v e r ，n e w t o n sm e t h o di sa d e r i v a t i v ed e p e n d e n tm e t h o d i no t h e rw o r d s ，a te a c hi t e r a t i o n ，t h em e t h o dn e e d st o c o m p u t et h ed e r i v a t i v eo ft h ee q u a t i o n o nt h eo t h e rh a n d ，t h ed e r i v a t i v e f r e em e t h o d s s u c ha st h eq u a s i - n e w t o nm e t h o da n dt h es o - c a l l e d s p e c t r a lg r a d i e n tm e t h o da r e g e n e r a l l yn o tn o r md e s c e n t t h er e s e a r c hi nt h es t u d yo fn o r md e s c e n td e r i v a t i v e f r e e m e t h o df o rs o l v i n gn o n l i n e a re q u a t i o n si sa ni m p o r t a n td i f f i c u l tt o p i c i nt h i st h e s i s ， o nt h eb a s i so ft h er e c e n t l yd e v e l o p e dn o r md e s c e n tg a u s s - q u a s i n e w t o nt y p em e t h o d f o rs o l v i n gs y m m e t r i cn o n l i n e a re q u a t i o n sb yg ue t a l ，w ep r o p o s ean o r md e s c e n t c o n ju g a t eg r a d i e n tt y p em e t h o df o rs o l v i n gs y m m e t r i cn o n l i n e a re q u a t i o n s w et r yt o e x p l o i tt h ei d e ao ft h ec o n ju g a t ed e s c e n tm e t h o di nt h es o l u t i o no fu n c o n s t r a i n e d o p t i m i z a t i o nt ot h em e t h o d t h ep r o p o s e dm e t h o de n jo y ss o m ea t t r a c t i v ep r o p e r t i e s 1 a te a c hi t e r a t i o n ，t h em e t h o dc a ng e n e r a t ed e s c e n td i r e c t i o nt ot h en o r mf u n c t i o no f t h ee q u a t i o n ；2 n od e r i v a t i v en e e d st ob ec o m p u t e d ；3 u n d e rw e e kc o n d i t i o n s ，t h e m e t h o di sg l o b a l l yc o n v e r g e n t ；4 t h em e t h o dr e s e r v e st h el o w e rs t o r a g eo ft h ec d m e t h o df o ru n c o n s t r a i n e do p t i m i z a t i o n c o n s e q u e n t l y ，i tc a nb ea p p l i e dt os o l v el a r g e s c a l es y m m e t r i cn o n l i n e a re q u a t i o n s w ea l s od on u m e r i c a le x p e r i m e n t st o t e s tt h e p r o p o s e dm e t h o d w ef i r s tt e s tt h eg l o b a lc o n v e r g e n c eo ft h em e t h o d t h e nw et e s t t h em e t h o df o rr e l a t i v e l yl a r g es c a l ep r o b l e m s t h en u m e r i c a lr e s u l t ss h o wt h a tt h e p r o p o s e dm e t h o di se f f i c i e n t k e yw o r d s ：s y m m e t r i cn o n l i n e a r e q u a t i o n s ；d e r i v a t i v e f r e el i n e a r s e a r c h e s ； c o n j u g a t eg r a d i e n tm e t h o d ；g l o b a lc o n v e r g e n c e i i i 求解对称非线十牛方程组的一种修正共轭梯度法 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t i i i 附表索引v 符号说明v i 第1 章绪论1 1 1 非线性方程组的背景- 1 1 2 非线性方程组的迭代解法2 1 3 本文的主要工作4 第2 章求解非线性方程组的无导数线性搜索6 2 1 非单调的无导数线性搜索6 2 2 单调无导数线性搜索与近似最速下降方向7 第3 章求解对称非线性方程组的无导数下降型c d 方法1 0 3 1 修正c d 方法1 0 3 2 求解对称非线性方程组的一种无导数c d 型算法1 2 第4 章数值实验1 9 4 1 数值实验的相关说明1 9 4 2 数值结果及其分析2 0 结 论2 2 参考文献2 3 致j 射2 6 硕上学位论文 附表索引 表4 1 问题1 的数值结果2 0 表4 2 问题2 的数值结果2 l v 求解对称非线性方程组的一种修正共轭梯度法 为了后面使用方便， r ： r ”： a ，九： ( x ) ，p ( x ) ： i | 1 l ： x ： s l ： j ： v ： d k ： v f ( x k ) ： m a x ( x ，少) ： ： 符号说明 现在将本文中所使用到的记号标记如下： 实数空间； n 维实数向量空间；一 步长因子； 目标函数； e u c l i d e a n 范数； 问题的最优解； 使得； 存在； 任意； 目标函数厂( x ) 在坼处的方向； 目标函数f ( x ) 在砟处的梯度函数； 中取最大的数； 无穷求和 硕十学位论文 第1 章绪论 1 1 非线性方程组的背景 ； ， 其中z ( 待1 ，2 ，n ) ，r “一r 连续可微若引入向量表示： f c x ，= 二三 ，x = 三 ，。= 三 f ，吼( x ) 、7 化问题的一阶必要条件，等式最优化问题的”k k t ”条件1 1 等下面的两点边值问 题 2 1 也是一个典型的对称非线性方程组： d = ( ，x ) l o t l ，砌 x 扣o ) 上二阶连续可微求解该问题的常用方式之一是利用差分方法将其离散化，取步 长 则： 厅= 击，l = 力，j = o , 1 , - - n + 1 求解对称非线性方程组的种修正共轭梯度法 我们引入矩阵 x ”( 。) = 萨1 ( _ + l 一2 _ + _ 一。) ，= 。，l ，刀+ 1 及映射妒：r ”一r ”为： a = 21 一121 121 一l l2 ( x ) = h 2 f ( t l ，x 1 ) 一口 h 2 f ( t 2 ，x 2 ) h 2 f ( t 。一l ，x 。一1 ) h 2 f ( t 。，x 。) 一卢 从而上述两点边值问题可以通过求解对称非线性方程组获得其数值解： a x + ( x ) = 0 数值方法是求解( 1 1 ) 的主要方法解非线性方程组的算法有直接法和迭代法， 本文仅研究其迭代法我们将在下一节中详细介绍有关求解非线性方程组的迭代 法求解非线性方程的其它算法可参见o r t e g a 和r h e i n b o l d t 的文献【3 】 1 2 非线性方程组的迭代解法 迭代法是求解( 1 1 ) 的一类主要算法，而牛顿法和拟牛顿法【4 3 是求解非线性方 程组的两种典型迭代法 一 求解( 1 1 ) 的牛顿法的迭代格式如下： x m = + d ，k = 0 ，1 ，( 1 2 ) 其中d 。称为牛顿方向，是下面线性方程组的解： f ( ) d + f ( x t ) = 0 牛顿法的一个主要优点是其局部超线性收敛性和二次收敛性；即当x 充分接 近方程组( 1 1 ) 的解x 时，算法产生的点列在一定条件下满足： l l x 。+ 。一x i l = 。0 l x 。- - x * 1 1 ) ， 和 i j x 。+ ，一x = o ( x k - - x * i | 2 ) 2 硕上学位论文 牛顿法的另一个优点是牛顿方向d 。是方程组( 1 1 ) 的模函数( x ) = 去舻( x ) 1 1 2 的 一个下降方向事实上，我们有： v f ( x 。) r d 。= - i i f ( x 。) 1 1 2 0 ，k - = 0 步2 若护( ) l l s ，则算法终止得到问题的解否则，转步3 步3 解线性方程组 b i d + f ( x 女) = 0 ， 得解以 步4 由线性搜索确定步长0 1 。 步5 令x 榭= 以+ a 女d ，若0 f ( x 川) l i s ，则得解+ 1 ，否则，由拟牛顿修正公 3 求解对称非线性方程纽的一种修正共轭梯度法 式确定玩 步6 令k ：= k - t - 1 ，转步1 上面步4 中的修正公式可采用b r o y d e n 秩一公式或b f g s 公式等 拟牛顿法的一个重要优点是其局部超线性收敛性有关各种拟牛顿法的局部 收敛性及其超线性收敛性可参考文献【5 7 】 由上面的迭代过程可以看出，拟牛顿法是一种无导数算法，即在算法的迭代 过程中无需计算方程组( 1 1 ) 的导数因而，可用于求解不可微非线性方程组当 方程组可微但其导数难以计算时，拟牛顿法也是最受欢迎的求解方法之一然而 正是由于拟牛顿法不计算导数，因此，算法产生的拟牛顿方向以不能保证是方程 组模函数的下降方向，从而使得算法的全局收敛性问题变得较为困难 研究拟牛顿法的全局收敛性问题需要采用无导数线性搜索，我们将在下一章 中介绍几种无导数线性搜索技术 1 3 本文的主要工作 本文进一步研究求解非线性方程组的无导数算法与前面拟牛顿法不同，我 们需要研究求解大规模非线性方程组的无导数算法而且算法是下降算法，即算 法的每次迭代均能产生使模函数下降的方向我们集中于对称非线性方程组的求 解 求解对称非线性方程组的第一个下降型无导数算法由g u ，l i ，q i ，z h o u 8 l 提 出，在文献 8 】中，作者针对对称非线性方程组的特点，构造了一个使方程组模函 数下降的无导数方向该方向是最速下降方向和某个拟牛顿矩阵的乘积，因而是 一个退化的拟牛顿方向在此基础上，文献1 8 i 提出了求解对称非线性方程组的一 种下降型无导数b f g s 算法，文章证明了，若采用适当的线性搜索技术，则这种 算法具有全局收敛性和超线性收敛性 最近，伍杰【9 1 ，l i ，w a n g 1 0 】将文献 8 中的思想推广到了求解对称非线性方程 组的共轭梯度法，并证明了无导数共轭梯度型算法的全局收敛性其数值结果表 明无导数共轭梯度型算法是求解对称非线性方程组的一种有效算法 本文进一步研究求解对称非线性方程组的无导数共轭梯度法我们集中于研 究c d 型共轭梯度法算法的基本思想如下：在文献 8 】的基础上我们产生一个近 似的最速下降方向，再结合求解无约束最优化问题的c d 算法的思想提出了求解 对称非线性方程组( 1 1 ) 的一种c d 型无导数算法，在一定的条件下，我们证明了 算法的全局收敛性本文所提出的算法具有如下优点： 1 算法的每次迭代都能产生使得方程组模函数下降的充分下降方向； 2 算法不需要计算函数的导数； 3 在较弱的条件下算法具有全局收敛性； 4 硕上学位论文 4 该算法继承了共轭梯度法存储量少的优点，因此可用于求解大规模对称非 线性方程组 本文以后的各章节安排如下：在第二章中，我们详细介绍了无导数线性搜索， 包括单调线性搜索和非单调线性搜索，并介绍了应用无导数线性搜索求解对称非 线性方程组的无导数最速下降法；。在第三章，我们将求解无约束最优化问题的共 轭梯度法的思想引入进来，构造了一个无导数的修正c d 型共轭梯度法，并证明 其全局收敛性；在第四章，我们通过数值试验检验我们的算法，并通过与无导数 最速下降法的比较认为无导数修正c d 型共轭梯度法是求解大规模对称非线性方 程组的一种有效算法 5 求解对称非线性方程组的一种修正共轭梯度法 第2 章求解非线性方程组的无导数线性搜索 一由于本文研究的是无导数算法，因此需要采用无导数线性搜索已有的求解 无约束最优化问题的线性搜索方式均利用了目标函数的导函数信息，因而，不能 应用于求解非线性方程组的无导数算法 已有的求解非线性方程组的无导数线性搜索可分为两类：即单调型线性搜索 和非单调型线性搜索本章，我们分两节分别介绍相关的无导数线性搜索 2 1 非单调的无导数线i 生搜索 如l 司上一章所指出的，求解非线性方程组的拟牛顿法和其他无导数算法，由 于其方向的计算不需要方程组的导数信息，因而算法产生的方向一般不能保证是 方程组模函数的下降方向此时可采用非单调无导数线性搜索 求解非线性方程组的第一个非单调无导数线性搜索由l i 和f u k u s h i m a 1 1 】提 出，该线性搜索确定的步长口。满足： 0 f ( x k + a 七以) 0 2 一f | 尸( 坼) 1 1 2 一仃。0 a 。f ( x k ) 0 2 一c r 2 陋。巩1 1 2 + s 。0 f ( x k ) 0 2 ( 2 1 ) 其中仃。，仃：是给定的正常数，正数序列忙。) 满足： 旦 吼 ( 2 2 ) 七霉o 容易证明在f ( x i ) 0 的条件下，不等式( 2 1 ) 对所有充分小的a 。是成立的因 而，可通过类似于a r m i j o 型线性搜索的方式确定步长a 。一般地，可通过下面 的方式获得a 。： 给定p ( o ，1 ) ，令a 。是集合 p i = o ，1 ， 中使得( 2 1 ) 成立的最大者 上面的这种无导数线性搜索是非单调的，也就是说由它产生的序列扩( 坼) ) 不 一定是单调递减的但是，当接近于非线性方程组( 1 1 ) 的解时，( 2 1 ) 式中的 s 。i i f ( x 。) f f 2 会充分小，因此，我们认为这是一种近似的下降搜索这种非单调的线 性搜索的优点在于： 当i i f ( x 。) 雌有界时， u x m - x , 1 1 2 o o ， ( 2 3 ) k = 0 更进一步，序列杪( 砟) 是收敛的，利用线性搜索( 2 1 ) ，l i 和f u k u s h i m a 1 1 1 提出了 求解对称非线性方程组的一种高斯一牛顿型b f g s 法并证明了算法的全局收敛性 6 硕十学位论文 和超线性收敛性： 定理2 1 t 1 1 】设f 连续可微，f ( x ) l i p s c h i t z 连续，且f7 ( z ) r = f ( x ) 则采用 无导数线性搜索( 2 1 ) 的高斯一牛顿型b f g s 法所产生的点列k 收敛于对称非线 性方程组( 1 1 ) 的唯一解而且收敛速度是超线性的 l i 和f u k u s h i m a e l 2 1 提出了另一种无导数线性搜索，该线性搜索中确定步长晓i 的条件是： f ( x 。+ a 。d 。) l l 一0 f ( x 。) l i 仃。l l 位。d 。0 2 + s 。 ( 2 4 ) 其中口，仃：是给定的正常数，正数序列墨。) 同样满足( 2 3 ) 利用该线性搜索，文献 12 提出了一种求解一般( 非对称) 非线性方程组的 b r o y d e n 秩一算法并证明了算法的全局收敛性和超线性收敛性 l i 和f u k u s h i m a ”】还提出了另一种无导数非单调线性搜索，该线性搜索的条 件是： 0 f ( x 女+ o l d i ) - i i f x t ) l i 一仃。0 a 七f ( x 。) - o - 2 i j f ( x 。+ o r 。d 。) 一f ( x 女) i i + 。， ( 2 5 ) 其中仃。，仃：是给定的正常数，正数序列扛。) 同样满i f = ( 2 3 ) 这种线性搜索能保证i k + 。- - x 。0 o o 因此，点列k 必定是收敛的l i 和 k = o f u k u s h i m a 1 3 】证明了采用线性搜索( 2 5 ) 应用d f p 方法求解对称非线性方程组时具 有全局收敛性 b i r g i n ，k r e j i e 和m a r t i n e z 1 4 1 对文献 1 2 】中的线性搜索进行了改进，提出了如 下线性搜索方式： 0 ，( x 女+ a d k ) l l ( 1 + 口女o - ( ，- 1 ) ) j l f ( x 七) 0 + s l ， ( 2 6 ) 其- 中仃( o ，1 ) ，卢【0 ，l 】，s t 同样满足( 2 3 ) 其他非单调线性搜索可参见文献 1 5 2 3 】 2 2 单调无导数线性搜索与近似最速下降方向 若d 。是方程组( 1 1 ) 的模函数( x ) = 如，( x ) 1 1 2 的下降方向，即v f ( x 。) rd k 0 ，则 此时可采用单调无导数线性搜索，如a r m i j o 型线性搜索方式等在文献【8 】中， 作者采用了如下搜索条件： f ( x t z g ( 允) ) f ( x ) 一仃l ( ，( x t + a f ( x ) ) 一f ( x 。) ) 7 g 。( a ) 一仃：l l 允f ( x ) 1 1 2 ( 2 7 ) 上面的线性搜索实质上是一种近似于求解无约束最优化问题的a r m i j o 型线性搜 索 7 求解对称非线性方程组的一种修正共轭梯度法 实现单调无导数搜索的一个重要条件是以必须是厂在处的一个下降方 向对于无导数算法而言，构造的下降方向是一个非常赋有挑战性的工作，当 f 7 ( x ) 非对称时，尚未见有相关研究 对于对称非线性方程组，文献【8 】利用f7 ( x ) 的对称性，巧妙地构造了厂的一个 无导数下降方向其基本思想如下： 注意到： v f ( 加加烛坐警竽型， ( 2 8 ) 当训， ) 0 足够小时，! 垡型善堕) 二! 盟是方程组模函数的方向导数的一个很好的 估计基于这样的观察，我们得到方程组模函数的一个近似： v f ( x ) f ( x + a f ( _ x ) ) - f 一( x ) ， 令： g 。( a ) ：些芷掣掣! 垃， 利用f ( x ) 的对称性，不难导出： l ：i m 。v f ( x 。) 7 g 。( z ) = i i v ( x 。) 0 u ” 因此，当允充分小时，一( a ) 是在x k 处的下降方向它是的最速下降方 向的种近似我们称之为近似最速下降方向 由上面的过程可以看出，当九充分小时，以下不等式成立： f ( x 女一a g 。( a ) ) f ( x 女) - a 1 ( ，( x i + a f ( x ) ) 一，( x t ) ) 7 g 。( z ) - a 2 i i z f ( x 七) 1 1 2 ( 2 9 ) 其中仃1 ，仃2 都是正常数，仃l ( 0 ，1 ) 通过以上的讨论，我们可以构造方程组模函数f ( x ) 的一个下降方向 过程1 ( 估计最速下降方向) 给定常量仃l ，p ( o ，1 ) ，。仃2 令a = j d ， f = 0 ，1 ， 记为a = p 。满足 f ( x 一z g ( 九) ) f ( x 七) 一仃1 ( 尸( x t + 允f ( 石i ) ) 一，( x t ) ) r g 女( a ) 一a 2 z f ( x ) 1 1 2 ，的最j 、整数 ，记g k = g k ( p 慵) 说明：过程1 提供了一种方式得到方程组模函数的下降方向一g 。同时，不等 式( 2 9 ) 告诉我们： f ( x t 一丸g ) 0 ，0 。l ， ( 3 1 ) d 21 一 坼) + 色巩一1矿 j 上面公式中成的不同选取方式对应于不同的共轭梯度法，著名的有： 成= 胪= 鼍篇鬻， 阽眩= 怒， 成= 酽= 监器胖， 卢。= 卢尸= 一j 些圣缟， 凤卅= 而牖 我们以c d 方法为例给出非线性共轭梯度的算法如下： 算法3 1 ：f 非线性共轭梯度法c d 算法) 1 0 硕十学位论文 步1 给出x o r ”，d o = 一v 厂( x o ) ，0 l ，七：= 0 步2 若0 夥( ) | l ，则算法终止得到i 口- j 题的解坼否则，转步3 步3 由线性搜索确定步长因子仅。 步4 确定砟+ l = + a t 巩 步5 。由( 1 3 ) 确定或其中卢。= 卢尸决定 步6 令k ：= k + 1 ，转步1 若将算法3 1 中步5 中的仇= p 尸2 6 1 换为反= 卢尸 2 7 1 ，卢。= p 尸2 8 1 ， 几= 卢严2 9 1 ，卢。= 卢夕r 【30 1 ，我们就称相应的算法称为f r 算法，p r p 算法，h s 算 法，d y 算法 本文集中于对c d 算法的研究，c d 方法又称为共轭下降法( c o n j u g a t ed e s c e n t m e t h o d ) ，该方法是在1 9 8 7 年由f l e t c h e r 2 6 1 首先引入的c d 方法的一个重要性质 是：在近似线性搜索条件 i v f ( x , + 1 ) 2 反l 一研( 稚) 2 ，0 仃 1 下，当可( ) 0 时，卢尸公式满足： 夥( 坼) 0 也就是说只要强w o l f e 线性搜索条件中的参数仃 l ，在每次迭代中c d 方法产生 的搜索方向是下降盼戴或虹和袁亚湘1 3 l j 证明了在w o l f e 线性搜索下，只要每个 搜索方向是下降方向，那么c d 方法的全局收敛性就能得到保证在推广的w o l f e 线性搜索下戴或虹和袁亚湘【3 1 】详细给出了c d 方法全局收敛性证明并且他们得 出该方法在推广的w o l f e 线性搜索下依然能够保证每次迭代所产生的搜索方向是 下降的然而，c d 算法与其他的所有共轭梯度法都具有一个相同的缺点，即： 当采用非精确线性搜索时，所产生的方向都不能保证是目标函数的下降方向 为了克服共轭梯度法的这种缺陷，人们提出了共轭梯度法的各种修正形式， 参见文献 3 2 3 9 这些修正算法的一个共同优点是算法能产生充分下降方向，该 性质与算法所采用的线性搜索无关而且，在一定条件下，这些修正的算法都具 有全局收敛性然而，关于c d 算法的修正形式尚不多见 本节，我们首先提出一种求解无约束最优化问题的修正c d 共轭梯度法 类似于m p r p 方法，我们提出一种修正的c d 算法如下： ，d k 一吼赢蚤箩甾， 2 ， 其中 酽一摆器， 求解对t 4 ：t 线性方程组的一种修正共轭梯度法 吼一瓦- - 丽k - l - k - i ， 儿一。= 夥( 故) 一耵( 吒一。) 一 通过计算我们得知有如下等式成立： 彰可( ) = 一吼w ( 稚) r 夥( ) + 成c d 口t 耵( 砟) = 赤高l l v ：( x , ) l 一擐拣屯坝砟) ：g 梁掣陬硝 以一。夥( 靠一。) ”一“” = 一l l v ：( - , ) 1 1 2 上式保证了当不是原目标函数的稳定点时，我们有： 町( ) 1 畋 0 即修正c d 方法中所构造的反一定是目标函数在处的一个下降方向而且，当 采用的是精确线性搜索时，有： v f ( x d 7 以一1 = 0 此时： 吼= 一j 主两 - 1 y k - i = 罢兰嬲= 从而，修正c d 方法就等价于c d 方法了 在上面的基础上，我们给出求解无约束最优化问题的一种修正c d 型共轭梯 度算法如下： 算法3 2 ( 求解无约束最优化问题的修正c d 型算法) 步1 给出x o r ”，d o = 一v 厂( x o ) ，0 0 且充分小时，破( a ) 是f ( x ) 在x k 处的下降方向 类似于上一章中近似最速下降法的过程，我们给出无导数修正c d 型方法的 两个主要过程： 过程1 ( 计算无导数修正c d 型方法的方向) 给定常量q ，p ( 0 ，1 ) ，仃2 令九= p 。，i = 0 , 1 ，记为p 满足下式的最小 整数i f ( x l , + 2 d ( 旯) ) 厂( x 。) + 仃。( f ( x 。+ 允f ( x 。) ) 一f ( x 。) ) r 巩( a ) 一仃：iz f ( x 。) 0 2 0 3 l i 允以( 允) 1 1 2 ( 3 6 ) 记以= 矾( j d ) 1 3 求解对称非线性方程纽的一种修正共轭梯度法 我们给出下面的定理证明上述不等式的存在性 定理3 1 ：当允 0 足够小时，不等式( 3 6 ) 成立 证明由对称方程组的定义， 娥g 女( a ) = f ( ) f ( ) = v f ( x i ) 记： 一f v 厂“。、 k = 0 j , - - k 以2 t 一瓦可( 坼) + 瓦c d 以一。 尼1 其中： b”cd一磐，一缓t，一yk-1lgk 堋喝q d ；一一1口t l g 一1 则有： m l i m v f ( x ) r d i ( 允) = v f ( x t ) 7 d k 所以： r l i m , ；l - - - 0 i l f ( x t + 2 d ( 九) 允 ) 一f ( x t ) 6 1 ( f ( _ ) ci + z f ( x ) ) 一f ( x ) ) 7 1 d 女( 九) 允 = 渤阿( 故) r 以( a ) 一仃g e ( 九) r d t ( a ) j = ( 1 - - c t l ) v f ( x t ) 。巩 o l 当兄 0 足够小时，不等式( 3 5 ) 成立 上述过程提供了一种方式得到搜索方向喀同时，不等式( 3 6 ) 告诉我们 f ( x 女+ 九矾) 0 ，0 3 0 ，s 0 ，七：= 0 步2 若| | 耵( 坼) | | 0 ，使得： 舻( x ) 忙m ，v x q 炉( x ) 忙m v x q 证明：由假设a ，对任意给定的，有： l i f ( x ) 0 - l 1 x - y ol + l l f ( y o ) | i l ( 1 l x l + l y 。”l f ( y 0 ) l | ，v x q ， 0 ，7 ( x ) i | 三0 x 一i i + i i f ( y o ) l l l 0 x + h y o i ) + if ( y 。) l i ，v x eq 又因为水平集q = x r ”i f ( x ) f ( x o ) 有界，所以对于任意的x q ，存在常数p ， 使得：i i x l i 尸，令 m = 上妒+ 怫8 ) + m a ) ( 铷f ( ) l l ，l i f ( ) m 即知： 妒( x ) 忙地v x eq 扩( x ) l l m v x q 定理3 3 设数列 x k ) 由算法3 2 产生，那么： 1 5 求解对称非线性方程纽的一种修正共轭梯度法 z n ；t , f ( x , ) 1 1 2 ， k = o 忆训2 o 。， 0 0 ，c k 0 ， 所以： 一 g 2 o 即得：a k 0 ，使得： 0 f ( x 。) 忙s ，v k 不防设l i m s u p a k = 元，显然有瓦【o ，1 】 如果允 0 ，则存在 x k ) 的一个子列 x k ) ，k k 使得： 由定理3 3 ， 所以： l i m 九= a 0 七足七+ “ 。芷l i ，r a 。+ 。；t , i i f ( x t ) l = 万。k l i 。m 。+ 。i if ( x , ) l = ：0 1 6 硕十学位论文 与假设矛盾 如果a = 0 ，这就意味着 。；l i m i i f ( 坼) i i = 0 kki e - - * 1 1 ! i m 丸= 0 ，此时k = 膏- - ) 由算法3 2 可知：p 。1 九不满足不等式( 3 6 ) 所以： ( 托+ p q a k d k ) - - f ( x 。) 仃。( f ( x k + p 。1 a k f ( x k ) ) - f ( x k ) ) r d k 一仃：忙一1 九f 魄堋2 一口3 1 1 p 一1 九以( 兄硼2 另一方面，应用中值定理，3 t k ( 0 ，1 ) ，使得： 其中：= 则得到： 易知： f ( x 七+ p 。1 九t d t ) 一f ( x 女) = p 一1 允t v f ( x 女+ 气j p 一1 a 七d ) rd k = p - 1 z k v f ( x ) r d k + p _ 1 九( v f ( x t + t k p & k d k ) 一耵( ) ) r 以 p - l a 女v f ( x ) r d t + l p 。2 a 刘训2 九 口t = ( 仃1 9 t ( p 。1 a t ) 一f ( x t ) ) r 甜女， ( 厶+ 仃。) p 。1l l 畋0 + 仃：p l i ，( 吒) 0 2 i 觋q 从而存在 0 ，当k 时， 再由 = 舰( h - 、丝i l d , l l 狐 p 百i 矿丽最翮丽 o p 百i 莎丽再；下而 0 ! 刍! ! 1 2 ：l 生8 垒2 ：1 ! ! 兰业堕8 恻l = ( 厶+ 仃。) p 一1 + a ：p 一10 ，( 吒) 0 2 l l d 。1 1 2 ( 厶+ 仃，) p 一1 + 仃：p 一1i l f ( x o ) 1 1 2l e 2 ， 1 7 生 求解对称非线性方程组的一种修正共轭梯度法 d = ( 厶+ 仃3 ) j d 一1 + 仃2 p 一1ir ( - o ) 1 1 2 9 2 联系定理3 3 的第二个式子，有： 而 所以： o o 鼽矾8 2 薹鬲荔酾老而砑诵2 1 1 以1 1 2 薹d a k 2 ， l i m ( 咖a k 2 了= ( 1 一盯。) 2 ， 另外考虑 所以： 即得： ( ) 2 0 0 ， k = o k 0 2 = 衫以= 晤g 纠k 一4 4 巩一。1 1 2 + ( 2 0 k _ 爵帖七1 1 2 丽l e v i2：挫一螳iig-ii霄1ig i g 霎奇参 ( 7 1 以) 2 8 0 4 一 。l 。0 2 一台0 1 1 2 一s 2 壹( g 。r ) 2 ： k = l 喜群掰 上式与( 3 7 ) 矛盾 所以不管什么情况，假设不成立 即： l i m s u p lv f ( x _ ；i ) l i = o k - - - o ) 是有界序列，所以一定有收敛子列： 命题得证 ，1 i mt = x ，v f ( x ) = 0 i e k 女+ “ 1 8 ( 3 7 ) 硕 = 学位论文 第4 章数值实验 本章我们将就无导数修正c d 型算法以及近似最速下降法进行数值试验，所 选用的两个对称非线性方程组分别来自于文献 9 】和文献 4 0 1 4 1 数值实验的相关说明 我们先对两个典型的对称非线性方程组进行重述： 问题1 ： 考虑非线性方程组f ( x ) = 出+ 石 矿办( x ) 5 。，其中以为向量x 的维数， a = 91 1 91 一l91 - 1 ( x ) = e o s ( x 1 ) c o s ( x 2 ) c o s ( x d l 9 问题2 ： 考虑无约束最优化问题： m i n f ( x ) ，x r ” 其中f ：r ”专r 满足： 厂( x ) = ( ( 。+ # ) 2 - 4 x j 一，+ 3 ) 相应的对称方程组是： g ( x ) = i 1 耵( x ) = o ， 其中g ( x ) = ( 蜀( x ) ，9 2 ( x ) ，g 。( x ) ) r ， 蜀( x ) = 毛( 彳+ ) 一1 ， 蜀( x ) = 誓( l + # + 1 ) 一1 ，i = 2 ，3 ，刀一1 ， 1 9 邑 ) = 吒( 吒2 一l + 2 ) 我们对于非线性方程组1 和2 ，采用m a t l a b 编程，在内存为1 g ，c p u 为 2 1 0 g h z 的个人电脑上，分别对算法2 1 ( 近似最速下降法) 和算法轴( 无导数修正 c d 型算法) 进行数值试验 对于近似最速下降法，选用