（应用数学专业论文）求解互补问题数值算法的一些研究.pdf

中文摘要 互补问题是运筹学与计算数学的一个交叉研究领域，它与非线性规划、极大极 小、对策论、不动点理论等分支有紧密联系，在力学、工程、经济、交通等许多实 际部门有广泛的应用这使互补问题成为非线性科学和计算科学研究的一个热点问 题，求解互补问题的算法的研究也取得了很多成果本文研究互补问题的数值方法 绪论部分，概述了互补问题的各种形式以及在工程、经济中的应用，同时分类介 绍了求解互补问题的几种主要算法最后，介绍了本文的内容安排 第一章将岛一函数非线性互补问题( n c p ( f ) ) 转化为求解一个等价的非线性方 陧组，利用光滑化的f i s c h e r - b u r m e i s t e r 函数构造与n c p ( f ) 等价的光滑方程组在 比基础上建立求解n c p ( f ) 的参数微分法数值实验结果进一步验证这一方法的可 盱性和有效性 第二章将求解互补问题( c p ( f ) ) 转化为求解一个等价的不动点方程利用不动 点方程构造迭代公式并将迭代公式光滑化求解，进而提出求解互补问题的逐点逼近 阜法，从理论上证明了算法的大范围收敛性，数实试验的结果表明这一算法是可行的 i 缸有效的 最后一章是对本文的总结和对将来研究工作的展望 关键词：互补问题，局函数非线性互补问题，光滑f i s c h e r - b u r m e i s t e r ，参数微分 去，不动点方程，逐点逼近法，大范围收敛性 i 中文文摘 本文主要探讨互补问题的数值求解方法提出了求解局一函数非线性互补问题 的参数微分法和求解一般互补问题的逐点逼近法，详细分析了所给算法的收敛性， 并利用m a t l a b 平台，对一些算例进行了数值实验，以验证所做的理论分析文章 的结构安排如下： 绪论概述了互补问题的各种形式，同时分类介绍了求解互补问题的几种主要算 法，指出互补问题有着广泛的实际应用背景和重要的理论意义最后，介绍了本文的 内容安排 第一章研究f 是连续可微r 一函数的非线性互补问题( 简记为e o n c p ) ，将 求解e o n c p 转化为求解一个等价的非线性方程组由于转化后的非线性方程 组相应的非线性映射一般是非光滑的，因此利用光滑化的f i s c h e r - b u r m e i s t e r 函 数构造与n c p ( f ) 等价的光滑方程组在此基础上建立求解n c p ( f ) 的参数 微分法数值实验表明，这一方法是有效的第一节引言，n c p ( f ) 等价于方 程组皿向) = 0 ，这里皿：舻一船的一个半光滑函数这样的函数是可以 构造的，比如，f i s c h e r - b u r m e i s t e r 函数咖啊( 口，b ) = a + b 一 萨干可 f i s c h e r - b u r m e i s t e r 函数在除原点外的任意一点是可导的，在原点是半光滑的为此引入光 滑参数，得到光滑f i s c h e r - b u r m e i s t e r 函数( p ，a ，6 ) = a + b 一归+ 口2 + 6 2 于 是n c p ( f ) 等价于方程组o ( z ) ：= g ( 肛，z ) = ( p ，西( p ，z ) ) r = 0 ，其中圣( p ，z ) = ( ( p ，x l ，毋( ) ，( p ，z 2 ，而( z ) ) ，咖( p ，z n ，r ( z ) ) r 接着证明了西( z ) = 西( p ，2 ) 在名= ( p ，z ) 舻+ l ，p 0 连续可微，g ( z ) = g ( p ，z ) 在名= ( p ，z ) 皿+ 舻连 续可微，如果f 是r 函数，则矩阵g 的j a c o b i 矩阵在风- + j 护非奇异第二节同 伦法，介绍同伦法的基本思想和构造日( z ，t ) 的多种方法，为第三节构造同伦方程做 准备第三节建立求解方程g ( 彳) ：= g ( p ，2 ) = ( p ，西( p ，z ) ) t = 0 的参数微分法将 求解方程g ( z ) ：= g ( p ，$ ) = ( p ，雪( p ，茁) ) r = 0 转化成求同伦方程 h ( z ，亡) = g ( z ) + 一i ) g ( z o ) = 0 ，t 【0 ，l 】，z 4 + 舻 求上述同伦方程的解z = z ( t ) ，等价与求微分方程 f 掣：- f g ，( 删】叼( ) ， tz 赫 福建师范大学林钊硕士学位论文 最后给出定理表明同伦方程h ( z ，力= g ( 名) 4 - 一1 ) g ( z o ) = o ，t 【0 ，1 】，名 风斗研存在唯一解z = z ( 亡) 且z ( 亡) 满足上述微分方程第四节数值试验，采用 四阶经典r u n g e - k u t t a 格式求解上述微分方程初值问题并给出4 个数值例子所有 的程序都为m 语言并在m a f l a b2 0 0 8b 环境下运行，实验结果表明算法是可行的而且 是有效的第五节对本章进行小结 第二章研究求解互补问题的另一种算法_ 逐点逼近法投影法是求解互补问题 的一类基本而又重要的计算方法，逐点逼近法是投影法中的一种第一节引言简要 的介绍了互补问题及本章的安排第二节预备知识介绍了本章用到的一些基本概 念和性质，为之后的文章作铺垫第三节是本章的重点逐点逼近算法由投影【】+ 的基本性质，互补问题c p ( f ) 等价于下面的不动点方程z k a f c x ) + = 0 利 用上述不动点方程构造了迭代公式矿+ 1 = 陋一a f ( x k ) 】+ 这个迭代公式的收敛结 果要求f 是强单调和l i p s c h i t z 连续的无疑，这个条件太强，而把许多实际问题排 除在外于是提出了新的的迭代公式口1 = p a k f ( z 知+ 1 ) 】+ 迭代公式z 1 = 扩一a f ( x 七) 】+ 中的刃h 1 是由显式求出，而迭代公式$ 1 ；p a k f ( x k + * ) 】+ 中 的$ 知+ 1 是由隐式求出实际计算时比较困难，于是将方程z 知+ 1 = k 知一舭f ( $ 1 ) 】+ 光滑化求解这样，求解方程z 七+ 1 = 矿一a k f ( z k + 1 ) + 等价于求解下面的光滑方程 组 ，“、 日( z ) ：= 日( p ，z ) 2i l 2 0 ， g ( p ，z ) 其中 g ( p ，z ) = g l ( p ，z g 2 ( p ，z g n ( p ，z g i , 2 k + 1 ) ：2 z ：+ 一 ：一q 七置( z 七+ - ) ) 一、乍鬲i _ ：j i ；石而 本文将基于迭代公式z 1 = 囟七一a k f ( x 知+ 1 ) 】+ 提出求解互补问题的逐点逼近算法， 第四节证明了算法在f 是伪单调的假设下具有大范围收敛性第五节给出了4 个数 i v 中文文摘 值例子所有的程序都为m 语言并在m a t l a b2 0 0 8b 环境下运行，实验结果表明算法 是可行的而且是有效的第六节对本章进行小结 最后一章，对本文的工作进行了总结，介绍本课题的研究进展和所取得的成果， 指出今后进一步开展研究工作的设想、展望、建议以及尚待解决的问题 v a b s t r a c t c o m p l e m e n t a r i t yp r o b l e mi sac r o s s - c u t t i n gr e s e a r c h i n y ga r e ao fo p e r a t i o n a l r e s e a r c ha n dc o m p u t a t i o n a lm a t h e m a t i c s i th a sab r a n c hc l o s ec o n t a c tw i t hn o n - l i n e a rp r o g r a m m i n g ，t h e o r yo fm a x i i n i na n dm i n i m a ，g a m et h e o r y , f i x e dp o i n tt h e o r y ，w h i c hh a saw i d er a n g eo fa p p l i c a t i o n si nm a n yr e a ls e c t o r s ，f o re x a m p l e ，m e c h a n i c s ， e n g i n e e r i n g ，e c o n o m i c ，t r a n s p o r t a t i o na n d s oo n t h er e s e a r c ho ni ti sa l w a y st h e h o ts p o t si nn o n l i n e a ra n dc o m p u t a t i o n a ls c i e n c e m a n yr e s u l t sh a v eb e e na c h i e v e d o u rt e s td e a l sw i t ht h en u m e r i c a lm e t h o d so ft h e c o m p l e m e n t a r i t yp r o b l e m d i f f e r e n tf o r m u l a t i o n so fc o m p l e m e n t a r i t yp r o b l e m sa r ei n t r o d u c e di na ni n t r o - - d u c t i o n ，a l o n gw i t ht h e i rv a r i o l l sa p p l i c a t i o n si ne n g i n e e r i n ga n de c o n o m i c s t h e n ， s o m ee x i s t i n ga l g o r i t h m sf o rc o m p l e m e n t a r i t yp r o b l e m sa r ed e s c r i b e d f i n a l l y , t h e o r g a n i z a t i o no ft h i st h e s i si so f f e r e db r i e f l y i nc h a p t e r1 ，s o l v i n gt h en o n 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 ( n c p ) i st or e f o r - m u l a t et h en c pa san o n l i n e a rs y s t e mo fe q u a t i o n s t h ee q u i v a l e n tn o n l i n e a rs y s t e m o fe q u a t i o n sb a s e do nt h es m o o t h i n gf i s c h e rf u n c t i o ni sc o n s t r u c t e d p a r a m e t r i cd i f - f e r e n t i a t i o ni sg i v e nt os o l v et h e 蜀- f u n c t i o nn o n 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 w e p r o p o s es o m en u m e r i c a le x p e r i m e n t ，a n dt h er e s u l t ss h o wt h ef e a s i b i l i t ya n de f f i c i e n c y o ft h em e t h o d i nc h a p t e r2 , w ef i r s tr e f o r m u l a t et h ec o m p l e m e n t a r i t yp r o b l e m ( c p ) a sas y s t e m o ff i x e dp o i n te q u a t i o n s b a s e do nt h e s ee q u a t i o n s ，a ni t e r a t i v ef o r m u l ai sc o n - s t r u c t e d t h e nw ep r o p o s et h ep r o x i m a lp o i n ta l g o r i t h mb a s e do nt h es m o o t h i n g i t e r a t i v ef o r m u l a t h ep r e s e n t e dm e t h o dc o n v e r g e sw i d e l yu n d e rm i l dc o n d i t i o n s s o m en u m e r i c a le x a m p l e sa r eg i v e nt oi l l u s t r a t et h ee f f i c i e n c yo ft h ea l g o r i t h m i nt h el a s tc h a p t e r ，w es u mu pt h er e s e a r c he f f o r t si n t h i st h e s i sa n dg i v ep r o s p e c t s o ft h ef u r t h e rr e s e a r c hi nt h ef i e l d s k e y w o r d s ：c o m p l e m e n t a r i t yp r o b l e m s ，p 0 一f u n c t i o nn o n 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 s ，s m o o t h i n gf i s c h e r - b u r m e i s t e rf u n c t i o n ，p a r a m e t r i cd i f f e r e n t i a t i o nm e t h o d ，t h e f i ) ( e dp o i n te q u a t i o n s ，th ep r o x i m a lp o i 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 福建师范大学硕士学位论文独创性和使用授权 声明尸明 本人( 姓名) 盐剑，学号2 q q 昼q 昼鲤，专业 应用数学所呈交的论文( 论文题 求解互补问题数值算法的一些研究) 是本人在导师指导下，独立进行的研究 阼及取得的研究成果尽我所知，除论文中已特别标明引用和致谢的内容外，本论 否包含任何其他个人或集体已经发表或撰写过的研究成果对本论文的研究工作 出贡献的个人或集体，均已在论文中作了明确说明并表示谢意，由此产生的一切 聿结果均由本人承担 本人完全了解福建师范大学有关保留、使用学位论文的规定，l i p 福建师范大 茸权保留学位论文( 含纸质版和电子版) ，并允许论文被查阅和借阅；本人授权 枣师范大学可以将本学位论文的全部或部分内容采用影印、缩印或扫描等复制 瑟保存和汇编本学位论文，并按国家有关规定，向有关部门或机构( 如国家图书 中国科学技术信息研究所等) 送交学位论文( 含纸质版和电子版) ( 保密的学位论文在解密后亦遵守本声明) 学位论文作者签名：抓场1 指导教师签名： 签字日期：d 7 年6 月f 日 签字日期牛夕夥日 互补问题的模型 绪论 数学规划的创始人g b d a n t z i n g 和他的学生r w c o t t l e 在1 9 6 3 年首先提 出了互补问题第二年，c o t t l e 第一次提出了求解互补问题的非线性规划算法【1 1 互 补问题与变分不等式有着密切的联系，互补问题也可以看作变分不等式的特例互 补问题是指这样的问题，它包含的两组决策变量之间满足一种“互补关系”互补 关系反应了广泛存在的一种基本关系根据问题中变量所满足的条件不同，以及互 补关系的不同形式，互补问题被区分为若干类型由于互补问题的类型繁多，下面列 举几种比较常见类型的数学形式【2 】 1 线性互补问题 令m r ，l x n 是一n 佗实矩阵，q 舻是一n 维矢量，线性互补问题是：寻 求解o 册，满足 $ 0 ，m x + q o ，x t ( m x + q ) = 0 ( 1 ) 线性互补问题被记为l c p ( m ，q ) 如引入矢量y 舒，可= m x + q ，则变量蕊与挑 满足条件甄0 ，玑0 ，戤执= o ， = l ，n 这表明了两组变量 戤) 与伽) 满足 互补关系线性互补问题的基本来源是线性规划与二次规划 2 广义线性互补问题 令m 1 ，m 2 眇n 为两矩阵，pc 舻为一多面体广义线性互补问题是： 求z ，y 舻，满足 z 0 ，y 芝0 ，尬彩一m 2 y 只x t y = 0 ( 2 ) 广义线性互补问题被记为e l c p ( m l ，m 2 ，p ) 3 非线性互补问题 令f ：舒_ 即是由酽到舻的一映射，相应的非线性互补问题是：求矢 量z 舒，满足 z 0 ，f ( z ) 0 ，x r f ( x ) = 0 ( 3 ) 1 福建师范大学林钊硕士学位论文 非线性互补问题被记为n c p ( f ) 当映射f 是线性映射时，即f ( x ) = m x + q ，则 非线性互补问题化为线性互补问题l c p ( m ，g ) 4 广义非线性互补问题 令g ，h ：j _ j p 是两个映射，广义非线性互补问题是：求矢量z 舻，满足 g ( z ) 0 ，h ( x ) 0 ，g ( z ) ? 日( z ) = 0( 4 ) 广义非线性互补问题被记为c p ( g ，明 5 混合非线性互补问题 令g ：研磁_ 研和h ：研磁一冠是两个映射，混合非线性互补问题 是：求u 研，u 磁满足 ， g ( o j ，v ) = o ( 5 ) iu 0 ，日( u ，u ) 0 ，v r h ( u ， ) = 0 混合非线性互补问题被记为m n c p ( g ，日) 6 半定互补问题 令伊表示矩阵空间舒黼中的全部对称矩阵组成的子空间，毋g ( 示s e e 的全 部半正定矩阵组成的子集对于任意x ，y 伊，定义 内积”( x ，y ) ：= t r ( x y ) ，符 号t r 表示矩阵x y 的迹可以证明：鼹是一凸锥，而且满足 霹= y s 帆l ( x ，y ) o ，y x 肆)( 6 ) 令，：伊_ 伊是一映射，半定互补问题是：求x 伊，满足 x 辞，f ( x ) 霹，( x ，) ) = 0( 7 ) 半定互补问题被记为s d c p ( f ，研) 【3 】 应用背景 “互补问题 作为一类新的数学模型，它在工程领域和经济均衡理论等中有着 广泛的应用下面我们做一下简要介绍 1 工程中的互补问题f 4 5 】 2 绪论 互补问题在工程领域中有广泛的应用，其中一个重要的原因是工程中系统平衡 的概念等同于数学上互补的概念下面给出接触问题来简单的说明一下 考虑两个弹性物体a 和b 的接触问题设它们的表面是光滑面，在物体a 的 表面上有n 个点与物体b 的表面上的n 个点组成点对假设在外面的负荷下，两物 体仅有小的变形，且遵守线性弹性律令氐表示两物体第主对点在负荷前的距离，戤 表示第i 对点的接触压力( 沿垂直方向) ，碾和碡分别表示第i 对点沿垂直方向的弹 性形变在外面负荷的影响下，各点对的距离将均匀地减小入因n 个点对的接触压 力与负荷是平衡的，令负荷为厶故有l = 铂 = 1 设弹性形变t 1 = ( u ，记) t 和铲= ( u ；，醒) t 有关系式t 1 = a 1 z ，铲= a 2 x ，其中a 1 和a 2 是对称矩阵，它们的元素表示影响系数令a ：= a 1 + a 2 ，可：= 讲+ 记+ 氏一入，i = 1 ，n ，a o 作为一参数这一弹性接触问题可转化为寻求接 触压力矿，使其满足 z o ，矿= 知+ 占一a e 0 ， ) r 矿= o 其中e = ( 1 ，1 ) t 上式是一参数线性互补问题 2 经济中的互补问题 互补问题在工程领域经济中同样有广泛的应用下面给出一般的价格均衡【明来 简单的说明一下 考虑由若干市场组成的网络模型令表示网络中的结点( 即市场) 个数，二表 示网络中的有向弧的个数，t ( n ) 表示由结点n 出发的弧的集合，日m ) 表示到达结 点n 的弧的集合，表示网络的起点的集合，表示网络的终点的集合，岛表示连 接起点i 与终点j 的所有路的集合，b 表示通过路p 的流量，h = ( k ) 表示所有路 上的流量的矢量，厶表示弧口上的流量，= ( 厶) 表示所有弧上的流量的矢量， 表示结点( 市场) n 上的商品价格，7 r = ( ) 表示价格矢量，c 口( ，) 表示弧口上的运 输费用，c ( ，) 表示所有弧上的运输费用矢量，c p ( ) 表示路p 上的运输费用，) 表示在结点n 的商品的供应量，它是价格矢量丌的函数，上) n ( 丌) 表示在结点n 的商 品的需求量，它是价格矢量7 r 的函数令a = 】表示结点与弧的关联矩阵，其 中4 0 满足 3 令 福建师范大学林钊硕士学位论文 a 他= 三1 ，兰三： = k 撕上 则弧口上的流量厶= k ，路p 上的运输费用勺= d a p c a ( f ) 当给 i 6 i j e j p j = b a 定一个网络后，一般价格均衡问题是寻求价格与流量，满足条件： ( a ) 每条弧口上的流量与价格为非负，即有 厶0 ，d n 0 ，& 0 ，7 i n 0 ，va ，n ( b ) 每个结点佗的供应量、需求量与弧上的流量为守恒，即为 风一& + 厶一厶= o , v n a e t ( n )口日( 哟 ( c ) 如任意一路p 上的流量为正数，则局部价格等于流通价格，即有 0 ，p 号死- i - a p = 乃 f。c。力ot,c+(f，)tat，-，7rt：a。0s何)一。何)一a，=。 4 绪论 互补问题的算法 互补问题的出现引起了人们浓厚的兴趣，特别是8 0 年代中后期，随着科技与经 济的发展，互补问题越来越重要，成为了非线性科学和计算科学研究中的热点问题， 同时也涌现出了许多求解互补问题的有效算法 7 - 1 1 这里简单的作如下介绍： 1 投影法 投影法是求解互补问题的一类基本而又重要的计算方法【1 2 - 1 4 】它源于g o l d s t e i n 【1 5 】和l e v i t i n - p o l y a k 1 e 的求解凸约束优化问题的投影梯度法，包括著名的外梯度 法、逐点逼近法、矩阵分裂法等其基本迭代格式为 矿+ 1 = 矿一a f ( x k ) + 近年来，关于逐点逼近法研究得文献很多f 1 删，例如，k i w i e l 研究了广义逐点逼 近法在求解凸规划问题时的收敛行为k 印a l 趿和t i c h a t s c h k e 研究了不精确的广 规划的内点法，此方法具有多项式时间并具有实用性在此后的2 0 年，内点法的研究 取得了丰硕的成果【2 1 ，矧如今，内点法被推广到求解线性规划问题，线性互补问题， 聊= ( ：) = 0 - m ， 其中x = d i a 9 ( x l ，刃2 ，2 n ) 记z = ( 矿，矿) t 当f 是蜀函数时，j a c o b i 矩 阵v h ( z ) t 是非奇异的给定矿船，此类内点法的一般迭代格式为： + 1 = + 入七 ( 1 1 ) l v 日( 驴) t 魂= 一豆( 矿) ， 福建师范大学林钊硕士学位论文 这里张= ( z 蚕，话) r 为了调节迭代的收敛速度，豆( z 七) 是h ( z 七) 的一个微小 扰动；k 是步长因子，它的选取要使下一个迭代点z k + 1 硌，且效益函数有一定 量的下降一般采用线搜索或信赖域确定k 的值【2 3 3 非光滑牛顿法 非光滑牛顿法始于2 0 世纪9 0 年代初期，随着人们对非光滑研究得不断深入， 该方法的研究得到迅速的发展【2 4 1 求解互补问题的光滑牛顿法的基本思想是将互补问题转化为一个与之等价的非 光滑方程组，然后利用广义牛顿型方法( 如b 可微阻尼牛顿法或半光滑牛顿法等) 求解其算法的一般框架是： ( 1 ) 将互补问题转化为一个非光滑方程组 霍( z ) 拳 = 0 ( 1 2 ) 其中妒：r r 是某个n c p 函数 ( 2 ) 用广义牛顿型方法求解非光滑方程组皿( z ) = 0 ( 3 ) 对为了得到算法的全局收敛性，用线搜索方法极小化适合的效益函 数( 如i i 皿( z ) 1 1 2 或i i 皿 ) 1 1 ) ，选取合适的步长因子 本文主要工作及内容安排 互补问题和广义互补问题为运筹学、工程等领域的热门课题，研究这些问题的 求解方法不但在理论上具有重要价值，而且有广泛的应用前景本文的主要内容安 排如下： 第一章，将非线性互补问题转化为一个与之等价的方程组，由于互补函数的特 殊性，所得到的方程组往往是非光滑的通常需要用光滑的方程组去逼近原方程互 补函数的选择不同，效果不同f i s c h e r - b u r m e i s t e r 函数有很多好的性质，只在孤立 点( 0 ，0 ) 不可导，为此引入光滑参数，得到光滑f i s c h e r - b u r m e i s t e r 函数，在此基础 上建立求解互补问题的参数微分法 6 、，、，、， 只 b r l 2 n 仇慨 够 够 够 ，j-。一 绪论 第二章，由投影【】+ 的基本性质，互补问题o p ( f ) 等价于下面的不动点方 程z k 一口f ( z ) 】+ ；0 ，这里a 为任何正数利用上述不动点方程构造了迭代公 式z k + l = 陋七一a k f ( z k + 1 ) 】+ ，后6k 迭代公式中的x k + l 是由隐式求出，实际计算 时比较困难，于是将迭代公式光滑化求解在此基础上提出求解互补问题的逐点逼 近算法，并在f 是伪单调的假设下证得算法是全局收敛的 最后一章，对本文的工作进行了总结，并对今后的工作做了展望 7 第一章求解局一函数非线性互补问题的参数 微分法 本章讨论求解岛一函数非线性互补问题的参数微分法我们将岛一函数非线性互 补问题( n c p ( f ) ) 转化为求解一个等价的非线性方程组由于转化后的非线性方 程组相应的非线性映射一般是非光滑的，因此利用光滑化的f i s c h e r - b u r m e i s t e r 函 数构造与n c p ( f ) 等价的光滑方程组在此基础上建立求解n c p ( f ) 的参数微分 法数值实验表明，这一方法是有效的 19 1 引言 非线性互补问题( 简记为n c p ( f ) ) ：求名舻，使得 g 0 ，f ) 0 ，x t f ( x ) = 0 ，( 1 1 1 ) 其中f ：舻_ 即是一个给定的函数本章我们假设f 是连续可微岛一函数 众所周之，n c p ( f ) 等价于方程组 皿( z ) = 0 ， 这里皿：舻_ 舻的一个半光滑函数 b u r m e i s t e r 函数【2 5 】 伽( o ，6 ) = 口+ b 一“巧万 和 皿( z ) = = 0 ( 1 1 2 ) 这样的函数是可以得到的，比如，f i s c h e r - ( 1 1 3 ) 容易证明仍旧( o ，b ) = 0 成立当且仅当a o ，b 0 ，a b = 0 f i s c h e r - b u r m e i s t e r 函 数在除原点外的任意一点是可导的，在原点是半光滑的为此引入光滑参数，得到光 9 p p p 毋 毋 晶 1 2 b 忆 b b b 朋 朋 胎 惦 惦 地 ，-i-i、 福建师范大学林钊硕士学位论文 滑f i s c h e r - b u r m e i s t e r 函数 2 6 - - 2 8 ( p ，口，6 ) = a + b 一“西丽 这里参数弘 0 易知，( 0 ，a ，b ) = c v b ( a ，6 ) 接下来，我们介绍几个有用的定义和结论 ( i i 4 ) 定义1 1 ： ( 1 ) 矩阵m 舻n 被称为p o 一矩阵，如对任意z 舻，。0 ，存在 一分量0 ，使得 x k ( m x ) k 0 ( 2 ) 函数f ：舻_ 形被称为p o 一函数，如对任意z ，y 舻，历y ，存在一个下 标 o n ，使得 其中 y i 。，( $ 幻一鼽。) 【 ) 一r ( ) 】0 令名= ( p ，z ) r + + 兄p 和 g c 彳，：= g 似，z ，= ( 西。：z ，) = 。， 圣( p ，z ) = ( p ，x l ，日( z ) ( p ，x 2 ，岛( 刀) ( p ，z n ，r ( z ) 因而，n c p ( f ) ( 1 1 1 ) 等价于下面的方程： o ( z ) = 0 ( 1 1 5 ) ( 1 1 6 ) ( 1 1 7 ) 通过具体的计算，不难得到g 在墨斗尼。连续可微，且其j a c o b i 矩阵为 6 y c 名，= ( 影：，上) 。z ，+ 三。z ，j 。z ，) ( 1 1 8 ) 第一章求解岛一函数非线性互补问题的参数微分法 其中 t ，( 名) ：= 、伧c 仇( z ) = 以( p ，$ i ，皿( z ) ) ：蕾) ， d r ( z ) ：= m a g a l ( z ) ，眈( z ) ，( z ) ) ， d 2 ( z ) ：= d i a g 6 ( z ) ，6 2 ) ，6 n ( z ) ) 及 比) = 1 - 万翥等雨 ( 1 1 9 ) 啦( 名) = 1 一了菘矛i 鞴，6 ) = 1 一了菘尹翻( 1 1 1 。) 不难发现 - 1 ( 石) 0 ，0 锄( 2 ) 2 ，0 玩0 ) 2 ( 1 1 i i ) 成立对于所有i = 1 ，2 ，n 引理1 2 ： 令g ：舻+ 1 _ 尼i + 1 ，圣：舻+ 1 _ 舻分别由( i i 5 ) 和( 1 1 6 ) 定义， 则 ( a ) 西在名= ，。) 舻+ 1 ，p 0 连续可微 ( b ) g 在名= ( p ，$ ) r + + 舻连续可微，它的j a c o b i 矩阵由( 1 1 8 ) 定义如 果f 是蜀函数，则矩阵( z ) 在且h 舒非奇异 证明：结论( a ) 的证明简单以下证( 6 ) ，由( 1 1 5 ) 和( a ) 得到g 在皿+ 舻连 续可微由( 1 1 1 1 ) 得到对所有z = ( p ，z ) 风+ 尼。，d t ( z ) 和z ) 2 ( z ) 是正定对角 矩阵由( 1 1 8 ) 为了证g ，扛) 是非奇异的，我们只须证明矩阵d l ( z ) + d 2 ) 0 ) 是非奇异的事实上，因为f 是蜀一函数，所以f 7 0 ) 是岛一矩阵对于所有z 忍 由d 2 ( 名) 是正定对角矩阵知矩阵d 2 ( z ) f ，( z ) 的所有主子式是非负的由定义( 1 1 ) 知，矩阵d 2 ( z ) f ，( z ) 是非奇异的，则矩阵g ，( z ) 也是非奇异的这样，结论( b ) 得证 1 2 同伦法 我们知道，用牛顿法求解非线性方程组，其收敛速度是相当快的，在适当的条件 下，该方法有二阶收敛速度但牛顿法对迭代的初值要求很苛刻，如果初值不在牛顿 1 1 福建师范大学林钊硕士学位论文 迭代的收敛域内，该方法失效可是与线性方程组的求解相比，非线性问题迭代求解 时的初值选取有相当的难度同伦延拓法扩大了初值的选取范围【2 0 】 同伦是代数拓扑学最基本的概念之一下面给出它的完整定义 定义1 3 ：设x 与y 是拓扑空间，f o ，f l ：x y 是连续映像，记【0 ，1 】，若 存在连续映像h ：x ，_ y ，使得对一切z x 成立h c = ，0 ) = f o c z ) ，日( z ，1 ) = f l c x ) ，则称f o 同伦与 ，记为f o 掣 ：x _ y ，称映像h 为从f o 到 得同伦 或伦移，记为h ：f o 型f l ：x y 或 墨 考虑f ：dcj 沙一j 护，求f ( z ) = 0 的一个解矿d 同伦法的基本思想是 引入参数t ，构造一函数簇h ：d 【0 ，1 】c 舻+ 1 一俨代替单映射f ( z ) ，使日满 足条件： 日( z ，0 ) = f o ( 。) ，日( 。，1 ) = f ( z ) ，v 。d 假设昂0 ) = 0 的解已知，从t = 0 出发可以求解 日( z ，t ) = 0 ( 1 2 1 ) ( 1 2 2 ) 对于t 【0 ，1 】，假设( 1 2 2 ) 的解为z ( 亡) 如果窭( 亡) 可以形成舻中的一条光滑曲线， 其起点茁( o ) 为r ) = 0 的解，根据假设它是已知的，曲线z ( t ) 的终点z ( 1 ) 正是我 们要求的矿，日( z ，t ) 称为一个同伦，它的解z ( 亡) 称为同伦曲线 构造h ( x ，t ) 的方法有多种，例如 日0 ，t ) = t f ( z ) + ( 1 0 f 0 0 ) 其中f 0 0 ) 为一非常容易找到零点的函数再如 h ( x ，亡) = f ( z ) + 一1 ) f o ( z ) 其中z o 舻为一任意选定的向量还可以取 日( z ，t ) = f ( z ) 一e - ( x ) 在这种情况下，必须舌一0 0 才能得到原方程的解 1 2 ( 1 2 3 ) ( 1 2 4 ) ( 1 2 5 ) 第一章求解蜀一函数非线性互补问题的参数微分法 1 3 参数微分法 本节建立求解方程( 1 1 5 ) 的参数微分法我们利用方程( 1 2 4 ) 构造同伦方程 如下： h ( z ，t ) = g ( z ) - i - 一1 ) o ( z o ) = 0( 1 3 1 ) 其中名o = ( 脚，护) 蜀+ j p 是任意选取的初始点容易发现 h ( z ，0 ) = g ( z ) 一g ( 严) = 0 ( 1 3 2 ) 的解是平凡解，即，而 h ( z ，1 ) = g ( 名) = 0( 1 3 3 ) 的解z = ( 0 ，矿) 即为方程( 1 1 5 ) 的f g ，其中矿为n c p ( f ) ( 1 1 1 ) 的解现在把求 解方程( 1 1 5 ) 变成求同伦方程 h ( z ，亡) = g ( z ) - t - 0 1 ) g ( 矿) = 0 ，t 【o ，1 】，名r + + 月：，i ( 1 3 4 ) 的解名= z ( t ) ，这里名：【0 ，1 】_ 风+ 2 连续依赖于t ，当t = 0 方程( 1 3 4 ) 的 解矿为已知，当t = 1 时，方程( 1 3 4 ) 的解z = z ( 1 ) 就是方程( 1 1 5 ) 的解 对于同伦方程( 1 3 4 ) 映射z ：f 0 ，1 】一r h 舻是连续可导的，且日对z 和t 有 连续的偏倒数也和风，定义 ( t ) = 日( z ( t ) ，力，vt 【o ，1 】( 1 3 5 ) 则在【0 ，1 】上连续可导，且 ) = 也( z ) ，亡) 7 ) + 凰( 名 ) ，t ) ，v 亡【0 ，1 】 注意到上乙( z ( 亡) ，t ) = g 7 ( z ( 古) ) ，风0 ( t ) ，亡) = o ( z o ) 于是上式等价于 ) = g 0 ( 力) 7 ( t ) + c ( z o ) ，vt 【0 ，l 】 因名= 名( t ) 满足( 1 3 4 ) ，故对所有t 【0 ，1 】有i j c ) = 0 ，于是名( 亡) 满足微分方程 g 7 0 ( 亡) ) ( 亡) = 一o ( z o ) ，v 亡【o ，1 】 ( 1 3 6 ) 1 3 福建师范大学林钊硕士学位论文 反之，若名：【0 ，1 】_ r + + x 即是微分方程( 1 3 6 ) 的解，并满足五x c z ( o ) ，0 ) = 0 ，则 由中值定理，得 1 1 日( z ( 亡) ，0 1 l = i l ( 亡) 一( o ) 0 s u pi i ( s ) i l = 0 这表明日( z ( 亡) ，t ) = 0 ，即微分方程( 1 3 6 ) 在初始条件h ( 4 0 ) ，0 ) = 0 时的解 为z = z ( 亡) ，并给出了同伦方程( 1 3 4 ) 的一个解根据引理1 2 ( 6 ) 知g 7 ( z ( 亡) ) 对任 意t ( 0 ，1 ) ，z = ( p ，。) r + + 舻是可逆的，且日( z o ，0 ) = 0 则求方程( 1 3 4 ) 的 解z = z ( 亡) ，等价与求微分方程 善掣_ - 【瞅) ) 】_ 1 g ) ( 1 3 7 ) iz ( o ) = 矿 的解 引理1 4 ： ( 摄动引理) 设a ，b 舻x l l , a 可逆，且i ia qj i - - - a 如果0 a b0 p ，叩 1 ，则b 也是可逆的，且 i i 矿i i 0 易知g ，( z ) 在z 0 处连续因此，对v0 s 0 使当z s 时有 i i c ( z ) 一g 7 ( z o ) i | s 则由引理1 4 可知，对vz s g 秽( 名) 。1 i i h = p 1 28 1 4 第一章求解r 一函数非线性互补问题的参数微分法 定理1 1 ：( 反函数定理) 设f ：dc 舒_ 舻在z o i n t ( d ) 处有强f 一导 数，f 7 ( 护) 非奇异，则f 在护处为局部同胚映射并且，如果u 是护的任一开领 域，f 是u 上的一对一映射，而是f 在u 上的限制，那么，f u l 是在f ( x o ) 处有 强f 一导数，且 巧1 ( f ( 护) ) = 【f ( 扩) 】 下面的定理表明同伦方程( 1 3 4 ) 存在唯一解z = 名 ) 且名( t ) 满足微分方 定理1 2 ：设映射g ：日廿舻_ 舻+ 1 由( 1 1 5 ) 所定义，则方程( 1 3 4 ) 即c c z ) = ( 1 一句g ( z o ) ，t 【o ，1 】，z s 存在唯一解名：【0 ，1 j _ sc 凰+ 酽 且2 (