第三节-牛顿迭代法

1一牛顿法及其收敛性牛顿法是一种线性化方法，其基本思想是将非线性方程逐步归结为某种线性方程来求解.0)(xf设已知方程有近似根（假定)，将函数在点展开，有0)(xfkx0)(kxf)(xfkx),)(()()(kkkxxxfxfxf于是方程可近似地表示为0)(xf.0))(()(kkkxxxfxf（1）这是个线性方程，记其根为，则的计算公式为1kx1kx10.4牛顿迭代法2),,1,0()()(1kxfxfxxkkkk（2）这就是牛顿(Newton)法.牛顿法的几何解释.方程的根可解释为曲线与轴的交点的横坐标（图7-3).0)(xf*x)(xfyx设是根的某个近似值，过曲线上横坐标为的点引切线，并将该切线与轴的交点的横坐标作为的新的近似值.kx*x)(xfykxkPx1kx*x图7-33注意到切线方程为).)(()(kkkxxxfxfy这样求得的值必满足(1），从而就是牛顿公式（2）的计算结果.由于这种几何背景，牛顿法亦称切线法.1kx牛顿法（2）的收敛性，可直接由上节定理得到，对（2）其迭代函数为,)()()(xfxfxxg由于.)]([)()()(2xfxfxfxg假定是的一个单根，即，则由上式知，于是依据可以断定，牛顿法在根的邻近至少是平方收敛的.)(xf*x0*)(,0*)(xfxf0*)(xg*x4又因,*)(*)(*)(xfxfxg故可得.*)(2*)(*)(*lim21xfxfxxxxkkk（3.3）例7.3.1用牛顿法解方程.01xxe（3.4）解这里牛顿公式为,11kxkkkxexxxk取迭代初值，迭代结果列于表7-5中.5.00x.!*)()(1pxgeeppkk.!*)()(1pxgeeppkk556714.0356716.0257102.015.0057kxk计算结果表所给方程（3.4）实际上是方程的等价形式.若用不动点迭代到同一精度要迭代28次，可见牛顿法的收敛速度是很快的.xex6对于给定的正数，应用牛顿法解二次方程C,02Cx可导出求开方值的计算程序C).(211kkkxCxx（3.5）这种迭代公式对于任意初值都是收敛的.00x事实上，对（3.5）式施行配方手续，易知.)(21;)(212121CxxCxCxxCxkkkkkk二牛顿法应用举例7以上两式相除得.211CxCxCxCxkkkk据此反复递推有.20011kCxCxCxCxkk（3.6）记,00CxCxq整理（3.6）式，得8.1222kkqqCCxk对任意，总有，故由上式推知，当时，即迭代过程恒收敛.00x1qkCxk723805.104723805.103723837.102750000.10110067kxk计算结果表解取初值，对按（3.5）式迭代3次便得到精度为的结果（见表7-6).100x115C610由于公式（3.5）对任意初值均收敛，并且收敛的速度很快，因此可取确定的初值如编成通用程序.00x10x例7.3.2求.1159三简化牛顿法与牛顿下山法牛顿法的优点收敛快，牛顿法的缺点一每步迭代要计算及，计算量较大且有时计算较困难，二是初始近似只在根附近才能保证收敛，如给的不合适可能不收敛.)(kxf)(kxf)(kxf0x*x0x10为克服这两个缺点，通常可用下述方法.（1）简化牛顿法，也称平行弦法.其迭代公式为.,1,0)(1CxCfxxkkk（3.7）迭代函数).()(xCfxx若在根附近成立，即取，则迭代法（3.7）局部收敛.*x1)(1)(xfCx2)(0xfC11在（3.7）中取，则称为简化牛顿法，这类方法计算量省，但只有线性收敛，其几何意义是用平行弦与轴交点作为的近似.如图7-4所示.)(10xfCx*x图7-412（2）牛顿下山法.牛顿法收敛性依赖初值的选取.如果偏离所求根较远，则牛顿法可能发散.0x0x*x例如，用牛顿法求方程.013xx（3.8）在附近的一个根.5.1x*x设取迭代初值，用牛顿法公式5.10x131231kkkkkxxxxx（3.9）计算得.32472.1,32520.1,34783.1321xxx迭代3次得到的结果有6位有效数字.3x13但如果改用作为迭代初值，则依牛顿法公式（3.9）迭代一次得6.00x.9.171x这个结果反而比更偏离了所求的根.6.00x32472.0*x为了防止迭代发散，对迭代过程再附加一项要求，即具有单调性：.)()(1kkxfxf（3.10）满足这项要求的算法称下山法.将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度.将牛顿法的计算结果14)()(1kkkkxfxfxx与前一步的近似值适当加权平均作为新的改进值kx,)1(11kkkxxx（3.11）其中称为下山因子，（3.11）即为)10(),,1,0()()(1kxfxfxxkkkk（3.12）(3.12)称为牛顿下山法.选择下山因子时从开始，逐次将减半进行试算，直到能使下降条件（3.10）成立为止.1若用此法解方程（3.8），当时由（3.9）求得6.00x15，它不满足条件（3.10）.9.171x通过逐次取半进行试算，当时可求得.此时有，而显然.32/1140625.11x656643.0)(1xf384.1)(0xf)()(01xfxf由计算时,均能使条件（3.10）成立.计算结果如下：1x,,32xx1.0000086.0)(,32472.1;00667.0)(,32628.1;1866.0)(,36181.1443322xfxxfxxfx即为的近似.一般情况只要能使条件（3.10）成立，则可得到，从而使收敛.4x*x0)(limkkxf}{kx16四重根情形设，整数，则为方程的重根，此时有)(*)()(xxxxfm0*)(,2xm*x0)(xfm.0*)(,0*)(*)(*)()1(xfxfxfxfmm只要仍可用牛顿法（3.2）计算，此时迭代函数0)(kxf)()()(xfxfxxg的导数为011*)(mxg且，所以牛顿法求重根只是线性收敛.1*)(xg17,)()()(xfxfmxxg则.用迭代法0*)(xg),1,0()()(1kxfxfmxxkkkk（3.13）求重根，则具有2阶收敛，但要知道的重数.mm*x构造求重根的迭代法，还可令，若是的重根，则)(/)()(xfxfx*x0)(xfm,)(*)()()(*)()(xxxxmxxxx若取故是的单根.对用牛顿法，其迭代函数为*x0)(x)(x18.)()()]([)()()()()(2xfxfxfxfxfxxxxxg从而可构造迭代法),,1,0()()()]([)()(21kxfxfxfxfxfxxkkkkkkk（3.14）它是二阶收敛的.例7.3.3方程的根是二重根，用上述三种方法求根.04424xx2*x解先求出三种方法的迭代公式：（1）牛顿法.4221kkkkxxxx19（2）用（3.13）式.2221kkkkxxxx（3）用（3.14）式.2)2(221kkkkkxxxxx取初值，计算结果如表7-7.5.10x414213562.1414213562.1425497619.13414211438.1414215686.1436607143.12411764706.1416666667.1458333333.1132177321xxxxkk）方法（）方法（）方法（三种方法数值结果表20计算三步，方法（2）及（3）均达到10位有效数字，而用牛顿法只有线性收敛，要达到同样精度需迭代30次.21五弦截法与抛物线法用牛顿法求方程（1.1）的根，每步除计算外还要算，当函数比较复杂时，计算往往较困难，为此可以利用已求函数值来回避导数值的计算.)(kxf)(kxf)(xf)(xf),(),(1kkxfxf)(kxf1弦截法设是的近似根，利用构造一次插值多项式，并用的根作为新的近似根.由于1,kkxx0)(xf)(),(1kkxfxf)(1xp0)(1xp1kx).()()()(111kkkkkkxxxxxfxfxfxp（5.1）22因此有).()()()(111kkkkkkkxxxfxfxfxx（5.2）（5.2）可以看做牛顿公式)()(1kkkkxfxfxx中的导数用差商取代的结果.)(kxf11)(kkkkxxxfxf几何意义.曲线上横坐标为的点分别记为，则弦线的斜率等于差商值,其方)(xfy1,kkxx1,kkPP1kkPP11)(kkkkxxxfxf23程是).()()(11kkkkkkxxxxxfxfxfy因之，按（5.2)式求得的实际上是弦线与轴交点的横坐标.这种算法因此而称为弦截法.1kx1kkPPx表7-524弦截法与切线法（牛顿法）都是线性化方法，但两者有本质的区别.切线法在计算时只用到前一步的值，而弦截法（5.2），在求时要用到前面两步的结果，因此使用这种方法必须先给出两个开始值.1kxkx1kx1,kkxx01,xx例7.3.4用弦截法解方程.01)(xxexf解设取作为开始值，用弦截法求得的结果见表7-8，比较例7.3.1牛顿法的计算结果可以看出，弦截法的收敛速度也是相当快的.6.0,5.010xx56714.0456709.0356532.026.015.0087kxk计算结果表实际上，弦截法具有超线性的收敛性.25定理6假设在根的邻域内具有二阶连续导数，且对任意有，又初值，那么当邻域Δ充分小时，弦截法（5.2）将按阶收敛到根.这里是方程的正根.)(xf*x*:xxx0)(xf10,xx618.1251p*xp012262抛物线法设已知方程的三个近似根，以这三点为节点构造二次插值多项式，并适当选取的一个零点作为新的近似根，这样确定的迭代过程称抛物线法，亦称密勒（Müller）法.21,,kkkxxx0)(xf)(2xp)(2xp1kx在几何上，这种方法的基本思想是用抛物线与轴的交点作为所求根的近似位置（图7-6).)(2xpy1kxx*x图7-627插值多项式).)(](,,[)](,[)()(12112kkkkkkkkkxxxxxxxfxxxxfxfxp有两个零点：,],,[)(4)(22121kkkkkkkxxxfxfxfxx（5.3）式中).](,,[],[1211kkkkkkkxxxxxfxxf问题是该如何确定，假定在三个近似根中，更接近所求的根，为了保证精度，选（5.3）中较接近的一个值作为新的近似根.为此，只要取根式前的符号与的符号相同.1kx21,,kkkxxxkx*xkx1kx28例7.3.5用抛物线法求解方程.01)(xxexf解设用表7-8的前三个值56532.0,6.0,5.0210xxx作为开始值，计算得.21418.2],,[,83373.2],[,68910.2],[,005031.0)(,093271.0)(,175639.0)(0121201210xxxfxxfxxfxfxfxf故.75694.2)](,,[],[1201212xxxxxf