（计算数学专业论文）不精确拟牛顿法的收敛性.pdf

大连理工太学硕士学位论文 摘要 非线性方程组的数值求解常见于许多科学与工程计算领域，具有十分鲎要的理论意 义翻实用徐氆在n e w t o n 法的基础上发曩两碍到的不糖赡n e w t o n 法是疆翦求鳃大规 模稀疏非缵睦方程组的主要方法之一不精确n e w t o n 法麓一个内外迭代过程，其补迭代 是n e w t o n 迭代，丽内选代则是某个线性迭代关于解非线性方穗组和无约束优化的不 精确牛顿型方法的研究很多，假关于不精确秩1 、秩2 修正攒牛顿法的研究尚未觅强， 这大概是因为秩1 、秩2 修正拟牛顿方程易于求解的缘故，但拟牛顿法撤广到b e m a e h 空闯上算子方程或m i r k n m x 闯繇上爵，豳为子闻篷静精确求释交褥酲难或不可麓，就有 必要研究不精确拟牛顿法本文对有限维非线性方程组建立不精确拟牛顿法的收敛性理 论，为研究b n a n e h 奎i u - j 算子方程程m i l i m a x 瓣题静不精确援牛溪法敲静准备。 关键调：非线性方程组；不精确拟牛顿泌；收敛性 王伟t 不精确拟牛顿法的收敛性 c o n v e r g e n c eo fq u a s i n e w t o nm e t h o d s a b s t r a c t n u m e r i c a im e t h o d sf o rn o n l i n e a re q u a t i o n sa r ev e r yi m p o r t a n ti nm a n ya r e a s i n e x a c tn e w t o nm e t h o d w h i c hi sb a s e do nn e w t o nm e t h o d i so n eo ft h em 越nm e t h o d s f o rs o l v i n gl a r g es p a r s es y s t e m so fn o n l i n e a re q u a t i o n s i n e x a c tn e w t o nm e t h o di sa n i n n e r o u t e ri t e r a t i v ep r o c e d u r e w i t hn e w t o ni t e r a t i o na si t so u t e ri t e r a t i o na n dal i n e a r i t e r a t i o na 8i t si n n e r t e r a t i o n t h e r ea r el o t so fr e s e a r e hr e s u l t sa b o u ti n e x a c tn e w t o n l i k em e t h o d sf o rs o l v i n gn o n l i n e a re q u a t i o n sa n du n c o n s t r a i n e do p t i m i z a t i o n ，h o w e v e r ， n or e s u l to ni n e x a c tr a n ko n eo rr a n kt w ou p d a t e dq u a s i - n e w t o nm e t h o d sh a sb e e ns e e n ， m a y b eb e c a u s er a n ko n ea n dr a n kt w ou p d a t e dq u a s i n e w t o ne q u a t i o n sa r ee a s i e rt os o l v e t h a nn e w t o ne q u a t i o n s w h e nq u a s i n e w t o nm e t h o d si se x t e n d e dt oo p e r a t o re q u a t i o n i nb a n a c hs p a c eo rm i n i m a xp r o b l e m s ，i ti sd i f f i c u l to ri m p 0 8 8 i b l et os o l v es u b p r o b l e m s e x a c t 坟s oi t i sn e c e s s a r yt oi n v e s t i g a t ei n e x a c tq u a s i n e w t o nm e t h o d s i nt h i sp a p e r ， c o n v e r g e n c eo fi n e x a c tq u a s i n e w t o nm e t h o d sf o rn o n l i n e a re q u a t i o n si nr ”i sp r o v e nu n - d e rc o m m o n l yu s e dc o n d i t i o n so nu p d a t e dm a r r i e s t h er e s u l t ss e r v ea sp r e p a r a t i o nf o r c o n v e r g e n c et h e o r yo fi n e x a c tq u a s i n e w t o nm e t h o d sf o ro p e r a t o re q u a t i o n si nb a n a c h s p a c ea n dm i n i m a xp r o b l e m s k e y w o r d s ：n o n l i n e a re q u a t i o n s ；i n e x a c tq u a s i - n e w t o nm e t h o d s ；c o n v e r g e n c e i i 太连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解l 大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文 作者签名 王讳 导师签名：耋星楚 型鲨年1 2 日旦日 独创性说明 露者器重声鹱：本矮学位论文是我令人在导撵摇导1 f 进行鲍研究工佟 及取得研究成果。尽我所知，除了文中特别加以标滋和致谢的地方外，论文 中不包禽其他人已经发表或撰写的研究成果，也不包含为获得大述理工大学 或其他单位的学位或诞书所使用过的材料。与我一阔工作的同志对本研究所 做的贡献均已在论文巾做了明确的说明并表示了谢意。 捧老签名：兰! 堑耳期：婴兰! ! ! ：星 大连理工大学硬士学位论文 1 绪论 随着现代科学技术的迅速发展，科学与工程计算的许多领域中所出现的非线性问题 越来越多，关于各种非线性问题的研究也日益受到人们的高度重视，各门交叉学科中的 非线性问题已经逐渐成为科学研究的热点之一非线性问题作为数学科学的主要研究课 题之一，不仅是现代科学技术发展的需要，而且也是现代计算技术高速发展的必然结果 利用计算机求解各类非线性问题，例如非线性有限元问题，非线性断裂问题，非线性弹 塑性问题，电路问题，电力系统计算问题，经济与非线性规划问题等，最终都可转化为 非线性方程组的数值求解 1 1 综述 非线性方程组的一般形式为 f ( x ) = 0 ( 1 1 ) 其中f ：d c 酽一舒为非线性算子，集合d 称为f 的定义域( 1 1 ) 中映射f 可以 是光滑的。也可以是非光滑的或半光滑的这里，我们主要考虑映射f 是光滑的情形 自从计算机问世以来，许多学者就已经在非线性方程组的求解问题上做了大量的研 究工作，得到了许多重要的成果o r t e g a 和r e i n b o l d t 1 对七十年代以前的有关理论做 了系统的总结，并对有关数值方法做了详尽的分析，其中包括n e w t o n 法，割线法，延拓 法以及极小化方法等n o c e d a l 和w r i g h t 2 详细地介绍了求解非线性方程组的有关方 法，并给出了算法描述以及实际操作时应注意的细节问题有关介绍非线性方程组数值 解法的著作，还可参阅f 3 ，4 ，5 ，6 ，7 】 与线性方程组不同，对于非线性方程组的求解除了极特殊的情形外，直接法几乎是 不可能的因此，目前求解非线性方程组主要用迭代法迭代法一般只能求出非线性方 程组的一个解按照方法的特点，可大致将迭代法分为以下几类： ( a ) 线性化方法，包括n e w t o n 法，割线法，拟n e w t o n 法等； ( b ) 由线性方程组的解法发展而得到的方法，如非线性j a c o b i ，g a u s s - s e i d e l 和s o r 法，非线性a d i 法等； ( c ) 延拓法； ( d ) 极小化方法，如最速下降法，共扼梯度法等； ( e ) 由( a ) ，( b ) 相结合而得到的方法，如n e w t o n - s o r 法，s o r - n e w t o n 法等 王伟：不精确拟牛顿法的收敛性 以上只是对求解非线性方程组的迭代法的大致分类有些方法可能很难归属于确定 的哪一类，特别是那些用于求解特殊类型方程组的方法在迄今为止发展起来的各种数 值方法中，可以说n e w t o n 法是求解非线性方程组( 1 1 ) 的最基本而又最重要的方法许 多方法都是以n e w t o n 法为基础，经过进一步改进，推广和发展而得到的，如割线法，拟 n e w t o n 法，不精确n e w t o n 法和信赖域方法等 n e w t o n 法最早是由n e w t o n 于1 6 6 9 年为了求解三次方程3 2 3 2 z 一5 = 0 而提出的后来，r a p h s o n 于1 6 9 0 年又给出了 用于求解更一般的三次方程z 3 一b x = c 的n e w t o n 法的另外一种形式因此，现在人们 也将n e w t o n 法称为n e w t o n - r a p h s o n 方法f 8 j n e w t o n 法的显著优点是收敛速度快，其不足是在迭代的每一步均需计算j a c o b i 矩 阵并求解n e w t o n 方程当j a c o b i 矩阵难以形成，或者当问题的规模较大时，n e w t o n 法 的计算代价就很昂贵此外，不具有全局收敛性质则是n e w t o n 法的另一缺点当j a c o b i 矩阵奇异或坏条件时，n e w t o n 法在数值上还会遇到困难 为减少n e w t o w 法计算量大的不足，d e m b o ，e i s e n s t a t 和s t e i h a u g 于1 9 8 2 年提出了 求解非线性方程组的不精确n e w t o n 法【9 】顾名思义，不精确n e w t o n 法就是在n e w t o n 法的每步迭代中只对n e w t o n 方程进行非精确求解不精确n e w t o n 法实质上是一类内 外迭代算法，其外迭代为经典n e w t o w 法，而其内迭代则可采用任何能够准确而有效地 对n e w t o n 方程加以求解的线性迭代法这种内外迭代技术由于能够充分利用j a c o b i 矩 阵的结构和稀疏性，因此可以大大降低n e w t o n 法的计算代价理论分析和实际应用均 表明，不精确n e w t o n 法是求解大规模稀疏非线性方程组的十分有效的方法1 3 j 针对n e w t o n 法每步迭代都要计算导数的不足，人们对n e w t o n 法提出了各种不同 的改进方式，由此也发展出了大量的方法，包括割线法，离散n e w t o n 法，拟n e w t o n 法 等拟n e w t o n 法是六十年代发展起来的有效方法之一，其中b r o y d e n 秩1 方法和b f g s ， d f p 秩2 方法是几个常用的拟n e w t o n 法，拟n e w t o n 法其实就是将n e w t o n 法中的 j a c o b i 矩阵用拟n e w t o n 矩阵近似代替得到的拟n e w t o n 法的最大优点是拟n e w t o n 矩阵可由简单的递推关系而得到，因此，它大大降低了n e w t o n 法的计算量和n e w t o w 法一样，拟n e w t o n 法也是局部收敛的，而且在一定的条件下，其收敛速度可以是超线 性的 1 2 论文创新点 文献【1 0 】中证明了鼠与f 7 ( z ) 充分接近时，不精确n e w t o n 型法具有超线性收敛性， 但是这个条件比较强，用拟牛顿法修正得到的秩1 、秩2 校正矩阵不能满足这个条件本文 讨论了在秩1 、秩2 校正矩阵满足的常见条件l i b k f 7 ( z + ) 】( z 抖1 一x k ) l i = o ( 1 l x 抖1 一x k i i ) 2厶 大连理工大学硕士学位论文 下，不精确拟牛顿法的超线性收敛性问题 1 3 论文写作章节安排 本文基本框架如下： 第一章：对求解非线性方程组的迭代法进行介绍 第二章t 介绍非线性映射基本性质 第三章：不精确n e w t o n 法的收敛性对n e w t o n 方程近似求解的n e w t o n - g m r e s 方法 第四章；拟n e w t o n 法及校正公式性质 第五章：不精确拟n e w t o n 法的收敛性 3 大连理i 大学硕士学位论文 2 非线性方程组基本知识 2 1 非线性映射的性质 为了考虑非线性方程组f ( x ) = 0 的求解，我们首先引进有关非线性映射的一些定义 和性质这些定义和性质是研究非线性方程组算法的基础 设向量值函数f ：d c r “一兄”，其中 f ( x ) = ( ( z ) ，2 ( z ) ，工。( 。) ) 丁， 这里 ( z ) 为f 扣) 的第i 个分量函数一般情况下， 五( z ) 为非线性函数 定义2 1 设f ：dc 彤一彤如果对任意固定的h r ”，恒有 i m l l f ( 护+ 嘲一f ( x o ) l l = o 则称f 在点o o 处是半连续的若有 川l i l m 。i i f ( 。+ a ) 一f ( 。) | i = o 则称f 在点七。处是连续的 定义2 2 称映象f ：dc 舒一册子d 的内点z 处g 一可微( g h t e a u x 可微) 或g - 可导，如果存在线性映豪a 三( 彤，r ”) ，使得对任何h 舒，x + h d ，有 l i m i i f ( x + t h ) - 。f ( x ) - t a h l l ：o ， t 一0 t 此时，称a 为f 在点z 处的g 一导数，记为f ，( z ) = a 定义2 3 称映象f ：dc 彤一舻于d 的内最z 处f 。可微( f r & h e t 可微) 或f - 可导，如果存在线性映象ae 工( 舻，尼“) ，使得对任何h 即，z + h d ，有 l i 。l l 兰壁生二享生2 二墨!= 0 此时，称a 为f 在点z 处的f 一导数，仍记为f ( z ) = a 定义2 4 映象f ：dc 彤一尼“在d ocd 上是荷尔德( h o l d e r ) 连续的，如 果存在常数l 0 及p ( 0 ，l 】，使得对一切z ，y d ，有 l i f ( x ) 一f ( y ) i lsl i i x 一 9 特别地，如果p = 1 ，则称f 在d 0 上是李普希茨( l i p s c h i t z ) 连续的 5 蕾鹤：不耪确耘牛援法蜂收敛性 t t f ( 。+ 固一f 0 ) 一f ( 。) d l 等l d 8 2 ：i ( x - t - e “k y - - x “) ) 、 f 国) 一f 忙) 2 l 主差二! 篓二：j b 。) 这里，囊( 。j 是f 净) 一涵( 2 ) ，点( 。) ，蠡) r 的第i 个分量函数， 定理2 8 设f ：dc 舻一舻在凸集d ocd 上巍续可微。则对任意的 z ，钍， d o ，有 | f 扣) 一f ( ”) 一f 7 扛) 扣一v ) f l 董 s u p 】i f 7 0 + t ( u 一”) ) 一f ，( z ) i i 一” 0 o 0 ，使得v u ，u d ，当m 舣删“一删，怕一x l l se 蹿，骞 n i f u 一 i i i | f ( 缸) 一f 扣) | | p f 仳一”m 建疆2 。1 2 。( v o nn e u m a n n l 瑾) 强设e j ”，i r ”。“是单位矩簿，羚| l 是满足j i i i 一1 的相容矩阵范数如果0 e 0 1 ，则口一e ) 非奇异，且 ( 卜司一= e ir ( z - 妒冬南 知荩a 菲专劳，| | a “p 一脚i 1 ，则b 菲奇异，丑 b = ( j a - 1 b ) 。a _ i t b - 1 i i 可 2 2 迭代法的一般原理 设f ：d c j 一舻，考虑方程 f ( z ) = 0( 2 1 ) 若存在矿d ，使得f ( 矿) = 0 ，则称矿是方程的解用迭代法求方程( 2 1 ) 的解，先将 ( 2 。1 ) 纯为等羚静方程； z g ( x 1( 2 2 ) 这里映象g ：dc 彤一彤方程( 2 2 ) 的解( 即矿一g ( z ) ) 称为映象g 的不动 惹嚣霓霆遂代法袁瑟方程( 2 。1 ) ，裁是密( 2 2 ) 申浃象g 缒不动京。 7 王伟：不精确拟牛顿法的收敛性 定理2 1 3 若g ：dc 舻一口为有界闭集d ocd 上的严格非膨胀映象， c ( d o ) cd ，则g 在d o 内有唯一不动点 定理2 1 4 ( b r o u w e r 不动点定理) 设g ：dcj 一月2 在有界闭凸集d ocd 上连续，且g ( d o ) cd o ，则g 在d o 中至少有一个不动点 用迭代法求解方程( 2 1 ) ，通常构造如下迭代序列： 矿“= a ( x 2 ) ，k = 0 ，1 ，2 t ( 2 3 ) 对于( 2 3 ) 的迭代形式，g 可以有各种表示方式g 可能只依赖于f 及f 如果g 不依赖于迭代步数k ，且妒“只依赖于扩，则称迭代( 2 3 ) 为单步定常迭代如果映 象g 还依赖于迭代步数k ，则迭代形式可表示为。+ 1 = c ( z ) ，k = 0 ，1 ，2 ，并称之 为单步非定常迭代有时得到新的近似z 1 除依赖于x 。外，还依赖于前几次迭代的信 息这时的迭代为多步迭代通常称g 或g 为迭代函数用不同的方法构造出不同 的迭代函数可得到不同的迭代法设g ：dc 彤一酽，如果一个迭代法得到的序列 一i k = 0 ，1 ，2 ) cd ，则称迭代序列是适定的因为 舻) 适定时，g 在其上才有意 义，因此对任一迭代法，适定性是起码的要求若矿dc 即是方程( 2 1 ) 的解，且序 列 矿i k = 0 ，1 ，2 ) c d ，满足。l i mx = 矿或i i m 忙。一矿l i = 0 ，则称迭代序列收敛 于矿 定义2 1 5 设f ：dcr - 一p ，矿d 是方程f ( z ) = 0 的一个解若存在矿的 一个邻域scd ，对任何初始近似3 7 0 d ( 对于m 步迭代法，初值为z o ，z 1 ，x r n _ 1 s ) ，迭代序列( 砂i k = 0 ，1 ，2 ) 总是适定的且收敛于矿，则称矿是迭代序列的吸引 点， 定理2 1 6 设矿是方程偿纠的解，若存在一个开球 s = s ( 。+ ，5 ) = 。| | i z z + 0 o ) c d 和常数口( o ，1 ) ，使得对一切z s ，有 i l g ( 。) 一g ( 茹+ ) | | s 血i i 。一z + l i ， 则对任意。o d ，矿是迭代序列偿圳的吸引点 定理2 1 7 ( 奥斯特洛夫斯基( o s t r o w s k i ) 定理) 设映象g ：dcr “一届1 有一个不动点。+ ei n t d ，且在矿处f 一可导，g ( 矿) 的 谱半径 p ( a 7 ( ) ) = 口 0 ， 使得当k 时有 。+ 1 一嚣+ 8 0 1 8 妒一。+ 8 ”， 则称序列 护) 至少p 阶收敛当p 一1 时( 这时必须有0 0 ，使得 。( 矿) d ，且对任意。o m ( 矿) ，算法，j 所 产生粒，轰列 是适定静昱超线性收敛于矿若遵存在l 0 ，使得 i f ( 。) 一f ，( 。+ ) 9 lj ! z 一茹。歉v x 母( g + ) 则序列 妒 至少是二阶收敛的 k a n e o r o v i c h l l q 绩凄了n e w t o n 法戆努个萋名跨收敛蝗定理。k a n t o r o d c h 意理 与定理3 1 的主磐区别题它没有假设非线性方程组( 3 1 ) 的解矿的存在性 定理3 。2 。设f ：d c 帮一舻荻前始近似轳满足下列务铮： 俐 f ，扫。) r 1 存在，且 l f 一( 扩) 】。”， f | 【0 0 ) r 1 f ( x o ) i r l ； 圆在x 0 秘领域( 轳，5 ) 璁，罗盘) 旁在暑满足l i p s c h i t z 条镑： f i f ( x ) 一f 7 ( v ) | | 7 j l 茹一玑魄，y n ( x 。， 并且 p = 筘目7 妄， d 竿吼 群方程缎f 和) 一0 于( 护，0 态有解矿，菇算法3 1 产生静序列 茹2 收敛于矿，并有 估计式 胁* 删差 盼 j = o 其中 一= 暑1 譬。+ 、l 一2 尹 1 2 太连理l 太学瑚士学位娩文 k a n t o r o v i c h 定理的优点是不需要假设方程缀( 3 1 ) 的解矿的存在性有关k a n t o r o v i c h 寇理的改避秘稚广，戳及n e w t o w 法盼洪差依诗，计算复条隆分辑，可参随史献 l ，8 ，1 2 ， 1 3 ，1 4 1 定瑾3 1 裘露，在一定条捧- f ，n e w t o n 法楚二酚收敛熬然褥，农n e w t o n 法鳃每 多遮代中酃蚕汁算j a c o b i 缒阵尸( 妒) 并求解n e w t o n 方程( 3 1 ) ，当较大或f ( 。) 较 笺杂嚣孛，n e w t o n 法静计算攮将会缀大+ 舅辨，巍j a c o b i 矩黪f 妒鸯异或嚣基f 孛黠， n e w t o n 法潜要求辩令奇浑袭蒡 ：条 争懿线链方程缌，扶嚣会菇鬣数赣上浆鑫滚 3 。2 不精确n e w t o n 法 为了克服n e w t o n 法计算擞大的不足，d e m b o ，b i 8 e i 】s t a t 和s t e i h a u g m 于1 9 8 2 年摄 蹬了不精确n e w t o n 法不精确n e w t o n 法就蹙在n e w t o n 法盼每步迭代申只对n e w t o n 方程进行非精确求解不精确n e w t o n 法实质上是一类内外遮代算法，其外迭代为经典 n e w 吨o w 法，而箕隐迭代掰冒采甭任何髓够准确稀有效蟪辩n e w t o n 方程斑戮求解盼壤 性迭代法不精确n e w t o n 法蕊降低tn e w t o n 法的计算燕，叉能保持n e w t o n 法酌局部 二阶浆鼓堍疆，是求鹈夫靛模黎缓骸 霹繇翡一释留实督符静露觳方法。 算法3 2 ( 苇精确n e w t o n 算法) ： 1 络定新磕扩口 2 对千k = 0 ，1 ，一，直到 收敛， 2 1 选取( 0 ，1 ) - 2 2 通过对n e w t o n 方程韩精磕求睇而褥剜z ，满惹 | | f ( 妒) 十f ( 妒) 妒s , l l f ( z s l l 。磐。9 2 3 。令z 自十1 ：= = z o + 窖2 袭上露弱舞法中。鼗察】稼魄为第步遗健懿强剃瑗，a z o 努苓犍臻n e w t o n 步， 不等式f 3 4 ) 籍称佟不精确n e w t o n 条捧。 农不攮确n e w t o n 法的每步迭代巾，只对n e w t o n 方程进铡# 携辘求解。耀为f ( x ) + f ，( 妒) a z o 凝燕f ( z ) 瓣是帮筏洼摸懑，又是n e w t o n 方程鲍残爨，所以冁鳇大拳在本 质上刻划出了对n e w t o n 方程求解的精确程度特别，如果选取所有的执i0 ，则不精确 n e w t o n 法赣逐化为n e w t o n 法为以下讨论方便，我船g l 入下面瓣概念 定义3 3 称o “建l i f l i 的一个稳定点，是指对于任憩s 冗”，都有 | | f ( 。) | | 曼| | f ( 。) 十f ( 。) s 融 我们将| | f 的稳寇点酶金簿记为s f ( t l f i i ) ( s t a t i o n a r yp o i n t so fi i f i i ) 容努验证， 王伟：不精确拟牛顿法的收敛性 s p ( i i f i i ) 3 z i f ( 。) = o ) u z i f 7 ( z ) = o ) 定理3 4 设 a = m a x 训f 7 ( 矿) j j + 南，2 9 ， u 其中卢= i i f ( z + ) - 1 n 则对于l l y 一j 充分小，不等式 1 l l y z + | | l i f ( 可) | | o ij 掣一z + | | u 成立 不精确n e w t o n 步一般是由f ，( 矿) ，f ( z ) ，m 以及所采用的范数决定的关于不精确 n e w t o n 步的存在性，易知以下的结论成立【1 5 】： ( 1 ) 对于任意的仉f 0 ，1 ) ，都存在不精确步的充要条件是f ( 一) n ( f 7 ( 矿) ) ，这里 r ( ( 一) ) 表示算子f 7 ( ) 的值域； ( 2 ) 对于任意的讯f 0 ，1 ) ，都不存在不精确步的充要条件是f ( z ) 0 ，并且扩 s p ( 0 f 1 1 ) 与上面的结论( 2 ) 等价的一个说法是，对某个讯 0 ，1 ) ，存在不精确n e w t o n 步的 充要条件是f ( x ) = 0 或一gs p ( h p i i ) 如果采用的是2 _ 范数，则舻gs p ( i i f i i ) 的充 要条件是f ( 一) 上r ( f 7 ( 一) ) ，因而对某个啦【0 ，1 ) ，存在不精确n e w t o n 步的充要条件 是f ( 矿) = 0 或f ( 一) 乒r ( f 0 ) ) 值得指出的是，在不精确n e w t o n 法中，我们对n e w t o n 方程采用近似求解策略是 合理的在n e w t o n 法的迭代中，如果一离方程组( 3 1 ) 的解较远时，由n e w t o n 法确 定的线性模型p ( x ) + f 7 ( 矿) 乳与f ( 一+ 乳) 的差距可能会很大因而，此时精确求解 n e w t o n 方程可能会得不偿失一方面，精确求解n e w t o n 方程会造成大量计算上的浪 费；另一方面，计算所得到的n e w t o n 步可能无助于整个迭代序列的收敛，甚至导致迭代 发生中断反之，如果对n e w t o n 方程非精确求解而得到一个不精确n e w t o n 步船，则此时 的线性模型f ( x ) + f 7x 2 ) 鼽与f ( 一+ s k ) 可能会吻合地较好这样既节省了计算量， 又有和于整个序列的收敛在不精确n e w t o n 法中，如果迭代点舻离非线性方程组( 3 1 ) 的解较远时，也不宜选用过小的强制项选用过小的强制项就有可能导致o v e r s o l v l n g 现 象：亦即对于n e w t o n 方程的求解达到适当的精度时， 0 f ( 妒) 0 就会得到最好的下降， 而对n e w t o n 方程进一步精确地求解则可能会对| j f ( 矿) | | 的下降起不到任何好的作用， 更有甚者，还可能导致迭代中断f 另外，定理( 3 1 ) 只保证了当初值x o 充分靠近非线性方程组( 31 ) 的解矿时， n e w t o n 法是二阶收敛的换句话说，此时迭代过程中所得到的n e w t o n 步长才都是好的 步长但是，当迭代点。o 离矿较远时，定理就无法保证n e w t o n 步是好的步长了既 1 4 太连理工大学硕士学位论文 然如此，此时对n e w t o n 方程进行非精确求解就是很自然的了 不猿礁n e w t o n 浚荦羹n e w t o n 法一襻，遣燕禺帮收敛戆。苓跨薅n e w t o n 法懿缓睦 收敛性阐述如下【q ： 定理3 5 谩f ：拶一j 在哥凸袋dc 魏“中连续可擞，密在d ，f ( 矿) = 0 ， 且f ( 矿) 非奇异，并设0 。 t 1 是绔定的常数，如果不精确n e w t o n 法中的强 制序列 氇 滏足0 钕_ - 5 霸。 t 0 ，使得当o o 域( 矿) 时，不精 确n e w t o n 法产生的迭代序列f 妒，收敛到矿，并且 | | 。+ 1 一。“l kst l l x 。一。4 | | 。 ( 3 5 ) 其中8y 艮= | | f ( 扩妇” 上述定理表明，如果不精确n e w t o n 法中的强制序捌 啦 一致地小于1 ，员i 此方法 是局鞠；线性收敛的奖于不精确n e w t o n 法的收效速度，我们还肖如下定理吼 定理3 6 设f ：舻一瘁2 在开凸策dcj 护中连袋可微，存在矿d ，f ( 矿) = 0 ， 且f ( 矿) 非帑异，如幕由不精确n e w t o w 法产血的序列和) 收敛于矿，则 口，当钕一0 醇， 矿) 怒线往收效于妒j 俐当仉= o ( 1 f ( x k ) 1 1 ) 且( o ) 收矿点l i p s c h i t z 连续时，( 茁。) 基阶收敛千矿 上述定毽嶷嗳，幂猿确n e w t o n 法憋蔽簸速淡取决予强裁彦穰 讯 静选取 朔| l ， 当讯= o ( 1 l f ( x ) j i ) 时，不精确n e w t o n 法也能够达到n e w t o n 汝的二阶收敛速度 液臻不耩魂n e w t o n 法建黪实瑟嚣雾封，鸯嚣令善娶鳇闻疆游要舞决；一个怒魏留 选取强制序列 仉) ，另个是用什么方法对n e w t o n 方稷进行非精确求解强制序列对 于不耩确n e w t o n 法熟收敛控鹱秘数毽霉亏势起饕至关重爨戆终是它不仅影响着冀法秘 计算效率，而融还影响着算法的准确性和强健性定理( 3 5 ) 提供丁选取强制序列的一个 原则：只有强铡痔列一致地小予1 ，才熊保证不耩确n e w t o n 法产熊的选代序列是髑部收 敛的因而在舆体实施时，一般总是预先给定强莉序列的一个上辨。 t ，然蔚荐在 迭代道程中选取强制顼礁s 。强制序列的最简单的选取方法就是选取常数序列然 而，簧选取一令能够使得不精硫n e w t o n 法酶整体诗算效率达羹| 簸高静强耩序列，整十 分困难的尤其是在实际应用中，由于无法判断当前迭代点与真解之间的距离，因此， 往往缀难确定警蘸强裁凌懿大小 到目前为止，还没有一种最优的选取强制序列的策略在实际计算中，许多研究者 懿替给毒过一麓巽簿选敬方式兄争吴霉鼗表缝懿选致方式魏- f ： 1 c a i ，g r o p p ，k e y s 和t i d r i r i ”】选取仉= 1 0 2 。b r o w n 稳s a a d 1 选取魄= 意 1 5 王伟r 不精确拟牛顿法的收敛性 3 d e m b o 和8 t e i h a u g 1 q 采用m i n 去，i i f ( x ) 怫 4 e i s e n s t a t 和w a l k e r 2 q 给出了仇的两种选取方式； ( a ) 给定伽【0 ，1 ) ，选取 栌避生蒜竿幽，z ，一 或 仉= 避堕等幕簪剑，。， ( b ) 给定1 ( 0 ，1 1 ，u ( 1 ，2 1 ，啦 0 ，1 ) ，选取 仉刊器瑞h 皓舭，一 上面的几种关于强制序列的选取方式中，e i s e a s t a t 和w a l k e r 所给出的两种方式的 影响最大，且目前已被广泛采用其中选取方式( a ) 直接反映了上一次迭代中f ( z ) 与其 局部线性模型的吻合程度。选取方式( b ) 反映了从。“1 到一时l f f ( 动i | 的下降程度 在适当的条件下，e i s e n s t a t 和w a l k e r 证明了当迭代初值。o 充分靠近非线性方程组的 解矿时，采用上面的选择方式( a ) 或( b ) 所对应的不精确n e w t o n 法都是适定的，且迭 代点列 z 。) 收敛于矿对于选取方式( a ) ， 一) 是q - 超线性收敛的；对于选取方式( b ) ， 当7 k l l f ( x 。) l l ，翻执行c m r f 菇遥伐： ( b 1 ) m = m 十1 渤) 诗薯罗( 岔勺，箨执嚣a r n o l d i 过蛙； 咖一谭( f 协) ) ，i 一1 ，2 ，m + l f p ) 一越。豫 h 。+ 1 。= i 坼。+ 1m m + 12 l a m + l ，m 设露r ( ”+ 1 ) 。m 为上h e s s e n b e r g 阵，其非零元素为 氇j ，# = 1 ，一，j + 1 ，j 一1 ，m ( 6 3 ) 求解最小二乘问邂。r a 胛i n0 觑e l 一蠢r m y l l ，得列解向量r ”。 ( 6 4 ) 令8 r ? 8 = i i 晟e l 一日k 9 。辨 ( c ) 令i = b ，讹，一，0 j 。”并彤成s 斧= s 2 + 0 臀。 ( d ) 今晚= s 2 , 3 g 蠹+ 1 = + 最 算法3 , 3 中步2 2 是运用g m r e s 方法近似求解第k 个n e w t o n 方程的过程，其作 爱是诗募出一个合适懿不耱魂n e w t o n 步。在步( b ) 孛，a r n o l d i 过程熙子拇造k r y l o v 子空间墨。的标准正炭基u ，地，这里 弼。：一s 竹 蝮，f ( z 。) 罐，( f ( z 。) ) 2 r 2 ，( ，( 扩) ) m - - 1 r 2 每个m 对应一次g m r e s 迭筏，每次g m r e s 迭代孛鄂震要求壤最枣= 浆海运 m ￥+ m u f s + f | ( 删 1 7 王焦；不壤魂攒譬顿法妁凝敛佳 豳为 数菠枣二黎趣题( 3 , 6 ) 可转纯为 如) 一+ l 焉； f r a 舻i n 慨8 l h , n y f r _ 这就魁在算法3 3 口3 ，2 4 1 中给出的形式步( b ) 执行完毕以后，不精确n e w t o n 条件 褥裂潢是，紧接饕便峦k r y l o v 子空阕的标准正交基形成不糖确步痞( 步( c ) 程( ) ，算 法执行到此，就得湖下一个非线性送代点z 1 = 护十靠 在理论上，g m r e s 方法能够在最多 步迭代内计算出线性方程组鳓精确勰但 在实际计算中，由于舍入误箍的影响，情况并不总是遮祥事实上，由予舍入误差的积 累，通过a r n o l d i 过程计算出的魄的正交性将会很快失去因此，为了计算出一个满意 秘多长，逶常需要飘行授多淡g m r e s 遥代然磊，魏采m 禳大，k r y l o v 予燮阉秘基 的存储将会是一个问题( 是n 行m 列矩阵，而通常n 比较大) 因此，谯实际计 雾孛，最夫龛诤静m 逶常雳一争事筑给定黪藏婺数纸一来叠g 嚣疆爨蓿经过。步 g m r e s 遗代以后，残量范数i 卜? i i 仍然不能充分小，则需鼹采用璧启动的g m r e s 方法，凌嚣为g m r e s ( m ) 方法陶g m r e s ( m ) 方法藩不是乏处是炙法保送速代事裂 的收敛性，因而g m r e s ( m ) 方法在一定程度上会降低g m r e s 方法的强健性而且， g m r e s ( m ) 方法懿牧敛速度可能会缀慢， 1 8 大连理i 大学硕士学位论文 4 拟n e w t o n 法 4 1 拟n e w t o n 法 n e w t o n 法的显著优点是收敛速度快，其不足是在迭代的每一步均需计算j a c o b i 矩 阵并求解n e w t o n 方程当j a c o b i 矩阵难以形成，或者当问题的规模较大时， n e w t o n 法的计算代价就很昂贵拟n e w t o n 法是六十年代发展起来的求解非线性方程组的有效 方法它克服了n e w t o n 法需要求导、求逆的缺点，而把j a c o b i 矩阵f 7 ( 一) 简化为形如 b k + l = b k + b k ，k = 1 ，2 的矩阵递推关系式，这样不仅简化了计算过程，而且还能保证算法的超线性收敛速度所 以拟n e w t o n 方法是近几十年来求解非线性方程组和最优化问题的最重要的方法之一 显然我们希望鼠+ - 是j a c o b i 矩阵f ，( 一) 的某种近似，由于 f ( x ) y 其中 8 k = 矿+ 1 一z ，y = f ( x 。+ 1 ) 一f ( x ) 故我们要求 b k + l s k = y k( 4 1 ) 式( 4 1 ) 称为拟n e w t o n 方程它要求矩阵风+ i 对z 1 ，具有差商性质一般的拟 n e w t o n 迭代算法为： f z 抖1 = 一一巧1 f ( 一) b k + 1 ( 茹+ 1 一。2 ) = f ( z + 1 ) 一f ( z ) ，k = 0 ，1 ，t t ( 4 2 ) i 鼠+ 1 = b k + a b k ， 其中鼠是秩