第2章非线性方程求根

1、1例例. 1 xr求求球球体体没没入入水水中中的的深深度度的的球球体体浸浸入入水水中中，密密度度为为将将一一半半径径为为 ，3 43)3( 32 rxrx 解解：根据阿基米德定律，排出的水质量应等：根据阿基米德定律，排出的水质量应等于球体自身的质量：于球体自身的质量：2. 043)( 323 rrxxxf即即0)1(4)(2,0(0) 3 rrff因因为为)2x(0 0)2(3)( rrxxxf 且且的存在唯一。所以方程 0)( xf现代科学技术或工程技术领域的许多实际问题，常常可以归结为求解函数方程：( )0f x ，: fRR其中函数一般是非线性的.如果函数 能写成如下形式如果有使得( )

2、0f，则称 为方程( )0,1,gm且有( )0f x 的根根， 或称 为函数 的零点零点。( )f x( )0 xmf则称 为的 重根，mf或函数的 重零点。f( )()( )mf xxg x3如：如：1110( ).0, 1.nnnnf xa xaxa xan ( )sin0.xf xex 当f (x)为代数方程时，理论上已经证明，大于五次 的多项式一般没有代数解法。 当f(x)为超越方程时，一般不能用代数方法求其根。 所以，超越方程(含有指数和对数等)代数方程（多项式）对于一般的非线性方程，只能用数值方法数值方法求解。4方程求根的问题分成两步：第二步：根的隔离确定根所在的区间，使方程在这

3、个小区间内仅有一个根，该区间叫隔根区间。第三步：根的精确化已知根的一个近似值后，用某种方法对其进行加工，使之满足给定的精度要求。第一步：根的存在性5求隔根区间的一般方法理论依据： ( ) , ( )( )0( )0 , f xa bf af bf xa b设在上连续，且，则 在内至少有一个实根 ； ( ) , ( )0 , f xa bf xa b若在内严格单调，则 在内只有一个根。6本章主要介绍二分法二分法与迭代法迭代法（包括Newton迭代法及其变型、弦割法等）二分法是方程求根最常用而且也是最保险的方法之一。一、算法的基本思想将区间对分，保留有根的区间，舍去无根的区间。如此往复，以逐步逼近

4、方程的根。 ( ) , ( ) ( )0.f xa bf a f b 假设在上连续且基本条件：基本条件：700000000(1)., , ().2 ()0( ) , ()0ababa bxfxfxfxa bfx令，取中点，求若，则得到在上的一个零点；若，则作下一步。01100101()()0()( )0.fxfaaabxfxf baxbb(2).若， 则 令，；若， 则 令，1100 ( )0,f xa bab这样，我们得到 的一个新的含根区间，其长度是原区间长度的一半。,( )kkabf x(3). 对新的含根区间重复上述步骤，我们可以得到一个区间序列，序列中的每一个区间都是函数的含根区间且

5、区间的程度依次减半。二、算法的步骤8a x0 b( )f x a1 b1三、算法的收敛性 11 , ,.,.kka ba ba b二分法产生一个含根区间序列：11,11 ().().22kkkkkkka bbababa其中区间的长度为： k (2)kkkf xabx因此，当足够大时，我们可以用作为函数的一个根 的近似值。1.22kkkkbabax此时有误差估计误差估计：常用来估计k的值9四、算法的优点与缺点 缺点：缺点：不能求偶数重根及复根；收敛速度非常缓慢，与以1/2为公比的等比级数相同；没有充分利用函数值。因此一般不单独使用，但往往可以为其它快速方法提供初值。优点优点：计算简单且必收敛，是

6、一种可靠的算法；对函数性质要求低，只要求函数f(x)连续就可以了。用二分法求方程 3( )1 0f xxx 在1,1.5内的实根， 要求 0.005.解解111.5 1|0.00522kkkb ax 6.k 即可推出所需的迭代次数满足 在区间1, 1.5上至少存在一个根。 ( )(1)1 0,( )(1.5) 0.875 0,f aff bf 其具体过程如下： 例例2.1.1由于因而( )0f x 由误差估计式1061.5 11.32420.0039. 0.00572x11例例2.1.22.1.232( )4100 .f xxx4求 在区间1,2上的根，使得误差不超过10解解4112 1|10

7、22kkkb ax 12.3,k 即可推出所需的迭代次数满足 因而函数 在区间1, 2上存在惟一的零点。 ( )(1)5 0,( )(2) 14 0f aff bf 由于以及2( )380,1,2,fxxxx 由误差估计式( )f xk因此可取 =13.12二分法的一种修正是试位法试位法。在二分法中，原来区间的中点为新的区间的一个端点。因此，每迭代一步，区间的长度均减半。在试位法中，不用中点，而用过点 与 的直线的零点作为新区间的一个端点。在实际计算中，试位法比二分法往往收敛得要快。(,()kkaf a(,()kkbf b在试位法的每一步计算中，有( ),0,1,.( )( )kkkkkkkb

8、axbf bkf bf a13等价变换等价变换( )xx( )0f x ( ) 0f x 的根( ) x的不动点迭代法是一种逐步逼近的方法: 首先给出一个粗糙的初值，反复利用同一个迭代公式，逐步逼近精确解。 用迭代法求方程根的基本步骤如下：第一步：化为同解方程 且连续14第二步：产生迭代序列先建立适当的迭代格式：迭代格式：0 , .xa b再取适当的初值1()kkxx，012,.,.kxx xx利用上述格式可产生一列数：1()( )( )( )m 0likkkkkxxxxf xx若迭代序列收敛，则由可得，因而是的不动点，也即若就是，的根。第三步：取极限limkkx 一定收敛吗？15xy0 x1

9、x2xyx( )yx在直角坐标系中同时作 和 两条曲线，如图所示，则这两条曲线的交点的横坐标就是方程 的根 ，也就是 的根。迭代格式 由 求 ，相当于过曲线上 作水平线与直线 相交，过交点作x轴的垂线，此时垂足至原点距离等于 ，故垂足横坐标为 。yx( )yx( )xx( ) 0f x 1()kkxxkx1kx(, ()kkxxyx1kx()kx 迭代法的几何解释：16由上图可见，曲线斜率 时迭代序列收敛，且 越小收敛越快；反之，若 ，则迭代序列发散。|( )| 1x|( )|x|( )| 1xxyy = xxyy = xx0p0 x1p1 x0p0 x1p1( )xx( )xx在根附近，曲线

10、的切线不说明能太陡！17例例2.2.12.2.130( )10 1.5.f xxxx 求方程 在附近的根解解3311 0 1 2 . 7 8 1.51.35721 1.33086. 1.324721.1132472kkkkxxxxx（ ） 将方程改写为由此建立迭代公式得迭代收敛。3312 0 1 2 .1.52.37512.39.1.1kkkxxxxkx（ ） 若将方程改写为建立迭代公式 得迭代不收敛。18下面给出简单迭代法的一个收敛性定理。1 ( ) , , ;(2), , ,( ) , , , ()( )01( )( ) .kkkaxbLxyxa bxa bx ya bxxa bxa bx

11、xL xyx0存在唯一的根设函数在区间上满足条件:(1)对任意，都有存在常数使得对一切都有则定理2.2方程在上且对任何初值由迭代格式产生的迭代序列并收敛于有误差估计式，.110 1kkLxxxL。Lipschitz条件保证迭代不中断，连续时保证有解压缩映像19 存在唯一性证明证明做辅助函数( )( )xxx，则有( )0,( )0,ab所以，存在点( )0( ). ，使，即若又有*( *) ，则有*( )( *)*.L 所以*. 收敛性任取初值0 , ,xa b则110| ()( )|.,kkkkxxL xLx 所以，任意的初值都收敛。20 误差估计11110()().,kkkkkkkxxxx

12、L xxL xx11.kpkkpkpkkxxxxxx 110.kpkLLxx 10101.11kpkLLLxxxxLL10.1kkLxxxLpp 由 的任意性，令，可得证毕2111 ( ) , 1 , ;( )0(2), , , ( ) , , , , ()(0,1,.) 1( ). kkxC a,ba bxa bxa bxxa bxa bxaxbLLkxx0设函数在区间上满足条件（ ）对任意，都有存在常数使得对一切都有则方程在内有唯一的根且对任何初值迭代序列均收敛于推，并有论10 .1kkLxxxL1 ()()()(),xCa,bxyxyxy当 函 数()时 ， 由 微 分 中 值 定 理

13、得 ：其 中在和之 间 。 由 此 不 难 推 出 下 述 结 论 。2210 1( )( ) , 1.kkLxxxLxxaLb注常数 越小，简单迭代法收敛越快。误差估计式表明:因而构造迭代函数的原则是使在有根区间上有尽可能小的上界。给出了精度要求，可用上述误差估计式来确定所需的注2.迭代次数。101kkxLkxxL设所要求的精度为 ，即要求 ，只需迭代次数 满足 ,即满足10(1)ln/ ln.|LkLxx231| |kkxx可通过检查来判断迭代过程应因否终止而。p对任意正注 .整数3，有1121| | . |kpkkpkpkpkpkkxxxxxxxx 12111(. 1)|,1ppkkkk

14、LLxxxxL11 |.1kkkpxxxL 令，得24例例2.2.32.2.32 ( )9sin10 f xxx 求在0,1内的一个根。解解 (0)10, (1)8sin 10 0,1 ff 由 于，因 而为 有 根 区 间 。1sin1.31( )sin1. 3110sin 01( )sin111,331| cos|1( ).66sin1xxxxxxxx将方程化为等价方程：此时，在区间0,1上，且1000,10 1), (kkxxxx根据定理，任取，由简单迭代格式所产生的迭代序列收敛于方程在中的根。比如取0.4.也可化为等价方程也可化为等价方程 . .但此时定理条件不成立，迭代序但此时定理条

15、件不成立，迭代序列不能保证收敛。列不能保证收敛。2arcsin(91)xx25例例2.2.42.2.42 ( )10 f xxx 用简单迭代法求方程的根。解解 (1.5)0.250, (2)10 1.5,2 ff 由于，因而为有根区间。1111( ) 1.51.5 1( )2 12111( )3.1622112 2.5xxxxxx 且（因）22222111 1( ) 1.51( )1221.5111 (2 ( )1.5)2.25xxxxxx 因且0 1.5,2,x 根据定理，任取由这两种等价方程所构造的简单迭代方法都收敛，且第一种所产生的迭代序列收敛较快。26由于定理中条件(1)一般难于验证，

16、而且在大区间上，这些条件也不一定都成立。所以实际使用迭代法总是在根的邻近进行。*( )( ,)( )1.xOx 如果函数在其不动点 的一邻域定内连理2.2.2续可微，且*01, ()kkxxx 则存在正数使得对任意，由迭代格式产生的迭代序列收敛于 ，且其误差估计式与定理2.2.1中的相同。|( )| 1 实际上只要即可表明收敛性与初值的选择有关！27*( )(,)( )1,1, ( )1.xOxLxxL 因在内连续，且故存在正数使得对，有证 实际用迭代法计算时，先用二分法求得较好的初值，然后再进行迭代。1(), ( )( )()( ),().kkxxL xxxx 另一方面，由又有即。由定理2.

17、2.1知，迭代序列收敛于28性质性质 1. 若方程 x=(x) 在处有根，则当|()|1时，称为超线性收敛；当p =2时，称为平方收敛或二次收敛。显然，迭代序列的收敛阶越高，它的收敛速度就越快。311( )0kkxx 对于简单迭代格式，当线性时只能达到收敛阶。1|( ) |( )() |kkkxxx )1|( )|,|kk 1|lim|( )|0.|kkk 因为，由得(kxx其中 介于 与 之间。设)连续，则有32 在实际使用中收敛的阶有时很难直接确定，常常采用一些其它的方法来确定收敛的阶。使用Taylor展开式是一种常用的方法。如果 在根 处充分光滑(各阶导数存在)，则可对 在 处进行Tay

18、lor展开，得1(1)21()()()()()()()().()2!(1)!( )() .!kkkppkkppkxxxxxpxp ( )x( )x33(1)( )( ).( )0,p 如果()11( )()() ,!ppkkkxxxp 则( )( )0,p但是()1|( ) |.|!pkpkxxp即11()()|limlim|( ) |() |lim.!kkppkkkkppkxxpp上式说明迭代法为 p 阶收敛的。34()1()lim.!pkpkkp ( )( )xxx中的定理2迭代函数在不动点如附.2.4果近满足：( )xp(1)存在 阶导数且连续；(1)( )(2)( )( ).( )0,

19、( )0.pp 1 ()kkxxp则迭代法为 阶收敛且有补充35例例2.2.62.2.6( )0( )0ff设，证明由( )( )( )f xxxxfx建立的迭代法至少是平方收敛的。证明证明根据上述定理，只需证明( )0. 222( )( )( )( )( )1( )( )( )( )0.( )xxxf xfxf x fxxfxfxf x fxfx 因为故该迭代法至少是平方收敛的。Newton迭代法36 迭代法的加速11(),0,1,2.( ),( )( )( )(1)(2.().)kkkkxxkxxxxxxxx 简单迭代过程的收敛速度与迭代函数有关，在许多情况下 可以在此基础上构造新的迭代公

20、式，使得方程与有相同的根由新的迭代公式产生的迭代序列比原来的迭代公式产生的迭代序列收敛得快这加方法称为速技巧种37( )( )( ( )xxxx l 令新的迭代函数为1 其中是待定参数。选取使得( *)( *)( ( *) 1)0 xxx 构造加速迭代序列即()( *)1( *)1()1kkkkxxxx1()( ()1kkkkkkxxxx38 迭代法的埃特金加速法1lim( )( )| 1.kkkkxxx 如果迭代序列线性收敛于 ，则且0|211 .kkkkkxxxx当适当大时，有39221212kkkkkkx xxxxx由此解出.2121()2kkkkkkxxxxxx重新整理得21+121(

21、).2kkkkkkkxxxxxxx定义序列此迭代方法称为。可以证明：此序列比原来的序列更快地收埃特金加速敛于法。40211, kkkkkxxxcxx定迭代序列收敛于理2.2.3且如，果lim0.kkkxx则41(1). 21()()()2kkkkkkkkkkkyxzyyxxxzyx k=0，1，2，埃特金迭代格式可改写成：(2). 1()(0,1,.)kkxxk2( ( )( ).( ( )2 ( )xxxxxxx 其中迭代函数42 小结1. 2 3 4 迭代法的基本思想.迭代法收敛的条件及误差估计.迭代法的收敛速度.迭代法的加速43用迭代法解非线性方程时，如何构造迭代函数是非常重要的，那么怎

22、样构造的迭代函数才能保证迭代法收敛呢？一、Newton迭代法将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解。 基本思想基本思想非线性问题的最简单解法是线性近似！440200000( ) ()( )()()()().2f x xTaylorfxf xf xfxx- xxx!Taylor将在近似值处展开成级数展：开：；00001()0 ()()0 )( fxxxf xfxxf x =x若，则有解，取 作为的根的新的近似值，记为求；解：000( ) ()()()0 f xf xfxxx线性化取：线性部分作为的近似，有； 迭代格式迭代格式451211().()fxxxfx1()()kkkkf

23、 xxxfx上述格式称为NewtonNewton迭代格式迭代格式。这样一直下去，可以得到一列迭代序列 ，其迭代格式为：类似地，同样可以得到kx46几何意义几何意义,1()( )()() ()kkkkkkxf xyf xyf xfxxxxx过点作函数的切线，其方程为，因此，就是该切线与 轴交点的坐标。xy1x2x0 x( )yf xNewton迭代法又称为切线法切线切线 原来是以直线代替原来是以直线代替曲线的近似方法啊曲线的近似方法啊!47 局部收敛性局部收敛性( )( ).( )f xxxfxNewto迭n代函数迭代法的为x对 ( )求导,有222( ) )( ) ( )( )( )( )1,

24、( )( )fxfx f xf x fxxfxfx 222( )( )( )( )( )( )( )( )( )( )fxfxfxxf xfxf xfxfxfx482( )( )()( )0( )( )()( )( )( )0.( )( )( )0( )( )()( )0f xg x xgfxg xxg xfgf xfffff 且，此时，故所以，(1) 当 是的单根时:.Newton( )0( )0f 因而，法在根 的至少是二阶收敛的邻近；当时，所以恰为二阶收敛的。4911( )( )()()0( )()( )()( )( )( )( )()( )()( )( )0)(2)( )()( )(:

25、( )()mmmmmmf xg xxgfxm xg xxgxf xxxfxxg xxm xg xxgxxg xxfmg xxxxmgm(2)当是的，且，此时，重根时，50()lim( ),( )()()lim()( )( )()( )lim( )1lim 11.( )()( )xxxxxxxxg xxmg xxgxxg xmg xxgxm 2()0Newtonm 当时，所以法线在根性的邻近是收敛的。改进：改进：1(),()kkkkf xxxmf x则至少是二阶收敛的。511( ) 0( )0( )Newton()()( )0kkkkfff xf xxxfxf设 ，且在 邻域内具有二阶连续导数，

26、则由法产生的迭代序列局部定理2.3.1收敛到 ，且收敛阶至少为2。又当时，收敛阶恰为2。缺点：缺点：对初值要求较高，计算量较大。优点优点：收敛速度快，精度高，格式简单，应用广泛。 优点与缺点优点与缺点 52下图表明Newton法收敛性依赖于初值x0 的选取。x0 x0 x0总之，Newton法具有收敛快，稳定性好，精度高等优点，是求解非线性方程的有效方法之一。但它每次迭代均需计算函数值与导数值，故计算量较大。而且当导数值提供有困难时，Newton法无法进行。此外，由于它是局部收敛的，因而对初值要求较高，只有初值选得充分靠近根时，才能保证序列收敛。53注注1 1：使用牛顿迭代法存在从一个根跳到另

27、一个根的情况。注注2 2：如果f(x)=0没有实根，则牛顿迭代序列不收敛。54例例2.3.1 用Newton法解方程f(x)=x(x+1)2-1=0在0.4附近的根。解解 将函数f(x)求导，得到210( )(1)(31)()(1)1,()(1)(31)0.4,kkkkkkkkkfxxxf xxxxxxfxxxxNewton迭代格式为取计算结果如下k 0 1 2 3 xk 0.4 0.47013 0.46539 0.46537所以，取根为0.4654.55 全局收敛性全局收敛性( )Newtonf x如果函数在某一个含根区间满足一定的单调性和凸凹性，则得到迭代法的全局收敛性。定理定理2.3.2

28、 2( ) , f xCa b设函数且满足如下条件：0001)( ) ( )0;2)( ) , ;3)( ) , ()()0.f a f bfxa bfxa bxf xfx在上不等于零在上恒正或恒负;4)初值满足条件Newton( )0 , .kxf xa b则由迭代法产生的序列单调收敛于在区间内的唯一根保证了根的存在性保证了根的存在性 函数单调，根唯一函数单调，根唯一函数图形的凸向不变函数图形的凸向不变 , ( ) , xa bxa b保证时，56例例2.3.22Newton 9sin10 xx 用迭代求在0,1内的一个根。解解21 ( )9sin1 (1)0, ( )0 31,13f xx

29、xff由于满足，且在区间上满足条件( )18cos610( )18sin180fxxxfxx，000001 ,1()()03()0NewtonNewtonxf xfxf xx故由定理可知：当初值满足，即时，迭代法收敛。如取0.4，按迭代格式计算.57 Newton迭代法的计算步骤迭代法的计算步骤000(),().0 xf xfxk123输入精度 , ，最大迭代次数N，初值 ，计算令第一步：；()|kkfx3如果N或|，则输出算法失败标志，并终第二步：止迭代；1()()kkkkf xxxfx第计算三步：；111()|:1kkkkxxf xxkk12如果|,或|,则终止迭代，并取；否则，并转第四步

30、：第二步。58 程序框图程序框图112| ()|kkkxxf x或终止准则：终止准则：|()|kkNf x或|( )?|kkNf x或59例例2.3.3Newton0.cc 用法建立求的迭代格式,其中解解2( )( )0.f xxcf x作函数，则函数的正根即为 c21Newton()1().()22kkkkkkkkkf xxccxxxxfxxx迭代格式为0( )20( )20.xfxxfx因为当时，根据全局收敛性定理，对任何满足200()0,f xxc00 xcx即的初值，上述Newton迭代产生的迭代序列. c均收敛于60二、简化Newton法10().()kkkf xxxfx0( )(

31、).()f xxxfx0Newton().()()().kkkfxfxfxfx迭代中每次都要计算如果较繁，工作量就很大。为了避免计算导数值，可将取为某个定点处的值近似替代，如取这时迭代式变为此格式称为简化简化NewtonNewton迭代迭代。迭代函数为kxx和切线法不同，此时的迭代序列为一系列平行直线与轴的交点。 迭代格式迭代格式6100(,()xf x0 x1x)(xfy 2x 几何意义几何意义00,1()()() ()( )()kkkkkxfxyfxfxxxyfxxxfx用 过 点且的 直 线来 代 替 曲 线， 取 该 直 线 与轴 交 点斜 率 为的横 坐 标作 为的 新 的 近 似

32、值 。621().kkkf xxxc( )( ),f xxxc()kfxc进一步推广，可以把取为任意常数， 迭代函数成为此格式称为推广的简化推广的简化NewtonNewton迭代迭代。迭代格式为 进一步简化进一步简化由简单迭代的局部收敛条件|( )|1,xLx 收敛性与收敛速度收敛性与收敛速度630 x1x)(xfy 2x(NewtonNewto)nfx可 见 ， 当时 ， 推 广 的简 化法 才 是的 。 因 此 ， 在 推广 的 简 化迭 代 中 ， 常 数 c至 少 应 与 导 数同 号c与同 号 且 满 足 上 式局 部 收 敛。 若 不 然 ， 迭 代 可 能 发 散 。( )fx右

33、 图 中 c与反 号 ， 结 果 发 散( )02.fxc得64推广的简化Newton法收敛时，因为1| | ()( )| |( )|,kkkxxx ( )cf若，有1|( )|( )|10.|kkfc 所以，推广的简化Newton法只有线性收敛速度。( )Newtoncf虽然如此，只有 选得好，比如很接近，收敛也是相当快的。它的计算却比法简单得多。kx其中位于与之间；65三、下山Newton迭代1(),()kkkkkf xxxfx在Newton迭代法中，若函数较复杂，初值的选取较困难时，为防止迭代发散，可改用如下的迭代式，以扩大初值的选取范围：01kk其中称为。通过适当选取下山下山因子因子，

34、使得1|()|()|kkf xf x成立，|()|kf x要求的即值单调下降。上述迭代方法称为下山下山NewtonNewton法法。66211111,.2 2,|() |() |1kkkkxf xf xxk下山因子的确定一般。即由迭代得到计算值后，取不同的 值试算，例如，直到成立，则计算值即采用试算法取为第步的迭代值。12111,.,Newton222kxk再 取用 求 得 的与 下 山迭代 仿 照 前 面 的 过 程 计 算 第步 的 迭 代 值 。*012kkxx如 果 计 算 过 程 中 碰 到 一 个 迭 代 值取 不 到 满 足要 求 的值 ， 则 称 “” (一 般 给 出 下 山

35、因 子 的 下 界=)， 需 要 另 取 初 始 值， 仿 照上 述 过下 山 失 败程 重 算 。112| ()|kkkf xxx或终止准则：终止准则：67例例2.3.52.3.53Newton 03xx用下山迭代法求的根。解解323120( )( )13Newton3.1Pkkkkkkxf xxfxxxxxxxx由于，下山迭代格式为取 初值=-0.99，计算结果见（曾金平）书37表2.3.2.NewtonNewtonNewton下山法当1时，只有线性收敛速度，但对初值的选取却放得很宽。某一个初值对迭代不收敛，对下山法却可能收敛得很好。68四、弦割法 迭代格式迭代格式Newton()kfx用

36、上式替代迭代格式中的，化简得111()().()()kkkkkkkf xxxxxf xf x11()()(),kkkkkf xf xfxxxNewton( )( )( ).f xfxfx由于迭代法带有的导数，使用起来不方便。为了不求导数，可用导数的近似式替代由上式定义的迭代算法称为弦割法弦割法，也称为割线法割线法。为什么称为弦割法？是从它的几何意义而言。1,( )0kkxxf x其中是的两个近似根，69 几何意义几何意义1kxx就是割线由此与轴交可以看出，点的坐标11()()()().kkkkkkf xf xyf xxxxx111,( )0(,(),(,()( )kkkkkkxxf xxf xxf xyf x设是的两个近似根，过两点作函数的割线，其方程为11()().()()kkkkkkf xxxxxf xf x0y 令，可得切线切线 割线割线 1kxkx1kx( )y f x还是以直线代替还是以直线代替曲线的近似方法啊曲线的近似方法啊!70 收敛性与收敛速度收敛性与收敛速度111(