（应用数学专业论文）一种求解优化问题和非线性方程组的下降算法.pdf

河南大学硕士学位论文 摘要 本论文提出一种求解大规模无约束优化问题的下降算法，推广该算法用于求解 大规模非线性方程组，并证明算法的全局收敛性和数值试验验证算法的有效性 第一章，给出下降方向的定义和基本性质，以及下降算法在牛顿型算法与共轭 梯度算法中的作用；列出求解非线性方程组的无导数算法晟新研究进展；列出本论 文所用到的一些记法，基本概念，符号，定义 第二章，基于a n ，l i 和x i a o 的下降p s b 算法基础上，提出一种求解无约束优化问 题的充分下降算法该算法的搜索方向仅与当前点和前一迭代点的梯度有关，在不 使用任何线搜索的情况下，算法所产生的方向满足充分下降性在适当的条件下，建 立算法的全局收敛性使用c u t e r 函数测试库中的测试问题，验证算法的有效性 第三章，推广第二章所提算法，使之用于求解大规模非线性系统所提算法不需 要计算j a c o b i a n 矩阵，节省存储空间，加快算法运行速度在适当的条件下建立算法 的全局收敛性通过“个大规模非线性方程组对算法效率进行验证，结果表明所提 算法可与著名的软件d f _ s a n e 相媲美 关键词：无约束优化；非线性方程组；下降算法；无导数算法；全局收敛 河南大学硕士学位论文 a b s t r a c t i nt h i st h e s i s ，w ep r o p o s ead e s c e n ta l g o r i t h mf o rs o l v i n gl a r g e - s c a l eu n c o n s t r a i n e dm i n i - m i z a t i o n ，a n de x t e n di tt os o l v en o n l i n e a rs y s t e mo fe q u a t i o n s u n d e rs o m em i l dc o n d i - t i o n s ，w ee s t a b l i s hi t sg l o b a lc o n v e r g e n c e n u m e r i c a le x p e r i m e n t sa r e a l s or e p o r t e d ，w h i c h i l l u s t r a t et h a tt h ep r o p o s e dm e t h o di sp r a c t i c a la n dp r o m i s i n g i nt h ef i r s tc h a p t e r ，w eg i v et h ed e f i n i t i o na n ds o m ep r i m a r yp r o p e r t i e so ft h ed e s c e n t d i r e c t i o n w es h o wt h a td e s c e n td i r e c t i o np l a y sa ni m p o r t a n tr o l ei nn e w t o n - t y p em e t h o d a n dc o n j u g a t eg r a d i e n tm e t h o d m o r e o v e r ，s o m er e c e n tp r o g r e s so ft h ed e r i v a t i v e - f r e e s c h e m em e t h o df o rs o l v i n gn o n l i n e a rs y s t e mo fe q u a t i o n sa r ep r e s e n t e d t oe n dt h i s c h a p t e r ，s o m ei m p o r t a n tn o t a t i o na n ds y m b o l sw h i c hu s e di nt h ec o n t e x ta r ea l s oi n c l u d e d i nc h a p t e r2 ，b a s e do nt h es u f f i c i e n td e s c e n tp s bm e t h o do fa n ，l ia n dx i a o ，w e d e v e l o pas u f f i c i e n ta l g o r i t h mf o ru n c o n s t r a i n e dm i n i m i z a t i o n a te a c hi t e r a t i o n ，t h e g e n e r a t e dd i r e c t i o n si sa c o m b i n a t i o no ft h eg r a d i e n ta tc u r r e n ta n dp r e v i o u ss t e p s t h e a t t r a c t i v ep r o p e r t yi st h a tt h eg e n e r a t e dd i r e c t i o n sa r ea l w a y sd e s c e n t ，a n dt h ep r o p e r t yi s i n d e p e n d e n to fa n y l i n es e a r c hr u l e u n d e rs o m ea p p r o p r i a t ec o n d i t i o n s ，w es h o wt h a tt h e m e t h o dc o n v e r g e sg l o b a l l y w et e s tt h ea l g o r i t h mb yu s i n gs o m ep r o b l e m sf r o mc u t e r l i b r a r y , w h i c hs h o wt h a tt h ep r o p o s e dm e t h o di se f f e c t i v e i nc h a p t e r3 ，w ee x t e n dt h em e t h o dw h i c hg i v e ni nt h ep r e v i o u sc h a p t e rt os o l v e n o n l i n e a rs y s t e mo fe q u a t i o n s a te a c hi t e r a t i o n ，t h ej o c o b i a ni n f o r m a t i o ni sn o tr e q u i r e d ， w h i c hs a v e st h ep cm e m o r ya n di m p r o v e st h ep e r f o r m a n c e u n d e rs o m ec o n d i t i o n s ，w e e s t a b l i s ht h eg l o b a lc o n v e r g e n c e 。f i n a l l l y ，w ed os o m en u m e r i c a le x p e r i m e n t sb yu s i n g4 4 p r o b l e m s ，t h en u m e r i c a lc o m p a r i s o n si l l u s t r a t e dt h a tt h ep r o p o s e dm e t h o di sc o m p e t i t i v e w i t ht h es a t e - o f - t b a r tm e t h o dd f s a n e k e yw o r d s ： u n c o n s t r a i n e do p t i m i z a t i o n ；n o n l i n e a rs y s t e mo fe q u a t i o n s ；d e s c e n t d i r e c t i o n ；d e r i v a t i v e - f r e ea l g o r i t h m ；g l o b a lc o n v e r g e n c e i i 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成酌，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学住或证书而 使用过的材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。，、；? 、乍一 ，：j 。，j ，? ijr 。i 学位牢请a ：( 学位毒作者) 签名：f 毋之茗医 毒一i 一。一“；7 ，、7 ，一。“、 _ ：r ，。 鞋； 。： 、”“ 一| j | t 一，i 、 。j f 。一j 参? j ”i j j7 1 j 壤? 钠f 矿年冬琵1 0a i ：、。，。：j ：；：。7 j j ：! ：“2 0 矿年f 月6 日 夕，。“? 亏，磐j 麓二： 。 。o j 一，一：， 乏?“。= = 5 ：；毒j o i 妒，：，一。z ，：0：jr ? ， p ：，1i ”l ；7；? 7 ，7 ，。t i ：+ ? ，。 j ：一j 7 ， 。；，i ；。，关于学位论文著作权使用授权书多 、一 l ( x + ) ) ，则称z + 为以缈奎局 最优解俨格全局最优解，如果存在占 0 ，使得所有满足忙一矿0 ( z + ) ) 成立，则称矿为以缈的局部最优解俨格局 部最优解夕当目标函数，是凸函数时，局部最优解也是全局最优解 1 1 1充分条件、必要条件 由定义1 1 1 可知，求最优化问题的解分为局部最优解和全局( 整体) 最优解二 般情况下，非线性优化问题的局部最优解看成是所求问题的解因此，在实际的计算 和求解当中，通常是找到满足局部最优解必要条件的点下面是判断矿r n 是否是 问题( 1 2 ) 的最优解的条件 一阶必要条件设函数，连续可微，若z + 是( 1 2 ) 的局部最优解，则 v ( z + ) = 0 ， 其中，v f ( x ) 表示，( z ) 的梯度 二阶必要条件设函数，二阶连续可微，若z + 是( 1 2 ) 的局部最优解，则 v f ( z + ) = 0 ，且牡t v 2 f ( x + ) 让芝0 ，v u r n ， 其中，v 2 ，( z ) 表示f ( x ) 彭j h e s s i a n 阵 二阶充分条件设函数f - - 阶连续可微，若 v f ( x ) = 0 且t t v 2 f ( x + ) u 0 ，v 乱r 礼， 则矿是( 1 2 ) 的严格局部最优解 1 1 2 算法步骤 求解问题( 1 2 ) 的方法通常是采取迭代形式，其基本思想是：给定初始点x 0 r n ， 按照某种准则产生一个迭代序列 【z 七 ，若点列是有限点列，最后一点是问题( 1 2 ) 的最 优解；若点列是无穷点列，其极限点是问题( 1 。2 ) 的最优解，迭代格式： 、l ， 3l f 如七 a+ 2 = l+七 z 河南大学硕士学位论文 其中步长o z 七由线性搜索给出，也是搜索方向 最优化算法的基本迭代步骤如下： 算法1 1 2 步1 选取初始点z o ，并令k ：= o j 步2 构造搜索方向如，依照一定规则，构造，( z ) 在点钆处的下降方向或可行下降方 向作为搜索方向； 步3 确定搜索步长q 七，确定以z 知为起点沿搜索方向如的适当步长，使目标函数值有 某种意义的下降，通常t t 邑f ( x , k + a k d k ) ，( z 南) i 步4 求出新的迭代点，令x k + 1 = z 七+ o e k d k ； 步5 检验x k + l 是否满足某种终止准则若满足，停止迭代，得到近似最优解i 否则， 令k ：= k + 1 转例 由上述迭代过程可知，构造搜索方向和确定沿该方向下的合适步长是优化算法 的核心所在 1 1 3 线搜索 最优化的基本迭代算法是从当前点x k 开始，沿方向也，寻找一个最“好”的点作 为下一迭代点显然，最“好”的点就是在这个搜索方向上，使目标函数值达到最小 值的点因此，步长q 七的计算对于每一次迭代都是非常重要的，它的选取一般是由某 种线搜索确定下面给出计算步长o l 血通常使用的线搜索 精确线搜索：a 七满足 o e k2 a r g 勰，( 钆+ c y d k ) ( 1 4 ) 此种搜索由于计算量大，所以在实际中很少采用，一般采用以下非精确线搜索： a r m i j o 线搜索：给定6 ( 0 ，1 ) ，a 七= m a x ，j = 0 ，1 ，2 ，) 满足 f ( x k + o e k d k ) f ( x k ) + 6 a k w ( x k ) 。d k ( 1 5 ) 其中p ( 0 ，1 ) w o l f e 线搜索：q 七同时满足下面的两个不等式 m 七+ q k d k ) m 七) 棚v m 七) i 以，( 1 6 ) iv ，( 矾+ a k d k ) t d k a 2 v f ( x k ) t d k ， 河南大学硕士学位论文 其中盯1 ，c r 2 为常数，满足o 0 1 ，0 1 0 2 o 使得 f ( z + q d ) o 充分小时，t a y l o r 展开 f ( x + a d ) = ，( z ) + q v ，( z ) t d + d ( q ) ，( z ) ， 则有 v f ( 矿d 监掣 0 由于参数觑的差异而产生不同的共轭梯度法，例如：f r 方法，h s 方法，c d 方法，l s 方 法，d y 方法及p r p 方法近年来，许多学者对非线性共轭梯度法有了更进一步的拓 河南大学硕士学位论文 展对仇也提出了许多不同的形式，文章【9 】中的d a i 和y u a u 的杂交共轭梯度方向的下 降性依赖与所采用的线搜索在h a g e r 和z h a n g 1 0 ，1 1 文章中由共轭梯度法产生的方 向总是下降的，且与线搜索无关h i r o s h i 和m a s a h i r o 1 2 ，w e i 1 3 ，1 4 等学者提出的新 共轭梯度法，具有好的收敛性关于共轭梯度及其它方面的介绍，可看h a g e r 和z h a n g 的 综述性文献 1 5 】以及d a i 和y u a n 关于非线性共轭梯度法的专著【5 】 1 2 2 最新进展 下降性质对迭代方法在全局收敛性方面是非常重要的，许多已有的方法也都具 有这种特殊性质如：最速下降法，严格b r o y d e n 族拟牛顿法【1 6 】等等有些方法，如 初期的谱梯度方法 17 ，p r p 共轭梯度法等，它们的收敛方向对于目标函数是不完全 下降的在过去的一段时期内，为避免这些缺点，做出了很多的努力，并找到了一 种新的方法 1 8 】众所周知，在求解非凸极小化问题中，如果使用a r m i j o 型线性搜索， 当接近最优点的时，标准p r p 共轭梯度方法在有限点内无限度的循环为消除缺陷， h a g e r 和z h a n g 1 0 】修 h y p r p 公式并且提出一种方法，它的显著特征是对于任何线 性搜索都是下降的，且有 d k t g k 一舢七限 z h a n g ，z h o u 和l i 1 9 进一步研究t p r p 方法并且提出了一种修正的p r p 方法，由 它产生的方向总能使( 1 7 ) 成立，并且不依赖于任何线搜索规则另外，为了提高f r 方 法的数值性能，z h a n g ，z h o u 和l i 2 0 改进了f r 方法，使其所产生的方向也是能使等 式( 1 7 ) 成立 最近，a n ，l i 和x i a o 1 6 在求解无约束最优化问题中构建了一种充分的下降方向 这个方向是由最速下降方向与某初始方向在梯度子空间上正交投影的谱乘积的线 性组合，具体形式如下： d k2 - - q k 胛一淼) 瓦 ( 1 1 3 ) 其中，k 是一个常数，五是一个待定的方向，它可以是牛顿方向或者是拟牛顿方向，也 可以是其它形式的方向显然，等式( 1 1 3 ) 定义的方向如满足( 1 7 ) 式与( 1 1 3 ) 相比较， ( 1 1 2 ) 式中的凤和如一1 分别取代( 1 1 3 ) 式中的系数矩阵 狮一砰g k g ) 和五 6 河南大学硕士学位论文 ( 1 1 3 ) 式可看成是比非线性共轭梯度方法更的一般的表现形式这个技巧适用于p s b 方 法 1 6 】，而且能给出p s b 方法在求解无限凸函数时具有全局收敛性和超线性此外， 2 1 】中给出的方向仅仅是( 1 1 3 ) 的一个特例 1 3 无导数算法 非线性方程组 f ( z ) = 0 ，z r n ，( 1 1 4 ) 其中f ：r n r 是个连续的映射 求解非线性方程组【2 ，2 2 ，2 3 ，2 4 ，2 5 ，2 6 】一般拟牛顿法是由等式( 1 3 ) 产生迭代序 列 z 知) 其中搜索方向也是由线性方程确定： j k d + f ( z ) = 0 ，( 1 1 5 ) 其中， 是f ( z ) 在点x 七的j a c o b i a n 矩阵，在a 七= 1 时这个方法就是著名的牛顿法 尽管拟牛顿法有一些好的性质，但在求解方程组时每一步还要使用j a c o b i a n 矩 阵或者是它的近似矩阵对于低维的非线性方程组它是有效的，但对于高维的却不 理想在本文中，给出的维数是n ( n 是一个很大的数) ，或者f 的j a c o b i a n 矩阵是非奇 异的，或者不需要一个大量的存储这里为解决这个问题，所以无导数方法是很受我 们的欢迎 近年来，无导数方法受到研究者更多的关注c r u z ，m r t l n e z ，和t l u y d a n 【2 7 】提 出求解非线性系统的谱梯度算法s a n e ，其是两点步长方法 17 的推广和应用因 为s a n e 使用的有限差分算子来代替方程的j a c o b i a n 矩阵信息，并不是真正意义上的 无导数算法在2 0 0 6 年，基t l f 2 5 和g l l 2 8 的无导数线搜索和非单调技术，c r u z ， m r t l n e z ，和r a y d a n 2 9 提出求解非线性方程组的无导数算法d b s a n e 为避免g l l 线 搜索的弊端，在 3 0 】中，w c h e n g 和d h l i 使用z h a n g 和h a g e r 的非单调线搜索替换d f s a n e 中的g l l 线搜索，得到一种新的无导数方法，实验结果表明，所提算法数值表 现优越于比d f s a n e 众所周知，共轭梯度方法因其简单的迭代和较低存储而非常适合求解大规模无 约束最优化问题但其用来求解大规模非线性方程组很少受到关注近年来，c h e n ， 7 河南大学硕士学位论文 x i a o ，和h u 3 1 】结合【2 1 】和【1 9 下降共轭梯度法，提出了一种求解( 1 1 4 ) 的新的无导数算 法，数值试验表明，所提算法非常有效，而且可与d f s a n e 相媲美 8 1 4 本文主要工作 本文的主要工作及创新点如下： 第二章，基于文章 1 6 】中的下降p s b 算法基础上，提出一种求解无约束优化问题 的新的充分下降方向： 虻一州卜蒜概。 该方向是当前点与前迭代点梯度信息某种方式的组合显然，在不使用任何线搜 索的情况下，算法所产生方向满足充分下降性 第三章，在第二章方向的基础之上做了进一步的推广，亦即是用凡取代了第二 章方向中的梯度g k 如下： 如一最觯一繇 使之用于求解大规模非线性系统算法不需要j a c o b i a u l 矩阵，并给出算法和数值实验 文章中所用的符号： z ： 实变量 r ：全体实数组成的集合 郧： 全体n 维实向量组成的集合 ，( z ) ：目标函数 风：f ( z ) 在点z 惫处的值 9 ( z ) ：目标函数，在点z 的梯度 j ：单位矩阵 ，( z ) ：f ( z ) 的j a c o b i a n 矩阵 a 1 ：矩阵a 的逆 a t ： 矩阵a 的转置 i l ：向量的欧氏范数 9 第二章一种求解无约束最优化问题的充分下降方法 考虑如下无约束优化问题： 2 1 引言 m i i ( x ) ，z r n ， ( 2 1 ) 其中，f ( z ) g 连续可微函数 本章改进搜索方向( 1 1 3 ) ，提出一种求解( 2 1 ) 的充分下降算法给出了在一定条 件下的相应算法的全局收敛性和数值实验 2 2改进的搜索方向 类似于公式( 1 1 3 ) ，c h e n g 2 1 】提出了如下方向： 如一鲰+ 筇唧一蹄) 讪 ( 2 2 ) 显然( 2 2 ) 是( 1 1 3 ) 的特例，即使用筋r p 代替九，d 七一1 代替五在本节中用肌一1 代替( 1 1 3 ) 中 的五，并取h = 1 ，得： 以一州j 一器舢 ( 2 3 ) 令 凰= ，一砑g k g ( 2 4 ) 引理2 2 1 如果巩由俾彳，式所定义，则磁= 凰 证明：略 上述的论点表明：对于所有的0 ，可舯，有 y t h k y = t 磁= y t h k h ：y ：可可t 风s ：i i z - & t 可1 1 2 0 即风是一个对称半正定的矩阵 1 1 河南大学硕士学位论文 引理2 2 2 若如由偿圳式所定义，则 l i d 七t 1 2 = i l g k1 1 2 + i i h k g k 一11 1 2 证明：由搜索方向如的定义和范数的定义，有 证毕 = ( 一鲰州一淼) ) t ( - 鲰州一淼m _ = i l g k l l 2 2 卉( 卜淼) g k - 1 + 1 1 ( ，一1 9 k g i 。) 船1 ) 1 1 2 = i l g k1 1 2q ( 鲰t 舭g t g k g j p ) + 1 1 ( 卜踹) ) 1 1 2 = i i g 惫1 1 2 2 ( 夕j g k - 1 - - 订) + 1 1 ( 一g k g 。) ) 1 1 2 = i i g 七1 1 2 + t 1 ( 卜淼k i ) 纰1 ) 1 1 2 2 3算法和它的全局收敛性 ( 2 5 ) 本节给出算法和全局收敛性定理的证明由( 2 3 ) 式确定的方向符合充分下降条 件为使算法具有全局收敛性，同时也考虑了g r i p p o 和l u c i d i ( g l ) 【3 2 】所给线搜索求 解q 七= _ p b = 0 ，1 ，) ，即 ，( 。七十a 七d 七) f ( x e ) 一6 q 2 l i d 七j j 2 ， ( 2 6 ) 其中6 ( o ，1 ) ，p o ，p ( o ，1 ) 下面是充分下降算法的步骤： 算法2 3 1 ( s s d ) 步0 给定初始点z o 舻，让o j a 2l l d k1 1 2 则存在常数m 0 ，则有 燃i d k l l m ( m 七) 一他) ) 2 。、j “甩， j 、“尤十1 ，。 i i 另一方面，如果。七= p ，由( 2 6 ) 得 i i d k l i 6 1 p 一2 ( y ( z k ) 一，( z _ j c ) ) 由( 2 5 ) 式得 i i d 七| f i | 鲰i i 联立上面两个不等式，有下面结论： 燃61p一2(y(xk)一mm)1ak l l 2 。尸 7 。、“一十1 7 7 上式中，若令m = 5 - 1 f i _ ，这就得到( 2 1 1 ) 式证明完毕 定理2 3 4 若序列 钒) 由算法2 3 j 产生，则有 l i m i n fl i g k l i = 0 甩+ 证明：由假设2 3 3 ) i 1 ，存在一个正的常数7 ，使得 i i g k l i 彳 由( 2 3 ) 可得 i l 如0 0 ，由( 2 1 4 ) 铷m i n fi i d k l i = 0 ，则l 呻i i l f | | 鲰i | = o 成立 心0 0几，c + o o 若1 徊i n q 七= 0 ，则存在一个无限的指标集k ，使得 l i m i n l l d k l l 2 = 0 ( 2 1 5 ) k e k 七 在算法2 。3 1 内从线性搜索中，当k k 足够大，p 一1 q 七不能使( 2 6 ) 式成立由引理2 3 1 的 第一步的证明可知不等式( 2 1 0 ) 成立由于i l d k l l 是有界的，r ( 2 1 5 ) 成立由( 2 1 0 ) 说明 i n l l 鲰0 = 0 是成立，这与假设矛盾证毕 2 4数值结果 本节分析算法s d d 算法由软件f o r t r a n 7 7 使用双精度编写，在安装有w i d o wx p 系 统( i n t e lp e n t i u md u a le 2 1 4 01 6g h z ，2 5 6 勾存) 的电脑上运行算法终止的条件是： l l i o 。1 0 ( 2 1 6 ) 若算法迭代次数超过1 0 0 0 0 次或者是函数赋值的数达至u 2 0 0 0 0 ，算法被迫终止测试函 数 叭c u t e r 3 3 6 j 题库中选取，问题维数1 0 0 0 维和2 0 0 0 维线搜索( 2 6 ) 中的参量取 值如下： = 1 ，石= 1 0 4 ，p = o 5 ， 算法2 3 1 的数值结果见下表，表中符号定义如下，其中的符号”说明算法此时失败 1 5 + k z j 惫 z ， 一 6 脚 一 膏 d 2 七 q 脚 河南大学硕士学位论文 p r o b l e m ：测试问题的名称； d i m ：测试问题的维数； i t e r ：迭代次数； n f ：函数赋值的数量； t i m e ：c p u 每秒中运算的次数； f v ：最终的函数值： n o r m - l ： 最终函数梯度的2 1 范数； n o r m 2 ：最终函数梯度的范数； 由表知，s s d 对这些测试问题非常有效，在非常短的时间内就能找到问题的解 1 6 河南大学硕士学位论文 表a j n = 1 0 0 0 时s s d 算法的数值结果 p r o b l e md i mi t e r n ft i m ef vn o r m - 1n o r m - 2 d q d r t i c 1 0 0 01 5 61 5 1 30 0 90 3 9 5 e - l l0 3 9 3 e - 0 50 7 7 9 e - 0 5 d i x m a a n a1 0 0 04 11 2 20 0 30 1 0 0 e + 0 10 6 5 1 e - 0 70 1 4 3 e 0 5 d i x m a a n b1 0 0 04 51 3 00 0 40 0 1 0 0 e + 0 10 1 7 6 e ；0 50 9 6 2 e 0 5 d i x m a a n c1 0 0 03 41 1 50 0 30 1 0 0 e + 0 10 3 3 5 e - 0 60 3 7 4 e - 0 5 d i x m a , a n e1 0 0 02 8 1 92 8 4 03 2 30 1 0 0 e + 0 10 9 9 9 8 0 50 9 9 9 8 0 5 e d e r l 8 c h1 0 0 07 34 1 50 0 4 0 6 0 0 e + 0 40 3 0 1 e - 0 50 6 6 9 e - 0 5 v a r d i m1 0 0 0 1 7 8 2 60 0 3 0 3 3 8 e - 2 00 1 1 6 b 0 60 2 1 2 b 0 5 l i a r w h d1 0 ( ) o7 7 0 10 6 4 7 0 8 l0 1 7 1 8 1 1o 9 4 7 8 0 50 9 6 8 8 0 5 d i x m a a n f1 0 0 06 2 4 49 4 7 31 1 0 70 1 0 0 e + 0 10 9 9 9 e - 0 50 9 9 9 e - 0 5 d i x m a a n g 1 0 0 03 3 1 33 7 8 04 0 00 1 0 0 e + 0 10 9 9 9 e - 0 50 9 9 9 e - 0 5 d i x m a , a n h1 0 0 05 1 5 47 4 8 37 9 50 i o o e + 0 10 9 9 3 e - 0 50 9 9 4 e - 0 5 d i x m a a n i 1 0 0 0 2 8 1 5 2 8 3 42 7 00 1 0 0 1 p , + 0 10 9 9 9 e - 0 50 9 9 9 e - 0 5 d i x m a a n j 1 0 0 0 5 1 8 6 7 4 4 1 8 3 90 1 0 0 e + 0 10 9 9 8 e - 0 5 0 9 9 8 e - 0 5 d i x m a a m k1 0 0 07 9 1 01 2 8 3 51 4 4 20 1 0 0 1 p , + 0 10 9 7 0 e - 0 50 9 8 7 e 0 5 e n g v a l l 1 0 0 07 23 9 60 0 30 1 1 0 e j r - 0 40 8 2 5 e - 0 50 9 0 6 e - 0 5 c o s i n e1 0 0 08 6 75 7 5 31 6 5- 0 9 9 9 e + 0 30 9 4 7 e - - 0 50 9 4 7 8 0 5 d e n s c h n b1 0 0 05 31 7 6o 0 10 1 1 1 e 1 00 2 7 4 e 0 60 7 1 9 b 0 5 d e n s c h n f1 0 0 07 37 0 10 0 40 1 0 4 8 1 20 1 8 0 8 0 60 5 0 2 8 0 5 g e n r o s e 1 0 0 03 5 74 0 9 40 3 40 1 0 0 p , + 0 10 6 0 4 e - 0 50 7 5 4 e - 0 5 p e n a l t y l 1 0 0 01 11 2 20 0 00 1 3 3 e - 1 10 7 3 1 8 0 70 2 3 1 8 0 5 s r o s e n b r1 0 0 01 7 1 81 8 6 8 91 1 00 5 0 1 8 1 00 2 5 8 8 0 60 6 3 3 d 0 5 w o o d s2 0 0 0 d q r t i c 1 0 0 06 7 0 57 1 7 41 1 70 3 3 7 e - 0 60 3 2 2 b 0 60 9 9 9 e 一0 5 b r o y d n t d 1 0 0 01 4 7 31 1 6 4 02 9 30 4 5 3 e + 0 30 5 1 4 8 0 50 9 7 3 e , - 0 5 b r o w n a l1 0 0 01 52 6 60 1 00 8 7 7 b 1 20 1 2 5 e 二0 6o 3 9 7 e 二0 5 g e n h u m p s 1 0 0 04 3 71 2 5 21 4 60 4 3 9 8 0 90 8 5 2 8 0 50 9 3 7 8 0 5 b d e x p 1 0 0 0250 0 10 3 7 5 e 1 20 2 3 2 e 1 10 3 7 2 b 1 1 1 7 河南大学硕士学位论文 表a 2 n = 2 0 0 0 时$ s d 算法的数值结果 p r o b l e md i mi t e rn ft i m ef vn o r m - 1n o r l n 2 d q d r t i e 2 0 0 02 5 22 3 9 90 2 10 6 7 1 e - l l0 5 1 5 e - 0 50 7 7 7 e 广0 5 d i x i t l a , a n s ,2 0 0 04 6 1 3 8 0 0 60 i o o e + 0 10 5 3 4 e - 0 60 5 8 4 e - 0 5 d i x m a a n b2 0 0 0 3 4 1 1 10 0 40 0 1 0 0 e + 0 10 8 0 3 e - 0 60 6 0 8 e - 0 5 d i x m a a n c2 0 0 05 11 4 20 0 60 1 0 0 e + 0 10 5 0 4 f r 0 60 4 7 1 e - 0 5 d i x m a a n e2 0 0 04 9 5 24 9 7 31 4 5 90 1 0 0 e + 0 10 9 9 9 8 0 50 9 9 9 e ；0 5 e d e n s c h2 0 0 06 9 4 0 6 0 0 70 1 2 0 e + 0 50 6 2 5 e - 0 50 9 3 6 e - 0 5 v a r d i m1 0 0 0 l i a r w h d1 0 0 0 d i x m a a n f 2 0 0 0 4 8 8 84 9 8 41 5 7 00 1 0 0 e + 0 10 9 9 9 e - 0 50 9 9 9 e - 0 5 d i x m a a n g 2 0 0 0 6 4 2 17 7 7 52 1 1 8 0 1 0 0 e + 0 1 0 9 9 9 e - 0 5 0 9 9 9 e - 0 5 d i x m a a n h2 0 0 04 9 4 64 9 6 51 4 2 60 i o o e + 0 10 9 9 9 e - 0 50 9 9 9 e - 0 5 d i x m a a n i2 0 0 0 d i x m a a n j 2 0 0 05 1 3 75 4 6 04 6 4 20 1 0 0 e + 0 10 9 9 9 b 0 50 9 9 9 e - 0 5 e n g v a l l 2 0 0 0 7 3 4 0 40 0 40 2 2 1 e + 0 40 5 8 1 b 0 50 9 8 3 b 0 5 c o s i n e2 0 0 08 3 15 5 3 7 3 2 60 1 9 9 e + 0 40 9 3 9 e - 0 50 9 8 0 8 0 5 d e n s c h n b2 0 0 06 72 1 20 0 30 1 0 3 8 1 00 2 2 0 8 0 60 8 7 5 8 0 5 d e n s c h n f2 0 0 08 58 1 30 1 40 1 1 6 5 8 1 20 2 5 5 8 0 60 8 7 1b 0 5 g e n r o s e 2 0 0 03 8 14 3 8 90 6 00 1 0 0 e + 0 10 4 9 5 e 0 50 9 4 5 e - 0 5 p e n a l t y l 2 0 0 01 3 1 1 4 7 0 0 10 2 4 7 e ；1 00 2 2 2 e - 0 6 0 9 9 4 b 0 5 s r o s e n b r2 0 0 01 7 8 6 1 9 3 9 6 1 9 00 1 2 3 e - 0 90 2 7 1 e - 0 60 9 9 4 e - 0 5 w o o d s2 0 0 01 6 71 8 1 7 61 - 9 00 6 8 2 8 1