（应用数学专业论文）半光滑方程组的牛顿类方法.pdf

中文摘要 摘要 最优化理论与方法是一门应用性很强的学科，它研究如何从某些实际问题的众多可 行方案中找出最优解。最优化技术在金融、贸易、管理、科学研究等国民经济的许多领 域中有着广泛的应用。 非线性方程组的求解是最优化理论的重要组成部分。经典的求解算法是牛顿法。此 方法在初始点足够接近解时具有良好的收敛性，然而在实际计算中对每一步迭代线形方 程组的精确运算往往是困难且不必要的。事实上，不精确牛顿法通过对每步迭代方程组 的近似求解从而在一定程度上克服了牛顿法的弱点。同时，迭代矩阵的不理想仍然会给 计算带来麻烦，而仿射变换可以通过改变矩阵的条件数从而改变计算效果。因此，本文 首先提出了用不精确仿射牛顿法求解非线性方程组，此方法迭代形式具有一般性，可以 将牛顿法、不精确牛顿法等牛顿类方法结合其中，并证明了算法具有好的局部收敛性。 本文又提出了用投影牛顿类法去解决更为一般的带有界约束的半光滑方程组问题。 这种方法的思想是将每一步牛顿类迭代点在约束区间上做投影，从而保证迭代点始终在 可行集内，通过证明，算法具有局部二次收敛性。 以上的方法虽然收敛速度较快，但遗憾的是只在局部收敛，也就是说这需要初始点 选得足够好，而这很多时候是很难做到的。众所周知，线性搜索是保证最优化理论与方 法整体收敛性的一项重要技术。本文最后便运用仿射技术合理构造一个等价方程组的情 况下，将仿射内点牛顿类方向与线性搜索相结合构造了一种算法，从而解决了整体收敛 性问题。本文结构如下： 第二章提出了用不精确仿射牛顿法求解非线性方程组，给出了算法的超线性收敛性 的分析与证明结果。第三章给出了解决约束半光滑方程组问题的投影牛顿类法和仿射内 点法。此算法可以拓展地把不精确拟牛顿法等牛顿类方法应用于解决带变量有界约束的 半光滑方程组问题。在合理的假设下，此算法具有全局收敛性和局部的超线性收敛速率 或二次收敛速率。第四章给出了一些具体的数值试验结果，表明了算法是有效的。最 后，第五章对本文工作进行了总结，并且提出了进一步的研究方向。 关键词：非线性方程组；半光滑；有界约束i 不精确牛顿法；仿射变换；投影；内点； 局部收敛速率；整体收敛性。 第1 页 英文摘要 a b s t r a c t o p t i m i z a t i o n ，w h i c hm a k e sr e s e a r c ho nh o wt of i n dt h eo p t i m a ls o l u t i o na m o n gm a n yf e a - s i b l ep r o j e c t s ，i sw i d e l ya p p l i e di nm a n yf i e l d ss u c ha sf i n a n c e ，t r a d e ，m a n a g e m e n ta n ds c i e n t i f i c r e s e a r c h h o wt os o l v et h es y s t e mo fn 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 tc o m p o n e n to fo p t i m i z a t i o n ac l a s s i c a la l g o r i t h mf o rt h ep r o b l e mi sn e w t o n sm e t h o d t h em e t h o di sa t w a e t i v eb e c a u s ei t c o n v e r g e sr a p i d l yf o ra n ys u f f i c i e n t l yg o o di n i t i a lp o i n tx 0 h o w e v e r , s o l v i n gas y s t e mo fl i n e a r e q u a t i o n s ( t h en e w t o ne q u a t i o n s ) e x a c t l ya te a c hs t a g ec a l lb ee x p e n s i v ei ft h en u m b e ro fu n - k n o w n si sl a r g ea n dm a yn o tb e j u s t i f i e dw h e nz ki sf a rf r o mas o l u f i o n b u tt h ed r a w b a c k sc a nb e o v e r c o m et os o m ee x t e n ti fw es o l v e dl i n e a re q u a t i o n si n e x a c t l ya n du s i n ga f f i n et r a n s f o r m a t i o n w i l li m p r o v et h ei 弓s i l l ta n dt h ef e a s i b i l i t y s o w ep r o p o s ea l la f f i n ei n e x a c tn e w t o nm e t h o d f o rs o l v i n gb o u n d c o n s t r a i n e ds e m i s m o o t he q u a t i o n s 。an e w t o n l i k em e t h o dw i t hp r o j e c f i o ni sp r o p o s e d i no r d e rt og e n e r a t ef e a s i b l ei t e r a t e s ，w ei n t r o d u c en e w t o n l i k em e t h o dt h a ti s a u g m e n t e db yt h ep r o j e c t i o no n t of e a s i b l es e t i ti sp r o v e dt h a tt h ea d d i t i o n a lp r o j e c t i o nd o e sn o t a f f e c tt h el o c a ls u p e r - l i n e a rc o n v e r g e n c es p e e d i no r d e rt oo b t a i ng l o b a lc o n v e r g e n c e w ed e s c r i b ea na l g o r i t h mc a l l e da f f i n es c a l i n gi n t e r i o r m e t h o d 1 1 地b a s i ci d e ai st or e q u i r eas t e pb a c k t r a c k i n ga l o n gt h en e w t o n l i k es t e pb yt h es t r i c t i n t e r i o rf e a s i b i l i t ya n dl i n es e a r c ht e c h n i q u e ，b e c a u s el i n es e a r c hi sa ni m p o r t a n t t e c h n i q u ew h i c h c a no b t a i ng l o b a lc o n v e r g e n c e t 1 l ef r a m eo ft h ep a p e ri sf o l l o w i n g ： i nc h a p t e r2 ，a na f f i n ei n e x a c tn e w t o nm e t h o df o rt h es y s t e mo fn o n l i n e a re q u a t i o n si sp r o - p o s e d w ew i l lf i n di th a sl o c a ls u p e r - l i n e a rc o n v e r g e n c em t eu n d e rs o m er e a s o n a b l ec o n d i t i o n s i nc h a p t e r3 ，w e p r o p o s e sa f f i n ei n e x a c tn e w t o nm e t h o dw i t hp r o j e c t i o na n da f f i n es c a l i n gi n t e r i o r m e t h o df o rs o l v i n gb o u n d - c o n s t r a i n e ds e m i s m o o t he q u a t i o n s 1 1 l ea f f i n es c a l i n gi n t e r i o rm e t h o d i s a c o m b i n a t i o n o f i n e x a c t n e w t o n m e t h o d a n d l i n es e a r c h m e 山o d i f t h e i t e r a t e d i r e c t i o n d o e s n t s a t i s f ya c c e p t a b l er u l e s ，w ec a ng e tn e ws t e pw h i c hc a nd e c l e a s et h ef u n c t i o nv a l u eb yu s i n gb o t h l i n es e a r c ha n di n t e r i o rp o i n tb a c k t r a c k i n gt e c h n i q u e w ew i l lg i v eaf u l lp r o o fo ft h eg l o b a la n d l o c a ls u p e r - l i n e a rc o n v e r g e n c er e s u l t s f u r t h e r m o r e n u m e r i c a lr e s u l t sa g i v e nt oi n d i c a t et h a t t h ea l g o r i t h mi su s e f u la n de f f e c t i v ei np r a c t i c e f i n a l l y , i nc h a p t e r5 ，as u m m a r yo ft h i sp a p e ri s m a d ea n dr e s e a r c hd i r e c t i o ni sp r o p o s e d k e yw o r d s ： n o n l i n e a re q u a t i o n s ；s e m i - s m o o t h ；b o u n dc o n s t r a i n e d ；i n e x a c tn e w t o nm e t h o d s ； a f f i n es c a l i n g ；p r o j e c t i o n ；i n t e r i o rp o i n t ；l o c a lc o n v e r g e n c er a t e ；g l o b a lc o n v e r g e n c e 第页 主要符号对照表 主要符号对照表 3 p 1 2 维实向量空间 ，p x mnx m 维实矩阵 0 z i 0 2e u c i i d 范数 约束优化问题在可行点z 处的等式约束指标集 一4 ( z ) a 让 工( z ，a ) f ( x ) f ，( z ) o f ( x ) x i n t ( x ) f 札 z 甄 z 膏 0 k h 以 k r k 仉 & r c o n o ( r ) d ( z ) s g n 约束优化问题在可行点z 处的不等式约束指标集 约束优化问题在可行点z 处的有效集 l a g r a n g e 乘子 约束优化问题的l a g r a n g e 函数 非线性影射 j a c o b i a n 矩阵 次梯度集合 可行集 严格可行集 有界约束下界向量 有界约束上界向量 非线性方程组的精确解或极小化问题的k - k - t 点 向量z 的第纠、分量 第k 步迭代点 第k 步迭代点的第i 个分量 第k 步搜索方向 第k 步线性搜索因子 残量序列 相对残量序列 压缩映射 第k 步仿射矩阵 第步仿射矩阵的条件数 尺度矩阵 符号函数 第页 论文独创性声明 本论文是我个人在导师指导下进行的研究： 作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表 示了谢意。 作者弛：乎f 醐： 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 名：砷铆鹳：皆殆日期 第一章最优化理论基础 第一章最优化理论基础 1 1 最优化问题简介 最优化问题是在许多可行方案( 决策) 中挑选最优的方案( 决策) 。最优化理论与方法是 研究如何从实际问题的众多方案中选取最优方案的一门学科。近年来，随着电子计算机 的普及以及优化计算方法的迅速发展，它在工农业生产、交通运输、金融、管理、通讯 等众多领域的实际应用日益广泛。为了确定最优的方案，需要针对具体的实际问题建立 相应的最优化模型，再根据模型的具体形式和特性来选择适当的最优化方法去求解。 最优化问题的数学模型一般形式为： r a i n ，( z ) s t q ( z ) = 0 ，i ( 1 1 ) c ( z ) 0 ，l z 其中，：舻一跪1 ，c l ：驴一蹰1 ，z 舻称为优化变量或决策变量，( z ) 称为目标函 数，龟( z ) 是约束函数，和z 分别是等式约束的指标集 l ，2 ，m ) 和不等式约束的指标 集 m + 1 ，m + 2 ，力。定义集合q 为 q d = e f z ic f ( z ) = 0 ，t ；q ( z ) 0 ，i 刁 则称q 为约束集合、约束区域或可行域。若七q ，则称为可行点或可行解。 等式约束等号满足时，可行域成为”严格可行域”，即( 1 1 ) 的严格可行域为： i n t ( q ) d = e f z ic f ( z ) = 0 ，t 占；q ( 。) 0 ， z ) ( 1 2 ) 当不要求不 ( 1 3 ) 对于一个可行点z ，所有的等式约束都被认为是有效约束。考虑不等式约束c ( z ) 0 ，如果有c f ( z ) = 0 ，就称约束q ( z ) 0 在点z 是有效约束或起作用约束：如果有c f ( z ) 0 ，就称不等式约束c f ( z ) 20 在点z 是无效约束或不起作用约束。如果所有的不等式约束 都是不起作用约束，就称z 是可行域的内点。 若问题( 1 1 ) 中不含约束条件，即q = 舻，称模型( 1 1 ) 为无约束优化问题。若模 型( 1 1 ) 中含有约束条件，即称模型( 1 1 ) 为约束优化问题。 1 2 最优性条件 最优化问题的最优解所必须满足的条件称为最优性条件。本节将介绍常用的一阶必 要条件和二阶必要条件。最优性条件不仅对于最优化理论的研究具有重要意义，而且对 最优化算法的设计和终止条件的确定起重要作用。 第1 页 1 2 最优性条件 定义1 2 i 设矿q ，a ( x ) 是起作用约束集，如果或者所有的化p ) ， 4 ( 矿) 都 是z 的线性函数，或者 v c i ( 矿) ，i 一4 ( 矿) ) 线性无关，则称问题( 1 1 ) 具有线性无关约束品 性。 为了更方便地讨论约束优化问题的局部极小点的最优性条件，我们引入约束优化问 题( 1 1 ) 的拉格朗日函数： 其中a 称为拉格朗日乘子。 下面我们先给出最优解的一阶必要性条件。 定理1 2 1 ( 【3 2 】) 设矿q 是问题( 1 1 ) 的局部最优解，若在矿点线性无关约束品性成立，则 存在向量”= ( a i ，婶) t ，使得 v 。l ( x ，”) = 0 ， n 0 ，i z kc i ( z ) = 0 ，i z ( 1 5 ) ( 1 6 ) ( 1 7 ) 定理1 2 1 通常被称为k a m s h k u h n t u c k e r ( 简称k - k - t ) 定理，( 1 5 ) ( 1 7 ) 称为问题( 1 1 ) 的一阶必要性条件或k _ 1 0 - t 条件。满足此条件的点称为k u h n m ，c l ( c r 点或k k - t 点。( 1 7 ) 式 称为互补松驰条件。如果对任意t z ，k 和q ( 矿) 中有且只有一个取零值，则称为严格互 补松驰条件成立。 由定理1 2 1 可知，无约束最优化问题的一阶必要性条件可描述为 v ( x 1 = 0 下面我们给出最优解的二阶必要条件定理。 定理1 2 2 ( 【3 2 】) 设矿q 是最优化问题( 1 1 ) 的最优解，且函- 数f ( x ) 与q ( z ) ，i = 1 ，2 ，p 二阶连续可微又设定理1 2 1 中的约束规范条件在点矿成立，从而存在拉 格朗日乘子向量”使k k - t 条件成立如果严格互补松弛条件在矿成立，则： 时一切满足 8 丁v ：。l ( x ，r ) s 0 s t v c l ( x ) = 0 ，i 4 ( z ) 的方向s 均成立 最后，给出最优解的二阶充分条件定理。 第2 页 4 z qk ，埘 一z ， = zl 第一章最优化理论基础 定理1 2 3 ( 【3 2 】) 设最优化问题( 1 1 ) 9 7 函数，( z ) 与c f ( z ) ，i = 1 ，2 ，m 均二阶连续可微， 在可行点矿处定理1 2 1 的约束规范条件成立，若存在拉格朗日乘子向量”使k - t - t 条件 和严格互补松弛条件成立，且对所有满足 的非零向量8 有 s r v c ( = ) = 0 ，t 4 ( 矿) s t v 。2 。l ( 矿，”) 8 0 则矿是问题( t 1 ) 的一个严格局部最优解 1 3 最优化方法的结构 求解问题( 1 1 ) 通常是通过求其k - t - t 点的途径得到它的最优解。一般采用的是迭 代法。其基本思想为：给定一个初始点。o 舻，按照某一迭代规则产生一个迭代序 列 z k ) ，使得当 z 是有限点列时，其最后一个点是k _ t _ t 点：当 z k ) 是无限点列时，它 的任意一个聚点是k t - t 点 最优化问题求解的基本迭代格式如下： 算法1 3 1 ( 最优化方法的基本迭代格式) 1 给定初始点z o ，k = 0 2 按某一规则构造搜索方向p k 3 确定步长a k 4 取下一个迭代点。k + 1 = x k + o t k p k 5 剖别z + 1 是否满足终止准则若满足，则停止迭代，z i + 1 是近似局部最优解；否 则，k # k + l 转第2 步 在以上迭代格式中，关键的两步是构造搜索方向m 和确定步长a k 。不同的构造方 向p 七和确定步长o k 构成了不同的算法。线搜索策略和信赖域策略是保证最优化方法整体 收敛的两类技术。个好的算法应具备的典型特征是：迭代点z 女能稳定地接近局部极小 值点矿的邻域，然后迅速收敛于矿。因此，评价算法优劣的标准之一是由它产生的迭代 序列 钆的收敛速度。设序列 ) 在某种范数意义下收敛于矿，即 1 i m0 k z 0 = o 若存在实数口 0 及一个迭代次数k 无关的常数q 0 ，使得 规搿钆 则称算法产生的迭代序列 z k ) 具有q o 阶收敛速率。特别地 第3 页 ( 1 8 ) ( 1 9 ) 1 4 解非线性方程组的牛顿法 ( 1 ) 当口= 1 ，q 0 时，迭代点列 ) 叫做具有q 一线性收敛速率； ( 2 ) 当l o 时，迭代点列 叫做具有q 二阶收敛速率。 另一种收敛速度是冗一收敛速度( 根收敛速度) ，即设 = 1 i ms u p 慨一矿0 1 胪 其中p 1 ，则若当一o o 时，满足o 岛 1 ，则迭代点列 x k n q 做具有r p 阶收敛速 率。 特殊的，当p = 1 时，称迭代点列 z k ) 叫做具有r 一线性收敛速率；当p = 2 时，称迭 代点列 “叫做具有r 一平方收敛速率。 算法的另一个重要特征为终止迭代所需要的终止准则。我们有时采用 或 0 z 膏+ 1 一k 0se ( 1 1 0 ) ，( o ) 一，( 瓢+ 1 ) e 来作为终止准则。对于有一阶导数信息的目标函数，根据最优性的一阶必要条件以及算 法的设计思想可以采用如下迭代终止准则： | l v ，( z i ) e 1 4 解非线性方程组的牛顿法 慌兰 ( 1 1 2 ) 其中 0 = 1 ，2 ，n ) 是定义在n 维e u c l i d 空间舻中开域d 上的实值函数。若用向量记号， 令 f ( x ) = 则上述方程组可以改写为 仁) ： 厶( ) z 1 ： f ( z ) = 0 第4 页 0 = ( 1 t 3 ) 第一章最优化理论基础 这里f 表示定义在舻中开域d 上的非线性向量函数，记为 f ：d c 铲耕。f 1 1 4 ) 若存在矿d ，使f ( x ，) = 0 ，则矿成为方程组( 1 1 3 ) 的解。非线性方程组的迭代解法 就是研究寻找方程组( 1 1 3 ) 的解矿的方法和有关理论。 非线性方程组的问题在许多领域有着广泛的应用。例如非线性有限元问题，非线性 断裂问题，弹塑性问题及其他非线性力学问题，电路问题，电力系统计算，经济与非线 性规划等等。 非线性方程组问题早在七十年代便在理论上和数值解法上有了大量的研究， 在o r t e g a 与r h e i n b o l d t 的书( 【l 】) 与文献( 【2 】) 中，已做了较系统地介绍。但是，由于非线 性方程组求解问题无论在理论上还是解法上都不如线性方程组成熟和有效。因此，对其 仍有不少问题需要研究。 牛顿法是求解非线性方程组的一个经典方法。它的基本思想是将非线性问题逐次线 性化而形成迭代程序。由于它收敛快，因此直到现在它仍然是一个重要方法，而许多新 的算法都是针对牛顿法存在的问题，在它的基础上改进而得到的。因此，对牛顿法进行 深入研究不仅在实际计算上有重要作用，而且在理论上也是很有意义的。 对于问题( 1 1 3 ) ，假设f ：3 p 一舻满足下列性质： ( 1 ) 存在矿使得f ( x ) = 0 ： ( 2 ) f 在矿的邻域中连续可微； ( 3 ) f ，( 矿) 非奇异 经典牛顿法的迭代格式为： f ( x k ) d k = - f ( z ) ，s k + l = z 女+ d k ( 1 1 5 ) 关于牛顿法的收敛性分析，已有很多形式不同的结论。综合这些结论，我们知道牛 顿法局部可达二次收敛，应用范围广，这是它的优点。但是由于每一步的精确线搜索需 要的计算量大，并且过分追求精度反而会降低整个方法的效率，因此人们提出了既花费 较少的计算量，又能达到足够下降的不精确牛顿法( 【7 ，8 ，9 】) 。这类方法在每次迭代中只是 近似的求解线性方程组问题( 1 t s ) ，即引入残量n ，记为 “三f 7 ( t ) 以+ f ( x k ) 不精确牛顿法的迭代格式为： 一( z t ) 如= 一f ( z t ) + 仉( 这里币氅s 仉) ，巩+ = z t + 如 ( 1 1 6 ) 其中0 曼r k 1 ，可以看出，它是用来控制不精确程度的序列如果仉兰0 ，则( 1 1 6 ) 就是 牛顿法。那么面临的一个重要问题就是，怎么控制残量的大小才能保持牛顿法的超线性 第5 页 1 4 解非线性方程组的牛顿法 收敛速率。通过理论分析( 【7 】) ，有下面定理： 假设不精确牛顿法所产生的迭代序列 z 女 收敛于矿，则 ( o ) 若珊一致收敛于零，则。女超缉陛收敛于矿 ( 6 ) 若f 0 ) 在矿处p 一阶日蒯d 盯连续，且当后一时 m = o ( jj f ( x k ) j l ) 则 z k ) q 一( 1 + a ) 阶收敛于矿 ( c ) 若 啦 兄一( 1 + a ) 阶线性收敛于o ，则 z k ) r 一( 1 + a ) 阶线性收敛于矿 由以上结论可知，不精确牛顿法的收敛速率可以由相对残量序列 仉 来控制，且当 其一致收敛于零时，方法可以保持牛顿法的局部超线性收敛速率。不精确牛顿法可以应 用于各种牛顿类方法，尤其对于大型问题将会收到很好的效果。作为这个方法的一个应 用，s t e i l l 卸g ( 【3 】) 提出了求解大型最优化问题的不精确拟牛顿法，d 曲i i i s 和w a l i 【e “【4 】) 也讨 论了拟牛顿法中的不精确性问题。 第6 页 第二章非线性方程组不精确仿射牛顿法 2 1引言 对于非线性方程组问题 f ( z ) = 0 其中f ：舻一g p 具有下列性质： ( 1 ) 存在矿使得f ( x ) = 0 。 ( 2 ) f 在矿的邻域中连续可微； ( 3 ) f ，( 矿) 非奇异 不精确牛顿法求解的过程是给出一个初始点。o 之后， 点z k 及方向如： if 7 ( 钆) d k = 一f ( x k ) + 仉 踹鲰 iz t + 1 = 茁+ d k ， ( 2 1 ) 按照如下算法计算第女步迭代 其中o 仉 l ，称相对残量序列。f 7 ( z k ) 是f ( z ) 在z 点处的j 扯o b i a n 矩阵。 不精确牛顿法与牛顿法相同，也具有局部的超线性收敛速率，它的收敛性分析在不 少文献中都已详细给出( 【9 】) 。而有时在求解问题( 2 1 ) 时，迭代矩阵的不理想会给计算带来 麻烦。仿射变换可以改变矩阵的条件数，使得计算更为稳定和有效( 【5 ，6 】) 。例如，考虑下 面仿射变换问题 户( z ) = 0 ，f 三p f ( 2 3 ) 其中p 舻“为非奇异矩阵。 这样，求解问题( 2 1 ) 便转化为求解( 2 3 ) 。下面便对于问题( 2 3 ) 利用不精确牛顿法进 行迭代，容易看出，( 2 2 ) 中求迭代线性方程组在仿射变换下形式是不变的，而相对残量 部分在仿射变换下变为 嵩淼_ r k| l r f k ) 0 这种将不精确牛顿法和仿射变换相结合的方法便是不精确仿射牛顿法， 点x o 之后，按照如下算法计算第步迭代点z 及方向以： if ，( z ) 如；- f ( z k ) + “ 龋鲰 【x k + l = z + 以 第7 页 即给出一个初始 【2 4 ) 2 2 不精确仿射牛顿法的构造与性质 更为一般地，本章将讨论用仿射牛顿类方法求解问题( 2 1 ) ，即给出一个初始点x o 之 后，按照如下算法计算第k 步迭代点。 及方向出： i 展出= 一，( 钆) + 亿 丽i i p 脚k r a 圳l i 孙 ( 2 5 ) 川r f ( z i ) 0 1 ”“7 【x k + l = z t + d k ， 其中0 仉 1 ，b k = f 7 ) ，b k ，r 咿“非奇异h - i i r b k i i 一致有界。 可以看出，算法( 2 5 ) i m 过作仿射变换把问题f 2 1 ) 转化到仿射空间中来解决。而且， 当鲰e 钆，h p b k = f ，( 巩) 时算法为不精确仿射牛顿法；当日k 为f ( x k ) 的近似矩阵时， 算法对应于不精确仿射拟牛顿法；若有y k 兰k ，r 兰i ，即为通常的不精确牛顿法。由 此，不精确牛顿类方法的迭代格式可以统一表示为( 2 5 ) ，而不精确牛顿法和其仿射问题 是算法( 2 5 ) 的特殊情况。 2 2 不精确仿射牛顿法的构造与性质 本节先做出以下常用的几个必要且合理的假设： 假设( 1 ) ：f ：d ( f ) 一舻，其中d ( f ) 为开集，f 在d ( f ) l 连续可微。 假设( 2 ) ：存在矿d ( f ) 使得f ( 矿) = 0 j | f 7 ( 矿) 非奇异。 假设( 3 ) ：f ，0 ) 在d ( 刁上( ka ) 一h g i d e r 连续( 其中o as1 ) 即存在k o ，使得任意y ，。 d ( f ) ，有i l f 7 ( ! ，) 一f 0 ) k i i v z l l l 显然，当a = 1 时，f 7 满足“p s c h i t z 条件。 假设( 4 ) ：记矿点处邻域s ( x ，u ) = p l z 咿，忙一矿0 墨u ，cd ( f ) 。矿为s ( 矿，u ) 上满 足( 2 1 ) 的唯一解。 假设( 5 ) ：记 b ( u ) 兰 f i v ，z s ( 矿，u ) ，有i l f 7 ( z ) 一1 i f ( p ) 一f 0 ) 】l l l v 一2 0 1 ) 其中以为常数。 p x ( 矿) - - - - - - 8 u p 业! 兰= 2 二麓! 智号= - 竺生业l 玑。s ( z 。，u ) ，”z ) ， e ( v ，z ) ；p ( z ) 一1 ( 。p ( ) 一f ( z ) ) 注意，当( z ) 在d ( f ) 上( 耳，a ) 一h 6 1 d e r 连续时，记靠= 吼1 | r f ( 2 ) 1 1 1 一，则算法( 2 5 ) 形 式上可以转化为下面的形式： 下面讨论这种算法形式。先引入引理： f ( 巩) + “ 而以 + 也 第8 页 ( 2 6 ) 麓一 ，_-，、_-【 第二章非线性方程组不精确仿射牛顿法 引理2 2 1 ( 【9 】弓l 理2 6 ) 设f 最) ，则存在口 m i n u ，( 矿) 】女) 使得f ，( z ) 在s ( 矿，盯) 中可逆，f i n z ，! ，s ( 矿，盯) 成立 其帆( 加耳卷鼯研 z s ( x ，盯) ，其中取盯 l i n u ，阻 ( z ) 】一1 1 ) l j 一( z ) 一1 f ( 。) 0 = l i f ( z ) 一1 ( f ，( z ) 一f 7 ( ) ) 0 p ( z ) 0 z 一茁1 1 1 1 因f ，( z ) - 1 = ，一( 矿) 1f ，( z ) ) “p ( 矿) ，故 l i e ( 矿1 f ( 圳f 矿下碥f 瓦栖 1 i e ( ，z ) 1 1 l i e ( 卫) 一1 f ( 卫) 1 1 1 1 f 7 ( z + ) 一1 ( ，( y ) 一f ( z ) ) o i i ! ：j i ； 鹄 注：在不混淆的情况下，为方便起见，以下简记纵( 矿) 为矿，记纵0 ) 为p z j l 理2 2 2 设f b ) 且z ，y s 扛，盯) 则成立 1lie(ie(x+t一z)，y)lldtsp。(z)(旦三；j掣二+mj)o + + t 一z ) ) ，s p ( z ) ( 旦j + ) 其中m = m i n i l z 一f | 1 ，l i x 一! ，0 1 ) o ”e z + t z z l 川l 出三羞：j 卫+ 一t ( x z - x ) - y l - l 、d t i i ； d t + i i x - ，i i 。，。：， p ( z 1 j j 卫一z + z 0 1 4 ) 2 7 = p ( 击忙一矿旷+ i i 矿一训1 ) e ( z + t ( z z 。) ，f ) = e ( z + ( 1 一t ) ( 卫一动，y ) z 1 i l e 。+ ( 1 一t ) ( z 一z ) ，) 【| d t p ( ! ，1 ( 1 一t ) z 一z 旷d t + z 1o 茁一f 旷d t l ( 2 8 ) 2 p ( 南i i x - - x * 1 1 1 + i x - 训1 ) 2 3 算法的收敛性分析 综合( 2 7 ) 与( 2 8 ) 式可得结论。口 由引理2 2 2 可知，若f b ( “，) ，则当。k 一矿，弧一矿时 r 1 u m i i e ( 矿- i - t ( z 女一矿) ) ，y k ) l l d t = 0 ( 2 9 ) # 。j o i 理2 2 3 ( 【7 】引理3 1 ) 记留三m a x 1 1 - ( 矿) 1 1 + 两南，2 i i 一( 矿) - 1 i i ，则当i i y - - x * i i 充 分小时，成立 割一矿峪i i f ( y ) i i z 恬一矿i i 2 3 算法的收敛性分析 2 3 1 算法的局部收敛性 这一部分将对于算法( 2 6 ) 进行收敛性分析。首先，给出下面保证算法合理有效的定 理。 定理2 3 1 已知z d ( f ) ，设存在，y 【o ，1 ) 与五使得i i f ( x ) + b d l l = 7 1 1 f ( x ) l l ，月- t c o n d ( p ) 1 ，其中c o n d ( p ) = l i p l | | i f _ 1 叭则存在q 。【0 ，1 ) ，使得任意q p 艋。，1 ) ，有d 满足l l p ( f ( x ) + b d ) ，7 1 1 p f ( x ) i 证明：首先，由已知条件可得 l i p ( f ( x ) + b 西| | l i p i i i i f ( x + 口西0 = 7 1 1 p i | | i f ( x ) l i r l l p i | | i f 1 p f ( z ) = 7 c o n d ( p ) h p f ( x ) i 显然f ( x ) 0 ，且i 0 设 恤三哗端俨叫p ， 则。s l ，且对任意的叩血，1 ) ，令s 兰三墨五则有 p ( f 0 ) + b d ) l l = f ( ) + f 1 - 面r l 鳓0 s 丁石l i p f 扛) o + 丁三1 r - - r m i a 弓兰o p f ( z ) + b 西 = 慧刮l + 品i i 即p ) 1 1 第l o 页 第二章非线性方程组不精确仿射牛顿法 得结论成立口 注意：此定理的意义在于保证了算法( 2 5 ) 的合理性与存在性，当然也同时保证了算 法( 2 6 ) 的合理有效性。要保证算法有效执行，则对矩阵p 的条件数有一定要求。 下面这个定理给出了算法( 2 6 ) 的收敛性分析结果和不精确仿射牛顿法所产生的迭代 序列 z k ) 收敛的条件此定理对于后面解决收敛速度的相关证明非常有用。 定理2 3 2 若f 毋) ，记= o k c o n d ( p k f 7 ) ) 0 最f ，) l i - 1 ，设b k = f 7 ( 弧) ，z o s ( x ，j ) ，且礁s 驴 l ，。并记r = 南6 ( 1 + y ) 则当k = 7 + 扩 1 时，不精确仿射牛顿法 产生的数列 z k 收敛于矿，且当充分大时，有 i x k + l z l | ，c l l f 女一z 0 证明：由算法迭代过程及中值定理可知 = ( 孤- 二矿) 【p ( 挑) - 1 f ( 讥) 一，一( v k ) - l f f f d o 女) o q + f 7 ( 弧) - 1 “ ( 2 1 0 ) = 一z 1 e ，弧) d t ( z e 一矿) + f ，( 讥) - 1 巧1 最“ 2 e ( & , y k ) d t ( x k - - x * ) i i 茎委尝l + i d t l l x - x l l - 0 1 1 x 。- x l l 亿 纠峄半+ 一 其中m = m i n l x k v k l l ，i i x 一z , k l l l 而且由中值定理及假设( 5 ) 可得 0 p ( 班) _ 1 尸f 1 p k r i l i 巩( 最f ，( 孤) ) - 1 i l o k l i p k f ( x k ) 1 1 e l l ( p k f ( 玑) ) - 1 1 r 一( y k ) 1 1 1 0z ? ( 讥) - 1 f 7 ( 靠) d tx k x * ) 1 1 1 ( 2 1 2 ) o k c o n d ( p k f ( y ) ) 0 r f ，( 弧) 旷10 u + e ( 靠，v k ) ) d t ( x 一z ) 旷 ，1 j 0 ( 魄+ h 0 e ( 靠，弧) d t ) 0 一矿 将( 2 1 1 ) ，( 2 1 2 ) 代2 x ( 2 1 0 ) 可得 f f z 七+ l 一卫0 1 瑟i ? 鞘端篙：忙。旷， 2 3 算法的收敛性分析 对于不精确仿射牛顿法，有z 女= 讥，即m = 0 ，故当充分大时，有 慨+ - 一矿恪( 南i l x k - - x s 禹慨一矿卅v k ) l l x k - - x * 1 1 1 s 【煮6 ( 1 + v k ) + y k l l z t 一矿1 1 1 ( 7 + y ) l l x k 一矿驴 = k 0 z 知一茁0 证毕。口 注意，文献【8 】( 定理3 1 ) 针对a = l 时即f 7 满足l i p s c h i t z 条件时的情况进行了收敛性分 析。而定理2 3 2 是对更一般的f 7 忙) 在d ( f ) 上( k ，a ) h 6 1 d c r 连续( 其中0 1 ) ，则称 钆) q p 阶 收敛于矿 定义3 ：若当k o o 时，满足h ms u pj i x k 一矿1 1 1 胪 1 ) ，则称 钆) r p 阶收 敛于矿 下面给出关于迭代序列局部收敛速率的定理： 定理2 3 3 对于算法( 2 6 ) ，假设f 最p ) ，若迭代数列 z k ，( 鲰) 均收敛于矿，且舭一矿0 = o ( 1 l = k 一矿i i ) ，则有以下结论成立 ( 1 ) 若a = 1 ，则 z k ) q 一超线性收敛于矿的充要条件是 熙s u p i p k r l l = 。圳鼽i i = 。( i i p f ( 圳) ( 2 ) 迭代序列 z 女) q 一( 1 + a ) 阶收敛于矿的充要条件是 恕s u p 剖器耘 佃钏鼽i i = d ( i i p - 即e ) 1 1 1 + ) ( 3 ) 迭代序列 女) r 一( 1 - 4 - a ) 阶收敛于矿的充要条件是 1 i ms u p l l 最“俨+ 矿 o ，使得 i 专+ 击圳。1 1 1 - 14 一d 旆+ 黠瑞】 g 即得 l l z + 1 一z 0 = o ( 1 l x k z 0 1 + 1 ) ( 2 2 6 ) 印 巩) q 一( 1 + a ) 阶收敛于矿 反之，假设 z q 一( 1 + a ) 阶收敛于矿 由引理2 2 3 和( 2 2 3 ) 式可得 赤i l x k 一：r l lsi i p k f ( z , o i i p z 慨一矿， 故 高每慨一矿一i i p k f ( 酬1 ( 例1 + 一矿1 1 1 + 1 从而 z 一z 0 1 + 1 = o ( 1 l p t f ( x ) 1 1 1 + 1 ) 再由引理2 2 2 ，( 2 1 0 ) 式及0 z + 1 一矿0 = o ( 1 l ：e k 一矿1 1 1 + 1 ) 得，当七一o o 时 , 1 0s i p k r k l i | j 最f ( k ) j j ( j | z k + l z 0 + 0 e ( 靠，) j j d t j j z 一z j j ) 剑即( 训川驴州) 讹( 州訾譬+ 删k 卅 慨f ，( 讥) ”o ( 1 l z k - z 1 1 1 ) + 点i i z 一矿1 1 1 拟 + m i n l l x 一k 0 1