（应用数学专业论文）不精确newtonlike方法及其应用.pdf

北方t 业大学硕十学位论文 摘要 非线性方程组的数值解法在实际中有广泛的应用，特别是在各种非线性问 题的科学计算中更显出它的重要性而且，随着计算机的广泛应用，有更多的 领域涉及到非线性方程组的求解问题，例如，动力系统，非线性有限元问题， 非线性力学问题，还有非线性最优化与非线性规划问题等因此，研究非线性 方程组的解法就具有重要的实际意义由于非线性方程组的复杂性，在解法上 除了极特殊的非线性方程组外，直接法几乎是不能使用的，这需借助于迭代法 来求解 尽管牛顿迭代法是一种经典的求解非线性方程组的方法，但是在牛顿迭代 法中每步迭代都需要计算雅可比矩阵及其逆或解线性的牛顿方程组，当自变量 个数比较多时，其计算量是非常大的，而且当牛顿迭代法中的，( 以) 奇异或病 态时，迭代过程无法进行或虽能进行但难以得到较好的数值解特别是当x 。远 离方程组的解工时，用直接消去法高精度地求解牛顿方程组得到的迭代点，往 往有不小的盲目性，有时甚至无法迭代，得不到方程组的解 本论文在牛顿法研究的基础上，主要探讨了求解非线性方程组的牛顿类方 法和不精确牛顿类方法及其收敛性在理论上，研究了它们的局部收敛性和半 局部收敛性，并且在合理的假设下得到了一些新的结果同时，在适当的条件 下给出了不精确牛顿法半局部收敛性的康托洛维奇型定理及证明在应用方 面，除了用这两种方法直接求解非线性方程组外，还将它们应用于无约束最优 化和非线性偏微分方程的数值求解中数值实验结果表明了这两种方法的必要 性和可行性另外，对牛顿法的一个变形迭代公式也做了局部与半局部收敛性 分析，证明了它是三阶收敛的，并给出数值例子 关键词：非线性方程组；不精确牛顿类法；局部收敛性；半局部收敛性 北方工业大学硕十学位论文 l n e x a c tn e w t o n ii k em e t h o da n di t sa p p ii c a t i o n a b s t r a c t t h en u m e r i c a lm e t h o df o rs o l v i n gt h en o n l i n e a re q u a t i o ns y s t e m si sw i d e l y u s e di np r a c t i c e i t si m p o r t a n c ei se s p e c i a l l ys h o w ni nt h es c i e n t i f i cc o m p u t a t i o no f t h ed i v e r s i f i e dn o n l i n e a rp r o b l e m s m o r e o v e r ，w h i l ec o m p u t e r sa r ew i d e l yu s e di n v a r i o u sf i e l d s ，n o n l i n e a re q u a t i o ns y s t e m sa r ed e a l tw i t hi nm o r ea n dm o r ef i e l d s ， s u c ha st h ed y n a m i cs y s t e m s ，n o n l i n e a rf i n i t ee l e m e n t s ，t h en o n l i n e a rd y n a m i c sa n d t h en o n l i n e a ro p t i m i z a t i o na n dt h en o n l i n e a rp r o g r a m m i n g a sar e s u l t ，i ti so f p r a c t i c a ls i g n i f i c a n c et op r o b ei n t ot h es o l u t i o n sf o rt h en o n l i n e a re q u a t i o ns y s t e m s d u et ot h ec o m p l e x i t yo ft h en o n l i n e a re q u a t i o ns y s t e m s ，e x c e p ts o m ee x t r e m e l y s p e c i a ln o n l i n e a re q u a t i o ns y s t e m s ，i t e r a t i o nm e t h o di n s t e a do fd i r e c tm e t h o d ， w h i c hc a l lh a r d l yb eu s e df o rs u c he q u a t i o ns y s t e m s ，s h o u l db ea d o p t e d a l t h o u 曲n e w t o n si t e r a t i o ni sac l a s s i c a lm e t h o df o rs o l v i n gt h en o n l i n e a r e q u a t i o ns y s t e m s ，e a c hs t e po fi t e r a t i o ni nt h en e w t o nm e t h o di n v o l v e sc o m p u t a t i o n o ft h ej a c o b i a nm a t r i xo ri t si n v e r s i o na sw e l la st h es o l u t i o no ft h el i n e a re q u a t i o n s y s t e m s w h e nt h e r ea r ec o m p a r a t i v e l ym a n yv a r i a b l e s ，h u g ea m o u n t so fc a l c u l a t i o n a r en e e d e d b e s i d e s ，w h e nt h ef ( 坼) i nt h en e w t o n si t e r a t i o ni ss i n g u l a ro ri l l - c o n d i t i o n e d ，t h ei t e r a t i o np r o c e s sw i l ln o tw o r ko rh a r d l yw o r k e s p e c i a l l y ，w h e n 石l i sf a rf r o mt h es o l u t i o no f 了o ft h el i n e a re q u a t i o ns y s t e m s ，t h ei t e r a t i o n p o i n t sa c c u r a t e l yf o u n dw i t ht h ed i r e c te l i m i n a t i o nm e t h o dt e n dt ob eh e l p l e s sf o r g e t t i n gt h es o l u t i o no ft h en e w t o ne q u a t i o n s b a s e do nt h en e w t o nm e t h o d ，t h et h e s i sm a i n l yp r o b e si n t ot h en e w t o n l i k e m e t h o da n di n e x a c tn e w t o n - l i k em e t h o de m p l o y e df o rs o l v i n gt h en o n l i n e a r e q u a t i o ns y s t e m sa n dt h et w om e t h o d s c o n v e r g e n c e t h e o r e t i c a l l y , t h et h e s i s s m d i c st h e i rl o c a lc o n v e r g e n c ea n ds e m i l o c a lc o n v e r g e n c ea n dg e t ss o m en e w c o n c l u s i o n su n d e rt h er e a s o n a b l ea s s u m p t i o n s m e a n w h i l e ，u n d e rt h ea p p r o p r i a t e c o n d i t i o n , w ep r o v ek a n t o r v i c h - t y p et h e o r e mo nt h es e m i l o c a lc o n v e r g e n c eo ft h e i n e x a c tn e w t o nm e t h o di nt h ep a p e r ，i nt e r m so fa p p l i c a t i o n ，t h et w om e t h o d sa r e n o to n l yd i r e c t l ya p p l i e df o rs o l v i n gt h en o n l i n e a re q u a t i o ns y s t e m sb u ta l s of o rt h e n u m e r i c a ls o l u t i o n so ft h eu n c o n s t r a i n e do p t i m i z a t i o na n dn o n l i n e a r p a r t i a l 2 北方工业大学硕士学位论文 d i f f e r e n t i a le q u a t i o n s t h er e s u l t so ft h en u m e r i c a le x p e r i m e n t ss h o wt h en e c e s s i t y a n df e a s i b i l i t yo ft h e s et w om e t h o d s i na d d i t i o n ，w ed i s c u s sav a r i a n to ft h en e w t o n m e t h o di nt e r m so fi t sl o c a la n ds e m i l o c a lc o n v e r g e n c e ，s u c hv a r i a n ti sp r o v e dt ob e t h i r d - o r d e rc o n v e r g e n ta n dn u m e r i c a le x a m p l e sa r eg i v e n k e y w o r d s ：n o n l i n e a re q u a t i o ns y s t e m s ；i n e x a c tn e w t o n l i k em e t h o d ；l o c a l c o n v e r g e n c e ；s e m i l o c a lc o n v e r g e n c e 3 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得j e 友王些太堂或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名多丝劾签字日期：，7 年稠哆日 学位论文版权使用授权书 本学位论文作者完全了解韭左王些塞堂有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权j e 友王些太堂可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：弦幢；磊 签字日期刁铴6 月妒 学位论文作者毕业后去向： 工作单位： 通讯地址； 导师签名：关p 叙 签字日期：摊6 月) 日 电话； 邮编： 北t y y 业大学硕士学位论文 i绪论 科学计算与工程应用中常常需要求解下列菲线性方程组 f ( x ) = 0 ，( 1 0 ) f = o r 。以9 t o 以) 2 ，x 2 0 l ，：，x 。y ，0 2 ( o o ，o y 这里f 表示定义在开域d c r4 上的非线性映射，也称为向量值函数或多值函 数，简记为f ：dc r4 r 1 ，它一般是连续可微的若存在x d ，使得 ，o + ) = 0 ，则称工为方程( 1 0 ) 的解 计算数学对于许多实际问题需要采用数值计算方法求解，有的问题需要转 化成非线性方程组来得到解决，而且，随着计算机的广泛应用，有更多的领域 涉及到求解形如( 1 o ) 的非线性方程组的问题例如，动力系统，非线性有限 元问题，弹塑性问题及其它非线性力学问题，还有非线性最优化与非线性规划 闻题等其中相当多的非线性方程组是由菲线性偏微分方程或常微分方程离散 化后得到的对含有非线性项的微分方程，无论是用差分方法还是用有限元方 法，一般地来说离散化后得到的方程组都是非线性方程组因此研究方程组 ( 1 0 ) 的解法就具有重要的实际意义非线性方程组的求解问题一直是人们关 心的问题，在解法上除极特殊的非线性方程组外，直接法几乎是不能使用的， 这需借助于迭代法来求解，也就是从给定的初始近似值开始，通过构造一个迭 代序列，使之能够收敛到方程的解而这其中牛顿迭代法是一种很重要的方法 1 1 牛顿法 由于非线性方程组的复杂性，一般情况是很难求出其解析解( 或精确解) 的，往往只能求其数值解( 或近似解) 通常采用的数值算法是如下的牛顿法 【”，即 五“= x k - f 7 瓴) 1 f ( x d ， k = 0 , 1 ，2 ， 或者， 慨f ( x d s 。乜= - f ( x d , 吼l ，2 ， 【 ( 1 2 ) 北方r t 业大学硕十学位论文 其中是初始值，扛。 称为n e w t o n 迭代序列，o 。) 是f 的雅可比( j a c o b i ) 矩阵，它一般为大型稀疏矩阵牛顿法( 1 1 ) 可以说是非线性方程组数值解法中 经典的算法从一维几何角度来说，t + 是函数f f x ) 在点( x k ，f ( t ) ) 的切线 y 一，( t ) = f ( x , x x - x d 与x 轴的交点与( 1 1 ) 式等价的( 1 2 ) 式的第二式是 个线性方程组或称之为牛顿方程组，它避免了求雅可比矩阵的逆，但得求解此 方程组牛顿法的优点在于若给定相当好的初值，它能够快速收敛到方程的解 ( 在适当的条件下) 由于它收敛快，因此直到现在它仍然是求解非线性方程组 的一个重要方法，而很多新的算法都是针对牛顿法存在的某些不足进行改进得 到的因此，对牛顿法进行深入研究不仅在实际计算上有重要作用，而且在理 论上也是很有意义的 牛顿法收敛性的研究一般分为局部收敛性和半局部收敛性已有很多文献 研究了牛顿迭代法的收敛性和误差估计关于局部收敛性定理，早在1 8 2 9 年 c a u c h y 研究了n = l 的一维情形；r u n g e 于1 8 9 9 年给出了在r ”条件下的定理； 1 9 1 6 年f i n e 第一次在r ”中不假定方程组解存在的情况下，证明了牛顿法的半 局部收敛性；1 9 3 6 年o s t r o w s k i 独立提出新的证明并讨论了误差估计，随后， w i l l e r s 于1 9 3 8 年也证明了类似的收敛性定理他们的证明虽然只针对以= 2 及n = 3 ，但通常可直接推广到一般的以康托洛维奇于1 9 4 8 年在b a n a c h 空间 中给出牛顿法著名的半局部收敛性定理，不久以后，又提出了优界原理的新证 法o r t e g a 2 和r h e i n b o l d t 3 1 于1 9 6 8 年用优界原理给出了牛顿法半局部收敛 性证明7 0 年代以后，很多学者对牛顿法误差估计及收敛性进行了研究，并绘 出了一些新的结果1 4 ，训牛顿法思想直观自然，从微分的角度来说，是在局部 以直代曲伴随着牛顿法理论的发展与实际应用，人们围绕牛顿法提出了各种 改进的牛顿算法，来减少计算量以提高运算效率其中有简化牛顿法，它以固 定的f 7 0 。) 代替f 7 0 。) ；有拟牛顿法，它的基本思想是用差商代替导数，其中 以b r o y d e n 提出的算法为代表，文 6 1 给出了b r o y d e n 法的半局部收敛性定理， 这些定理在理论上都是很有意义的；还有牛顿型法，等等 - 2 北方工业大学硕士学位论文 1 2 不精确牛顿法 尽管牛顿法有收敛速度快的优点，但是在牛顿迭代法中每步迭代都需要计 算雅可比矩阵及其逆或解线性方程组( 1 2 ) z ，当自变量个数比较多时，其计算 量是非常大的而对许多实际问题又需要快速求解，特别是当j 。远离方程组的 解x 时，用直接消去法高精度地求解线性方程组( 1 2 ) z 得到的n e w t o n 迭代 点，往往有不小的盲目性，有时甚至无法求解而且，由数值分析的理论可 知，当线性方程组的系数为大型的稀疏矩阵时，用高斯消去法等直接法来求解 它事倍功半因而，从某种意义上来说，牛顿法的应用受到了一定的限制八 十年代初开始，d e m b o 等人讨论了一类改进的n e w t o n 方法，试图克服上述缺 陷算法的基本思想是，每一步n e w t o n 迭代，不需要精确而是用迭代法近似 地求解线性方程组( 1 2 ) ：，由此而衍生出的一类方法称为不精确牛顿法： 做弘班气，ous琉ii盹)20,i2f(*ask 一， ( 1 3 ) 【= 一，( 五) + 气，恢s 琉f ( 气) i l ， “一 ” 其中仇f o ，1 ) 为一给定的常数控制序列文献l 7 j 中证明了该方法在适当的范数 下局部收敛不精确牛顿法在保持n e w t o n 法快速收敛性质的前提下，每一步 迭代的精度能够得到较好的控制，对于迭代过程中控制序列的选择，人们也进 行了一些必要的研究【引实现不精确牛顿法的算法较多，用某种迭代法求解线 性方程组( i 2 ) z ，若设定停机要求为相对残差小于吼，则都应属于此类算法， 例如，n e w t o n - s e i d e l ，n e w t o n - s o r ，n e w t o n - g m r e s 法，等等 不精确牛顿法本质上是一种双层迭代法，由外层迭代和内层迭代组成钋 层迭代就是经典的牛顿法，内层迭代过去常用求解线性方程组的一些经典的迭 代法，如j a c o b i 迭代、g u a s s - s e i d e l 迭代、s o r 迭代等来求解牛顿方程组 ( 1 2 ) z 而近2 0 年来，随着k r y l o v 子空间方法的迅速发展，这类方法特别是 g m r e s 方法【9 】及其循环形式的g m r e s ( m ) 被广泛用来求解线性方程组目前主要 是以g m r e s 方法为代表的k r y l o v 子空间方法，代替牛顿法中的直接法( 高斯 消去法) 对线性方程组进行近似求解因此这类方法又被称n e w t o n - g m r e s 方 法，或n e w t o n k r y l o v 方法 近期，浙江大学的黄正达【l o 】给出了b a n a c h 空间上不精确牛顿法的二阶收 敛性结果以及相应的误差估计清华大学的白峰杉等人研究了对称不定问题的 3 北方工业大学硕士- 学- 6 7 论文 不精确牛顿法【l ”，清华大学的唐云等人提出了一种分块加权平均的不精确牛顿 法【i “，以及用不完全l u 分解作为预处理的不精确方法，而且，分别把这些方 法应用到了大型电力系统的潮流计算中还有国外的，如p e t e rn b r o w n ， p s v a s s i l e v s k i 等提出了多重网格不精确牛顿方法 1 3 1 ，并把它应用到求解二 阶非线性偏微分方程中同时，j e p a s c i a k ，p s v a s s i l e v s k i 等人给出了修 正不精确牛顿法并证明其收敛性不依赖于网格 1 4 l ，也将此方法应用到了二阶非 线性偏微分方程中这些理论结果和实际应用都是不精确牛顿法的新发展 本论文将在已有的基础上，进一步讨论非线性方程组的迭代解法，探讨牛 顿类( n e w t o n 1 i k e ) 方法、不精确牛顿类( n e w t o n 1 i k e ) 方法收敛性的新结果，包 括局部收敛性和半局部收敛性分析并将其付诸于求解非线性方程组、非线性 偏微分方程以及无约束最优化等问题的实际应用中全文共分为七章，具体安 排如下：第一章绪论；第二章预备知识，是对与本论文有关的一些多元函数微 分学基本概念和非线性方程组迭代知识的简单介绍；第三章介绍不精确牛顿法 的半局部收敛性，同时，对牛顿法的误差估计式之一给出了新的证法；第四章 分析了n e w t o n 1 i k e 方法的收敛性，其中有局部线性收敛、局部超线性收敛和 半局部收敛，并给出在非线性偏微分方程和最优化等方面的数值应用；第五章 是不精确n e w t o n 1 i k e 方法的收敛性分析，也分为局部和半局部收敛性，也给 出了该方法在非线性偏微分方程中的数值实例；第六章讨论牛顿法的一个变形 公式的局部和半局部收敛性，证明此迭代公式是三阶收敛的，并且，给出了利 用此迭代公式求解非线性方程组的数值例子；第七章总结 4 北方工业人学硕士学位论文 2 预备知识 为了便于本论文以后各章节的讨论，在这一章我们简单介绍了一些基本概 念与定理，其中主要包括多元函数的一些知识和非线性方程组迭代法的一些基 本理论我们只给出了个别定理的证明对于其它定理或引理的证明，可查阅相 关的文献 2 1 多元函数微分学基本概念 一个实所咒阵a = ( a o ) 定3 l 了一个从r ”到r ”的线性映射，用a e l ( r , r 4 ) 表示矩阵或线性算子，当一= 所时，简记三( 掣，r ”) = l ( r 8 ) 如果线性算子 a l ( r 6 】是一一对应的，则a 为可逆的或非奇异的，它的逆记为a 一矩阵a 的谱半径记为p ( 一) = m ，。a x 。) l ，i ，其中碡为彳的特征值 引理2 1 1 ( n e u m a n n 引理) 设b l ( r 4 ) ，如果它的谱半径p ( b ) 1 那么 j 一丑的逆存在，且 ( j 一= l i m = y b ， ( 2 1 ) 如果i i b l l l ，那么i - b 可逆_ ，且有 l i ，一口) 。1 i i - e i i b i f = l ( 1 一 ( 2 2 ) 引理2 1 2 ( 摄动引理) 若a ，c 6 l ( r 露) ，a 。存在，且 l a 1 1 - 口，雌一c u - - p ，a p 0 ，使得对任何 ，s o ，8 ) c d ，有l l f ( ，) 一f ( 的0 1 ) ，定理2 1 1 一般不成立，但有如下定理 定理2 1 2 若f ：d c r 4 寸r 4 在凸集d 0 c d 上g 一可导，则对任何两点 x , y d o ，存在，f 2 ，0 ( 0 , 1 ) ，使得 f ( y ) 一f ( 工) = 7 ( 工+ t l ( ) ，一耳) ) 7 ( 石+ f 2 ( y j ) ) 厶( 石+ f 。( j ，一万) ) ( y 一工) ， ( 2 1 1 ) 其中z 是f 的第f 个分量函数 定理2 1 3 若f ：d c r ”呻r ”在凸集d o c d 上g 一可导，则对任何两点 x , y d o ，且f ，在d o 上半连续，则对任何的x , y d o ，有 ，( j ，) 一f ( = f ，( j + f ( ) ，一j ) ) o ，一x ) d t ， ( 2 1 2 ) 定理2 1 4 若f ：d c r 4 哼r ”在凸集d oc di - 连续可导，且f 满足 0 f ( y ) 一f x ) l l - 口j j y j 0 ，v x , y ed o ， ( 2 1 3 ) 其中口0 ，p 0 为常数，则有 i i f t y ) 一m ) 叫( 州) ，一膏) 1 1 s 南l j 一工r ( 2 1 4 ) 证明： i i f ) 一f ( 力一，( 力。一功恃0 n f o + f ( ) ，曲) 一f ( 曲】( y 一工) 班i f 忙o + f ( y 一勘一，( 曲l 陟一捌出 s 球旷工州蝴2 南旷矿 7 北方工业大学硕十学位论文 特别地，若p = 1 ，则p ( | 力一，( 力一，( 刁( y 一工) l 要眇一枷2 定义2 1 4 设映射g ：d c r 。- - 4 r 4 ，若存在口( 0 , 1 ) ，使得对任何两点 x , y e d oc d ，都有 8 g ( x ) 一g ( j ，) 0 s 口i p y 0 ， ( 2 1 5 ) 则称g 为d o 上的压缩映射，口称为压缩系数 定理2 1 5 ( 压缩映射原理) 设映射g ：d e r 4 斗r 4 为闭集d oc d 上的压 缩映射，且g ( d o ) c d o ，则对任一而d o ，序列黾+ = g ( x d ( k = o ，1 ，2 ，) 在d 0 收敛于惟一的不动点，且有误差估计式 i i x , - 工 u 啬卜札一1 1 - 啬o x , - x 。1 1 ( 2 1 6 ) 证明：由g ( d o ) c d o 知， 赡 有定义，且对一切d o ，有 j l 疋。一q ：l l c ( x ) 一g ( 一，) 0 口0 一。l - a 恢一l i 因而， h ，一吒1 1 兰i x k + j - - x k + j _ i 屿( 兰a ，) 恢k 。i i 南忆1 小鲁j 。i t 因0 a 1 ，故 是c a u c h y 列，从而收敛又d 0 为闭集，故有，d o ，使得 l t i 。m 毛2 工。 因g 为压缩映射必连续，故有，= 熙k - = 熙g ( 墨) = g ( ，) ，所以工为g 的 不动点，即方程工= g ( 曲有解， 假设还有y = g o ，) ，则由g 为压缩映射知， p y + 4 = 4 g ( 算) - 6 0 , + ) - a f - y i ， 因0 a 0 ，使得当k k 时有 0 工。+ 。一毒0 口0 x 。一工1 1 9 ， ( 2 2 0 ) 则称迭代序列 黾) 至少p 阶收敛特别地，当p = l 且0 口 0 ，称序列至少平方收敛如果对于k 毛有x k ；，或 毛，但 9 北方工业人学硕士学位论文 ! 觋蝌- o ， 则称迭代序列 x k 超p 阶收敛当p = l 时， 超平方收敛如果k 充分大时，且 ( 2 2 1 ) 称序列超线性；当p = 2 时，称序列 o 1 ，每迭 代一步的工作量为w ，则将 口：业或p l w ( 2 2 3 ) 称为迭代法的效率 定义2 2 3 设 ) 为r ”中的序列， t k 为r 中的非负单调递增序列，并 且满足 i i 以+ 一t0 + l 一气， k = o ，1 ，( 2 2 4 ) 则称 l 为 以 的优界序列( 或强函数序列) 定理2 2 1 设 为 黾 的优界序列，且 熙气2 t ( 2 2 5 ) 存在，则，= ! 妞五存在，且有 i ，一五0 f 一，k = o ，i ，1 ” ( 2 2 6 ) 以上这些预备知识都是最基本的概念和理论，它们对于非线性方程组的迭 代解法以及迭代序列的收敛性分析都是很有用的，是下面各章进行理论分析的 重要基础 1 0 - 北方工业人学硕士学位论文 3不精确牛顿法的半局部收敛性 我们考虑非线性方程组 ，o ) = 0 ，( 3 1 ) 其中f ：d c r 4 专r ”是给定的f 可导的非线性向量函数通常情况下，我们 并不知道( 3 1 ) 的解是否存在，自然希望能直接由迭代过程的收敛性确定解的存 在性，并且找到解，进而可估计误差l j x k - - x * 4 不过，这得给出初值x o 满足 的条件，以保证迭代收敛这就是我们要讨论的非线性方程组迭代解法的半局 部收敛性我们先讨论牛顿法的半局部收敛性 3 1 牛顿法的半局部收敛性 求( 3 1 ) 的数值解的经典算法可以说是如下的牛顿法： x t + l = x i 一旷( x t ) 】一f ( x ) ， k = o , 1 ，2 ， ( 3 2 ) 其中是初始值 关于牛顿法的局部收敛性定理，在一些文献 i , 1 5 1 中都有深刻的分析下面 我们借助于文 1 6 1 的方法，利用强函数及强函数序列给出关于牛顿法半局部收敛 性的康托洛维奇定理的另一种证法，并将相关的一些误差估计式作一下简单的 比较 定理3 1 设f ：d c r 4 哼r 4 在凸集d oc d 上f 一可导，并且满足 1 ) i f ( ) 】- l 存在，且 忙o 。) 。1 4 ， ( 3 3 ) 舻( 粕) 】1f ( x 。) 4 ，7 ( 3 4 ) 2 ) 在包含的闭球氟x o ，回d o 内，f 7 ( 曲存在且满足李普希茨 ( l i p s c h i t z ) 条件 i | f ( x ) - f o ) 4 s 足帖一y 4 ，v x , y e g ( x 0 ，回， ( 3 5 ) 而目。 北方工业大学硕士学位论文 p=砌蔓要，了1-4r=历z- 叩艿， 尸 则方程组( 3 1 ) 在s ( x o ，艿) 内存在解，且牛顿法( 3 2 ) 产生的序列 t c 氟，回收 敛于惟一解j ，并且有误差估计式 o x k - x l l 形护2 1 - ! = 糯l _ , i z 历 执6 ， 为了证明此定理先引让两个足埋 z j l 里3 1 若p = 邵可 j 1 ，则有 ( a ) j j l ( f ) 有两个正实根：f = ! 巫p叩，f - = 旦竺叩； ( b ) 序列以) 满足：0 = f o f - - - t 。 ( c ) f 一气：可0 2 k - i ( 1 - - 0 2 ) 玎，口：单 o ，记= 广一，咯= f 。一， 就有 h ( t t ) = 喜唯，( t a = 一互k ( + 唯) ， 并且有 - 叫+ 1 - = u k - - u k v k2 去，一羔2 素， 1 2 北方： 业大学硕士学位论文 等= c 2 ，即等= 印妒= c 蒜娄2 p 卜旷+ lkhl + l 一 而v i = f # 一t + ，所以有 驴r 中专旷。) ：等字玎，”t 2 一2 万【f 一) 2 i 7 尹玎， 可见，当七专时，蚝专o ，知呻f ，所以( b ) 成立 将p = 争l 一再1 - 万o ) 2 】代入上式可得到( c ) 成立 引理3 2设函数f ( 曲满足条件( 3 3 ) 和( 3 4 ) 则由迭代式( 3 2 ) 产生的序 列 t ) 满足 ( a ) s ( x o ，f ) ，8 f ( _ ) 一1 1 - 一h ( ) 一； ( b ) i i f ( 而) 0 ( ) ，8 鼍+ 一以0 。- t , ； ( c ) 氟矗+ ”t + 一岛+ ) 氟矗，t 一t k ) 证明：因妒o 。) 一1 i i ，护( 气) 一f ( 而) l i k k 一而9 = ( 恢一而移+ 万1 万1 ， 故由b a n a c h 引理知，f ( t ) 1 存在，且 忙( ) 1 忙 - h ( 恢一而旷 由( 3 2 ) 可知， ，( ) + 【，( ) r ( + l t ) = o ， f ( x k + 1 ) = 【f ( 以+ f ( + l 一黾) 一j y ( 赡) 】出( “一墨) ( 3 7 ) 下面用归纳法证明引理3 2 当七= 0 时，( a ) ，( b ) 和( c ) 成立，事实上， 工。s o 。，t ) ，i p o 。) 1 4 s = 一| i i ) ； l p o 。) o 丢= h ( t 。) ，i k 一而o = - f 瓴) 。f ( ) 0 一( t o ) h ( t o ) = 一f 0 ； 对每一个y i ( 而，t 一) ，因为 1 3 北方工业大学硕士学位论文 0 ) ，一而l i y 一五0 + 8 而- x o l l - , + - t t + t i = f 一f o ， 所以有y e i ( ，t t o ) 假设k s 一时，( a ) ，( b ) 和( c ) 成立，则当k = n + l 时， 8 h 广x o u - ( + l - t k ) = t 。+ i _ t o f ，毛+ l s ( x o ，t ) ； 一( k ) 。- - h 7 ( k ，一而旷一h ( t n + l - 乇) 一= 一h ( 一； o f ( 靠。) 8 蔓f 鼢o 。一f 出f ，。x 。一毛0 2 等( 。一) 2 = 会( + l 一) 2 + j l ( ) ( o l o ) + j j l ( 乙) = ( + ) ； i + ：一毛。i i = l l - r ( 。) 一1 ，( 毛。) is h ( 乙。) ( o 。) = o ：一岛。； 对每一个y e 氟矗。，t 一+ ：) ，同时 i i j ) ，一吒“i - h y - j , + 28 + 8 j e t + 2 一黾+ 1 0 s f 一+ 2 + + 2 一t k + i = f 一 “， 所以有y i ( + l t 一+ 。) 综所述，引理3 2 得证 由引理3 1 ，引理3 2 ，有0 耳。一五忙+ 用- t k ，由于 专f ，故 是 c a u c h y 列，从而有极限，记为工，所以当m 一时， l l x t - 4 t + - - t k = 警节2 口歹2 k - i y f h 于l i f ( x k ) h h ( t 。) ，取极限 鳃l l r ( x , ) l l - 熙j i l ( ) = h ( t ) = o ， 所以 f ( x 1 = 0 下面证明惟一性假设有另一解，则有 0 = f ( y ) 一f ( x ) = r f ( x + f ( y 一x ) ) ( y 一x * ) d t = 工( y 一工) 一1 4 北方工业大学硕士学位论文 由于工是非奇异的，所以y = r 口 注1 文献1 5 】中给出了误差估计式 l i x k 一工i f - 备( 2 p ) 2 l 1 ， ( 3 8 ) 并且指出，它可写成更为精确的估计式 i l x k - x l l 石r 等， ( 3 9 ) 其中口( p ) = l 一撕= 万而误差估计式 i i x , - x l l 南玑 ( 3 1 0 ) 其中口= 下1 - x l - 2 , o ，要比上两式更为精确 1 + 4 z 一2 p 注2 定理3 1 的证明方法与文献【1 7 】中的方法有所不同由此文献还可 知，误差估计式( 3 1 0 ) 是最优的，因为对一维情形该误差估计式可取得等号， 同时还有 f 一= 1 0 2 t - 丁1 ( 1 - - 0 2 ) 碍 3 ：2 不精确牛顿法及其半局部收敛性 3 2 1 引言 近年来，对( 3 1 ) 的数值求解常用到如下的不精确牛顿法： 誓主毒：二2 ( 工。) + 以，i i i i i f ( x , ) i i i i f ( x s ，7 。，七= o ，2 ，( s ，t ) 【，( 善1 ) s t = 一，( 工i ) + 以， s ，7 i ， 一v l q 、u 7 其中，仇【o 1 ) 它是求解非线性方程组的有效方法之一，有很多学者研究了 不精确牛顿法的收敛性r s d e m b o ，s c e i s e n s t a t 和t s t e i h a u g 7 1 ，以及b m o r i n i 1 8 1 研究了不精确牛顿法的局部收敛性e c t t i n a p 9 还讨论了不精确扰 动牛顿类方法的局部收敛性白中治和童培莉【2 0 】讨论了不精确牛顿法的半局 部收敛性 - 1 5 北方工业大学硕士学位论文 关于不精确牛顿法的局部收敛性有如下定理【见文【7 j 】： 定理3 2 1 假设仇叩皿。 叩 0 使得，若0 两一x + 0 占， 则不精确牛顿法在下述意义下是线性收敛的，即 i h + 一工t ，70 善睢， 其中0 y l i 。爿i f ( 善+ ) y ( 3 1 2 ) 而且，不精确牛顿法是超线性收敛的，即 “一毒i | - 00 一x 0 ， k - - ， 当且仅当 i l 喙i l - o ( 1 i f ( x k ) | d ，k - - o o 更迸一步，当f ( x ) 在x 处是p 阶h j l d e r 连续时，0 o o ， 当且仅当 i lr k 忙d ( 0 f ( ) i i i + p ) ，k 哼0 0 关于不精确牛顿法的半局部收敛性也有如下定理： 定理3 2 2 设f ：d c r “专r ”在凸集d oc d 上f r 6 c h e t 可导，对任意 x c d o ，f ( 非奇异，且0 ，( 工) 一10 s ，又设尸在d 上满足l i p s c h i t z 条件 0 f 7 ( 功一f 【y ) 0 茎三0 x - y i i ，协，y d o ( 3 1 3 ) 对给定的x 0 d b ，0 f ( x o ) 临，7 ，如果 o r = 三2 ( 1 + 可越。，) 2 ，7 + 节m “ l ， 同时，闭球s = s ( x o ，_ 竺_ ，c d o ，其中 l u 叩。= s u p r i ) 1 ，占= ( 1 + ，7 。) 1 1 ， 那么由( 3 1 1 ) 产生的迭代序列 c - s ，且收敛于( 3 1 ) 的一个解， 此定理要求其中的一个条件是需要处理肛( 曲一1 0 的界如果再结合下面的 条件( 3 1 5 ) ，可得到如下不精确牛顿法半局部收敛性的康托洛维奇型定理 1 6 北方_ 1 业大学硕士学位论文 3 2 2 不精确牛顿法的半局部收敛性足理 定理3 2 3 设f ：d c r ”寸r “在凸集d oc d j ：f r 6 c h e t 可导，f 7 在d 上满 足 0 f ( 工) 一，( j ，) i i - 上0 x - y i i ，v x ，y d o ( 3 1 4 ) 对给定的x 0 d o ，使得 o f ( 而) 一i 峰，l i f ( 而) 一1 ( ，( 而) 一r o ) l t ， 且 k - r k 一。忙圳吒- x k 小 ( 3 1 5 ) 其中 y = m a x ) 1 ，3 v t i 另外，由( 3 2 0 ) 式有 r 、+ 一一趔铲地 所以，序列 单调递增且有界 现在对( 3 2 0