计算方法第七章print

1、第七章第七章 非线性方程求根非线性方程求根7.1 方程求根与二分法7.2 迭代法及其收敛性7.3 迭代法收敛的加速方法7.4 牛顿法7.5 弦截法与抛物线法7.6 解非线性方程组的牛顿迭代法 本章讨论非线性方程 的求根问题，其中一类特殊的问题就是多项式方程的求根。 方程 的根 又称为 的零点，它使若 可表示为 ，其中 为正整数，且 。当 时，称 为单根，若 称 为 重根，或 的 重零点。若 是 的 重零点，且 充分光滑，则7.1 方程求根与二分法方程求根与二分法( )0f x 10110( )(0)nnnnf xa xa xaxaa( )0f x *x( )f x*()0f x( )f x*(

2、 )()( )mf xxxg xm*()0g x1m *x1m *xmm( )f x*x( )f xm( )g x*(1)*()*()()()0,()0mmf xfxfxfx7.1 方程求根与二分法方程求根与二分法 当 为代数多项式时，根据代数基本定理可知， 次方程在复数域有且只有 个根，因此可利用迭代法求代数方程的根。 n二分法 若 ，且 ，根据连续函数性质可知 在 内至少有一个实根，此时称 为方程的有根区间。例：求方程 的有根区间。解：通过计算部分点的函数值，得到如下结果：由此得到方程的有根区间为： 。( )f xnn( ) , f xc a b( ) ( )0f a f b ( )f x

3、 , a b , a b32( )11.138.841.770f xxxx0123456 的符号x( )f x1,2,3,4,5,67.1 方程求根与二分法方程求根与二分法n二分算法 设已找到有根区间 ，满足 ，且在 上只有一个零点，步骤如下： (1) 先设 对于一般的区间 ，设其中点为： (2) 检验 的符号，若与 同号，就取 ， 否则取 这样必有所以 就是新的有根区间，继续此过程，即可得到结果。算法：(1)令(2) 若 或 ，则输出 ，结束(3) 若 ，则令 ，否则令(4) 转向1) , a b( ) ( )0f a f b ( )f x , a b11,aa bb,nna b()/2nn

4、nxab()nf x()nf a1nnax1,nnbb1,nnaa1,nnbx11() ()0nnf af b11,nnab()/2xab( )f xbxx( ) ( )0f a f x axbx7.1 方程求根与二分法方程求根与二分法 这样，我们得到了一个序列 ，为确定 的收敛性我们有如下的定理： 定理：设 则二分算法产生的序列 满足 其中 为方程的根。 证明：因为 由 对分得到，所以对区间长度而 ，且 ，所以故当 时， ，且有误差估计式nxnx( ) , ,( ) ( )0,f xc a bf a f bnx*()/2 ,nnxxba* , xa b11,nnab,nna b1n 111(

5、)/2()/2nnnnnbababa*,nnxa b()/2nnnxab*()/2()/2 ,nnnnxxbaban *nxx*()/2nnxxba7.1 方程求根与二分法方程求根与二分法例：已知 在 有一个零点， ， ，用二分法计算的结果如下：32( )410f xxx1,2(1)5f (2)14fn有根区间11.0,2.01.52.37521.0,1.51.25-1.7968731.25,1.51.3750.1621141.25,1.3751.3125-0.8483951.3125,1.3751.34375-0.3509861.34375,1.3751.359375-0.0964171.3

6、59375,1.3751.36718750.0323681.359375,1.3671875 1.36328125-0.03215nx()nf x7.1 方程求根与二分法方程求根与二分法 ， ，另外，如果要求 ，可以从令 ，可得 ，即计算17次即可。81.36328125x *83823.9 10 xx*1.36523001x *381.95 10 xx510*()/22nnnxxba5210n105/log 216.6n 7.2 迭代法及其收敛性迭代法及其收敛性n不动点迭代法 将方程 改写成等价的形式 ，则的根 也满足方程 ，反之亦然。称 为 的不动点。而求 的根的问题就成为求 的不动点问题

7、。 选取初值 ，以公式 进行迭代， 称为迭代函数，若 收敛到 ，则 就是 的不动点，这种方法就称为不动点迭代法。 将 转化为 的方法可以是多种多样的，例： 在 上可有以下方法：(1) (2)(3) (4)取 ，有的收敛，有的发散，有的快，有的慢。( )0f x ( )xx( )0f x *x( )xx*x( ) x( )0f x ( ) x0 x1()nnxx( ) x nx*x*x( ) x( )0f x ( )xx32( )4100f xxx1,232410 xxxx3 1/2(1/2)(10)xx1/2(10/4 )xxx1/210/(4)xx01.5x 7.2 迭代法及其收敛性迭代法及

8、其收敛性n迭代过程的几何表示 方程 的求根问题在 平面上就是要确定曲线 与直线 的交点 ，对于 的某个近似值 ，在曲线 上可确定一点 ，它的横坐标为而纵坐标为 ，过 引 轴的平行线，交 于 ，然后过 再作 轴的平行线，它与 的交点记作 ，则 的横坐标为 ，而纵坐标为 ，按图中箭头所示路经继续做下去，在曲线上得到点列 其横坐标分别为按公式 求得的迭代值 如果点列 趋向于点 ，则相应的迭代值 收敛到所求的根 。 ( )xxxy( )yxyx*p*x0 x( )yx0p0 x01()xx0pxyx1q1qy( )yx kp1p1x12( )xx1p23,p p 1()kkxx123,x x x 1p

9、*pkx*x7.2 迭代法及其收敛性迭代法及其收敛性0 x1x2x3x*x0p1p2p3p1q2q3q*p7.2 迭代法及其收敛性迭代法及其收敛性 例3：求方程 在 附近的根 。解：将方程改写为 ，由此建立迭代公式：计算结果如下表：这是一个收敛的例子，也有不收敛的迭代公式，如我们对于同样的问题，如果将方程改写为令一种迭代公式 ，仍取初值 ，则迭代发散。 为此，我们要研究 存在性及迭代法的收敛性。3( )10f xxx 01.5x *x31xx311(0,1,2,)kkxxk0123456781.5 1.35721 1.33086 1.32588 1.32494 1.32476 1.32473

10、1.32472 1.32472kxk311kkxx01.5x ( ) x7.2 迭代法及其收敛性迭代法及其收敛性 定理1：(存在性)设 满足以下两个条件：(1) 对任意的 ，有 (2) 存在 ，使对任意 都有则 在 上存在唯一的不动点 。证明：先证不动点的存在性。若 或 ，则 或 就是不动点。因此由 可设 及 ，定义函数 ，显然 且满足 由函数的连续性可知存在 使 ，即 ， 即为 的不动点。 , xa b( )axb01l, , x yc a b( )( )xyl xy( ) x*x , a b( )aa( )bbab( )axb( )aa( )bb( )( )f xxx( )( )0,( )

11、( )0f aaaf bbb( ) , xc a b( ) , f xc a b*( , )xa b*()0f x*()xx*x( ) x7.2 迭代法及其收敛性迭代法及其收敛性再证唯一性。设 及 都是 的不动点，则由定理的条件(2)，得到矛盾，故 的不动点是唯一的。 证毕。 定理2：(收敛的充分条件) 设 满足定理1的两个条件，则对任意 ，由 得到的迭代序列 收敛到 的不动点 ，并有误差估计证明：设 是 在 上的唯一不动点，由条件1可知 ，再由条件2得因 ，故当 时，序列 收敛到 。*1x*2 , xa b( ) x*12121212()()xxxxl xxxx( ) x( ) , xc a

12、 b0 , xa b1()kkxx kx*x( ) x*101kklxxxxl* , xa b( ) x , a b , kxa b*110()()kkkkxxxxl xxl xx01lk kx*x7.2 迭代法及其收敛性迭代法及其收敛性由迭代公式可得据此反复递推，得到于是对任意正整数 ，有在上式令 ，注意到 即得到结果。证毕。111()()kkkkkkxxxxl xx110kkkxxl xx1121121010()1kpkkpkpkpkpkkkpkpkkxxxxxxxxlllxxlxxl p *limkppxx7.2 迭代法及其收敛性迭代法及其收敛性 根据定理2的结论，对于给定的计算精度，迭

13、代次数是可以预先确定的，但由于公式中含有常数 ，使得计算迭代次数较为复杂，根据估计式我们得到：令 ，得到由此可知，只要相邻两次计算结果的偏差 足够小即可保证近似值 有足够的精度。111()()kkkkkkxxxxl xxl112112111(1)1kpkkpkpkpkpkkppkkkkxxxxxxxxllxxxxl p *111kkkxxxxl1kkxxkx7.2 迭代法及其收敛性迭代法及其收敛性 对于定理中的条件2，在实际使用时，如果 且对任意的 有则由中值定理可知 有它表明定理中条件2可由 替代。1( ) , xc a b , xa b( )1xl, , x ya b( )( )( )()

14、,( , )xyxyl xya b ( )1xl7.2 迭代法及其收敛性迭代法及其收敛性n局部收敛性 前面讨论的收敛性称为全局收敛性，现在我们讨论局部收敛性。 定义1：设 有不动点 ，如果存在 的某个领域 ，对任意 ，迭代公式 产生的序列 且收敛到 ，则称该迭代法局部收敛。 定理3：设 为 的不动点， 在 的某个领域连续，且 ，则迭代法 收敛。 证明：由连续函数的性质，存在 的某个领域 ，使对任意 成立 ，此外，对于任意 ，总有 ，这是因为于是依据定理2可断定迭代过程对于任意的初值收敛( ) x*x*x*:rxx0 xr1()kkxx kxr*x*x( ) x( ) x*x*()1x1()kk

15、xx*x*:rxxxr( )1xlxr( )xr*( )( )()xxxxl xxxx7.2 迭代法及其收敛性迭代法及其收敛性n关于收敛速度问题的例 用不同的方法求方程 的根 。解：这里 ，可改写为各种不同的等价形式：(1) (2) (3) (4)取 ，对上述4种迭代法，计算三步所得结果如下*3x 230 x 2( )3f xx22*13,( )3,( )21,()2 31 1kkkxxxxxxxxx *12333,( ),( ),()1kkxxxxxxx 221*11(3),( )(3),4413( )1,()1122kkkxxxxxxxxx *12131313(),( )(),( )(1)

16、,()0222kkkxxxxxxxxx02x 7.2 迭代法及其收敛性迭代法及其收敛性注意 ，从计算结果看到迭代法(1)和(2)均不收敛，且它们均不满足定理3种的局部收敛条件迭代法(3)和(4)均满足局部收敛条件，且(4)比(3)快，这是因为(4)的 。为了衡量收敛速度，可以给出如下的定义。方法1方法2方法3方法402222131.51.751.752921.734751.7321433871.51.7323611.732051kkx0 x1x2x3x*()0 x31.73205087.2 迭代法及其收敛性迭代法及其收敛性 定义2 设迭代过程 收敛于方程 的根 ，如果迭代误差 当 时成立下列渐

17、进关系式则称该迭代过程是 阶收敛的，特别地， 时称线性收敛， 时称超线性收敛， 时称平方收敛。 定理4 对于迭代过程 ，如果 在所求根 的邻近连续，并且 (*)则该迭代过程在点 邻近是 阶收敛的。 证明：由于 ，据定理3立即可以断定迭代过程 具有局部收敛性。 再将 在根 处做泰勒展开，利用条件(*)，得到1()kkxx( )xx*x*kkxxk 1(0)kpkcp1p 1p 2p 1()kkxx( )( )pyx*x*(1)*( )*()()()0,()0ppxxxx*xp*()0 x1()kkxx()kx*x7.2 迭代法及其收敛性迭代法及其收敛性 在 与 之间，注意到 由上式得到因此对迭代

18、误差，当 时有这表明迭代过程 确实为 阶收敛。证毕。 定理说明，迭代过程的收敛速度依赖于迭代函数的选取，如果 ，则迭代过程只可能时线性收敛。 在例4中，迭代法(3)的 ，故它只是线性收敛，迭代法(4)的 ，但 ，故为2阶。( )*( )()()() ,!ppkkxxxxpkx*x1(),kkxx*(),xx( )*1( )()!ppkkxxxxpk ( )*1()!pkpkxp1()kkxxp( )0 x*()0 x*()0 x*()0 x7.3 迭代法收敛的加速方法迭代法收敛的加速方法n埃特金加速收敛方法 有的迭代过程虽然收敛，但速度很慢，因此迭代过程的加速是一个重要课题。 设 是根 的某个

19、近似值，用迭代公式校正一次得 ，而有微分中值定理，有其中 介于 与 之间。 假设 改变不大，近似地取某个近似 ，则有若将校正值 再校正一次，又得 ，由于 在两式中消去 ，得到 ，由此推得：0 x*x10()xx*100()()( )()xxxxxx *x0 x( )xl*10()xxl xx10()xx21()xx*21()xxl xxl*01*21xxxxxxxx7.3 迭代法收敛的加速方法迭代法收敛的加速方法在计算了 及 之后，可用上式右端作为 的新近似，记作 ，一般情形是由 计算 ， ，记该方法称为埃特金加速方法。 可以证明：它表明序列 的收敛速度比 的收敛速度快。22*02110021

20、0210()22x xxxxxxxxxxxx1x2x*x1xkx1kx2kx2221112()() /(0,1,)2kkkkkkkkkkxxxxxxxkxxx *1*lim0kkkxxxx kx kx7.3 迭代法收敛的加速方法迭代法收敛的加速方法n斯蒂芬森迭代法 埃特金方法不管原序列 是怎样产生的，对 进行加速计算，得到序列 ，如果把埃特金加速技巧与不动点迭代结合，则得到如下的迭代法：称为斯蒂芬森迭代法，它可以这样理解：我们要求 的根 ，令已知 的近似值 及 ，其误差分别为通过把误差外推到零，即过 及 两点做线性插值函数，它与 轴的交点就是迭代法的结果。 kx kx kx21()(),(),

21、(0,1,)2kkkkkkkkkkkyxyxzyxxkzyx( )xx*x*( )( ),()()0,xxxxxx*xkxky()(),()(),kkkkkkkkkkxxxyxyyyzy(, ()kkxx(, ()kkyyx7.3 迭代法收敛的加速方法迭代法收敛的加速方法即方程 的解：实际上就是将两个步骤合成一个步骤，如果把它看成一个不动点迭代 ，则 (*)关于上述不动点迭代法有以下的局部收敛性： 定理5 若 为(*)定义的迭代函数 的不动点，则 为 的不动点。反之，若 为 的不动点，设 存在， ，则 是 的不动点，且斯法是2阶的。()()()()0kkkkkkyxxxxyx21()()()(

22、)()2kkkkkkkkkkkkkxyxxxyxxxyxzyx1()kkxx2 ( )( )( ( )2 ( )xxxxxxx *x( )x*x( )x*x( )x( )x*()1x*x( )x7.3 迭代法收敛的加速方法迭代法收敛的加速方法 证明：设 是 的不动点，即 ，则有：即 ，所以 ，即 是 的不动点。反之，若 是 的不动点，且设 ，则故 与 有相同的不动点。 现设 且 ，则此时，若 收敛，且只是一阶的，但 却可以是二阶的。 *x( )x*()xx* 2* ()()( ()2 ()xxxxxxxx * 2 ()0 xx*()xx*x( )x*x( )x*()1x*2* ( )lim(

23、)lim( ( )2 ( )2( ( )( ) 1)lim( ( )( )2( ) 1xxxxxxxxxxxxxxxxxxxxx ( )x( )x*()1xa0a1()kkxx1()kkxx7.3 迭代法收敛的加速方法迭代法收敛的加速方法因为：取 ，即有：故：回到一般的 ，即有：所以：即 具有二阶收敛性。 证毕。* 2( )( )()()()2xxa xxxx *0 x 2( )()xaxo x22222( ( )()() )()xa axo xo axo xa xo x 222223 ( )()()xaxo xa xo x222232222()()( )()()2()x a xo xa xo

24、 xxo xa xo xaxo xx*x* 2( )() )xxo xx* 2lim( ( )/()nnxxxxc1()kkxx7.3 迭代法收敛的加速方法迭代法收敛的加速方法 例5 用斯蒂芬森迭代法求解方程 。解：前面的例3中已经指出迭代格式 是发散的，现用斯蒂芬森迭代法，取 ，则有迭代公式：取 ，得到：书上的方法是通过 得到的，结果一致。 特别注意：对于发散的算法 ，斯蒂芬森迭代法仍可能收敛。进一步还可证明斯蒂芬森迭代法的收敛阶可以高一阶。310 xx 311kkxx3( )1xx32643233333643296312221( )(1)2(1)(1)1 2(1)22213xxxxxxxx

25、xxxxxxxxxxxxxxxxxx 01.5x 123451.41629,1.35565,1.32895,1.32480,1.32472xxxxx,kkyz( )xx7.4 牛顿法牛顿法n牛顿法 对于方程 ，如果 是线性函数，则它的求根是容易的，牛顿法就是一种将非线性方程 逐步线性化的方法。 设已知方程 有近似根 (假定 )，将函数 在点 展开，有 ，于是方程 可近似地表示为 ，这是一个线性方程，记其根为 ，则 的计算公式为这就是牛顿迭代法。 ( )0f x ( )f x( )0f x ( )0f x kx()0kfx( )f xkx( )()()()kkkf xf xfxxx( )0f x

26、 ()()()0kkkf xfxxx1kx1kx1()(0,1,)()kkkkf xxxkfx7.4 牛顿法牛顿法n牛顿法的几何意义 方程 的根在几何上就是曲线 与 轴的交点的横坐标。设 是根 的某个近似值，通过曲线 上横坐标为 的点 引切线，切线方程为：令 ，解得 ，将其作为下一个近似值就得到牛顿法。因此，牛顿法在几何上可以解释为将近似值 处曲线上对应点 的切线与 轴的交点作为 的新的近似值，注意到切线方程的形式，我们可以将牛顿法称为切线法。( )0f x ( )yf xxkx*x( )yf xkxkp()()()kkkyf xfxxx0y ()()kkkf xxxfxkxkpx1kx7.4

27、 牛顿法牛顿法 关于牛顿法的收敛性，由于迭代函数为：由于假定 是 的一个单根，即 ， ，则由上式知 ，于是可得牛顿法在根 的附近是平方收敛的。又因故可得( )( )( )f xxxfx2( )( )( )( )f x fxxfx*x( )f x*()0f x*()0fx*()0 x*x*()()()fxxfx*1* 2*()lim()2()kkkxxfxxxfx7.4 牛顿法牛顿法例：用牛顿法解方程解：迭代公式为：取初值 ，迭代结果为：如果用格式 ，采用不动点迭代法，则要17次迭代才能得到同样的结果。10 xxe 11kxkkkkxexxx00.5x 1230.57102,0.56716,0.

28、56714xxx1kxkxe7.4 牛顿法牛顿法n牛顿法的计算步骤(1) 准备：确定初始值 ，计算(2) 迭代：按公式 迭代一次，得到新的近似值 ，计算(3) 控制：如果 满足 或 ，则终止迭代，以 作为所求的根，否则转步骤4，此处的 是允许误差，而(4) 修改：若 ，或 ，则停止，否则转(2)0 x0000(),()ff xffx1000/xxff1x1111(),()ff xffx1x1011011,xxxcxxxcxnn10f 112f1x12, 7.4 牛顿法牛顿法牛顿法应用举例： 应用牛顿法解二次方程：计算公式为：可以证明，这个迭代公式对于任意的初值均收敛。 求 ，应用上述公式，取

29、，计算3次即得到较高精度。20 xc11()2kkkcxxx115010 x 7.4 牛顿法牛顿法n简化牛顿法与牛顿下山法 牛顿法需要计算 ，计算量较大。 可能不收敛。为克服这两个缺点，通常采用下述方法：(1) 简化牛顿法迭代函数： 若 ，即取 在根 附近成立，则该迭代法局部收敛。 若取 ，则称为简化牛顿法。这类算法计算量小，单只有线性收敛。()kfx1(),0,0,1,kkkxxcf xck( )( )xxcf x01()cfx( )1( )1xcfx0( )2cfx*x7.4 牛顿法牛顿法(2) 牛顿下山法 牛顿法收敛依赖于初始值，因此可能发散，为防止迭代发散，我们对迭代过程附加一个要求，

30、即满足这项要求的算法称为下山法。 我们将牛顿法和下山法结合起来，即在下山法保证函数值稳定下降的前提下，用牛顿法加快速度，为此我们构造迭代公式： 即： ，称为牛顿下山法。其中 称为下山因子。n下山因子的选择 取 进行试算，逐次减半，直到下山条件成立。1()()kkf xf x1()()(1)()kkkkkf xxxxfx1()()kkkkf xxxfx17.4 牛顿法牛顿法n重根情形 设 ，整数 ， ，则 为方程 的 重根，此时有：只要 ，就可以用牛顿迭代法继续计算，此时迭代函数的导数为 ，且 ，所以牛顿迭代法求重根只是线性收敛。n改进方案一 取 ，则 ，用迭代法求 重根，则具有2阶收敛，但需要

31、预先知道重数 。*( )()( )mf xxxg x2m *()0g x*x( )0f x m*(1)*()*()()()0,()0mmf xfxfxfx()0kfx*1()10 xm *()1x( )( )( )f xxxmfx*()0 x1()(0,1,)()kkkkf xxxmkfxmm7.4 牛顿法牛顿法n改进方案二 令 ，若 是 的 重根，则对于它用牛顿法，其迭代函数为：从而可构造迭代法它是一个2阶的方法。( )( )/( )xf xfx*() ( )( )( )()( )xx g xxmg xxx g x*x( )0f x m2( )( )( )( )( )( )( )( )xf

32、x fxxxxxfxf x fx12()()(0,1,)()()()kkkkkkkf xfxxxkfxf xfx7.4 牛顿法牛顿法例9：方程 的根 是二重根，用上述三种方法求根。解：三种方法的迭代公式分别为： (1) (2) (3) 取初值 ，得到如下结果：(1)为线性收敛，精度不高，(2)(3)为2阶收敛，精度高已有10位有效数字，而方法(1)要30次才达同样精度42440 xx*2x 2124kkkkxxxx2122kkkkxxxx212(2)2kkkkkxxxxx01.5x 方法(1)方法(2)方法(3)11.4583333331.4166666671.41176470621.4366

33、071431.4142156861.41421143831.4254976191.4142135621.414213562kkx1x2x3x7.5 弦截法与抛物线法弦截法与抛物线法 为回避在牛顿法中需计算的 ，设法用函数值 来代替，下面介绍两种常用方法：n弦截法 设 是 的近似根，我们利用构造一次插值多项式 ，并用 的根作为的新的近似根 ，由于因此有：这个结果其实可以看成牛顿公式中导数用差商来代替()kfx1(),(),kkf xf x1,kkxx( )0f x 1(),()kkf xf x1( )p x1( )0p x ( )0f x 1kx111()()( )()()kkkkkkf xf xp xf xxxxx111()()()()kkkkkkkf xxxxxf xf x7.5 弦截法与抛物线法弦截法与抛物线法n弦截法的几何意义kx1kx1kx*x1kpkp1( )yp x( )yf xyxo111()()( )()()kkkkkkf xf xp xf xxxx