（应用数学专业论文）解一类线性互补问题的b可微法.pdf

河海人学倾士学位论文 摘要 本文重点考察一类线性互补问题( g ，m ) 的b 一可微法在介纠了研究背景、研究意义 利国内外研究现状斤，文章从局部收敛和大范围收敛两方面研究了算法的收敛性，建立了 相应的收敛性结论，并针对实际问题给出了具体算法 本文首先介绍了n e w t o n 型迭代法的基础知识，然后着重介缁了口一可微方程的n e w t o n 法，给出b 一呵微法的局部收敛结论， 推广了古典的n e w t o n 法， 但由j 二收敛的局部性， 该算法仍有一定的不足之处文章在证明人范围收敛定理时，假设 ，是不可约对角优势矩 阵，采用一维n e w t o n 寻查的方法，保证算法的收敛性文章的最斤部分将所得的收敛性结 论用于解决颈轴承问题，仿真结果表明算法可靠、有效本文最后提出了进一步研究的思路 平方向 关键词：n e w t o n 迭代法；线性互补问题；b 一可微函数；颈轴承问题；局部收敛；大范 嗣收敛 a b s t r a c t i nt h i s p a p e rw em a i n l y d i s c u s s e dt h eb d i f f e r e n t i a b l em e t h o d sf u rs o l v i n gl i n e a r c o m p l e m e n t a r i t yp r o b l e m s o nt h eb a s i s o fi n t r o d u c t i o no ft h er e s e a r c hb a c k g r o u n d ， m e a n i n g sa n dt h ed o m e s t i ca n da b r o a ds t u d ys i t u a t i o n ，t h ei t e r a t i v ea l g o r i t h m sa r es t u d i e dm a i n l y f r o mt w oa s p e c t s ，l o c a la n dl a r g e s c a l ec o n v e r g e n c e a n da l s ow ee s t a b l i s h e dt h ec o r r e s p o n d i n g c o n v e r g e n c ec o n c l u s i o n a p p l i c a t i o n so f t h et h e o r yt op r a c t i c a lp r o b l e mw e r ea l s os t u d i e d a tt h eb e g i n n i n go ft h i sp a p e r ，w eb r i e f l yi n t r o d u c e dt h ef u n d a m e n t a lk n o w l e d g eo ft h e n e w t o ni t e r a t i v em e t h o d s ，a n dt h el o c a lc o n v e r g e n c et h e o r e mw h i c he x t e n d e dt h ec l a s s i c a l n e w t o nm e t h o d ，b e c a u s eo ft h el o c a lc o n v e r g e n c e ，t h et h e o r e m h a di t sc e r t a i nr e s t r i c t l a r g e s c a l ec o n v e r g e n c et h e o r e mw a sp r o v e du n d e rt h ec o n d i t i o nt h a tm a t r i xm i si r r e d u c i b l e d i a g o n a l l yd o m i n a n tb yn e w t o n sm e t h o dw i t hl i n es e a r c h a tt h el a s tp a r to ft h i sp a p e r ，w ep r e s e n tt h em e t h o df o rs o l v i n gl i n e a rc o m p l e m e n t a r i t y p r o b l e m sa r i s i n gf r o mj o u r n a lb e a t i n g s n u m e r i c a lr e s u h ss h o w e dt h a tt h e s ea l g o r i t h m sw e r e r e l i a b l e ，e m c i e n ta n da l es u p e r i o rt ot h ee x i s t i n gm e t h o d s a n df i n a l l y ，w ep mf o r w a r ds o l l l em e t h o d sa n dd i r e c t i o n sf o rf u r t h e rr e s e a r c hm e t h o d s k e y e o r d s ：n e w t o ni t e r a t i v em e t h o d ；l i n e a rc o m p l e m e n t a r i t yp r o b l e m ；b d i f f e r e n t i a b l e f u n c t i o n ；j o u r n a lb e a r i n gp r o b l e m ；l o c a lc o n v e r g e n c e ；l a r g e s c a l ec o n v e r g e n c e 河海人学坝士学位论文 摘要 本文重点考察一类线性互补问题( g ，m ) 的b 一可微法在介纠了研究背景、研究意义 利国内外研究现状斤，文章从局部收敛和大范围收敛两方面研究了算法的收敛性，建立了 相应的收敛性结论，并针对实际问题给出了具体算法 本文首先介绍了n e w t o n 型迭代法的基础知识，然后着重介绍了口一可微方程的n e w t o n 法，给出b 一町微法的局部收敛结论，推广了古典的n e w t o n 法， 但由j 二收敛的局部性， 该算法仍有一定的不足之处；文章在证明人范围收敛定理时，假设 ，是不可约对角优势矩 阵，采用一维n e w t o n 寻查的方法，保证算法的收敛性文章的最亓部分将所得的收敛性结 论用于解决颈轴承问题，仿真结果表明算法可靠、有效本文最后提出了进一步研究的思路 丰方向 关键词：n e w t o n 迭代法；线性互补问题；b 一可微函数；颈轴承问题；局部收敛；大范 嗣收敛 a b s t r a c t i nt h i s p a p e rw em a i n l yd i s c u s s e d t h eb d i f b r e n t i a b l em e t h o d sf o r s o l v i n gl i n e a r c o m p l e m e n t a r i t yp r o b l e m s o nt h eb a s i so f i n t r o d u c t i o no ft h er e s e a r c h b a c k g r o u n d ， m e a n i n g sa n dt h ed o m e s t i ca n da b r o a ds t u d ys i t u a t i o n ，t h ei t e r a t i v ea l g o r i t h m sa r es t u d i e dm a i n l y f r o mt w oa s p e c t s ，l o c a la n dl a r g e s c a l ec o n v e r g e n c e a n da l s ow ee s t a b l i s h e dt h ec o r r e s p o n d i n g c o n v e r g e n c ec o n c l u s i o n a p p l i c a t i o n so f t h et h e o r yt op r a c t i c a lp r o b l e mw e r ea l s os t u d i e d a tt h eb e g i n n i n go ft h i sp a p e r ，w eb r i e f l yi n t r o d u c e dt h ef u n d a m e n t a lk n o w l e d g eo ft h e n e w t o ni t e r a t i v em e t h o d s ，a n dt h el o c a lc o n v e r g e n c et h e o r e mw h i c he x t e n d e dt h ec l a s s i c a l n e w t o nm e t h o d ，b e c a u s eo ft h el o c a lc o n v e r g e n c e ，t h et h e o r e m h a di t sc e r t a i nr e s t r i c t l a r g e - s c a l ec o n v e r g e n c et h e o r e mw a sp r o v e du n d e rt h ec o n d i t i o nt h a tm a t r i xm i si r r e d u c i b l e d i a g o n a l l yd o m i n a n tb yn e w t o n sm e t h o dw i t hl i n es e a r c h a tt h el a s tp a r to ft h i sp a p e r ，w ep r e s e n tt h em e t h o df o r s o l v i n gl i n e a rc o m p l e m e n t a r i t y p r o b l e m sa r i s i n gf r o mj o u r n a lb e a t i n g s n u m e r i c a lr e s u l t ss h o w e dt h a tt h e s ea l g o r i t h m sw e r e r e l i a b l e ，e m c i e n ta n da r es u p e r i o rt ot h ee x i s t i n gm e t h o d s a n df i n a l l y ，w ep u tf o r w a r ds m i l em e t h o d sa n dd i r e c t i o n sf o rf u r t h e rr e s e a r c hm e t h o d s k e y e o r d s = n e w t o ni t e r a t i v em e t h o d ；l i n e a rc o m p l e m e n t a r i t yp r o b l e m ；b d i f f e r e n t i a b l e f u n c t i o n ；j o u r n a lb e a r i n gp r o b l e m ；l o c a lc o n v e r g e n c e ；l a r g e s c a l ec o n v e r g e n c e 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 蔓遣垒! 。年；月工孑日 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术 期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或 电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子 文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权 河海大学研究生院办理。 论文作者( 签名) ：簋签 亟，a 5 年弓月叼日 第一审绪论 第一章绪论 1 1 研究背景及发展 非线性问题是科学研究$ l j _ e 程实践中的重要课题之非线性方程数值解法是解决该类 问题的撮基本的方法之一 随着科学技术的发展干u 电子计算机技术的。泛应削，求解形如 f ( x ) = 0( 1 1 ) 的非线性方程组的问题越来越多地被提山来了，其中，f 表示定义在r ”中开域上的1 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 法收敛性的研究已经有很长历史，关于局部收敛性定理最早是在1 8 2 9 年 c a u c h y 研究了 = 1 的情形，在r ”中情形下的定理最早是由r u n g e 于1 8 9 9 年给出的1 9 1 6 年f i n e 第一次在r ”中不假定方程组解存在的情况f ，证明了n e w t o n 法的收敛性，它的条 件与m b i c o b c k h x 定理类似，即假定导数f ( x ) 在个适当的球上非奇异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 ，但可直接推广到一般的n k a n t o r o v i c h 二f 1 9 4 8 年在b a n a c h 空间中给出了n e w t o n 法著名的收敛定理，一年后又提出优界原理的新汪 法7 0 年代以后，有人对n e w t o n 法误差估计及收敛性进行了研究，并给出了一些新的结 果，其中较有意义的是 2 2 2 6 给出的结果 n e w t o n 法半局部收敛定理以及n e w t o n 型迭代收敛定理在b a n a c h 空间都是成立的，闲 m 它可推广到一般的算子方程，应用到积分方程，两点边值问题，椭圆型边值问题 河海凡学顸十学位论文 等n e w t o n k a n z o r o v i c h 定理也可作为让明存在定理的工具，例如可见m o s e r ” 割线法的基本山容可参见文献 1 ，其由一点割线法与曲点割线法均可视为离散 n e w t o n 法，其效率与n e w t o n 法相当，h + l 点顺序割线法虽然效率较岛，但因稳定性不能 保证而较少使用， 1 0 ：对此进行的研究对实际计算尾有意义的改进 点割线浊是一个既 稳定效率又高的算法，是几前割线法中最有效的算法，它比b r o w n 方法效率更高这个算 法衽 1 1 中称为h 点割线法， 1 1 还给出一个二步割线法，也是一个i 供实际计算的算 法 1 2 在复月维空间上讨论多变量割线法，理论上是有意义的 b r e n t 方法是1 9 7 3 年才提出的”，它是b r o w n 方法的改进，是几前各种算法中效率 展高的算法，该算 去在解菲线性方程组的数学库中已被j l 泛采用n 4 将这些算法与b r o w n 浊及n e w t o n 沾做了分析比较， 1 5 对它做了址一步的推广，这对我们研究算法都是有意义 的 拟n e w t o n 法是最近讨论得很多的算法，对拟n e w t o n 法收敛性的寸港也适用于其他算 法特别耍指出的是g a y 在 1 6 中对b r o y d e n 方法收敛性做了更深刻的描述，他指出 b r o y d e n 方法应用于线性方程组a x = b ，其中a j 已f 彤) 为非奇异的，则该算法至少2 ”步 收敛实际计算中b r o y d e n 方法效率并不比n e w t o n 法高，但针对实际计算中出现的j a c o b i 矩阵为稀疏的情形，应用b r o y d e n 方法进行求解是拟n e w t o n 、法的一个重要的研究方向，这 个一作首先是由s c h u b e r t 丁1 9 7 0 年提出的，随后的研究还可参见 1 7 1 8 等 n e w t o n 法需要每步解一线| 生方程组，用诸如g a u s s 消元泫等方法求解时计算量很大， 且当r 远离解点x 时，无法求解，在这样的环境下，文 8 9 对不精确n e w t o n 、法局部收 敛性做r 一定的研究随后的研究还f u 参见 4 1 4 2 等 n e w t o n 法中要求f 连续可微，然而在许多实际问题中，并不定是光滑映射，此时 的n e w l o n 法不再适川【3 7 1 1 2 7 1 给出r 半光措甬数、口一可微晒数的相席的概念及件质， 此后不可微情况下的n e w t o n 法及拟n e w t o n 法取得了很大的进展，相应的也得到不_ j 微方 程组的非精确n e w t o n 算法一系列收敛结果 1 2 研究内容与意义 木文重点考察类线性互补问题( 如m ) 的局部和大范围收敛性，并建立了相应的收敛 性结论f 见第三章) 我们定义f ( x ) = m i n ( m x + q ，x ) ，易见f ( x ) = 0 的解和线性互补问题( q ，吖) 的群是 我们定义f ( x ) = m i m x + q ，x ) ，易见f ( x ) = 0 的解和线性互补问题( q ，m ) 的解是 第一章绪论 等价的，先证明f 在r ”上是占一可微的且其b 一导数町逆，最后证明收敛性 在证明局部收敛性时，推广了古典的解决f - 可微方群的n e w t o n 法，定义了一个迭代 法来解决问题，即 f ( x 、+ b f ( x 4 1 矿= 0 设扩为给定的迭代，求解如上方程中的d ，再令“= x + d 。，得到女+ 1 次迭代结果 证明人范围收敛定理时我们采h j 一维n e w t o n 寻查的方法， 即令吼= “s g ( z ) = 去f ( x ) 7f ( x ) ，其中m 女为满足如r 不等式的第一个非负整数m ： g ( x ) 一g ( x 2 + 卢”s d ) 一。声s g7 ( x ，d 。) 进而得到下次迭代值x “1 = x 2 - i - d 2 第四章将得到的收敛性结论应用丁颈轴承问题，将颈轴承的数学模型归结为一个线性 互补问题，使颈轴承问题得到有效解决 线性规划、对策论、经济学和工程力学等应用领域中的某些问题都可以转化成线性互 补问题，网而本文给出的算法适合许多实际问题 1 3 文献综述 借助期刊检索、光盘检索及网络数据库检索，我”j 搜集了人量的与本课题相关的文献， r 面对这些文献做出如下的综述 1 文献【1 ，2 ，4 ，5 ，6 1 系统介绍了1 线性方程组的基本理论和方法，除了讨论经典 的、常用的迭代法及其收敛性外还介绍近些年新发展的方法 2 文献 8 ，9 对不精确n e w t o n 法局部收敛性做了一些研究， 1 0 1 2 讨论了割线法 的效率及稳定性等， 1 6 1 8 讨论b r o y d e n 方法的收敛性， 2 2 - - 2 6 n 寸论了n e w t o n 法误 差估计及收敛性，并给出了一些新的结果 3 文献【2 7 给出了口一导数的原始定义，【3 6 在拓扑空间上比较了方向导数的各种定 义，指山在有限维的欧几里德空间尺”中，在局部l i p s c h i t z 连续映射条件r ，各种方向导 数的定义是等价的， 2 8 3 5 】， 3 7 4 2 】讨论了在不可微情况f 的n e w t o n 法和拟n e w t o n 法， 4 3 给出了线性互补问题和非线性方程组解的等价性的理论基础 4 文献 4 4 】， 4 6 5 1 对颈轴承问题进行了建模并具体分析了其解决的方法：【4 9 1 首 先提出可以用有限差分的方法解决颈轴承的自由面问题文 4 7 在 4 9 的基础上运片j 有限差 河海大学硕士学位沦文 分的方法给山了颈轴承问题的解决方法，文 4 4 1 1 4 8 运用区间理论给出了区间迭代序列 文【5 l 】给出了关于颈轴承问题的r e y n o l d s 方程的数值解法 4 第二二章n e 、q o n 型迭代浊基础知识 第二章n e w t o n 型迭代法基础知识 设映象f ：r ”斗r ”，求解非线性方程组 f f x l = 0 ( 2 1 ) 的n e w t o n 法是个最基本而且十分重要的方法，目前使用的很多迭代法都是以n e w t o n 法 为基础，并由它发展而得到的 2 1 迭代法及收敛性 设f ：d r ”斗r ”，用迭代法求解非线性方程组( 2 1 1 的解，就是构造一个收敛丁 方程组( 2 1 ) 的解x + 的迭代序列： 其中d 戒们把非线性方程组( 2 1 ) 改写成形式 x = g ( x ) ， 其中g ：d c r ”斗r ”，下面先给山几个不动点存在定理 ( 2 2 ) ( 2 3 ) 定理2 1 2 1 ( 压缩映象定理) 没g ：d c r ”斗r ”为闭集d n c d 上的压缩映象 g ( d o ) cd 0 ，则g 在d 0 中有唯一的不动点 定理2 2 2 1 若g ：dc 7 _ r ”斗r ”为有界闭集d o c d 上的严格非膨胀映象 g ( d o ) c 7 _ d o ，则g 在d 0 中有唯一的不动点 定理2 3 2 1 假定g ：d c r ”一r ”在闭凸集d i 匕d 上是非膨胀映象，且 c ( d o ) cd i ，则g 在d o 中有不动点的充要条件是至少有一个x o d 0 使序列 矿“= g ( x 。) ，( k = o ，1 ，) 有界 如果g 满足定理21 2 3 中的条件，则方程( 2 1 ) 有解x 存在，井可j i _ 1 迭代序列 河海大学硕l 学位论文 x “1 = g ( x ) ，k = o ，1 f 2 4 1 求得方程( 2 3 ) 的解，形如( 2 4 ) 的序列就是求解方程( 2 1 ) 的一种迭代法，通常g 可以有 各种不同的形式为了便丁计算，我们假定g 只依赖丁f 及f ，如果g 不依赖丁迭代步 数k ，且x “1 只依赖于x ，则称迭代序列( 2 4 ) 为单步定常迭代如果映象g 还依赖丁迭 代步数k ，则迭代序列( 2 4 ) 可表示为 x “1 = g k ( ) ，k = o ，1 ， ( 2 5 ) 并称为单步非定常迭代如果x “不仅依赖丁，还依赖于x “1 ，x “”1 ，则迭代序列 x “1 = g ( x ，x “”1 ) ，k = m 一1 ，m ， ( 2 6 ) 称为晰步定常迭代若g 还依赖于k ，则 x “= g k ( x 。，一，x 1 ) ，k = m - 1 ，m ， ( 2 7 ) 称为m 步非定常迭代 这里的( = 0 ，1 ，) 均为r ”中元素，g 或g k 称为迭代函数， ) 称为迭代序列， 用不同的方法构造出不同迭代函数就可得到不同的迭代法如果迭代法得到的序列 x ，k = o ，1 ，) c d ， 则称迭代序列是适定的它表明迭代法算出的每个x 都有意义若x + d 匕r ”是方程组 ( 2 1 ) 的解，且序列 x kk = o ，1 ，) 满足 ! 觋= x 或 ! 蚓o l i = o ， l l 则称迭代序列收敛于x 一个迭代法只有当它的迭代序列 ，k = o ，l ，) 是适定的和收敛 于x ，才能用它做为求非线性方程组( 2 1 ) 解的方法 定义2 1 但1 设f ：d c r “斗r ”，x e d 是方程组( 2 1 ) 的一个解，若存在x 的一 个邻域s c d ，使得对任何初始近似x o s ( 或对埘步法，取工o ，x “s ) 迭代序列 缸，k = 0 ，1 ， 总是适定的且收敛于x ，则称x 是序列的吸引点( a t t r a c t i o n ) 具有这种性质的迭代序列称为具有局部收敛性，如果一个迭代法能证明在解的一个充 分小的邻域内收敛，就说它具有局部收敛性在不假定方程组( 2 1 ) 的解存在的情况f ，只 6 第帝n e w t o n 型迭代法基础知识 根据迭代初始近似x o 满足的条件，就能证明迭代序列 ，t = 0 ，1 ，) 收敛到方程的解t + 就称这种迭代法具有半局部收敛性通常讨论迭代法收敛性主要就是研究它的局部收敛性 l j p n n 雌i 性，但由丁这种迭代法要求初始近似x o 与解x 必须充分靠近，才能使迭代 序列收敛到x + ，这给实际计算带来了相当的凼难，因此，对于具有犬范围收敛性的迭代法 研究，无论在理论上或在实际求解计算上都是十分重要的所谓人范围收敛的迭代法，就 是指以求解域d 中的任一点x o 为初始值，迭代序列 x k 七= o 1 ，- 都能收敛到方程组 ( 2 1 ) 的一个解x + 2 2n e w t o n 法的构造 将非线性映象f 逐步线性化，在每步迭代中解一个线性方程组，这样得到的迭代法就 是线性化方法 假定x + d 是方程组( 2 1 ) 的一个解，x d 是x + 的个近似，通过点x 可定义仿 射映象 l k ：r ”寸r ” 为 厶( x ) = 4 ( x x ) + f ( x ) ，( 2 8 ) 其中a k l ( r ”) 为非奇异的”阶矩阵，若用线性方程组l a x ) = 4 0 一x ) + f ( ) = 0 的 解x = “作为方程组( 2 1 ) 的新近似，即 x “1 = 扩一鼻1 f ( x ) ，k = 0 ，1 ， ( 2 9 ) 这程序就称为解非线性方程( 2 1 ) 的线性化迭代法通常4 与矿及f ，f 等有关，如果a 。 取法不同就可得到不同的迭代法，一种最简单的取法就是对所有的k 都取a k ；a l ( r ”) 非奇异，于是由( 2 9 ) 得 x 。“= x 一a 一1 f ( x ) ，k = o ，l ，一( 2 1 0 ) 它称为n 维平行弦方法，它的几佃意义就是：在r ”1 中”个超平面 7 河海大学硕士学位论文 z = a , j ( x ，一x ；) + 、，；( x ) 与超平面z = 0 的交点就是x “其中f = ( ：，无) 7 ，：为r ”1 的 + 1 个坐标分量 a = ( 口。) 若取一= f7 ( x 。) ，则由( 2 1 0 ) 可得 工“= x 一i f ( x 。) 】。f ( x ) ，k = o ，1 ， f 2 1 1 1 这个程序称为简化的n e w t o n 法与一维情形相似，若在点处用超切平面代替曲面，即 j 】线性方程组 l ( x ) = f ( x ) + ，( x ) ( x x 。) = 0 近似方程组( 2 1 ) ，则可得到第k + 1 次近似解 z “= x 一i f ( x ) r 1 f ( x ) ，k = o ，1 ， ( 2 1 2 ) 这就是解方程组( 2 1 ) 的n e w t o n 法这里的f ( x ) 就是f 的j a c o b i 矩阵它的几何意义就 是利用胛个超切平面 z = ，( x 2 ) + v ，：( x x + ) 与超平面z = 0 的交点x “作为超曲面z = f a x ) ，i = 1 ， 与超平面：= 0 的交点x + 的新 近似n e w t o n 法( 2 1 2 ) 每步要计算f ( x 。) 的逆，当 很人时计算是很困难的，实际计算 时可采用下列形式 取内x k + l 缸= ；x + k + a ) c 譬f ( x0 ， _ i = 。，1 ， ( 2 1 2 ) 【f ( ，) 缸。+。) = ， 一 、 即每步耍解一个n 阶线性方程组 按上述线性化方法得到的迭代法一般形式为 x “。= x 一【一( x ) 】一f ( x 。) ， k = o ，1 ，( 2 1 3 ) 为保证近似方程组( 2 1 ) 的解x + ，应要求4 ( x ) 近似于f ( x + ) 基于不同考虑，适 当选取a ( x 1 就得到n e w t o n 法的各种变型，这类方法称为n e w t o n 型迭代法 8 帮章n e w t o n ：a 迭代法基础知识 2 3n e w t o n 法收敛定理 为了方便讨论，我们将( 2 1 3 1 式记为 ( 2 1 37 ) 其中g ( x ) = j 一 爿( x ) “f ( x ) 定理2 4 2 1 若f ：r 。斗r “在x + 处f 叮导，x 是方程组( 2 1 ) 的解，瓯 d 是x + 的 邻域，又设a ：s 。cd l ( r ”) 在+ 处连续，a ( x + ) 1 f 奇异，则存在翻j 球 s = i ，j ) c s o ，使由( 2 1 3 ) 定义的映象g 在x s 卜有定义，3 i f f ：x 处有f 导数 g ( x 。) = i 一【爿( x + ) 】。1 f ( x + )( 2 1 4 ) 若还有p ( j 一【一( x + ) 】。f ( x + ) ) o ) ，使映象 g ( x ) = x i f 0 0 _ 1 f ( r ) 对所有x s 有定义，且n e w t o n 法( 2 1 2 ) 生成的序列 石 超线 性收敛到x 若还假定 f ( x ) 一f ( x + ) 8 8 l 卜一x 0 ， vx s ， 其中口 0 为常数，则n e w t o n 迭代序列 x 至少2 阶收敛 推论2 1 川若定理2 ，5 中还假定，在x 处二阶f 可导，且对任何俐f 0 ，矗r ”有 f ”f x + ) h h 0 则n e w t o n 法( 2 1 2 ) 为2 阶收敛 定理2 5 及推论说明在一定条件f ，总存在一个吸引域s ，只要初始近似在s 中 n e w t o n 迭代( 2 1 2 ) 生成的序列 x 总在s 中且收敛到x ，并且是超线性收敛的如果再 加上。些条件，n e w t o n 法具有2 阶敛速粗略说，用n e w t o n 法迭代次大约有效数位增 9 河海人学硪i 学位论文 加一倍，例如x o 准确到一位，则迭代3 次就可得到准确剑8 位的近似解这意味着n e w t o n 迭代收敛很快，这是它的主要优点还应指出n e w t o n 法是向校正的，也就楚说工“1 仅依 赖_ r f 及，前面迭代产生的舍入误差不会步步传f 去由丁n e w t o n 法具有这些优点 此，它仍是解非线性方程组的一个常州开勺重要力法 上面给出的n e w t o n 法与n e w t o n 型迭代法的局部收敛性与收敛速度，都是假定方程组 ( 2 1 ) 的解存在的前提下的，但实际计算时我们通常并不知道方程绢( 2 1 ) 解是否存在，f 面的定理真接从迭代过程收敛性确定方程组解的存在性，井对给定的迭代初值x o 给出保证 迭代收敛的判断准则 定理2 6 【2 1 设f ：d 亡r ”斗r ”在凸集d o c d 上f 可导，且对任何x 。y d o 有 f ( z ) 一f ( y ) i - l ( r ”) 满足 l l 【一( x ) 。l i ，l i f ( x ) 一爿( x ) 0 占，v x e d o ， 其中届占 1 ，若妒d o 使# 一 。) - l ，( ，州兰刁，口= 寻局仰+ 膨 l ，且闭球 s = 蜃( x o ，士) cd o ，则n e v a o n 型迭代( 2 1 3 ) i a x “。1 = x 一【爿( z ) 】一1 f ( x ) ，k = o ，1 ， 仍在s 中，且收敛到f ( x ) = 0 的一个解x 定理2 7 【2 1 ( m b l c o b c k b x 定理) 假定f ：d c r ”r 4 在凸集d o d 上f 可导，又 对任何x d 0 - f 7 ( x ) 非奇异，且恤f ( x ) 】i i - 卢，i i f ) - f ( y ) 1 | y 忙一y i i ， v x , y d o 若p d 0 使尸( x 。) 】一1 f ( p ) 0 叩，且a = 局唧 1 ，以及闭球 s = i ( x 。，t o ) cd 0 ，其中托= 玎a 2 1 ，则n e w t o n 迭代( 2 1 2 ) j 一0 x ”= x 一i f ( x ) 一1 f ( x ) ，女= 0 ，1 ， 产生的序列 x 。 c s = s ( x 0t o ) 并且收敛于f ( x ) = 0 的个解x + 此外 忙忙吼”。n j = 1 2 一， l o 第章n e w t o q 魁迭代法基础知诅 其中= 号喜( ) 2 ：- 1 0 使 l i f ( x ) 一f ( y ) l l r l l x y l l ， 再假定存在x 。d o ，使l i e f ( x 。) r | i ，f ( x 。) 】- 1 f o 。) 0 ，7 ，j ：l h = p y q i 1 ， i j 球 s = i ( 妒，广) c d o ，其中，= ( 而) 叩，( 向) = 1 - 4 _ 1 _ 一- 2 h ，则n e 叭。n 迭代( 2 1 2 ) x “= x 一i f7 ( x ) 。f ( x ) ，女= o ，1 ， 产生的序列 x 。) 均在闭球i 。，广) 内，并且收敛到f ( x ) = 0 在i ( x 。，t ”) n d o 内的唯一解 x + ，其中，= 三( 矗) 叩，三( ) = l + , 5 i 习一f i ，且误差估计为 i x * - - x k 忙击( 2 ) 2 。 a0 x “- - x k l l - 1 1 x + _ x k l l 臼2 。i i x 一x 。i i , t = ，2 ，一， 2 瓦2 牙舻糍 1 ， 当 = i 1 时得，2 ( x 2 1 ) 弦“一i i _ l l x - x i i _ _ l l x , - x k - , = l ，2 ， f 7 ( z 。) 】一1 卢，而m b i c o b c k h x 定理要求f ( x ) 】_ 1 1 1 - 在所有的点x d o 上t 葫, 2 ，至 河海大学顺，l 学位论义 什漱时，存在一个收敛半觏= 等，豫比y y k = 0 4 3 9 - 剥咖n 法 收敛好坏的一个重要标志满足定理2 7 收敛条件的方法的i 径比为0 3 6 9 ，返说明 g a n t o r o v i c h 定理对n e w t o n 法给山的收敛域比m b i c o b c k h x 定理给出的收敛域大，由此 也说明还可进一步改进k e w t o n 法收敛定理条件，使得收敛域进一步扩大 2 6 中对定理2 7 做了改进，得到了半径比为0 ，5 9 8 的收敛定理 k a n t o r o v i c h 定理可推广剑一般n e w t o n 型选代法( 2 1 3 ) ，我们有如r 的收敛定理： 定理2 9 2 1 假定f ：d 亡r ”_ r ”在凸集坟c d 上f 可导，且满足 l i f ( x ) - f ( y ) 忙y 忙一y l l ，v e y d 0 义设爿：d o c r ”斗l ( r ”) ，并且一d 0 ，对任何x d o 有 一( 工) 一爿( x 。1 1 o 使 i i f ( x ) 一p ( x + l i i x - x i l ，v x ed o 一f ( 工+ ) 忙，7 妒一工+ k = o 州1 一， 则由( 2 1 9 ) 生成的序列 ) 至少平方收敛于x + 1 4 型 第三誊b f 馓d 1 硝j 煎n e w t u n 第三章b 可微方程的n e w t o n 法 考虑非线性方程绸( 2 1 ) 的求解问题，当f 连续可微时，n e w t o n 法是求解此问题的1 f 常有效的算法，然而在许多实际问题中f 不一定是光滑映射，此时的n e w t o n 法1 i 再适心 本章将讨论当函数f 是丑可微时的局部和大范罔收敛性 3 1 引言 自从r o b i n s o n 提出了占一导数概念，在不可微情况下的n e w t o n 法和拟n e w t o n 法取得 r 很大的进展 p a n g 2 8 2 9 推广了古典n e w t o n 法，用于解扶b 一可微方程，并将方法用于解决非线 性互补问题和变分不等式问题h a r k 和x i a o 在文 3 0 做了相似的推广，解决了一类非线 陛互补问题文【3 1 】中，g w i n n e r 在赋范空问上讨论了不可微算子的广义s t i f l i n g - n e w t o n 法k o j i m a 和s h i d o 在文 3 2 中分析了对于分段连续可微方程的n e w t o n 法和拟n e w t o n 法文【3 3 中，k u m m e r 将k o j i m a - s h i d o 的结论推广到实b a n a c h 空间上，并研究了一类线 性连续算子的n e w t o n 法r o b i n s o n 在文 3 4 - 3 5 q b 讨论了不光滑函数的n e w t o n 法 1 9 9 3 年o i 和s u n 在1 3 7 1 啊j 用映射的广义j a c o b i 构造了一类解非光滑方程组的广义 n e w t o n 法 x “1 = x 一吁1 f ( x 2 )( 3 1 ) 其中ko f ( x ) ，o f ( x ) 是在点妒处的广义j a c o b i 3 ，o f ( x ) = c o l i m j f ( x , ) 当f 在x 处是、r 光滑时，q i 和s u n 在【3 7 仲证明了该广义n e w t o n 法的局部超线性收敛性 由丁计算k 比较复杂，即使可微情况也戍尽可能避免， x uh u i f u 在文【3 9 中，提出 如下拟n e w t o n 迭代格式： x “= 一j ( x l s ) 一1 f ( x 。) ( 3 2 1 其中j ( x k , s ) 为a f ( x ) 的一致相容逼近，并证明了此迭代函数为收缩映射，从而保证了 局部收敛性为构造j ( x ，s ) ，文 3 9 提山了两种方法：差分逼近与s s u b - j a c o b i a n 逼近疗 法前者具有一定的局限性，后者适用于广泛+ 粪的问题它是占次梯度概念在菲线性方 河海大学硕十学位论文 程组领域的延伸另外，文【3 9 1 还提出了模减技巧以保证n e w t o n 法与拟n e w t o n 法平稳收 敛 文 3 8 1 1 4 0 1 在 2 0 1 【2 1 的基础上做_ ：r 推广，给出了不光滑函数的b r