计算方法课件2

1、第第2 2章章 非线性方程求根非线性方程求根二、二、 非线性方程求解的迭代法非线性方程求解的迭代法1. 1. 迭代法的基本思想迭代法的基本思想2. 2. 简单迭代法及收敛性简单迭代法及收敛性一、一、 二分法二分法3. 3. 迭代过程的加速方法迭代过程的加速方法4. 4. 牛顿迭代法牛顿迭代法5. 5. 割弦法割弦法将一半径为将一半径为 r ，密度为，密度为 1 的球体的球体浸入水中，求球体没入水中的深度浸入水中，求球体没入水中的深度 d.球体排出水的质量为球体排出水的质量为.3)3(d)(2022drdxrxrd 球体本身的质量为球体本身的质量为.343 r则则.3)3(3423drdr 即即

2、. 043)(323 rrdddf现代科学技术或工程技术领域的许多实际问题，常常可以归结为求解函数方程：( )0f x ，: fRR其中函数一般是非线性的.如果函数 能写成如下形式如果有使得( )0f，则称 为方程( )0,1,gm且有( )0f x 的根， 或称 为函数 的零点。( )f x( )0 xmf则称 为的 重根，mf或函数的 重零点。f( )()( )mf xxg x如：如：1110( ).0, 1.nnnnf xa xaxa xan ( )sin0.xf xex 当当 f ( x ) 为代数方程时，理论上已经证明，大于五为代数方程时，理论上已经证明，大于五次的多项式一般没有代数

3、解法。次的多项式一般没有代数解法。 当当f ( x )为超越方程时，一般不能用代数方法求其根。为超越方程时，一般不能用代数方法求其根。 所以，所以，超越方程超越方程( (含有指数和对数等含有指数和对数等) )代数方程（多项式）代数方程（多项式）求方程的数值解问题大致分成三步：求方程的数值解问题大致分成三步：第二步：根的隔离第二步：根的隔离确定根所在的区间，使方程在这个小区间内仅有一个根，确定根所在的区间，使方程在这个小区间内仅有一个根，该区间该区间叫叫隔根区间。隔根区间。第三步：根的精确化第三步：根的精确化已知根的一个近似值后，已知根的一个近似值后，用某种方法对其进行加工，使之用某种方法对其进

4、行加工，使之满足给定的精度要求。满足给定的精度要求。第一步：根的存在性第一步：根的存在性方程是否有根？如果有，有几个根？方程是否有根？如果有，有几个根？求隔根区间的一般方法求隔根区间的一般方法理论依据： ( ) , ( )( )0( )0 , f xa bf af bf xa b设在上连续，且，则 在内至少有一个实根 ； ( ) , ( )0 , f xa bf xa b若在内严格单调，则 在内只有一个根。二分法是方程求根最常用而且也是最保险的方二分法是方程求根最常用而且也是最保险的方法之一。法之一。算法的基本思想：算法的基本思想：将区间对分，保留有根的区间，舍去无根的区间。将区间对分，保留有

5、根的区间，舍去无根的区间。如此往复，以逐步逼近方程的根。如此往复，以逐步逼近方程的根。 ( ) , ( ) ( )0.f xa bf a f b 假设在上连续且基本条件：基本条件：一、二分法一、二分法 基本思想基本思想00000000(1)., , ().2 ()0( ) , ()0ababa bxf xf xf xa bf x令，取中点，求若，则得到在上的一个零点；若，则作下一步。01100101()()0()()0.fxfaaabxfxfbaxbb(2).若， 则 令，；若， 则 令，1100 ( )0,f xa bab这样，我们得到 的一个新的含根区间，其长度是原区间长度的一半。一、二分

6、法一、二分法 算法的步骤算法的步骤,( )kkabfx(3).对新的含根区间重复上述步骤，我们可以得到一个区间序列，序列中的每一个区间都是函数的含根区间且区间的程度依次减半。a x0 b( )f x a1 b111 , ,.,.kka ba ba b二分法产生一个含根区间序列：11,11 ().().22kkkkkkka bbababa其中区间的长度为： k (2)kkkf xabx因此，当足够大时，我们可以用作为函数的一个根 的近似值。1.22kkkkbabax此时有误差估计误差估计：常用来估计k的值一、二分法一、二分法 算法的收敛性算法的收敛性1.22kkkkbabax,21abk.2ln

7、2ln)ln(abk程序程序2.1.1用二分法求函数用二分法求函数f(x)在区间在区间 a,b 上的一个实根上的一个实根一、二分法一、二分法 算法的程序算法的程序%Input a,b: 区间两端点区间两端点%Input Tol: 计算精度计算精度%Input N0: 最大迭代次数最大迭代次数%Output x: 根根i=0;fa=f(a);while i=N0 x=a+(b-a)/2; fx=f(x); if fx = = 0|(b-a)/20 a=x; fa=fx; else b=x; endend用二分法求方程用二分法求方程 3( )1 0f xxx 在在1,1.5内的实根内的实根， 要求

8、要求 0.005.解解111.5 1|0.00522kkkb ax 6.k 即可推出所需的迭代次数满足即可推出所需的迭代次数满足 在区间在区间1,1.51,1.5上至少存在一个根。上至少存在一个根。 ( )(1)1 0,( )(1.5) 0.875 0,f aff bf 其具体过程如下：其具体过程如下： 例例2.1由于由于因而因而( )0f x 由误差估计式由误差估计式( )kf x 的符号0 01.00001.00001.50001.50001.25001.2500- -1 11.25001.25001.50001.50001.3751.375+ +2 21.25001.25001.3751

9、.3751.31251.3125- -3 31.31251.31251.3751.3751.34381.3438+ +4 41.31251.31251.34381.34381.32811.3281+ +5 51.31251.31251.32811.32811.32031.3203- -6 61.32031.32031.32811.32811.32421.3242- -kakbkxk61.5 11.32420.0039. 0.00572x缺点：缺点：不能求偶数重根及复根；收敛速度非常不能求偶数重根及复根；收敛速度非常缓慢，与以缓慢，与以1/21/2为公比的等比级数相同；没有充为公比的等比级数相同

10、；没有充分利用函数值。因此一般不单独使用，往往为分利用函数值。因此一般不单独使用，往往为其它快速方法提供初值。其它快速方法提供初值。优点优点：计算简单且必收敛，是一种可靠的算法；：计算简单且必收敛，是一种可靠的算法；对函数性质要求低，只要求函数对函数性质要求低，只要求函数 f ( x ) 连续就连续就可以了。可以了。一、二分法一、二分法 算法的优缺点算法的优缺点等价变换等价变换( )xx( )0f x ( ) 0f x 的根( ) x的不动点迭代法是迭代法是一种逐步逼近的方法，首先给出一个一种逐步逼近的方法，首先给出一个粗糙的初值，利用同一个迭代公式，反复计算。粗糙的初值，利用同一个迭代公式，

11、反复计算。 用简单迭代法求方程根的基本步骤如下：用简单迭代法求方程根的基本步骤如下：第一步：化为同解方程第一步：化为同解方程 且连续二、迭代法二、迭代法 简单迭代简单迭代第二步：产生迭代序列第二步：产生迭代序列先建立适当的迭代格式：迭代格式：0 , .xa b再取适当的初值1()kkxx，012,.,.kxx xx利用上述格式可产生一列数：1()( )( )( )m 0likkkkkxxxxf xx若迭代序列收敛，则由可得，因而是的不动点，也即若就是，的根。第三步：取极限第三步：取极限limkkx 一定收敛吗？Function x_star, k=iterate1(fun,x0,ep,Nmax

12、)%一般迭代法解非线性方程，f(x)=0%fun为迭代函数,x为初始值,ep为精度(默认1e-5)%当|x(k)-x(k-1)|ep时终止计算%Nmax为最大迭代次数(默认500)%当迭代成功时x_star为方程的根，当迭代失败时%输出最后的迭代值%k为迭代次数if nargin4 Nmax=500; endif narginep&k fun=inline(x+1)(1/3);x_star,k=iterate1(fun,1.5)得到表得到表2.2；（1）kxkkxk01231.50001.35721.33091.325945671.32491.32481.32471.3247在在Mat

13、lab命令窗口执行命令窗口执行 fun=inline(x3-1);x_star,k=iterate1(fun,1.5)得到得到（2） ,3976.12,375. 221xx练习：练习：32( )4100 .f xxx求 在区间1,2上的根解解可构造下列等价方程：321(1)( )( )410;xxxf xxxx1/2210(2)( )4;xxxx3 1/231(3)( )(10);2xxx1/2410(4)( );4xxx3252( )410(5)( ).( )38f xxxxxxxfxxx01 .5x 取初值请同学们自己写出请同学们自己写出Matlab程序及计算结果。程序及计算结果。迭代序列

14、是否收敛或者收敛于哪一个根，不仅与迭代格式的构造有关，而且与初值的选取有关。一般来说，对于方程 可以写成多种等价形式( ),xx关键是构造的迭代格式1()kkxxk当时，( )0,f x 迭代格式的构造形式不仅影响迭代序列的收敛性，迭代格式的构造形式不仅影响迭代序列的收敛性，也影响迭代序列的适定性与收敛速度。也影响迭代序列的适定性与收敛速度。kx 是否收敛于精确解？xy0 x1x2xyx( )yx在直角坐标系中同时作 和 两条曲线，如图所示，则这两条曲线的交点的横坐标就是方程 的根 ，也就是 的根。迭代格式 由 求 ，相当于过曲线上 作水平线与直线 相交，过交点作x轴的垂线，此时垂足至原点距离

15、等于 ，故垂足横坐标为 。yx( )yx( )xx( ) 0f x 1()kkxxkx1kx(, ()kkxxyx1kx()kx 迭代法的几何解释：由上图可见，曲线斜率 时迭代序列收敛，且 越小收敛越快；反之，若 ，则迭代序列发散。|( )| 1x|( )|x|( )| 1xxyy = xxyy = xx0p0 x1p1 x0p0 x1p1( )xx( )xx在根附近，曲线的切线不说明能太陡！下面给出迭代法的一个收敛性定理。下面给出迭代法的一个收敛性定理。满满足足如如下下条条件件：设设迭迭代代函函数数,)(baCx ;,)(,)1(baxbax 时时当当.| )()(|, 1)2(成成立立都都

16、有有使使对对任任意意存存在在正正数数yxLyxbayxL 有有误误差差估估计计式式，并并收收敛敛于于产产生生的的迭迭代代序序列列迭迭代代格格式式且且对对任任意意上上有有唯唯一一解解在在则则方方程程 )(,)(10kkkxxxbaxbaxx .101xxLLxkk 二、迭代法二、迭代法 简单迭代的收敛性简单迭代的收敛性压缩映像保证迭代不中断Lipschitz条件 存在唯一性证明证明做辅助函数( )( )xxx，则有( )0,( )0,ab所以，存在点( )0( ). ，使，即若又有*( *) ，则有*( )( *)*.L 所以*. 收敛性任取初值0 , ,xa b则110| ()( )|.,kk

17、kkxxL xLx 所以，任意的初值都收敛。 误差估计11110()().,kkkkkkkxxxxL xxL xx11.kpkkpkpkkxxxxxx 110.kpkLLxx 10101.11kpkLLLxxxxLL10.1kkLxxxLpp 由 的任意性，令，可得证毕定理定理2.2.1的条件的条件(2)不容易得到不容易得到,由微分中值定由微分中值定理：理：满满足足条条件件：设设,)(1baCx ;)(,)1(bxabax 时时当当.1| )(|, 1)2(成成立立都都有有使使存存在在正正数数 LxbaxL 迭迭代代过过程程近近似似值值且且对对任任意意初初始始上上有有唯唯一一解解在在则则方方程

18、程,)(0baxbaxx , 2 , 1 , 0),(1 kxxkk 且且收敛收敛,)()()(,)(1yxyxbaCx则则若若不难得到如下推论。不难得到如下推论。.101xxLLxkk |)(|1kkkkxxxx|)()()(|kkxx |1 kkxx |kkxLx | )1(kxL 从而，有如下误差估计：从而，有如下误差估计：在推论的条件下，有误差估计式在推论的条件下，有误差估计式, 2 , 1 , 0|,|11|1 kxxLxkkk ., 2 , 1 , 0|,|1|01 kxxLLxkk 10 1( )( ) , 1.kkLxxxLxxaLb注常数 越小，简单迭代法收敛越快。误差估计式

19、表明:因而构造迭代函数的原则是使在有根区间上有尽可能小的上界。给出了精度要求，可用上述误差估计式来确定所需的注2.迭代次数。10(1)ln/ ln.|LkLxx101kkxLkxxL设所要求的精度为 ，即要求 ，只需迭代次数 满足1时，称为超线性收敛；时，称为超线性收敛；当当p=2时，称为平方收敛或二次收敛。时，称为平方收敛或二次收敛。显然，显然，迭代序列的收敛阶越高，它的收敛速度就越快迭代序列的收敛阶越高，它的收敛速度就越快。二、迭代法二、迭代法 迭代过程的加速方法迭代过程的加速方法1( )0kkxx 对于简单迭代格式，当线性时只能达到收敛阶。1|( ) |( )() |kkkxxx )1|

20、( )|,|kk 1|lim|( )|0.|kkk 因为，由得(kxx其中 介于 与 之间。设)连续，则有 在实际使用中收敛的阶很难直接确定，常常采用一在实际使用中收敛的阶很难直接确定，常常采用一些其它的方法来确定收敛的阶。使用些其它的方法来确定收敛的阶。使用TaylorTaylor展开式是展开式是一种常用的方法。一种常用的方法。如果如果 在根在根 处充分光滑处充分光滑( (各阶导数存在各阶导数存在) )，则可对，则可对 在在 处进行处进行TaylorTaylor展开，得展开，得1(1)21()()()()()()()().()2!(1)!( )() .!kkkppkkppkxxxxxpxp

21、( )x( )x(1)( )( ).( )0,p 如果()11( )()() ,!ppkkkxxxp 则( )( )0,p但是()1|( ) |.|!pkpkxxp即11()()|limlim|( ) |() |lim.!kkppkkkkppkxxpp上式说明迭代法为 p 阶收敛的。()1()lim.!pkpkkp ( )( )xxx中的定理2迭代函数在不动点如附.2.4果近满足：( )xp(1)存在 阶导数且连续；(1)( )(2)( )( ).( )0,( )0.pp 1 ()kkxxp则迭代法为 阶收敛且有补充例例 用两种收敛的迭代法求方程用两种收敛的迭代法求方程032x的根的根 。解：

22、解：原方程等价于原方程等价于),3(21)( ),3(41)(221xxxxxxxx容易验证，容易验证，, 1134. 0231)( ,21)(*11xxx3*x. 0)( ),31 (21)(*222xxx由定理知，相应的两个迭代公式均局部收敛由定理知，相应的两个迭代公式均局部收敛., 20 x取初值取初值在在Matlab窗口执行命令：窗口执行命令：fun=inline(x-(x2-3)*(1/4); x_star,k=iterate1(fun,2)fun=inline(x+3/x)*(1/2); x_star,k=iterate1(fun,2)计算结果如下表，计算结果如下表，k01232.

23、0000001.7500001.7343751.7323612.0000001.7500001.7321431.732051)(11kkxx)(21kkxx从计算结果上看，第二种迭代方法比第一种从计算结果上看，第二种迭代方法比第一种迭代方法收敛得快，这是因为迭代方法收敛得快，这是因为. 0)(, 0)( . 0)(*2*2*1 xxx由定理由定理2.5知，第一种迭代方法线性收敛，知，第一种迭代方法线性收敛，而第二种迭代方法为而第二种迭代方法为2阶收敛。阶收敛。二、迭代法二、迭代法 迭代过程的加速方法迭代过程的加速方法 AitkenAitken加速方法加速方法1lim( )( )| 1.kkkk

24、xxx 如果迭代序列线性收敛于 ，则且0|211.kkkkkxxxx但 适当大时，有221212kkkkkkx xxxxx由此解出.2)(122122kkkkkkxxxxxx定义序列定义序列.2)(1221221kkkkkkkxxxxxxx得到得到Aitken迭代加速算法：迭代加速算法：., 2 , 1,2)( ),( ),(1121111111kxxxxxxxxxxxkkkkkkkkkkk可以证明该序列比原来的序列更快地收敛。可以证明该序列比原来的序列更快地收敛。211, kkkkkxxxcxx定迭代序列收敛于理2.2.3且如，果lim0.kkkxx则例例2.2.52.2.5见书P30例2.

25、2.3及P31表2.2.3用迭代法解非线性方程时，如何构造迭代函数是非常用迭代法解非线性方程时，如何构造迭代函数是非常重要的，那么怎样构造的迭代函数才能保证迭代法收重要的，那么怎样构造的迭代函数才能保证迭代法收敛呢？敛呢？Newton(Newton(切线切线) )法法将将非线性方程线性化非线性方程线性化，以线性方程的解逐步逼近非线，以线性方程的解逐步逼近非线性方程的解。性方程的解。 基本思想基本思想非线性问题的最简单解法是线性近似！非线性问题的最简单解法是线性近似！二、迭代法二、迭代法 Newton迭代方法迭代方法0200000( ) ()( )()()()().2f x xTaylorfxf

26、 xf xf xx-xxx!Taylor将在近似值处展开成级数展：开：；00001()0 ()()0 )( fxxxf xfxxf x =x若，则有解，取 作为的根的新的近似值，记为求；解：000( ) ()()()0 f xf xfxxx线性化取：线性部分作为的近似，有； 迭代格式迭代格式1211().()fxxxfx1()()kkkkf xxxfx上述格式称为NewtonNewton迭代格式迭代格式。这样一直下去，我们可以得到一列迭代序列 ，其迭代格式为：类似，我们可以得到kx几何意义几何意义,1()( )()() ()kkkkkkxf xyf xyf xfxxxxx过点作函数的切线，其方

27、程为，因此，就是该切线与 轴交点的坐标。xy1x2x0 x( )yf xNewton迭代法又称为切线法切线切线 原来是以直线代替原来是以直线代替曲线的近似方法啊曲线的近似方法啊! Newton迭代法的计算步骤迭代法的计算步骤000(),().0 xf xfxk123输入精度 , ，最大迭代次数N，初值 ，计算令第一步：；()|kkfx3如果N或|，则输出算法失败标志，并终第二步：止迭代；1()()kkkkf xxxfx第计算三步：；111()|:1kkkkxxf xxkk12如果|,或|,则终止迭代，并取；否则，并转第四步：第二步。 程序框图程序框图112| ()|kkkxxf x或终止准则：

28、终止准则：|()|kkNf x或|( )?|kkNf x或 Newton法的法的Matlab程序程序function x_star,k=Newton1(fname,dfname,x0,ep,Nmax)if nargin4 Nmax=500; endif narginep&kfname=inline(x*exp(x)-1);dfname=inline(x+1)*exp(x);x_star,k=Newton1(fname,dfname,0.5)迭代迭代4次后得计算结果次后得计算结果k0 1 2 3 4 xk0.5 0.57102044 0.56715557 0.56714329 0.567

29、14329.56714. 03x说明：在说明：在Newton法中初始值的选取较困难：法中初始值的选取较困难：|;|1011xxx 满足满足出的出的）要保证按迭代格式算）要保证按迭代格式算（不能很小。不能很小。且且）要保证）要保证（)(, 0)(200 xfxf)()(0001xfxfxx)()()(0001xfxfxx)()()()()(10000000001xxfxxfxfxxfxfxx要保证要保证(1)成立，由一阶成立，由一阶Taylor展开式，可以得出展开式，可以得出. | )(|2)(| )(|0020 xfxfxf 定理定理 2.7 内有一阶导数和内有一阶导数和在区间在区间设函数设函

30、数,)(baxf满足满足二阶导数，如果二阶导数，如果,0bax ; 0)(, 0)() 1 (00 xfxf|;)(|2)(| )(| )2(0020 xfxfxf 的根。的根。收敛于收敛于所确定的序列所确定的序列迭代格式迭代格式作为初始近似值的作为初始近似值的则则0)()()( 10 xfxxfxfxxNewtonxkkkkk补充例例2.3.3Newton0.cc 用法建立求的迭代格式,其中解解2( )( )0.f xxcf x作函数，则函数的正根即为 c21Newton()1().()22kkkkkkkkkxcf xcxxxxfxxx迭代格式为0( )20( )20.xfxxfx因为当时，

31、根据全局收敛性定理，对任何满足200()0,f xxc00 xcx即的初值，上述Newton迭代产生的迭代序列. c均收敛于练习练习解解.101155，精精度度要要求求为为求求. 0115)(2 xxf内。内。区间区间所以根在所以根在确定根的范围。确定根的范围。11,10, 0)11(, 0)10() 1 (ff因为因为取取,10)2(0 x, 2)10(,20)10(,15)10(, 2)(,2)( fffxfxxf,15| )(|2)(400| )(|0020 xfxfxf迭代格式为迭代格式为作为初始值可行，作为初始值可行，所以取所以取Newtonx100).115(21211521kkk

32、kkkxxxxxx在在Matlab窗口执行窗口执行fname=inline(x*x-115);dfname=inline(2*x);x_star,k=Newton1(fname,dfname,10)迭代迭代4次后得到计算结果次后得到计算结果k0 1 2 3 4 xk10 10.75000000 10.72383721 10.72380529 10.72380529简化简化NewtonNewton法法10().()kkkf xxxfx0( )( ).()f xxxfx0Newton().()()().kkkfxfxfxfx迭代中每次都要计算如果较繁，工作量就很大。为了避免计算导数值，可将取为某个

33、定点处的值近似替代，如取这时迭代式变为此格式称为简化简化NewtonNewton迭代迭代。迭代函数为kxx和切线法不同，此时的迭代序列为一系列平行直线与轴的交点。 迭代格式迭代格式00(,()xf x0 x1x)(xfy 2x 几何意义几何意义00,1()()() ()( )()kkkkkxfxyfxfxxxyfxxxfx用 过 点且的 直 线来 代 替 曲 线， 取 该 直 线 与轴 交 点斜 率 为的横 坐 标作 为的 新 的 近 似 值 。1().kkkf xxxc( )( ),f xxxc()kfxc进一步推广，可以把取为任意常数， 迭代函数成为此格式称为推广的简化推广的简化Newto

34、nNewton迭代迭代。迭代格式为 进一步简化进一步简化由简单迭代的局部收敛条件|( )|1,xLx 收敛性与收敛速度收敛性与收敛速度0 x1x)(xfy 2x(NewtonNewto)nfx可 见 ， 当时 ， 推 广 的简 化法 才 是的 。 因 此 ， 在 推广 的 简 化迭 代 中 ， 常 数 c至 少 应 与 导 数同 号c与同 号 且 满 足 上 式局 部 收 敛。 若 不 然 ， 迭 代 可 能 发 散 。( )fx右 图 中 c与反 号 ， 结 果 发 散( )02.fxc得推广的简化Newton法收敛时，因为1| | ()( )| |( )|,kkkxxx ( )cf若，有1

35、|( )|( )|10.|kkfc 所以，推广的简化Newton法只有线性收敛速度。( )Newtoncf虽然如此，只有 选得好，比如很接近，收敛也是相当快的。它的计算却比法简单得多。kx其中位于与之间；NewtonNewton下山法下山法1(),()kkkkkf xxxfx在Newton迭代法中，若函数较复杂，初值的选取较困难时，为防止迭代发散，可改用如下的迭代式，以扩大初值的选取范围：01kk其中称为。通过适当选取下山下山因子因子，使得1|()|()|kkf xf x成立，|()|kf x要求的即值单调下降。上述迭代方法称为NewtonNewton下山法下山法。211111,.2 2,|(

36、) |() |1kkkkxf xf xxk下山因子的确定一般。即由迭代得到计算值后，取不同的 值试算，例如，直到成立，则计算值即采用试算法取为第步的迭代值。12111,.,Newton222kxk再 取用 求 得 的与 下 山迭代 仿 照 前 面 的 过 程 计 算 第步 的 迭 代 值 。*012kkxx如 果 计 算 过 程 中 碰 到 一 个 迭 代 值取 不 到 满 足要 求 的值 ， 则 称 “” (一 般 给 出 下 山因 子 的 下 界=)， 需 要 另 取 初 始 值， 仿 照上 述 过下 山 失 败程 重 算 。112| ()|kkkf xxx或终止准则：终止准则： Newt

37、on下山下山法的计算步骤法的计算步骤000(),().0 xfxfxk*12输入精度,下山因子的下界，正数，初值， 第一步 计算令：；1取下山第因子二步：；1() |() |kkfxfx第比较四|与|步：11()()()kkkkkf xxxf xfx计算及第三步：；1111() |() |:1()kkkkkkkkfxfxxxxxxkkfx11若|，则当|时,取，终止迭代； 当|时,，计算，(1)转第二步。1*1*11*1()|()|()|()|()()|/2kkkkkkkkkf xf xf xxf xxxfxf x222若|，则当，而|时,取，终止迭代；当，而|时,取 :=+ ，计算，转第二步

38、; 当，而|时,取 :=，(2)转第三步。要控制迭代次数？例例2.132.133Newton 03xx用下山迭代法求的根。解解NewtonNewtonNewton下山法当1时，只有线性收敛速度，但对初值的选取却放得很宽。某一个初值对迭代不收敛，对下山法却可能收敛得很好。323120( )( )13Newton3.1Pkkkkkkxf xxfxxxxxxxx由于，下山迭代格式为取 初值=-0.99，计算结果见书 37表2.3.2.弦割法弦割法 迭代格式迭代格式Newton()kfx用上式替代迭代格式中的，化简得111()().()()kkkkkkkf xxxxxf xf x11()()(),kk

39、kkkf xf xfxxxNewton( )( )( ).f xfxfx由于迭代法带有的导数，使用起来不方便。为了不求导数，可用导数的近似式替代由上式定义的迭代算法称为弦割法弦割法，也称为割线法割线法。为什么称为弦割法？是从它的几何意义而言。1,( )0kkxxf x其中是的两个近似根， 几何意义几何意义1kxx就是割线由此与轴交可以看出，点的坐标11()()()().kkkkkkf xf xyf xxxxx111,( )0(,(),(,()( )kkkkkkxxf xxf xxf xyf x设是的两个近似根，过两点作函数的割线，其方程为11()().()()kkkkkkf xxxxxf xf x0y 令，可得切线切线 割线割线 1kxkx1kx( )y f x还是以直线代替还是以直线代替曲线的近似方法啊曲线的近似方法啊! 收敛性与收敛速度收敛性与收敛速度111()kkkkkxxxxx因为在计算时，须事先知道和两点处的值，所以不能用简单迭代格式描述其迭代过程。但仍可证明如下定理：2( )( )0( )0.f xCf xf 设函数 - , + ， 其中 为的根， 为某正数。