计算方法第七章print课件.ppt

1、 本章讨论非线性方程 的求根问题，其中一类特殊的问题就是多项式方程的求根。方程 的根 又称为 的零点，它使若 可表示为 ，其中 为正整数，且 。当 时，称 为单根，若 称 为 重根，或 的 重零点。若 是 的 重零点，且 充分光滑，则7.1 方程求根与二分法方程求根与二分法()0f x 10110()(0)nnnnf xa xa xaxaa()0f x*x()f x*()0f x()f x*()()()mf xxxg xm*()0g x1m*x1m*xmm()f x*x()f xm()g x*(1)*()*()()()0,()0mmf xfxfxfx7.1 方程求根与二分法方程求根与二分法 当

2、 为代数多项式时，根据代数基本定理可知，次方程在复数域有且只有 个根，因此可利用迭代法求代数方程的根。n二分法 若 ，且 ，根据连续函数性质可知 在 内至少有一个实根，此时称 为方程的有根区间。例：求方程 的有根区间。解：通过计算部分点的函数值，得到如下结果：由此得到方程的有根区间为：。()f xnn(),f xC a b()()0f a f b()f x,a b,a b32()11.138.841.770f xxxx0123456 的符号x()f x1,2,3,4,5,67.1 方程求根与二分法方程求根与二分法n二分算法 设已找到有根区间 ，满足 ，且在 上只有一个零点，步骤如下：(1)先设

3、 对于一般的区间 ，设其中点为：(2)检验 的符号，若与 同号，就取 ，否则取 这样必有所以 就是新的有根区间，继续此过程，即可得到结果。算法：(1)令(2)若 或 ，则输出 ，结束(3)若 ，则令 ，否则令(4)转向1),a b()()0f a f b()f x,a b11,aa bb,nna b()/2nnnxab()nf x()nf a1nnax1,nnbb1,nnaa1,nnbx11()()0nnf af b11,nnab()/2xab()f xbxx()()0f a f x axbx7.1 方程求根与二分法方程求根与二分法 这样，我们得到了一个序列 ，为确定 的收敛性我们有如下的定理

4、：定理：设 则二分算法产生的序列 满足 其中 为方程的根。证明：因为 由 对分得到，所以对区间长度而 ，且 ，所以故当 时，且有误差估计式nxnx(),()()0,f xC a bf a f bnx*()/2,nnxxba*,xa b11,nnab,nna b1n 111()/2()/2nnnnnbababa*,nnxa b()/2nnnxab*()/2()/2,nnnnxxbaban*nxx*()/2nnxxba7.1 方程求根与二分法方程求根与二分法例：已知 在 有一个零点，用二分法计算的结果如下：32()410f xxx1,2(1)5f(2)14fn有根区间11.0,2.01.52.37

5、521.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.359375,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

6、 xx510*()/22NNNxxba5210N105/log 216.6N 7.2 迭代法及其收敛性迭代法及其收敛性n不动点迭代法 将方程 改写成等价的形式 ，则的根 也满足方程 ，反之亦然。称 为 的不动点。而求 的根的问题就成为求 的不动点问题。选取初值 ，以公式 进行迭代，称为迭代函数，若 收敛到 ，则 就是 的不动点，这种方法就称为不动点迭代法。将 转化为 的方法可以是多种多样的，例：在 上可有以下方法：(1)(2)(3)(4)取 ，有的收敛，有的发散，有的快，有的慢。()0f x()xx()0f x*x()xx*x()x()0f x()x0 x1()nnxx()x nx*x*x()

7、x()0f x()xx32()4100f xxx1,232410 xxxx3 1/2(1/2)(10)xx1/2(10/4)xxx1/210/(4)xx01.5x 7.2 迭代法及其收敛性迭代法及其收敛性n迭代过程的几何表示 方程 的求根问题在 平面上就是要确定曲线 与直线 的交点 ，对于 的某个近似值 ，在曲线 上可确定一点 ，它的横坐标为而纵坐标为 ，过 引 轴的平行线，交 于 ，然后过 再作 轴的平行线，它与 的交点记作 ，则 的横坐标为 ，而纵坐标为 ，按图中箭头所示路经继续做下去，在曲线上得到点列 其横坐标分别为按公式 求得的迭代值 如果点列 趋向于点 ，则相应的迭代值 收敛到所求的

8、根 。()xxxy()yxyx*P*x0 x()yx0P0 x01()xx0Pxyx1Q1Qy()yx kP1P1x12()xx1P23,P P 1()kkxx123,x x x 1P*Pkx*x7.2 迭代法及其收敛性迭代法及其收敛性0 x1x2x3x*x0P1P2P3P1Q2Q3Q*P7.2 迭代法及其收敛性迭代法及其收敛性 例3：求方程 在 附近的根 。解：将方程改写为 ，由此建立迭代公式：计算结果如下表：这是一个收敛的例子，也有不收敛的迭代公式，如我们对于同样的问题，如果将方程改写为令一种迭代公式 ，仍取初值 ，则迭代发散。为此，我们要研究 存在性及迭代法的收敛性。3()10f xxx

9、 01.5x*x31xx311(0,1,2,)kkxxk0123456781.5 1.35721 1.33086 1.32588 1.32494 1.32476 1.32473 1.32472 1.32472kxk311kkxx01.5x()x7.2 迭代法及其收敛性迭代法及其收敛性 定理1：(存在性)设 满足以下两个条件：(1)对任意的 ，有(2)存在 ，使对任意 都有则 在 上存在唯一的不动点 。证明：先证不动点的存在性。若 或 ，则 或 就是不动点。因此由 可设 及 ，定义函数 ，显然 且满足 由函数的连续性可知存在 使 ，即 ，即为 的不动点。,xa b()axb01L,x yC a

10、b()()xyL xy()x*x,a b()aa()bbab()axb()aa()bb()()f xxx()()0,()()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

11、b()x*12121212()()xxxxL xxxx()x(),xC a 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 迭代法及其收敛性迭代法

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

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

14、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),()0222kkkxxxxxxx

15、xx02x 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 设迭代过程 收敛于方程 的根 ，如果迭代误差 当 时成立下列渐进关系式则称该迭代过程是 阶收敛的

16、，特别地，时称线性收敛，时称超线性收敛，时称平方收敛。定理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 迭代法及其收敛性迭代法及其收敛性 在 与 之间，注意到 由上式得到因此对迭代误差，当 时有这表明迭代过程 确实为 阶收敛。证毕。定

17、理说明，迭代过程的收敛速度依赖于迭代函数的选取，如果 ，则迭代过程只可能时线性收敛。在例4中，迭代法(3)的 ，故它只是线性收敛，迭代法(4)的 ，但 ，故为2阶。()*()()()(),!ppkkxxxxpkx*x1(),kkxx*(),xx()*1()()!ppkkxxxxpk ()*1()!pkpkxp1()kkxxp()0 x*()0 x*()0 x*()0 x7.3 迭代法收敛的加速方法迭代法收敛的加速方法n埃特金加速收敛方法 有的迭代过程虽然收敛，但速度很慢，因此迭代过程的加速是一个重要课题。设 是根 的某个近似值，用迭代公式校正一次得 ，而有微分中值定理，有其中 介于 与 之间。

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

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

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

21、*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()lim()2()2()()1)lim()()2()1xxxxxxxxxxxxxxxxxxxxx ()x()x*()1xA0A1()kkxx1()kkxx7.3 迭代法收

22、敛的加速方法迭代法收敛的加速方法因为：取 ，即有：故：回到一般的 ，即有：所以：即 具有二阶收敛性。证毕。*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 xxO xA xO xAxO xx*x*2()()xxO xx*2lim()/()nnxxxxC1()kkxx7.3 迭代法收敛的加速方法迭代法收敛的加速方法 例5 用斯蒂芬森迭代法求解方程 。解：前面的例3中已经指出迭代格式 是发

23、散的，现用斯蒂芬森迭代法，取 ，则有迭代公式：取 ，得到：书上的方法是通过 得到的，结果一致。特别注意：对于发散的算法 ，斯蒂芬森迭代法仍可能收敛。进一步还可证明斯蒂芬森迭代法的收敛阶可以高一阶。310 xx 311kkxx3()1xx32643233333643296312221()(1)2(1)(1)1 2(1)22213xxxxxxxxxxxxxxxxxxxxxxxxxx 01.5x 123451.41629,1.35565,1.32895,1.32480,1.32472xxxxx,kkyz()xx7.4 牛顿法牛顿法n牛顿法 对于方程 ，如果 是线性函数，则它的求根是容易的，牛顿法就是

24、一种将非线性方程 逐步线性化的方法。设已知方程 有近似根 (假定 )，将函数 在点 展开，有 ，于是方程 可近似地表示为 ，这是一个线性方程，记其根为 ，则 的计算公式为这就是牛顿迭代法。()0f x()f x()0f x()0f x kx()0kfx()f xkx()()()()kkkf xf xfxxx()0f x()()()0kkkf xfxxx1kx1kx1()(0,1,)()kkkkf xxxkfx7.4 牛顿法牛顿法n牛顿法的几何意义 方程 的根在几何上就是曲线 与 轴的交点的横坐标。设 是根 的某个近似值，通过曲线 上横坐标为 的点 引切线，切线方程为：令 ，解得 ，将其作为下一

25、个近似值就得到牛顿法。因此，牛顿法在几何上可以解释为将近似值 处曲线上对应点 的切线与 轴的交点作为 的新的近似值，注意到切线方程的形式，我们可以将牛顿法称为切线法。()0f x()yf xxkx*x()yf xkxkP()()()kkkyf xfxxx0y()()kkkf xxxfxkxkPx1kx7.4 牛顿法牛顿法 关于牛顿法的收敛性，由于迭代函数为：由于假定 是 的一个单根，即 ，则由上式知 ，于是可得牛顿法在根 的附近是平方收敛的。又因故可得()()()f xxxfx2()()()()f x fxxfx*x()f x*()0f x*()0fx*()0 x*x*()()()fxxfx*

26、1*2*()lim()2()kkkxxfxxxfx7.4 牛顿法牛顿法例：用牛顿法解方程解：迭代公式为：取初值 ，迭代结果为：如果用格式 ，采用不动点迭代法，则要17次迭代才能得到同样的结果。10 xxe 11kxkkkkxexxx00.5x 1230.57102,0.56716,0.56714xxx1kxkxe7.4 牛顿法牛顿法n牛顿法的计算步骤(1)准备：确定初始值 ，计算(2)迭代：按公式 迭代一次，得到新的近似值 ，计算(3)控制：如果 满足 或 ，则终止迭代，以 作为所求的根，否则转步骤4，此处的 是允许误差，而(4)修改：若 ，或 ，则停止，否则转(2)0 x0000(),()f

27、f xffx1000/xxff1x1111(),()ff xffx1x1011011,xxxCxxxCxnN10f 112f1x12,7.4 牛顿法牛顿法牛顿法应用举例：应用牛顿法解二次方程：计算公式为：可以证明，这个迭代公式对于任意的初值均收敛。求 ，应用上述公式，取 ，计算3次即得到较高精度。20 xC11()2kkkCxxx115010 x 7.4 牛顿法牛顿法n简化牛顿法与牛顿下山法 牛顿法需要计算 ，计算量较大。可能不收敛。为克服这两个缺点，通常采用下述方法：(1)简化牛顿法迭代函数：若 ，即取 在根 附近成立，则该迭代法局部收敛。若取 ，则称为简化牛顿法。这类算法计算量小，单只有线

28、性收敛。()kfx1(),0,0,1,kkkxxCf xCk()()xxCf x01()Cfx()1()1xCfx0()2Cfx*x7.4 牛顿法牛顿法(2)牛顿下山法 牛顿法收敛依赖于初始值，因此可能发散，为防止迭代发散，我们对迭代过程附加一个要求，即满足这项要求的算法称为下山法。我们将牛顿法和下山法结合起来，即在下山法保证函数值稳定下降的前提下，用牛顿法加快速度，为此我们构造迭代公式：即：，称为牛顿下山法。其中 称为下山因子。n下山因子的选择 取 进行试算，逐次减半，直到下山条件成立。1()()kkf xf x1()()(1)()kkkkkf xxxxfx1()()kkkkf xxxfx1

29、7.4 牛顿法牛顿法n重根情形 设 ，整数 ，则 为方程 的 重根，此时有：只要 ，就可以用牛顿迭代法继续计算，此时迭代函数的导数为 ，且 ，所以牛顿迭代法求重根只是线性收敛。n改进方案一 取 ，则 ，用迭代法求 重根，则具有2阶收敛，但需要预先知道重数 。*()()()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改进方案二 令 ，若 是 的 重根，则对于它用牛顿法，其迭

30、代函数为：从而可构造迭代法它是一个2阶的方法。()()/()xf xfx*()()()()()()xx g xxmg xxx g x*x()0f x m2()()()()()()()()xf x fxxxxxfxf x fx12()()(0,1,)()()()kkkkkkkf xfxxxkfxf xfx7.4 牛顿法牛顿法例9：方程 的根 是二重根，用上述三种方法求根。解：三种方法的迭代公式分别为：(1)(2)(3)取初值 ，得到如下结果：(1)为线性收敛，精度不高，(2)(3)为2阶收敛，精度高已有10位有效数字，而方法(1)要30次才达同样精度42440 xx*2x 2124kkkkxxx

31、x2122kkkkxxxx212(2)2kkkkkxxxxx01.5x 方法(1)方法(2)方法(3)11.4583333331.4166666671.41176470621.4366071431.4142156861.41421143831.4254976191.4142135621.414213562kkx1x2x3x7.5 弦截法与抛物线法弦截法与抛物线法 为回避在牛顿法中需计算的 ，设法用函数值 来代替，下面介绍两种常用方法：n弦截法 设 是 的近似根，我们利用构造一次插值多项式 ，并用 的根作为的新的近似根 ，由于因此有：这个结果其实可以看成牛顿公式中导数用差商来代替()kfx1()

32、,(),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 xxxxx111()()()()kkkkkkkf xxxxxf xf x7.5 弦截法与抛物线法弦截法与抛物线法n抛物线法 设已知方程 的三个近似根 ，构造二次插值

33、多项式 ，并以 的一个零点 作为新的近似值。设 为：它有两个零点：式中：为了保证精度，我们选接近 的为 ，为此选根号前的符号与 的符号一致。()0f x 12(),(),()kkkf xf xf x2()px2()px1kx2()px21121()(),(),()()kkkkkkkkkpxf xf xxxxf xxxxxxx1121,()kkkkkkkf xxf xxxxx12122()4(),kkkkkkkf xxxf xf xxx1kxkx7.6 解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法 考虑方程组 (*)其中 均为 的多元函数，若用向量记号，可记为：，当 且 中至少有一个是自

34、变量的非线性方程时，称(*)为非线性方程组。非线性方程组的求根问题是非线性方程求根的直接推广。实际上只要把前面介绍的单变量函数的方法用到向量函数上就可以了。我们来给出解法的叙述。111(,)0(,)0nnnf xxfxx1,nff1,nxx()0F x 2n if7.6 解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法 若已给出方程组的一个近似根 ，将函数 的分量 在 用多元函数泰勒展开，并取其线性部分，则可表示为：(*)令上式右端为零，得到线性方程组：其中：称为雅可比矩阵()()()1(,)kkkTnxxx()F x()(1,)if xin()kx()()()()()()()kkkF x

35、F xF xxx()()()()()()kkkF xxxF x 11112222()1212()()()()()()()()()()nknnnnnf xf xf xxxxfxfxfxxxxF xfxfxfxxxx7.6 解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法求解(*)，并记解为 ，则得到 (*)这就是求解非线性方程组的牛顿迭代法，具体求解时，我们为了回避求矩阵的逆，可以采用下面的方法：令 ，则(*)可写为：其中 和 是已知的，从上式可以求出从而得到 。例见书第288页。作业：编程实现非线性方程组的求解。(1)kx(1)()()1()()()(0,1,)kkkkxxF xF xk()(1)()kkkxxx()()()()()(0,1,)kkkF xxF xk()()kF x()()kF x()kx(1)kxnP290 1,3,6,15