（应用数学专业论文）解极小化问题的块松弛—牛顿法.pdf

摘要 摘要 本文研究了求解约束及其无约束极值问题的迭代方法，研究的主要内容是结合 j a c o b i n e w t o n 迭代法和s o r n e w t o n 迭代法这两类迭代法所构成的块j a c o b i n e w t o n 迭代法和块s o r 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 迭代法的算法，并给出了 其收敛性的证明。 第二部分探讨了以非线性s o r 迭代法为基本迭代法，以n e w t o n 迭代法为辅助 迭代法的s o r n e w t o n 迭代法，将求解线性函数的逐次迭代法与解非线性函数的 n e w t o n 法相结合，形成复合n e w t o n 法，用于求解非线性无约束最优化问题和一些 约束最优化问题，给出相应的块s o r n e w t o n 迭代法的算法及其收敛性。 第三部分，结合我们提出的块j a c o b i n e w t o n 迭代法和块s o r n e w t o n 迭代法， 给出了在具体实例下的数值计算结果，从所得的结果中证明了将问题进行分块计算 时能够减少利用n e w t o n 法求j a c o b i 矩阵的逆的计算工作量。 关键词：s o r 迭代法；块j a e o b i n e w t o n 迭代法；块s o r n e w t o n 迭 代法 a b s t r a c t a b s t r a c t a ni t e r a t i v em e t h o df o rs o l v i n gc o n s t r a i n ta n du n c o n s t r a i n te x t r e m ep r o b l e mi ss t u d i e d i n t h i sp a p e r t h em a i nc o n t e n ti st ou s et h ei t e r a t i v em e t h o dt os o l v et h em i n i m i z a t i o n p r o b l e mo fn o n l i n e a rf u n c t i o n ，c o m b i n i n gb l o c kj a c o b i n - n e w t o ni t e r a t i v em e t h o da n d b l o c ks o r - n e w t o ni t e r a t i v em e t h o dw h i c ho r i g i n a t e df r o mj a c o b i n - n e w t o ni t e r a t i v e m e t h o da n ds o r n e w t o ni t e r a t i v em e t h o dr e s p e c t i v e l y t h i sp a p e rc o n t a i n st h r e ep a r t s ： f i r s t l y , j a c o b i n - n e w t o ni t e r a t i v em e t h o d ，w h i c ht a k e sl i n e a rf u n c t i o ni t e r a t i v em e t h o d a sb a s i ci t e r a t i v em e t h o da n dn e w t o ni t e r a t i v em e t h o da sa s s i s t i n gi t e r a t i v em e t h o d ，i s i n t r o d u c e d t h e nu n c o n s t r a i n to p t i m a le x t r e m ep r o b l e mi ss o l v e db a s e do nt h i sm e t h o d e s p e c i a l l y w h e nn o n l i n e a rf u n c t i o nh a sp a r t i c u l a r f o r m ，t h ea l g o r i t h mo fb l o c k j a c o b i n - n e w t o ni t e r a t i v em e t h o di sa c h i e v e da n di t sc o n v e r g e n c ei sp r o v e d s e c o n d l y , s o r - n e w t o ni t e r a t i v em e t h o d ，w h i c ht a k e sn o n l i n e a rs o r i t e r a t i v em e t h o d a sb a s i ci t e r a t i v em e t h o da n dn e w t o ni t e r a t i v em e t h o da sa s s i s t i n gi t e r a t i v em e t h o d ，i s d i s c u s s e d c o m p o u n dn e w t o nm e t h o d ，w h i c ho r i g i n a t e sf r o ms u c c e s s i v ei t e r a t i v em e t h o d u s e dt os o l v el i n e a rf u n c t i o na n dn e w t o nm e t h o du s e dt os o l v en o n l i n e a rf u n c t i o n ，i s i n t r o d u c e dt os o l v en o n l i n e a ru n c o n s t r a i n to p t i m a lp r o b l e m sa n ds o m ec o n s t r a i n to p t i m a l p r o b l e m s t h e nt h ea l g o r i t h ma n dc o n v e r g e n c e o fb l o c ks o r n e w t o ni t e r a t i v em e t h o di s a c h i e v e d f i n a l l y , n u m e r i c a lc a l c u l a t i o nr e s u l t s ，w h i c hu s et h eb l o c kj a c o b i n - n e w t o ni t e r a t i v e m e t h o da n db l o c ks o r n e w t o ni t e r a t i v em e t h o d ，a r ep r e s e n t e d t h er e s u l t sp r o v et h a ti t i sa b l et od e c r e a s ec o m p u t a t i o n a lc o m p l e x i t yw h e nc o m p u t i n gt h ep r o b l e mb yb l o c k s k e yw o r d s ：s o rl t e r a t i v em e t h o d ；b l o c kj a c o b i - n e w t o ni t e r a t i v em e t h o d ；b l o c k s o r n e w t o ni t e r a t i v em e t h o d 学位论文独创性声明、学位论文知识产权权属声明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文 中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意 义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论 文或成果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名： 杀b 砖。 学位论文知识产权权属声明 日期：矽许囱7 日 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本 人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单 位仍然为青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保仑彩 ( 请在以上方框内打“”) 论文作者签名：井勿冲 日期：芦抨白7 h 翩躲嗽型，嗍沙盼歹月” ( 本声明的版权归青岛大学所有，未经许可，任何单位及任何个人不得擅自使用) 引言 引言 在自然科学、社会科学、生产实践、工程设计和现代化管理中有许多实际问 题，需要从众多的方案中选出最优方案，这即是最优化问题。最优化理论与方法 是从上世纪四十年代蓬勃发展起来的用来解决最优化问题的一门独立的学科。根 据不同的分类方法，最优化问题可以分为线性规划，非线性规划，整数规划，动 态规划，多目标规划等，其中很多问题最后都可以转化成无约束优化极值问题和 约束优化极值问题来求解。本文主要研究求解无约束及其约束优化极值问题。 无约束最优化的一般形式为 m i n f ( x ) x r ” ( 1 ) 它的极小值问题可归结为夥( 工) = 0 ， 即 缸，川= 。 善( 矿巾= 。 善( 一，) ：o o x ( 2 ) 其中v f ：r ”一尺“，石= ( 五，) r ，彳为二次连续可微的( f = 1 ，以) 。 约束最优化问题的一般形式为 m i n f ( x ) ( 3 ) s t ( 力= 0 i e ( z ) 0 i i 这里的e 和，分别是等式约束和不等式约束的指标集，蜃( 石) 是约束函数。 本文研究求解无约束及约束优化的极值问题时，我们利用块j a c o b i n e w t o n 法 卜4 】、块松弛牛顿法( s o r n e w t o n ) 5 - s 1 等一系列方法进行求解。 s o r 迭代法用作辅助迭代法已有很多年了，b e l l m a n ，k a l l b a 9 1 ，g r e e n s p a n 10 1 ， g r e e n s p a n ，y 0 h e 【l l 】，g r e e n s p a n ，p a r t e r 1 2 1 以及o r t e g a ，r h e i n b o l d t 1 3 1 ，还有其他人 提出了很多分析和计算结果【1 4 1 6 】，它的基本形式可做如下表示： 如果f ：r ”一r ”有分量彳，石，设当前的近似解为= ( # ，) r ，对于 f 1 ，n ，非线性s o r 迭代法的基本步骤是从第f 个梯度公式中 青岛大学硕士学位论文 v f , ( 群+ 1 ，五k 小+ l ，l ，一，) = 0 ( 4 ) 解出，并令# “= # + q ( 玉一# ) ，于是为了从得出x “1 ，我们依次解n 个一元非线性方程组( 4 ) ，f _ 1 ，n 。当c o , = 1 时，则可以得到一个非线性 g a u s s s e d i a l 迭代法，此时r “= x t 。 注意，仅当方程( 4 ) 在某一个所考虑的特殊区域内有唯一解时，上面的做 法才有意义，但是甚至当这些方程有唯一解时，一般说这些解没有显式的表达式， 或者不能用一个有限的算法得出它们，而必须用一维迭代法。n e w t o n 法是我们 所熟知的解非线性方程组一个著名的迭代法，如果用一维n e w t o n 法来求解( 2 ) 的一个近似解，那么牛顿法起辅助迭代的作用，而现在s o r 是基本的迭代法， 因此现在n e w t o n 法和s o r 法在我们所熟知的方法中所起的作用正好相反，原则 上我们能把s o r n e w t o n 迭代法写成类似于n e w t o n s o r 迭代法的显式公式，在 这个方法中对( 2 ) 式作n e w t o n 法，得出一个近似解毫，并令# + 1 等于 # + ( 毫一# ) ，但是这些公式变得相当繁琐，我们将注意力局限于一步 s o r n e w t o n 迭代法( 当缈= l 时，它便是g a u s s s e d i a l n e w t o n 法) ，在这个方法 中，m = 1 ，f = 1 ，n ，k = 7 l ，其中是在第k 步上s o r 迭代法的总次数，并且 从# 出发进行n e w t o n 迭代，这种情形相当于求解适度的非线性椭圆边值问题 a u = 厂( x ，y ，“，u x ，“。) 的离散近似，b e l - s 1 7 首先严格的讨论了非线性g a u s s s e d i a l 迭代法，最近s c h e c h t e r 1 8 ，19 1 ，o r t e g a ，r o c k o f f 2 0 1 ，o r t e g a ，r h e i n b o l d t 【2 1 1 和其它著 者研究了这种方法，此时容易验证迭代法的显式是： # + 1 = # 一国( v ；z ( 石t ) ) 。1 v f , ( x t ) f = 1 ，n ，k = 7 1 ( 5 ) 其中我们令 # 。= ( 矸”，誓k 一+ 。l ，# ，) r ( 6 ) 在迭代法( 6 ) 中，我们当然也可以利用其它的一维迭代法来代替n e w t o n 法，例如对应于( 6 ) ，我们可以将一步s o r 正割法写成 x i t m # 叫坠笠型掣) - l 咻) ( 7 ) 或者将一步s o r s t e f f e n s e n 迭代法写成 2 引言 x k + l 扣( 型掣广w j ) ( 8 ) 其中x k , t 仍然由( 4 ) 来确定。但是根据渐进收敛速度和数值实验所得出的计算量 的结果来看，一步s o r n e w t o n 迭代法是目前所讨论的s o r 法中最有效的方法， 因此本文主要研究求解约束最优化极值问题的s o r n e w t o n 迭代法的算法及收 敛性质。在第二章中给出了当非线性函数具有特殊的形式即可分块时，我们将此 方法用于求解最优化问题的极小值，结合此形式给出了块形式的s o r n e w t o n 迭 代法，并证明了算法的收敛性，在第三章中给出了非线性函数的最优化问题具有 可分块形式时相应的数值实验结果。 由线性方程组j a c o b i 迭代法知其分量形式为： 岛一口f x ； # “= = l f ， i = 1 ，靠，k = 0 , 1 ， 这相当于从第f 个方程求出t ，而其余的工，保持取值石；。因此，非线性j a c o b i 迭代法的第k 步依次求解梯度等式： w ( 彳，。，玉，i ，一，) = o ， i = 1 ，n ( 9 ) 的解_ ，并令x ，= t ，i = 1 ，n 。 于是，为了从x 得出石“1 ，需依次解n 个一元非线性梯度等式( 9 ) ， i = 1 , 2 ，n ，如果用n e w t o n 法来求( 9 ) 的一个近似解，n e w t o n 法起辅助迭代 的作用，而j a c o b i 迭代则成为基本迭代，这就是j a c o b i - n e w t o n 迭代法。可见， 这里n e w t o n 法和j a c o b i 法和它们在前面所起的作用也正好相反。 类似的，一步j a c o b i n e w t o n 迭代法可表示为 # + 1 = # 一( v ；彳( ) ) 一w ( ) ( 1 0 ) i = 1 ，z ，k = 0 ，1 它恒等于一步n e w t o n j a c o b i 法。 在迭代法( 1 0 ) 中，我们同样可以利用其它的一维迭代法来代替n e w t o n 法， 类似于( 8 ) ，我们可以将一步j a c o b i 正割、法【2 2 1 写成 x k + l 一- - - # - - c o ( 型鼍骞棼幽) _ l 咻) ( 1 1 ) 或者将一步j a c o b i s t e f f e n s e n 迭代法写成 青岛大学硕士学位论文 x k + l 扣( 型攀警幽) - l 咻勺 ( 1 2 ) 其中矿仍然由( 4 ) 来确定。对于j a c o b i 迭代来说，最有效的仍然是将其与n e w t o n 迭代法结合，本文在第一章中给出了具有特殊形式的非线性函数的最优化问题求 解的块j a c o b i n e w t o n 迭代法，并在第三章中给出了相应的数值实验结果。 4 第二章解极小化问题的一种复合n e w t o n 法 第一章无约束极值问题的j a c o bi - 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 迭代法求解会更好， 给出了具体的算法，并进一步证明了其收敛性。 1 1 引言 无约束极值问题如下 m i n f ( x ) x r “ 叱譬 其中a 口是咒f 以矩阵，而，l = 以l + + 刀。， 。=ai：1兰耋。，三=一至；：彳!三一。至 ，u = 一 0 a 1 2 彳l 00 a 。一1 。 o oo 块j a c o b i n e w t o n 迭代法可以自然地推广到非线性函数的极小化问题上。将 o f ( x 。) = d k 一厶一巩分成块形式，考虑问题( 1 1 1 ) 的分块子问题 m i n f ( ( 0 1 1 工r ”( 1 1 2 ) 其中向量如下分块：将向量x = ( 而，x ：，x 。) 作分块，记子向量为力，( ，= 1 , 2 ，三) ， x = ( q ，缈2 ，吼) 。v f 的梯度分量v f , 对应地组成映射v f ：r “专尺“，梯度 可( x ) = 颗( z ) ，v a ( 功，既( 功) 称为可分块的，若存在一向量的分块 x = ( 缈。，缈：，吼) ，使( x ) = ( q ) ，把w 的梯度分量w 对应地组成映射 青岛大学硕士学位论文 v f , ：r ”专r 啊便可以把非线性j a c o b i n e w t o n 迭代法推广成块形式。 一步块j a c o b i n e w t o n 法的迭代公式： 西“= 钟一( v ；石( 钟) ) 一v f , ( 钟) ，= 1 ，l ，k = o ，l 1 ( 1 1 3 ) 其中v ；石( 国；) 表示作为钟的函数关于硝的j a c o b i 矩阵。 1 2 算法与性质 当其满足二阶最优性条件时，我们有如下的算法 算法1 2 1 将x 分为m 块，记为z = ( q ，国：，吼) ，对梯度v f , 进行相应的分块，使得 耵( 工) = w ( x ) ，( z ) ，v f , ( z ) ) ，给定参数q o ，乞 o ，口 2 ，7 7 k ：= 0 ， 初始值x 0c o ，占 0 。 步1 ：= ( 讲，磋) ，以x o 为初始点，用j a c o b i n e w t o n 迭代求解方程组 硝+ 1 = q k 一( v ，k m 姊k ) ) 。1 ( 硝) ，得 西“) ，对，= 1 ，三； 步2 ：若0 西+ 1 一钟0 s ，继续；否则，4 - k ：= 后+ 1 ，转步1 ： 步3 ：0 ) ：= 钟，= 1 ，l ，此时，“：= ( 群“，磋“) ； 步4 ：名= v f ( x t m ) 8 q x ：= 矿，停止。 引理1 2 1 【2 3 1 设g ：dc 7 r ”一r ”有一个不动点x ，并且在工是f 可微的。 如果g ( 石) 的谱半径满足p ( g ( x ) ) = 盯 o ，由f 的f 可导性，则存在一个常数刁 o ，使得 i i 蜀( 石) 0 7 i l z x 木0 b k s 1 对，= 1 ，我们有0 g 。 ) - g ，( 石) 1 1 - 0 ，记q = ( 钟，) ，仍称 第二章解极小化问题的一种复合n e w t o n 法 州= 嘭( x ) ，k = o ，i ，1 ( 2 2 5 ) 其中松弛因子国= ( 钟，戤) ，啄：dc r ”专r ”。 2 3 等式约束最优化问题的算法 考虑具有等式约束的最优化问题【2 4 】 m i n f c x ) “g ( x ) = 0 其中f ：r 4 寸r ，g ：r ”一r 。具有连续的二阶偏导数。 问题( 2 3 1 ) 的l a g r a n g e 函数为 l ( x ，力) = ( x ) + 旯r g ( x ) ( 2 3 1 ) ( 2 3 2 ) 在本节中，我们假定在x r ”处，最优化问题( 2 3 1 ) 满足如下二阶充分 条件： 了五+ r 使得 觇( x ，五) = 0 对于满足d 7 v g , ( x + ) = o ，i = l ，k 的d r ” o ，成立 d r v 2 三( x ，五。) d 0 其中v 厶v 2 三分别表示作为x 的函数的梯度和h e s s e 矩阵。 问题( 2 3 1 ) 的增广l a g r a n g e 函数为 ( 2 3 3 ) ( 2 3 4 ) p ( x ，a ，c ) = 厂( x ) + 五7 g ( x ) + 2 9 ( x ) r g ( v ) ( 2 3 5 ) 其中c 0 。求解( 2 3 1 ) 的乘子法的每次迭代中求解 卯( x ，2 k , c 。) = 0 ( 2 3 6 ) 青岛大学硕士学位论文 得到x “1 ，并设力“1 = 兄+ c 。g ( x n l ) ，此时成立 v l ( x k + l , 五“1 ) = 0 在本节的条件下，对适当的c 0 ，v 2 尸( x ，兄，c ) = 0 是j 下定的，根据上一节 的讨论，可以用b s o r - n 迭代法求解问题( 2 3 6 ) ，形成解等式约束最优化问题 ( 2 3 1 ) 的b s o r n 一乘子迭代法 2 5 - 2 7 】。 b s o r - n - 乘子迭代法步骤如下： 将x 分为m 块，对v p ( x o 五o ，c o ) ，v 2 p ( x o ，五o ，c o ) 进行相应的分块，确定 彩。= ( 群，k ) 的选取方法，给定参数q o ，乞 o ，口 2 ，7 o ，尼：= 0 ，初 始值x o ，五0c o ，占 0 。 步1 ：x 枷：= x 2 ，以栅为初始点，用b s o r - n 迭代求解方程组 v p ( x ，五k ，c k ) = 0 ，得 x 盯 ，对f _ 1 ，聊，0 一x y s ，z “l ：= x 州“) 。 步2 ：五= 兄+ c 。g ( x + 1 ) ，i = l ，m 步3 ：若忙( x “) 0 6 1r v l ( x k + l , 允“1 ) o ) ，或者 有占。= 岛= o ，算法产生一个无穷点列 ( x ，五。) ) ，使得 ( x ，a ) 斗( z ，五) 。 1 2 第二章解极小化问题的一种复合n e w t o n 法 2 4 等式约束优化的收敛性 对于迭代( 2 2 5 ) ，我们有如下引理： 引理2 4 1 2 3 1x c f f d 可a l ( r ”) 和任给占 0 ，总存在一种范数i | | i ，使 。 p ( 彳) i i 彳0 p ( 么) + 占 定理2 4 1 设dcr ”为开区域，国= ( q ，) ，在d 内f 可微，满足 0 瓯，( z ) 一g 二( x ) 0 三0 国7 一国0 ，v x d 且存在x d ，使得x = 瓯( x ) ，p ( g 二( 工) ) 0 ，使s = s ( x + ，6 ) cd ，对 v x s ，有 i i g o ( x ) - g o ( x ) - a g ( x - x + ) 怿忙一x 1 1 i 粉( x ) - g ( x ) 0 粉( x ) - g ( x ) + g ( x ) - g ( x ) 0 - i i g 。，( x ) 一瓯( x ) 0 + i l 瓯( x ) 一瓯( x ) 0 三忖- c o + ( o r + 2 占) x - x 0 由c o 。一国，而g r + 2 占 o ，i i r ，( x ) 0 qx - x 幸0 ，v x s 1 对，= 1 ，得0 吒。( 石) 一。( x + , i - c ll l x - x * | l ，地s 1 ，其中c l 为常数 用归纳法证得0 g ，( x ) - g ， ) 1 1 - - c l 忙一石乖0 坛s 1 ，有 i r i ( 工) 一工l l c ：卜z 木0v x s 1 由前边 a ，石( 石) g ，( x ) - g ，( 工) = a l f i ( x + ) ( 口，一口；) 一q a ，乃( 尺7 ( x ) ) ( 尺7 ( x ) - - x ) - q ，( z ) ，= 1 , 2 ，l 其中 q i ( x ) = ( a ，石( x ) - 0 ，f a x ) 【g ，( 功一q ( 工) - - ( 0 i , 1 - - l t f , 1 。) - o ) i r i ( r 7 ( 石) ) ， 这又等价于 d ( x ) 一a l ( x ) 吒小) 一吃：序+ ) 】 = ( 1 一a ) d ( x ) + a u ( x ) 】( z 一工) 一g ( x ) 其中g ( 石) = ( q l ( x ) ，g ( x ) ) r 综坷得溉岗圳乩2 ，三 溉险警铲型锪醴箦尸= 。 我们得到了h ( x + ) = o g o , ( x ) ，定理得证。 设f ( x ) 在x d 满足二阶充分最优条件： 耵( x ) = 0 ，且v 2 f ( x ) 正定，则对于f ( x ) = v f ( x ) 以及由( 2 4 1 ) 确定 的迭代矩阵h ( x ) 满足定理1 的条件：p ( h ( x ) ) 1 ，我们有以下结论。 青岛大学硕士学位论文 定理2 4 3 设a f ( x ) = d ( x ) 一三( x ) 一u ( x ) ，h ( x ) 由( 2 4 1 ) 确定， 人= a ( 缈) = d i a g ( ( ) 1 k l ，吃) 0 q 2 ，若o f ( x ) 正定，则有p ( h ( x + ) ) 0 记 = 口，由于o f ( x ) 正定，所以 = = 口， 所以& = 箐制2 = 1 ( o r - c 面o i l - r 国f i t ) 2 仃+ 以口 -u i 仃+ 口 。 ( 仃一哆盯一c o , a ) 2 一( 盯+ q 口) 2 = c o ：r ( o + 2 a ) ( c o 一2 ) 0 由此得对任给兄均小于1 ( o 咀 2 ) ，所以结论得证。 由此就可以保证算法的收敛，在实际计算中可以在l l x 川一x l l 占成立后让 算法的迭代停止。 1 6 第三章算法的数值实验结果 第三章算法的数值实验结果 本章利用m a t l a b t 3 6 1 对论文提出的算法做了一系列的数值实验，将算法应用 于具有特殊形式的无约束及约束最优化问题上，得出了比较满意的结果，说明了 这样的算法是比较有效的。 3 1 无约束最优化的例题 无约束最优化问题 m i n 厂( x ) 其中厂( x ) = 丢y r a y + l z 7 b z + 1 又= ( 鬲，瓦) r = ( 0 1 ，0 2 ，0 1 ，0 2 ，0 1 ，0 2 ) r ， y = x j ，z = f i x , 一夏) 2 ，( 一- 6 ) 2 ) r ， a = 64 0 41 4o oo2 0 009 o0o 00o oo0 ooo 9oo 1 400 o1 07 o71 2 ，b = ooo0l o1o1l o0 ooo ol010 l l 0oo ol 0oo 求解( 3 1 ) 的极值问题可以转化为求解如下函数 ( 3 1 ) x 1 ( x 5 2 - 0 2 x s + 6 0 n + 4 x 2 0 i x 5 2 + 0 0 2 x 5 1 4 0 1 = 0 x 2 ( 戈2 2 0 6 x 2 + - 2 + 屯2 + 2 0 4 h 一0 4 x s 一0 4 x 6 + 1 4 ) 一0 0 8 ( x 2 + 毛+ 屯+ ) + 4 _ 一3 2 3 2 = 0 2 0 x 3 + 9 而一3 8 = 0 x 4 x 2 2 0 4 x 2 x 4 3 5 4 x 4 + x 4 3 + 1 3 4 x 4 2 + 9 b 确一0 2 恐2 + o 0 8 x 2 + 0 7 2 4 1 8 x 3 = o x 5 ( 五2 0 2 x i + x 2 2 0 4 x 2 + 1 q b + 7 x 6 - 8 a s ) 一0 1 ( x 1 2 + x 2 2 ) + o 0 2 ( x , + 而) + 0 7 x 6 0 2 3 5 = 0 x 6 ( x 2 2 - 0 4 x 2 + 1 2 0 4 ) 一0 2 x 2 2 + 0 o r + 7 x 5 3 1 0 8 = 0 问题( 3 1 ) 的极小点为( o 1 ，0 2 ，0 1 ，0 2 ，0 1 ，0 2 ) r ，极小值f = 1 。以下以点 x = 1 ，1 ，1 ，0 ，0 ，o 】7 为迭代的初始点，分别用一步j a c o b i - n e w t o n 迭代法、分块 j a c o b i n e w t o n 迭代法、一步s e i d e l 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 迭代法利用m a t l a b 编程进行了数值求解，计算均在s = i ifi i 足 1 7 青岛大学硕士学位论文 够小以后终止。 j a c o b i n e w t o n 迭代法 一步j a c o b i n e w t o n 迭代法的迭代公式： = 一i v y , ( 工) 】i v ；z ( 工) ， i = 9o * o ，l ，k = o ，1 ， 计算结果见表3 1 1 。 表3 1 1 一步j a c o b i n e w t o n 迭代法的计算 n = 0n = l n = 1 0n = 5 0n = 8 0 s1 1 1 f1 6 2 0 0 e + 0 014 6 19 6 e 0 0 2 7 3 4 4 2 e 0 1 01 3 8 7 8 e 0 15 l 1 8 11 5 6 5 0 0 e + 0 0 14 2 9 6 3 0 3 0 4 e + 0 0 0 】0 0 0 0 6 7 0 3 e + 0 0 01 0 0 0 0 0 0 0 0 e + 0 0 01 ，0 0 0 0 0 0 0 0 e + 0 0 0 8 6 0 9 0 0 0 0 0 e + 0 0 03 。8 4 6 2 3 3 4 3 e + o o o1 6 0 0 3 4l1 4 e 0 0 30 。0 0 0 0 0 0 0 0 e + 0 0 00 0 0 0 0 0 0 0 0 e + 0 0 0 1 5 3 8 4 0 0 0 0 e + 0 0 1- 4 4 3 8 0 8 8 3 2 e + 0 0 0 3 2 5 8 7 8 5 5 8 e - 0 0 30 o 0 0 0 0 0 0 0 e + 0 0 00 0 0 0 0 0 0 e + o o o 1 6 2 0 0 0 0 0 0 e + 0 013 1 4 8 7 8 0 4 9 e + 0 0 02 9 6 415 6 6 5 e 0 0 24 9 9 6 5 5 8 7 2 e - 013o o 0 0 0 0 0 0 0 e + 0 0 0 v f 5 16 4 0 0 0 0 0 e + 0 0 07 0 6 8 5 9 0 2 8 e + 0 0 0 7 8 8 9 6 18 2 9 e 一0 0 31 3 3 1 5 7 3 7 4 e 0 1 30 0 0 0 0 0 0 0 c i e + 0 0 0 2 5 4 5 0 0 0 0 0 e + o o o1 6 4 8l9 4 6 7 e + 0 0 0- 2 4 2 2 4 6 6 0 3 e 0 0 2- 4 0 2 3 0 4 0 2 3 e 0 1 0 5 2 7 3 5 5 9 3 7 e 0 16 3 2 2 8 0 0 0 0 0 e + 0 0 01 5 2l8 8 5 8 6 e + 0 0 03 0 9 5 6 2 4 4 7 e 0 0 25 1 4 0 9 6 8 0 7 e 0 1 07 6 3 2 7 8 3 2 9 e 0 16 1 0 0 0 0 0 0 0 0 e + 0 0 0- 4 3 2 4 4 5 9 2 3 e 一0 011 0 0 1 3 7 7 8 9 e 一0 0 11 0 0 0 0 0 0 0 0 e 0 011 0 0 0 0 0 0 0 0 e 一0 0l 1 0 0 0 0 0 0 0 0 e + 0 0 03 9 6 9 8 8 3 6 3 e 0 0 12 0 0 1 9 3 4 0 2 e 0 0 1 2 0 0 0 0 0 0 0 0 e 0 012 0 0 0 0 0 0 0 0 e 0 01 1 0 0 0 0 0 0 0 0 e + 0 0 01 9 0 0 0 0 0 0 0 e 0 011 0 1 7 2 8 5 1 9 e 0 0 11 0 0 0 0 0 0 0 0 e 0 011 0 0 0 0 0 0 0 0 e 0 01 工 0 0 0 0 0 0 0 0 0 e + 0 0 03 4 9 8 6 4 4 9 9 e 0 011 9 9 4 5 2 3 5 3 e 0 0 12 0 0 0 0 0 0 0 0 e o o1 2 0 0 0 0 0 0 0 0 e 0 01 0 0 0 0 0 0 0 0 0 e + 0 0 01 9 9 7 519 4 2 e 0 0 19 8 9 5 7 7 1 5 3 e 一0 0 21 0 0 0 0 0 0 0 0 e 0 011 0 0 0 0 0 0 0 0 e 0 01 0 0 0 0 0 0 0 0 0 e + 0 0 02 5 5 3 7 9 7 4 7 e 一0 0 1 1 9 8 0 2 8 3 1 2 e 0 0 l2 0 0 0 0 0 0 0 0 e 0 012 0 0 0 0 0 0 0 0 e o o1 分块j a c o b i - n e w t o n 迭代法 将6 个变量依次两个一组，一步块j a c o b i n e w t o n 法迭代公式： ( x ) ”= ( z ) 一 v ；z ( ( 工) ) 。1 v f i ( ( 石) ) f = 1 ，2 ，3 ，k = o ，l ， 其中( x ) = ( ( x 1 ) ，( x 2 ) 壶，( x 3 ) 。) ，计算结果见表3 1 2 。 第三章算法的数值实验结果 表3 1 2 分块j a c o b i - n e w t o n 迭代法的计算数据 n = 01 1 = 1n = 2n = 3n = 4 si i l f1 6 2 0 0 e + 0 018 7 0 2 5 e 0 0 19 016 3 e 一0 0 41 0 0 6 9 e 0 1 2 1 8 11 5 6 5 0 0 e + 0 0 11 0 3 3 3 7 0 8 9 e + 0 0 01 0 0 0 0 0 0 0 4 e + 0 0 01 0 0 0 0 0 0 0 0 e + 0 0 01 0 0 0 0 0 0 0 0 e + 0 0 0 8 6 0 9 0 0 0 0 0 e + 0 0 05 1 0 5 9 5 2 2 5 e - 0 0 41 3 8 7 7 7 8 7 8 e - 0 1 60 o 0 0 0 0 0 0 0 e + 0 0 00 0 0 0 0 0 0 0 0 e + 0 0 0 1 5 3 8 4 0 0 0 0 e + 0 01 8 7 0 2 5 0 6 5 3 e - 0 019 016 2 8 2 8 7 e 0 0 4 1 0 0 6 9 1 6 7 7 e 0 1 2 0 。0 0 0 0 0 0 0 0 e + 0 0 0 v f 1 6 2 0 0 0 0 0 0 e + 0 0l2 9 4 2 0 9 1 0 2 e 0 1 51 9 4 2 8 9