求解非线性方程的迭代算法研究

1、陕西理工学院毕业论文第 1 页 共 18 页求解非线性方程的迭代算法研究求解非线性方程的迭代算法研究XXXX（XXXX 学院学院 XXXX 专业专业 XXXX 班班, ,陕西陕西 XXXX 72X00072X000）指导教师指导教师:XX:XX 摘要 在利用数学工具研究社会现象和自然现象，或解决工程技术等问题时，很多问题都可以归结为非线性方程的求解问题，无论在理论研究方面还是在实际应用中，求解非线性方程都占了非常重要的地位.迭( )0f x 代法是求解非线性方程根的一种最重要的方法，而迭代法的优劣对于非线性问题求解速度的快慢和( )0f x 结果的好坏都有很大的影响，所以从实际出发，进行高计算

2、效能迭代算法的研究具有重要的科学价值和实际意义.关键词 牛顿法;迭代法;非线性方程;收敛的阶;陕西理工学院毕业论文第 2 页 共 18 页目录目录1 引言引言.32 基础知识基础知识 .43 NEWTON 迭代法迭代法.53.1NEWTON迭代法的推导.53.2NEWTON迭代法的收敛.74 其它迭代格式和变形的牛顿法其它迭代格式和变形的牛顿法.104.1 其它的迭代的格式.104.2 变形的牛顿法.11结束语结束语.错误！未定义书签。参考文献参考文献 .13ZUODIAN .14TUTOR: QUANSHUANGYAN.14陕西理工学院毕业论文第 3 页 共 18 页1 引言引言近几十年来，

3、数值工作者们不断在原有的迭代法基础上的提出一些新的迭代格式，事实上这些新方法大多是根据实际情况的需要对经典的迭代格式进行修正和变形，因此Newton法等一系列经典的迭代法就成为我们讨论新的迭代方法的起点.数学家们对这些方法都做了很深入的研究，关于这方面的文章著作也是数不胜数，其中有非常丰富的理论结果和证明技巧是可以借鉴的.最基本的迭代法，自然对我们的讨论也是最核心的，所以在就来重点讨论Newton迭代法.陕西理工学院毕业论文第 4 页 共 18 页2 基础知识基础知识 非线性方程，就是因变量与自变量之间的关系不是线性的关系，这类方程很多，例如平方关系、对数关系、指数关系、三角函数关系等等.求解

4、此类方程往往很难得到精确解，经常需要求近似解问题.在利用数学工具研究社会现象和自然现象，解决物理、化学、生物、工程技术，甚至社会经济等实际问题时，往往都可以归结为求解某个非线性方程 (11)( )0f x 的根的问题.就方程(11)的形式而言，可能是次多项式：( )F xn11100nnnna xaxa xa也可能是由多种函数组成的非线性方程.譬如：在人口增长模型中假设某一地区人口的数量随时间连续增长，即( )( )dN tN tdt，其中N(t)表示该地区在t时刻的人口总数，为人口增长率常数.该微分方程的解为0( )tN tN e，其中N0为该地区的初始人口总数.但上述模型没有考虑到外部移民

5、的迁入的情况，若允许移民以某常速率u进入该地区，则微分方程是( )( )dN tN tvdt其解为：0( )(1)ttvN tN ee现假设某地区有100万人口，第一年内有435万移民迁入，第一年末总计人口1564万.根据上述数据可以推算出该地区的增长率常数满足方程：、43.5156.4100(1)ttee上面这个微分方程的解析解比较容易求出，所以求解这类问题就可转化为求解非线性方程的问题.谈到解非线性方程，就不得不提迭代法，它是最有效最便利的求解方法.迭代法就是从预知的解的初始近似值(简称初值)开始，采用某种迭代格式构造一近似值序列0121,kkx x xxx逐步逼近于所求方程的真解. 对方

6、程(11)求近似根，先将其改写成等价的方程： ( )xf x (12) 所谓等价就是：如果是方程(11)的根，那么*()xf x；反之如果满足方程(12)，*x*x陕西理工学院毕业论文第 5 页 共 18 页那么.最简单的等价变换是令，当然还可以根据的特点来变换.( )0f x ( )( )f xxF x( )F x称为迭代函数，为函数的一个不动点，求的零点就等价于求的不动点.选( )f x*x( )f x( )F x( )f x择一个初始近似值，将它代入(1.2)式右端，即可求得0 x0()xf x可以如此反复迭代计算 (13)1(),0,1,2,3kkxf xk如果得到的序列有极限 kx

7、*limkkxx则迭代方程(13)收敛，我们称(13)为不动点迭代法.不动点迭代法是最简单的迭代法，它是一种逐次逼近的方法.其基本思想是将隐式方程(12)归结为一组显示的计算公式(13)，就是说迭代过程实质上是一个逐步显示化的过程.但是迭代序列能否作为方程的根的好的近似，或者能否收敛于，以及能否快速的收敛kx*x*x到呢?这些都是我们后面所要探讨的问题.对于一种解法，为了考察它的有效性，一般都要讨论*x它的收敛性和收敛速度，即考虑在什么样的条件下构造的序列是收敛的，以及序列中的近似值是按什么样的误差下降速度来逼近真解的.迭代过程的收敛条件，一般与方程的性态(函数在解附( )F x近的性质，零点

8、的分布状态等)以及初值的近似度有关，而某些方法仅与初值的近似度有关，故有时也称收敛条件为收敛范围.迭代过程的收敛速度，是指在接近收敛过程中近似值误差的下降速度.一般来说，它主要由方法所决定，方程的性态也会有一些影响.如果由一种迭代解法构造出来的近似值序列与解的误差为123,kx x xx*x *1*limkrkkxxKxx或者，当充分接近于解时有关系式kx*x*1*rkkxxK xx当r1时，称该迭代法具有阶的收敛速度.通常具有阶收敛速度的算法，当接近收敛时其近似值的误差将按幂次为r的速度下降.因此越大，误差就下降的越多，收敛速度就越高；越小，误差就下降的越少，收敛速度就越低.陕西理工学院毕业

9、论文第 6 页 共 18 页3 Newton 迭代法迭代法3.1Newton 迭代法的推导迭代法的推导 对于求解非线性方程 (21)( )0f x 的零点问题，有很多种迭代方法,其中最为著名的就是Newton迭代法 (22)1()()nnnnf xxxfx这些迭代法是如何被取得的呢?事实上迭代法的推导方法也是多种多样的.下面我们就以Newton迭代法为例，介绍公式(22)的几个导出途径.方法一方法一，作泰勒级数展开并取线性部分.记*x是方程(21)的根于是,*2*()0()()()()()2kkkkkkxxf xf xfxxxfxxx将右边的二次项去掉，即得 *()()()0kkkf xfxx

10、x令满足1kx /1()()()0kkkkf xfxxx，即得公式(22).方法二方法二，重节点反插值.可以把方程(21)的根看做函数( )yf x所表示的曲线与x轴的交点.函数( )yf x有反函数( )xy，求根*x即为求.在处有函数值，即()kkxy.将在作重(0)kx()kkyf x(0)ky节点插值，即得 2(0)()()(0)(,0)(0)kkkkkkyyyyyy由数学分析可知，则得()1/()kkyfx .*21()(,0) ()()kkkkkkxxf xyyf xfx令陕西理工学院毕业论文第 7 页 共 18 页 ,1()()kkkkf xxxfx此即为公式(22).方法三方法

11、三，为了求曲线与轴的交点，用过()处的切线与轴的交点来近似.( )yf xx,()kkx f xx因为过的切线方程为,()kkx f x ，()()()kkkyf xfxxx它与轴的交点的横坐标即为x .1()()kkkkf xxxfx不同于以上三种传统的推导方法，Weerakoon1和Fernando运用Newton-Leibniz公式和Newton-Cots求积公式又提出了一种新的导出Newton法的方法.对于Newton-Leibniz公式 ， (23)( )()( )nxnxf xf xf t dt可用零阶Newton-Cots求积公式2(矩形公式) ( )()()nxnnxf t d

12、txxfx来代替(2，3)式中的定积分，并且令，就可得到Newton公式.类似( )0f x 的，将定积分替换为一阶Newton-Cots公式(梯形公式) ()( )()( )2nxnnxxxf t dtfxfx可得到一个隐格式的迭代法 .112 ()()()nnnnnf xxxfxfx为了把隐式变为显式,这里 *1()()nnnnf xxxfx由此可以得到一个三阶方法 12 ()()()()()nnnnnnnf xxxf xfxfxfx显然这两种方法的不同之处就在于选择的求积公式不同，所以得到了不同的收敛阶.后来，Frontini和Sormani又丰富了Weerakoon和Fernando的

13、结果.通常的插值型求积公式(高于零阶)可以统一记为 ， (24)1,0( )()()nmxnii nxif t dtxxA f陕西理工学院毕业论文第 8 页 共 18 页其中 ,()i nninxxx，i=0，1，2，m-1，是区间0，1上的求积节点，是相应的求积系1iimiA数且满足条件.把(24)式中的换为，代入(23)中.假设11miiAf/f是的一个根，令，可得到( )f x,x (2.5)1*,0()()nnmii nif xxA f其中 (26)*,()i nninxx 显然这是一个隐格式，那么用Newton迭代来代替上式中的就可/()()nnnf xxfx得到一个显式方法 ， (

14、2.7)11.0()()nnnmii nif xxxA f这里 (28),()()()ni nninf xxfx只要在(25)式中代入不同的求积公式，就可以得到不同格式的迭代法.显然这族迭代法的形式会随着求积公式的变化而变化，计算代价也会随之增加.但是已经证明了由以上推导方法得出的迭代法(除Newton法以外)的收敛阶是独立于求积公式的选择的.换句话说，就是虽然选择不同的求积公式可以得到不同的迭代格式，但是这些迭代法的收敛阶最高只能达到三阶收敛.之所以收敛阶无法提高，我们发现是因为上面的方法在将隐格式转化为显式时，是用Newton迭代来代替.于是我们尝试使用敛阶高于二阶的迭代法代替，同时提高求

15、积公式的代数精度，如此得到的迭代法的收敛阶就会随之提高.陕西理工学院毕业论文第 9 页 共 18 页 3.2Newton 迭代法的收敛迭代法的收敛到目前为止，已经有很多不同的迭代方法被数值工作者们提出了.在Ortega和Rheinboldt中已经有了比较详细的介绍.其中最经典的就是二阶收敛的Newton迭代法1()()nnnnF xxxF x (2.9)众所周知，Newton迭代法形式简单，收敛速度也比较快，在具体计算中一直都是求解非线性方程(2.9)最重要的迭代方法.数百年来，虽然新的迭代格式层出不穷，然而几乎所有的迭代法的研究都是以Newton迭代法的证明技巧和分析方法为基础的.有关New

16、ton迭代法的收敛性方面的研究是数不胜数，其中有很多理论结果都被借鉴.无论是理论研究还是实际应用，Newton迭代在迭代法的历史上所起的作用是其它任何迭代法所无法替代的.关于Newton迭代法的研究情况已有很长的历史.十九世纪初，Cauchy就在实数空间冗中对Newton法的收敛性进行了初步的研究.但所给的条件涉及求解一阶导数极小值之类的整体条件.1937年，Ostrowski10在复数空间C中对Newton法的收敛性进行了深刻的研究.后来Kantorovich5成功的给出了Banach空间内Newton法的著名的Newton-Kantorovich收敛性定理，关于这方面的文献4和7他给出的收

17、敛条件为：1.设F是由Banach空间X的一个非空凸集到同型空间y的Frechet可微算子；2.存在点0 x ，假设存在，且；10()F x100|()()|FxF xa3.100|()()( )|F xF xF ybxy，, x y；4.12ab ；5.*( 0,)B xt ，其中*11 2abtb. Kantorovich关于Newton法收敛性的著名工作可以说是解方程算法现代研究的起点.后来有很多数学家都对此定理进行了改进，他们主要是针对上述条件，给出了一些修正条件，来减弱Kantorvich9条件.后来，Wang和Guo将这些收敛性和唯一性定理的条件加以了统一(该条件包括了著名的经典K

18、antorovich条件)，给出了方程(11)解的唯一性及Newton法的收敛性定理.前面列举的这些收敛性条件都是仅考虑了P7的Lipschitz条件.Huang指出F的二阶的导数在收敛性条件中也是有用的，同时弥补了Kantorvoich条件不能判断从某个指定点出发的Newton迭代序列是否收敛.后来，Gutierrez，zhang分别又将此条件改进.此外Argyros在文献中利用了F的高阶导数信息，提出了两个收敛条件.Kantorovich关于Newton法的收敛性定理一直被视为收敛性分析思想的典范，它的特点是对F可微性要求较弱，但需要F的某阶导数的整体性态.为此在1986年国际数学家大会的

19、大报告上，Smale2用尸的解析性条件取代了Kantorovich的整体性假设(即F的某些阶导数在某个足够大的区域中具有Lipschitz连续的假定).完全只用F在初始点的信息来判断Newton迭代方法的收敛性.这对连续复杂性的研究是极为重要的.为了解脱对F的区域信息的依赖，Smale假设F在x解析(并且F在x的Taylor级陕西理工学院毕业论文第 10 页 共 18 页数收敛球内这种解析性不被人为破坏)，并且令( , )a F x 其中1( , ) |( )( )|F xF xF x1112( )( , )sup|( )|!kkkFxF xF xkSmale证明存在一个绝对常数，当0( ,

20、)F x时，从出发的Newton迭代(14)都有00 xx意义并且收敛.后来王兴华3和韩丹夫4求得了的最好结果，即.不仅如此，王兴华等032 2人还证明了是半局部行为下的普适常数.这一结果揭示了关于零点数值过程在半局部行为32 2上的统一性.有关Newton法的研究，除了上面所列，还有很多的学者作了大量的研究工作，并且积累了很多的文献.证明迭代法的收敛性的一个很不错的技巧是优函数技术，这是Kantorovich为了证明Banach空间内的Newton迭代法的收敛性而提出来的.Kantorvich在中提出利用优界函数原理的新证法，其思想就是将一个高维迭代过程和另一个一维迭代过程进行比较，由一维过

21、程的收敛性导出原过程的收敛性.即立足于以下事实：11|nnnnxxtt10100|nnjjnjxxxxttntN收敛，nxN是个Cauchy序列.在证明的过程中，使用的优函数主要有两种：一种是代数多项式.Kantor-vich就是把二次多项式21( )2h tbtt 作为优函数来证明Newton迭代法的收敛性的.当然还可以根据不同情况使用更高次的代数多项式，用代数多项式作优函数的最大好处是可以得到精确的显式误差估计.另一种是有理多项式.最先被Smale提出，其形式为2( )1th ttt 此优函数不仅可被用来证明各种迭代法在点估计判据下的收敛性，更重要的是，能够在同等条件下比较不同算法的效率.

22、除了优函数方法，还有一种证明迭代序列收敛的技巧是递归法.对此Gutierrez6和Hernandez7等人对Halley迭代，Chebyshev迭代，Super-Halley迭代，Jarratt型迭代的收敛性进行了一系列工作.在早期的文章中，用到的是四个实序列，现在减少到两个实序列，递归关系在不断的简化.不过无论是优函数方法还是递归法，它们实际上都是逐步归纳的方法.逐步归纳法的实质就是使后面一步迭代的逼近误差小于前一步迭代的逼近误差，在证明迭代过程的收敛性时，运用了每前进一步迭代都不会破坏定理假设条件的技巧.前面叙述了这么多，都只是理论方面的分析.那么如何具体使用迭代法来求解非线性方程呢?下面

23、我们就给出Newton迭代法求解方程的具体迭代步骤.以本苹开头列举的非线性方程为例，求解方程：陕西理工学院毕业论文第 11 页 共 18 页43.5156.4100(1)ttee首先确定迭代初值，利用迭代格式：01.5x 143.5100(1) 156.443.543.5100(1)xxnnnnnxxnnnneexxxeexx经过几步迭代以后，直到6|( )| 10f x，我们可得方程的解为01009979.其具体过程见下表：迭代次数nx()nf x11.5392.73820.7311697115.45630.25735822.561240.11200771.4818850.10105487.

24、62834E-0360.10099792.04904E-07陕西理工学院毕业论文第 12 页 共 18 页4 其它迭代格式和变形的牛顿法其它迭代格式和变形的牛顿法4.1 其它的迭代的格式其它的迭代的格式自Newton迭代法产生以来，又有很多种迭代方法被构造，其中有代表性的迭代法有：三阶收敛的Chebyshev迭代、Halley迭代、Super-Halley迭代(Newton凸加速)迭代及其变形；四阶收敛的Jarratt迭代法及其变形；另外还有实用的导数超前计值的、导数滞后计值的、避免导映照求逆等变形的Newton迭代法：以及阶收敛的King-Wemer等两点迭代格式.12三阶迭代法-Cheby

25、shev迭代、Halley迭代、Super-Haley迭代和四阶Jarratt型迭代可以概况为以下形式此式1()()nnnnyxF xF x (2.10)11( )()()nnnnnxxs F xF x 1110()()()()()nnnnnnnnnsF xFxyxt yxdtF xF x,0,1,0,1.（1）当时，(1.5)式即为Newton迭代法.()1ns（2）当11( )1(1)2nnnssas ，时，0,1a (a) .11()()()()nnnnnsF xFx F xF x (2.10)式变为一族具有三阶收敛的迭代,其中包括Cheby-shev(a=0)迭代法，Halley(a=

26、1/2)迭代法，Super-Haley(a=1)迭代法等. (b) 11101()()()()22() ()().33nnnnnnnnnnnnsF xFxt yxdtF xF xF xF xF xyx 将其代入(2.10)式，迭代法中避免了求二阶Frechet导数，但同时又能保持三阶收敛的速度,所以(b)中方法更有实际意义.（3）当，11()1(1)2nnnsss 时 (a) 11101()()()()22() ()().33nnnnnnnnnnnnsF xFxt yxdtF xF xF xF xF xyx陕西理工学院毕业论文第 13 页 共 18 页是具有四阶收敛的迭代方法，可将其写成 (2

27、.11)1()()1()22()()3()3()nnnnnnnnnf xf xxxf xfxfxfxfx显然这个方法在每步迭代时，只要计算一个函数值和两个导数值.它最大的优势就在于用较小的计算代价取得很快的收敛速度，并且(2.11)式可用于求解非线性方程组.我们认为迭代法(2.11)是很有价值的方法.(b)111()()()().3nnnnnnnsF xFxyxF xF x这也是一个四阶收敛的迭代方法.另外四阶收敛的迭代法还有：()()nnnnF xyxF x1()2 ()()nnnnnnnyxxyF xF yF xOstrowski10和Traub提出的，后来韩给出了其在Smale点估计下的

28、收敛性分析.此迭代法在一次迭代过程中只需要计算两个函数值和一个导数值，对于求解那些函数的导数值比较难计算的方程，这是个不错的选择.从表面看来，这一迭代法似乎比迭代法(2.11)更有优势，但是它仅适用于一维情形，这就使得此迭代法的实用性大大降低了.除了以上提到的这些三、四阶收敛的迭代法，还有很多变形的Newton迭代法.尽管Newton迭代是一个很强有力的方法并且收敛很快，但数值工作者还是从应用需要出发对它做了种种改进.这主要是因为在各种问题中映照的计值及其求逆的计算代价可能是很大的，所以希望变形的迭代法能够尽量少的涉及这种计算而不影响收敛速度，或者虽然做了同样的计算却能获得更快的收敛速度.关于

29、这方面的改进最为典型的要数三个变形的Newton迭代法了，王兴华，韩丹夫和孙方裕给出了其详细的收敛性分析.陕西理工学院毕业论文第 14 页 共 18 页4.2 变形的牛顿法变形的牛顿法 一大类在计算实践中行之有效的变形都可以写成：10(),nnnnxxA F xnN 的形式，这里用以代替的映照有如下一些取法：1()nF x:nAFE（1）即1 /() ,nm n mAF x11()(),1,1,.nnmknxxF xF xnmk mkmkmkN这里是m一个取定的自然数，而方括号表示取整数的部分.就是说，我们并不在每步迭代都计算导映照并求逆，而是每隔m步计算一次，并将其逆保持使用m步.这种方法可

30、以叫做减少导映照计值次数的Newton迭代.当m=1时，这就是平常的Newton迭代.设是减少导映照计算次数的Newton迭代nx产生的收敛于方程(11)的迭代序列，则其子序列的渐近收敛阶是m+l.如果用这种方法来求解mnx多元非线性方程组，与Newton迭代相比无疑能提高渐近效率.（2）即112(),nnnnnAAA F xA1()nnnnxxA F x11()(),1,1,.nnmknxxF xF xnmk mkmkmkN其中任意指定，使之接近于.这是避免导映照求逆的Newton迭代.其原理是借鉴当年没0A10()F x有除法硬件的计算机中求倒数的迭代法以求的逆，不过只迭代一次.这已足以达

31、到Newton1()nF x迭代的组合算式中对导映照之逆的精度要求，所以这种避免导映照求逆的Newton迭代仍保持平常的Newton迭代的渐近收敛阶.这一思想后来也被应用于变形其它的迭代法，来避免计算导数的逆.（3）有一个适当的超前量；1() ,nnnnAFx比 1111=x-().2nnnnA f x即11()(),nnnnxxFF x11111( )().2nnnxFF x我们称这种迭代法为导映照超前计值的Newton迭代.它并没有增加计值代价，但其渐近收敛阶却提高到了.12若令，则上式变为,2nnnxy陕西理工学院毕业论文第 15 页 共 18 页 (2.12)111111()(),2(

32、)().2nnnnnnnnnnxyxxFF xxyyxFF x这一两点迭代格式是WWerner9提出的.事实上，早在发表的六年之前RFKing8就已经在同一家杂志上提出了一个与(2.12)等价的迭代格式了.1111() (),2()().nnnnnnnnyxF yF xxxF yF x所以迭代法(2.12)被称为King-Werner迭代法.对于这三种变形迭代法，已经证明它们的收敛条件与Newton迭代是完全相同的，这个结论排除了对变形可能影响收敛性的担心.从而可以只从计算方便的考虑出发来选择变形.更重要的是，它们都可以直接应用于解方程组，所以这三种变形的迭代法是非常具有实用价值的.前面讨论的

33、这些迭代方法都是建立在非线性算子F是可导算子的前提之上的，若F是不可导算子，以上迭代方法便不能使用.一种解决方案便是把F分成两个算子之和，可导部分记为日，不可导但Lipschitz连续部分记为G.由此求解非线性方程(11)就变为求解方程( )( )0.H xG x于是Newton迭代法变为11() ()().nnnnnxxH xH xG x陕西理工学院毕业论文第 16 页 共 18 页小结小结以最经典的Newton迭代为例，详细的给出了它的几个收敛性条件，以及常用的证明技巧.同时还介绍了其它一些有代表性的迭代方法，简略的分析了它们各自的特点.从这些内容可以发现，关于迭代法的研究主要是从以下几个

34、方面进行的：迭代法的提出和推导，即如何构造迭代格式;由迭代格式所产生的序列需要具备什么条件才能收敛到方程的根;迭代法的收敛速度和计算效能等;高阶迭代算法的导出.陕西理工学院毕业论文第 17 页 共 18 页参考文献参考文献1SWeerakoom，TGIFernando，A variant of NewtonS method with acceleratedthird-order convergence，ApplMathLett13(2000)87932SSmaie，On the Efficiency of Algorithms of Analysis，Bull(MewSer3王兴华，韩丹夫，N

35、ewton迭代的区域估计与点估计，计算数学，12(1990)47-53。4王兴华，韩丹夫，孙方裕，若干变形Newton迭代的点估计，计算数学，2(1990)145156。 )AmerMathSoc13(1985)87-1215LVKantorovich，On the Newton method for Functional equations DockladyAkademii Nauk SSSR59(1948)1237-12406JMGutierrez，A New Semilocal Convergence Theorem for NewtonMethodJCompand ApplMath79(1997)1311457MAHernandez and MASalanova，A family of Newton type iterative proceases，lnern JComputMath51(1994)205-2148RFKing，Tangent method for nonlinear equations，NumerMath18(1972)298-3049WWerner，Uber ein Verfahem der ordnung 1+以 zur Nullstellenbestimmung，NumerMath32(1979)333-34210 AO