（计算数学专业论文）伪瞬时延拓方法.pdf

摘要 非线性方程组讨论的问题是f ( u ) = 0 ，其中f ：舻_ 舻，该问题广泛应用于工程、管 理和经济学等领域非线性方程数值求解中最典型的方法是n e w t o n 法和n e w t o n g m f e s 方法，其 中n e w t o n g r a t e s 方法是一类非精确的牛顿法，由于在很多实际问题中，这些方法在计算实施中 严重地受到初值选取的影响，从而导致非线性迭代不收敛，或是收敛到不好的结果因此，又有 研究者提出了一类非线性的全局化收敛性方法，f l o n e w t o n k r y l o v 子空间方法配以线搜索方法 但是在一些初值离精确较远的问题当中，该类方法仍小能得到令人满意的计算效果，甚至发生迭 代中断现象 在本论文中，我们介绍另一类求解非线性方程组的全局化收敛性方法伪瞬时延拓方法， 该方法是将一个与时间无关的问题转化为与时问相关的问题，在每个伪瞬时时间步上再采 用n e w t o n 法去求解非线性方程，最终获得一个快速的渐进收敛的一种方法经数值实验表明该 方法能够快速且很好的收敛到问题的精确解该方法具有物理背景，容易理解，对于发展到稳态 的问题甚是有效该方法可用于空气动力学、磁流体力学、辐射转换、反应流等领域 本文综述了一些非线性的方法，特别介绍了一种新的方法一伪瞬时延拓法；并提出了两种伪 时间步长的选取方法，最后通过数值实验验证了这几类非线性方法的有效性 关键词：伪瞬时延拓，非线性迭代方法，菲线性方程，全局收敛 a b s t r a c t t h en o n l i n e a re q u a t i o n sd i s c u s st h ep r o b l e mo ff o , ) = 0 ，f ：舻一+ r “1 1 1 ep r o b l e mi s w i d e l yu s e di ne n g i n e e r i n g ，m a n a g e m e n t ，a n de c o n o m i c s a b o u tt h en u m e r i c a ls o l u t i o no fn o n l i n e a r e q u a t i o n s t h em o s tt y p i c a lm e t h o di sn e w t o n sm e t h o da n dn e w t o n c _ r n l r e sm e t h o d b u ti nm a n yp r a c - t i c a lp r o b l e m s ，t h ei m p l e m e n t a t i o no ft h e s em e t h o d sa r es e r i o u s l yi m p a c t e db yt h ei n i t i a lv a l u e s ，w h i c h l c a d st ot h en o i l l i n e a ri t e r a t i o nd o e sn o tc o n v e r g eo rc o n v e r g e st ob a dr e s u l t s s o ，s o m er e s e a r c h e sp r o - p o s eag l o b a lc o n v e r g e n ta p p r o a c hc a l l e da sn e w t o n - k r y l o vs u b s p a c em e t h o dc o u p l e dw i t hl i n es e a r c h m e t h o d h o w e v e r , w h e nt h ei n i t i a lv a l u e sa r ef a rf r o mt h ea c c u r a t er o o t ，t h i sm e 也o dc a nn o tc o m p u t e s a t i s f a c t o r yr e s u l t s ，o re v e nt h ep h e n o m e n o no fi t e r a t i o nd i s r u p t i o n s i nt h i sp a p e r w ei n t r o d u c ea n o t h e rm e t h o d c a l l e da sp s e u d o t r a n s i e n tc o n t i n u a t i o nm e t h o d t h e t e c h n i q u eo ft h i sm e t h o di st ot r a n s f o r mat i m ei n d e p e n d e n tp r o b l e mi n t oat i m ed e p e n d e n to n ea n da t e a c ht i m es t e po nt h ep s e u d o t r a n s i e n t ，u s i n gt h en e w t o n sm e t h o d st os o l v en o n l i n e a re q u a t i o n st og a i na r a p i da s y m p t o t i cc o n v e r g e n c e t h r o u g ht h en u m e r i c a le x p e r i m e n t s ，i ts h o w st h a tt h em e t h o dc a nr a p i d l y a n dw e l lc o n v e r g et ot h ee x a c ts o l u t i o no ft h ep r o b l e m t h i sm e t h o dh a sap h y s i c a lb a c k g r o u n da n de a s y t ob eu n d e r s t o o d f o rt h ed e v e l o p m e n to ft h es t e a d ys t a t ep r o b l e m ，t h i sa p p r o a c hi sv e r ye f f e c t i v e 1 1 1 e t e c h n i q u ei sp o p u l a ri nt h ea e r o d y r n a m i c s 、m a g n e t o h y d r o d y n a m i c s 、r a d i a t i o nt r a n s p o r t 、r e a c t i o nf l o w a n ds o o n t h i sp a p e rd i s c u s s e ss o m en o n l i n e a ra p p r o a c h e s ，e s p e c i a l l yn e ww a y p s e u d o t r a n s i e n tc o n t i n - u a t i o nm e t h o d i ta l s op r o p o s e st w ok i n d so fp s e u d o t i m es t e ps e l e c t i o nm e t h o d s ，a n da d v a n t a g e sa n d d i s a d v a n t a g e so ft h e s et w ot y p e so fn o n l i n e a rm e t h o d sa r ev e r i f i e dt h r o u g ht h en u m e r i c a le x p e r i m e n t s k e yw o r d s ：p s e u d o t r a n s i e n tc o n t i n u a t i o n ，n o n l i n e a ri t e r a t i o n ，n o n i n e a re q u a t i o n s ，g l o b a lc o n v e r g e n c e l i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得宁夏大学或其它教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名： 。刁始 时间：p 卜年靼二矿日 关于学位论文使用授权的说明 本人完全了解宁夏大学有关保留、使用学位论文的规定，即：学校有权保留送 交论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复 制手段保存、汇编学位论文。同意宁夏大学可以用不同方式在不同媒体上发表、传 播学位论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 研究生签名： 导师签名： 、习扬 时间：2 6 b 年j 月j g 日 时 间：加p 年阴谚 宁夏人学硕 j 学化论文 第一章引言 1 1 研究背景和意义 随着现代科学技术的迅速发展，科学与工程计算的许多领域中所出现的非线性问题越来越 多，关于各种非线性问题的研究也日益受到人们普遍高度的重视，各门交义学科中的非线性问题 已经逐渐成为科学研究的热点之一利用计算机求解各类非线性问题，最终总可归结为非线性代 数问题的数值近似，而非线性代数方程组的数值求解，则是这些非线性代数问题的数值近似的基 础和关键所在 考虑非线性方程组 f ( u 1 = 0 对于求解形如光滑的非线性方程组( 1 1 ) 的问题，早在上个世纪七十年代以前，就己经有许多 学者做了大最的广泛深入且富有成效的研究t 作，并且已经得到了一系列实用高效的计算方法， 这在文献 1 3 】巾已经作了系统的总结但是由于函数f 的非线性性质，给研究这些问题带来了一 定的困难，从已有的理论与解法的实用性来看，对于菲线性方程组的算法设计和理论分析却远远 没有线性方程组那么成熟对于方程解的存在性以及有效解法还有待进一步研究和改善我们知 道除了极为特殊的非线性方程外，直接解法几乎是不可能的，一般都是采用线性化的方法去构造 各种形式的迭代程序，熟知的n e w t o n 法就是通过逐次线性化而形成的一种迭代法【4 _ 6 1 在各种 求解非线性方程组( 1 1 ) 的数值方法中，n e w t o n 法是最基本和最重要的方法之一，包括割线法，非 精确n e w t o n 法以及信赖域这些非线性的迭代算法，都是以它为基础，经过进一步改进，推广和 发展而得到的【7 - 12 】 随后又有作者提出了诸如n e w t o n k r y l o v 子空间方法【1 3 - 1 5 】，其中最为典型的是n e w t o n g m r e s 方法配以线搜索方法以及j f n k 等非线性迭代方法【1 6 - 2 0 】j f n k 法是专门求解大型隐式非 线性方程组的一种联立求解的算法j f n k 是非线性方程组的非精确n e w t o n 法和求解大型稀疏线 性方程组的k r y l o v 的一种完美结合由于在很多实际问题中，这些方法在计算实施巾严重的受到 初值选取的影响，从而导致非线性迭代不收敛，或是收敛到不好的结果如当初始迭代解离精确 解较远时，诸如线搜索和信赖域等方面，它们收敛到非物理解或局部极小残差范数，当解有复杂 的结构如激波或小连续的情况时，更是如此【2 1 2 2 1 因此，在这里我们介绍另一种求解非线性方程组的全局收敛性的方法一伪瞬时延拓方法，该 方法的思想是将一个与时间无关的问题转化为一个与时间相关的l 口j 题，然后再采用n e w t o n 法中 去求解该方程，最终获得一个快速的渐进收敛该方法具有物理背景，容易理解，对于发展到稳 态的问题比较有效该方法在空气动力学【2 3 】、磁流体力学【2 4 】、辐射转换、反应流【2 6 】等领域 已得到了广泛的应用 1 2k l n s o l 软件 本文数值实验均在n s o l 软件包上进行，该软件包由美国l l n l 实验室开发，躲g f l k r y l o v t 空间迭代方法作为线性求解器的非精确n e w t o n 解法器k i n s o l 是s u n d i a l 软件包的基本组成部 宁夏人学硕i j 学化论文第一章r ；f言 分，s u n d i a l 是一个非线性和微分代数方程求解器的套装( s u i t eo f n o n l i n e a r a n dd i f f e r e n t i a l a l g e b r a i c e q u a t i o ns o l v e r s ) ，它是f l q l l n l ( l a w r e n c el i v e r m o r en a t i o n a ll a b o r a t o r y ) 中的c a s c ( c e n t e rf o ra i r - p l i e ds c i e n t i f i cc o m p u t i n g ) 开发s u n d i a l s 提供了鲁棒的时间积分和非线性求解器，主要适用于 求解菲线性微分代数方程s u n d i a l s 基于标准c 语言开发，由串行并行常微分方程初值问题求 解器c v o d e p v o d e 、c v o d e 的扩展c v o d e 、非线性代数方程求解器k i n s o l 和微分代数方程初值问题 求解器i d a 等多个子包组成s u n d i a l s 的这四个解法器均提供串行和并行版本2 0 0 9 年5 月发布 了s u n d i a l s 当前最新的版本2 4 0 该解法器适合于在大规模并行计算机上求解f 2 r 1 1 3 本文主要研究工作 本文首先简要地综述了一些非线性迭代方法及其算法，并总结出方法各自的优缺点随后着 重介绍了一种新的具有全局收敛性质的方法一伪瞬时延拓方法，该方法严重地依赖于伪时间步长 的选取，如果选取的方法较好，则明显会加快收敛且收敛到一个好的结果，国外已提出了几种选 取方法，但国内研究并应用该类方法还很少，因此本文比较了几种已有的伪时问步长选取方法的 计算效果，并尝试设计更为有效的伪瞬时时间步长，并提出了加权的伪瞬时延拓方法最后，通 过对几个典型的非线性发展方程进行数值模拟实验，比较全局化的n e w t o n k r y l o v 子空间方法与 伪瞬时延拓方法的计算效果数值实验表明伪瞬时延拓方法是一类快速收敛且具有全局收敛性的 方法 2 宁夏人学硕l j 学化论文 第_ 尊数值方法综述 ! i i i 一 一一| 1 - _ 2 1n e w t o n 法 第二章数值方法综述 在求解非线性系统的物理模型时，最为典型的方法是n e 州o n 法我们假定+ l 为非线性模 型关于f ( u ) 函数的根，或者是二项泰勒展开式而( “) 的根，其中( u ) 代表二项泰勒展开式中的线 性部分，t 。为其初值，即 即 其中 t o ( u 。+ 1 ) = f ( u 。) + f ( 缸。) ( 让。+ 1 一乱n ) = 0 f l ( u 。) ( u 。+ l u n ) = 一f ( u 。) f ( t 。) p = 一f ( u 。) p2t n + 1 一u n 称为n e w t o n 步长 假定- j a c o b i a 矩阵f ( t 。) 是稠密的，为了从当前的点u 。计算n e w t o n 迭代点u 馆+ 1 ，必须先估 计f ( u 。) 并且判断迭代是否终止，如果迭代继续，则首先j a c o b i a 矩阵f ，( “n ) 必须被计算出或 是因子化，其次是计算f 7 ( u 。功= 一f ( n k ) 的解，最后是校正乱。+ l = u n + p 在这蝗步骤 中，f 7 ( u n ) 的估计或因子分解其代价很大f 7 ( 仳) 的因子分解花费o ( n 3 ) 浮点迭代通过有限差 分估计f 7 ( u ) 是估计f ( u ) 的倍因为f 7 ( u ) 的每一列需要一次f 的差分近似估计，冈此牛顿迭代 大概需要+ 1 次f 估计和o ( n 3 ) 浮点迭代。在很多情况下，f 7 ( 让) 可以更有效，更精确，更直接 地计算出来，而不是运用差分，比如对f 7 ( u ) 进行l u 分解，还有诸如q , r 或c h o i e s k y 等分解 定理：假定方程( 3 1 ) 有解u ；f 7 是l i p s c l l i t z 连续的；f 7 ( 仳) 是非奇异的，则存在6 ，如果u 耙属 于b o ) ，$ l j n e w t o n 迭代 平方收敛于t + t n + l = t 正n f 7 ( u n ) 一1 f ( 乱竹) 口 n e w t o n 法是假定初始迭代”充分接近”解的，然而，许多情况下，初始迭代不是菲常接近于根 的当初始迭代离根很远时，通常采用的方法是信赖域和线搜索方法，而这些传统的方法可能会 收敛到非物理解或是局部极小点，因此发生停滞现象，特别是l 口j 题复杂如激波或小连续的情况更 是如此以下是n e w t o n 法的实现算法： 3 宁夏人学硕i j 学化论文 第一：尊数值方法综述 - _ l _ i i 一_ i 一_ u ，! ，! ! ! ! _ ! ! ! ! ! ! ! ! ! ! ! ! ，! ! ! ! l ! ! ! ，皂! ! ! ! ! ! ! ! ! 蔓 算法2 1 1 ：( n e w t o n 法1 0 输入初始迭代仳o ，非线性映射f 1 r o = 0 f ( u o ) 0 为残差 2 f o r 佗= 0 ，1 ， 2 1 计算f 7 ( u ) ； 2 2 求解f 7 ( t 竹) p = 一f ( ) 2 3 置u n + 1 = u t l + p ； 2 4 估计f ( 牡) 注2 1 1 ：u n 是当前迭代步，t | 。+ l 是下一个迭代步 算法中f 7 ( 乱) 的估计和冈予化f 7 ( 札。) = l 【，的计算鼍很大，为了减少计算量，一种方法 就是将计算f 7 ( t ) 和因_ 予化f 7 ( t 上。) = u 这两步提出主循环，这意味着通过初始迭代u n + l = 咖一f 7 ( u o ) f ( u 。) ，在每一步有含有导数的迭代线性近似求解f ( 钍) = 0 ，通常称这一方法为弦 截法 算法2 1 2 ：( c h o r d 法) 0 输入初始迭代仳o ，非线性映射f 1 计算r o = i i f ( u o ) l l ，伯为残差 2 计算f ( u 。) ； 。 3 因子化f 7 ( u 。) ； 4 f o r 几= 0 ，l ， 4 1 求解f 7 ( u n ) p = - f ( u 竹) 4 2 置1 1 , n + 1 = 珏n + p ； 4 3 估计f ( u ) 实施n e w t o n 法时唯一不同于弦截法之处在于：迭代开始前先将j a c o b i a 矩阵计算出来和冈予 化，即在迭代中f ( 乱n ) 的近似解被用到如果初始迭代值足够精确，则弦截法j i 进行很少次迭 代假定f ( 乱) 和f 7 ( 乱) 是非精确求解的，则f ( ) + e 和f ( u ) + 用来代替f ( 札) 和f 7 ( 札) ，如果足 够小，则迭代的结果在小的局部范围内近似于精确解z + 如果是浮点舍入，贝j j l l f ( u 。) 1 1 不一定 比e 更小那么非线性残差将不会再减小，以至于迭代终止这表示n e w t o n 法在这一局部小范围 内不收敛i s ，6 1 n e w t o n 法是最基本和最重要的方法之一，包括割线法，非精确n e w t o n 法以及信赖域方法在 内的许多非线性迭代算法，都是以它为基础，经过进一步的推广和发展而得到的 n e w t o n 法的显著优点： 4 宁夏大学顶 j 学化论文第一章数值方泫综述 能快速地收敛到二阶精度； 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 法的汁算代价就很昂贵； 不具有全局收敛性质 2 2 非精确的n e w t o n 方法 为了减少n e w t o n 法的计算代价，并且避免其不足，1 9 8 2 年，又有研究者提出了求解非线性 方程组的非精确n e w t o n 法非精确n e w t o n 法就是在n e w t o n 法的每步迭代中只对n e w t o n 方程进行 近似求解即在n e w t o n 法的每步迭代中，我们需要求解n e w t o n 方程 f 7 ( 札。) p = - f ( u n ) ( 2 1 ) 当该线性方程组的维数较高时，计算其精确解的开销就会很大，辛h 应的n e w t o n 法的计算景也会 很大如果利用非精确n e w t o n 法，则既可减少算法的工作量，又能保持n e w t o n 法的局部二阶收 敛性因此，非精确n e w t o n 法是求解大规模稀疏非线性方程组的十分有效的t 具之一【7 | 算法2 2 1 ：( 非精确的n e w t o n 法) 1 选取初值x 0 r “ 2 对于k = 0 ，1 ，2 ， 2 1 选取丽【0 ，1 ) 2 2 近似求解n e w t o n 方程( 2 1 ) 并得到p ，使其满足 i i f c u 。) + f ( u n ) p l l 2 而l l f ( u 。) 1 1 2 ( 2 2 ) 2 3 置u n + l = t r i + p 在上述非精确的n e w t o n 方法中，丽为强制项，p 称作n e w t o n 法步长，而约束条件( 2 2 ) 贝j l 称作 非精确n e w t o n 条件 在上述算法的每个迭代步，我们只需近似求解n e w t o n 方程，得到满足非精确n e w t o n 条 件( 2 2 ) 的解显然，f ( u n ) + f 7 ( u n 汩既是n e w t o n 方程的残鼍，又是f ( 仳) 在u n 处的局部线性模 型，所以丽的大小在本质上刻划出了对n e w t o n 方程求解的精确程度特别，如果选取而= 0 ， 则非精确n e w t o n 法就退化为n e w t o n 法 值得指出的是，当迭代点z 七远离非线性方程组( 1 1 ) 的精确解时，不宜选用过小的强制项 因为如果选用过小的强制项，就很可能会导致解的 出( o v e r s o i v i n g ) 现象：即在求解n e w t o n 方程 时，若当前已达到了适当的精度，l i f ( z ) i | 就会得到很好的下降，菪此时再对n 州o n 方程去精确 5 宁夏人学硕l ! 学f 节论文第章数值方法综述 求解，则可能会造成大量的计算开销，并nj f ( x ) j l 不一定能更好的下降，这时则有可能会导致 迭代中断现象 关于非精确n e w t o n 法的局部收敛性分析表明，如果强制序列丽一致地小于1 ，则非精 确n e w t o n 法具有局部线性收敛速度；如果丽= 0 ，则非精确n e w t o n 法具有局部超线性收敛 速度；更进一步，如果丽= o ( i i f ( x ) h ) ，则非精确n e w t o n 法具有局部二阶收敛速度非精 确n e w t o n 法的这些特征，为我们恰当地选取强制序列提供了理论依据 强制序列对于非精确n e w t o n 法的收敛性质和数值行为起着至关重要的作用它不仅影响着 算法的计算效率，还影响着算法的准确性和强健性在具体实施时，一般总是预先给定强制序列 的上界叩。 1 ，然后再在迭代过程巾选取强制项仉 叩m 。z 强制序列的最简单的选取方法就 是选取常数序列当然，要选取一个能够使得非精确n e w t o n 法的整体计算效率达到最高的强制 序列，是十分困难的尤其是在实际应用中，由于无法判断当前迭代点与真解之间的距离，因此 很难确定当前强制项的大4 , s 1 非精确n e w t o n 法实质上是一类内外迭代算法，外迭代为经典n e w t o n 法，内迭代则可采用任 何能够准确而有效地计算n e w t o n 方程解的线性迭代法这种内外迭代的方法充分利用了j a c o b i 矩 阵的结构及其稀疏性，冈此其优点是：大大降低了n e w t o n 法的汁算成本，节省了存储空间，并 且提高了计算效率；其不足是：第一，若当迭代初值离精确解较远的时候，迭代的结果不收敛， 或是得到非精确解；第二，不具有全局收敛性 在非精确的n e w t o n 方法中，我们可以根据j a c o b i 矩阵的结构和特点，运用高效的线性迭代 法，如k r y l o v 子空问方法等去近似求解n e w t o n 方程，每步只需用有限差分替代j a c o b i 矩阵与向 量的乘积运算，从而允需显式形成j a c o b i 矩阵，因此，又称该方法为j a c o b i 矩阵自由的n k i 了空 间方法( j n ) 【9 一l 引目前，j f n k 方法在计算物理等许多领域已经得到了广泛应用，n e w t o n g m r e s 方法是这类方法的典型代表该方在很多时候都是配以线搜索方法使用，为的是能哥- 找 到好的牛顿方向，使残差能够逐渐减小，以便结果能更好的收敛因此，先简单的介绍一下全局 收敛以及线搜索方法 2 3 全局收敛 本文主要介绍了一种具有全局收敛性质的迭代方法一伪瞬时延拓方法，而全局收敛满足的条 件是：( 1 ) 初值任意选取；( 2 ) 保证结果一定收敛；( 3 ) 收敛的解唯一通常全局收敛包括线搜索和信 赖域等方法，其中线搜索是一个很有效的方法，常常配以其它方法使用，如n e w t o n - - k ：r y l o v 了空 间方法配以线搜索的方法，n e w t o n a r m i j o 解法器等那这一节先介绍一下线搜索 2 3 1 线搜索 这节通过一个简单的实例得到今局收敛的一个算法，该算法对迭代中的初始迭代收敛 于f 的一个解，或者在一些小的迭代步中求解失败很多诸如该算法，而我们最关注的是线搜索 方法和a r m i j o 准则 我们选择线搜索方法是因为它的简单性，并且因为在实施n e w t o n 法收敛的过程巾很容 易添加线搜索，下面先看这个例子对于单个方程，( u ) = a r c t a n ( u ) ，如果运n e w t o n 法荨 找解矿= 0 ，初值牡o = 1 0 我们发现当初值离精确解较远时，局部收敛理论适用，原冈 是，7 ( 乱) = 南对于很大的让值，( 札) 很小，此时，( u ) = a r e t a n ( u ) 考，因此牛顿步的次数要 6 宁夏人学硕i j 学化论文第章数值方法综述 比迭代本身大很多我们可以从以下迭代序列中看出： 1 0 ，一1 3 8 ，2 9 车1 0 4 ，一1 5 宰1 0 9 ，9 9 丰1 0 1 7 可以看出，对于精确解，该牛顿的迭代点上冲的数越来越大，导致了n e w t o n 方法的失败 假如再进一步分析，n e w t o i l 步s = 一蠢拳指向的解，在一定程度上有s t 。 1 r r o + 2 1 i f f 7 ( t o ) = 0 ，则失败终止， 2 2s = 一熬告( 寻找方向) 2 3 撕= t + 8 ( 试验点) 2 4 玎l f ( u t ) l i ，( u ) it h e n = u t e l s e s = s 2g o t o2 3 当我们应用算法l i n e s l 至l j 上述的例子中时，我们获得序列 1 0 ，一8 5 ，4 9 ，一3 8 ，1 4 ，一1 3 ，1 2 ，一0 9 9 ，0 5 6 ，一o 1 ，9 ，i c1 0 4 ，一6 木1 0 1 0 n e w t o n 法的平方收敛性只是出现在迭代的最后在第l ，2 ，3 ，4 次迭代时需要3 ，3 ，2 ，2 次步长的减小，在 第四次迭代后，整个牛顿步中非线性残差获得了下降，如果菲线性残差的绝对值持续下降，则小 需要置t = t + s ，也不需要测试步长我们称该方法为线搜索因为我们搜索线段u 。，u 。+ 。) 中 找出l i ( u 。) i 的减小 上述算法几乎一直运行的很好，然而在理论巾，解有可能振荡导致小收敛，为了改进此方 法，我们用足够减小来代替简单的减小在算法中去计算搜索方向d ，即n e 叭o n 方向d = 一羁熬， 并且测试步长8 = a d ，入= 2 - j ，j 0 ，宜至- i j f ( u + s ) 满足 f ( u c ) + a d i r r r o + 2 1 i f f 7 ( u o ) = 0 ，则失败终止， 2 2 s = 一篇( 寻找方向) 2 3a = l 2 3 1 毗= u + a d 2 3 2 玎i f ( u t ) i 1 一q 入) l ，( u ) lt h e n 札= u t e l s e a = 害g o t o2 3 线搜索在减d 、n e w t o n 步长时需要更多的技巧，而不仅仅是取失败的n e w t o n 步长的一半的 值这样做的目的是对于一些问题，可以通过合适的步长的减小因子使得n e w t o n 迭代在一步或 是两步减小时表现出好的结果并且其他的问题也需要很多像这样的减小如果步长的减小冈子 取0 1 的话可以是结果更好另一方面，减小入将会花费很大的代价，在整 n e w t o n 步中保证了快 速的局部收敛 2 3 2a r m i j o 准则的分析 上一节主要针对的是单个方程的线搜索算法介绍，这一节我们针对多元函数，通过两种方 法对上述算法进行扩充第一种是我们接受任意的方向，其满足非精确n e w t o n 法条件我们写 成h r m i j o 序列是 i l f 7 ( u 。) d n + f ( u n ) | l 叼。i i f ( u 。) i ( 2 4 ) 第二种方法是在减小入时允许更多的弹性，是满足 。匆入耐d 入n e ( 7 1 h o l d 其中0 o 0 盯l r r r o + r a 2 1 寻找方向d 使得 l i f 7 ( 乱。) d 。+ f ( u 。) l i l l f ( u 。) l i 若果找不到矗，则终止 2 2 入= l 2 2 1 毗= t + a d r 宁夏大学硕i + 学化沦文第节数值方法综述 2 2 2 玎l f ( u t ) i 1 一a a ) i ，( ) it h e n 钍= 札 e l s e c h o o s e 仃【a o ，仃1 1 ， a = a ag o t o2 2 1 最重要的是：该算法可能在迭代中出现以下情形，假定是通过n s o l a 算法得到的迭代解， f 7 ( ) 对于一些n 是奇异的，内迭代将终止 u 。一霞，f 局部小，而得到的不是精确解 i l u 。i l _ o o 如果f 没有根，算法必然失败，我们将看到如果f 没有根，则要么f ( u 。) 有有限个点是奇异的， 要么乱。变得无界 如果f 7 ( u 。) 是非奇异的并且有一个很好的近似被用来计算n e w t o n 步长，则j f 精确的n e w t o n 山 m i j o 的收敛理论是有效的，j a c o b i a n 矩阵近似的不好的话则会使得牛顿步变得不精确，当迭代 解离精确解很近的时候，也可能导致收敛的很慢，当迭代解离精确解很远的时候，输出的结果将 会更糟糕当初始迭代解离精确解很远的时候，诸如割线法和弦截法再配以线搜索将会实施的很 好，但是在实际应用中，许多运用非线性解法的研究人员可能会注意到线搜索可能会失败，面对 这样的失败只能通过运用更精确的j a c o b i a n 矩阵或是j a e o b i a n 矩阵向董乘积 总之，n e w t o n a n r i i i 解法器中非线性残差的范数在每步迭代中能持续的下降，并且能收敛到 问题的精确解，发散到无穷，或者当f 7 ( u 竹) 奇异的时候，在某一节点上迭代会发生停滞 差分逼近通常可以使得j a c o b i a n 矩阵足够精确，然而特别是对于复杂的大规模问题时， 在坐标方向差分是非精确的，然而差分在残差迭代步中时很精确的非精确的n e w t o n 方法诸 如n e w t o n k r y l o v 子空间方法运用向前差分逼近j a c o b i a n 矩阵向量乘秋的产物，当解高精确解很远 的时候，该方法能很好地收敛于n 丑题的精确解【6 1 2 4n e w t o n k r y l o v 方法 非精确的n e w t o n 法只具有局部收敛性质，为了保证其所产生的迭代序列收敛，通常要求迭 代初值必须与问题的真解充分靠近，而这一要求在实际应用中是难以得到实现的鉴于此，许 多学者通过各种途径将非精确n e w t o n 法加以改造，建立了具有全局收敛性质的非精确n e w t o n 方 法，如n e w t o n k r y l o v 方法，n g b 方法等，n e w t o n k r y l o v 方法是种菲精确牛顿法，该方法是求 解大犁稀疏非线性方程组重要并且很有效的方法，且k i n s o l 也是基- 于n e w t o n k r y l o v 予空间方法 的一种非线性解法器 f l 顾非精确的n e w t o n 法运用方向d 近似n e w t o n 方向使其满足 成立，此处的r 称作强制项 i i f 。) 厶+ f ( u 。) l l i i f ( t t 1 ) 9 宁夏人学硕卜学他论文第一节数值方法综述 牛顿迭代方法认为是运用非精确牛顿条件( 2 4 ) 通过线性迭代方法在迭代步中去求解方程并且 当上述条件成立时迭代终止我们称这类线性迭代为内迭代，通常非线性迭代称为外迭代 采用k r y l o v 子空间方法对n e w t o n 方程进行求解，我们即可得至j n e w t o n - k r y l o v 子空间方 法，n e w t o n k r y l o v 方法是运用i o y l o v 子空间基于线性解法器求解的，该方法不需要大量 存储并且花费大的代价去估计f ，并且具有稳健性现有的k r y l o v 线性解法器包括以下三 种：g m r e s ，b i c g s t a b ，t f q m r 【圳 众所周知，n e w t o n g m r e s 方法仅具有局部收敛性质，但是在实际应用中，具有全局收敛性 质的方法则往往更为有效对于n e w t o n g m r e s 方法来说，如果在其非精确n e w t o n 方向d 上配以 线搜索策略，则可得到以下算法： 算法2 4 1 ：n e w t o n k r 讲删配以线搜索方法【1 9 1 1