第三节牛顿迭代法

1、1一一 牛顿法及其收敛性牛顿法及其收敛性 牛顿法是一种线性化方法，其基本思想是将非线性方程 逐步归结为某种线性方程来求解.0)(xf 设已知方程 有近似根 （假定 )，将函数 在点 展开，有 0)(xfkx0)(kxf)( xfkx),)()()(kkkxxxfxfxf于是方程 可近似地表示为 0)(xf.0)()(kkkxxxfxf（1）这是个线性方程，记其根为 ，则 的计算公式为 1kx1kx10.4 牛顿迭代法牛顿迭代法2),1 ,0()()(1kxfxfxxkkkk（2）这就是牛顿牛顿(Newton)(Newton)法法. 牛顿法的几何解释. 方程 的根 可解释为曲线 与 轴的交点的横

2、坐标（图7-3). 0)(xf*x)( xfy x 设 是根 的某个近似值，过曲线 上横坐标为 的点 引切线，并将该切线与 轴的交点的横坐标 作为 的新的近似值. kx*x)( xfy kxkPx1kx*x图7-33注意到切线方程为 ).)()(kkkxxxfxfy这样求得的值 必满足(1），从而就是牛顿公式（2）的计算结果. 由于这种几何背景，牛顿法亦称切线法切线法.1kx 牛顿法（2）的收敛性，可直接由上节定理得到，对（2）其迭代函数为 ,)()()(xfxfxxg由于 .)()()()(2xfxfxfxg 假定 是 的一个单根，即 ，则由上式知 ，于是依据可以断定，牛顿法在根 的邻近至少

3、是平方收敛的. )( xf*x0*)(,0*)(xfxf0*)( xg*x4又因 ,*)(*)(*)(xfxfxg 故 可得 .*)(2*)(*)(*lim21xfxfxxxxkkk （3.3） 例例7.3.1 7.3.1 用牛顿法解方程 .01 xxe（3.4） 解解 这里牛顿公式为 ,11kxkkkxexxxk取迭代初值 ，迭代结果列于表7-5中. 5.00 x.!*)()(1pxgeeppkk.!*)()(1pxgeeppkk556714.0356716.0257102.015.0057kxk计算结果表 所给方程（3.4）实际上是方程 的等价形式. 若用不动点迭代到同一精度要迭代28次，

4、可见牛顿法的收敛速度是很快的.xex6 对于给定的正数 ，应用牛顿法解二次方程 C,02 Cx可导出求开方值 的计算程序 C).(211kkkxCxx（3.5）这种迭代公式对于任意初值 都是收敛的. 00 x 事实上，对（3.5）式施行配方手续，易知 .)(21;)(212121CxxCxCxxCxkkkkkk二二 牛顿法应用举例牛顿法应用举例7以上两式相除得 .211CxCxCxCxkkkk据此反复递推有 .20011kCxCxCxCxkk（3.6）记 ,00CxCxq整理（3.6）式，得 8.1222kkqqCCxk 对任意 ，总有 ，故由上式推知，当 时 ，即迭代过程恒收敛. 00 x1

5、qkCxk723805.104723805.103723837.102750000.10110067kxk计算结果表 解解 取初值 ，对 按（3.5）式迭代3次便得到精度为 的结果（见表7-6). 100 x115C610 由于公式（3.5）对任意初值 均收敛，并且收敛的速度很快，因此可取确定的初值如 编成通用程序. 00 x10 x例例7.3.2 7.3.2 求 . 1159 三三 简化牛顿法与牛顿下山法简化牛顿法与牛顿下山法 牛顿法的牛顿法的优点优点 收敛快，牛顿法的牛顿法的缺点缺点 一 每步迭代要计算 及 ，计算量较大且有时 计算较困难， 二是初始近似 只在根 附近才能保证收敛，如 给的

6、不合适可能不收敛. )(kxf)(kxf )(kxf 0 x*x0 x10 为克服这两个缺点，通常可用下述方法. （1） 简化牛顿法，也称平行弦法. 其迭代公式为 .,1 ,0)(1CxCfxxkkk（3.7）迭代函数 ).()(xCfxx 若在根 附近成立 ，即取 ，则迭代法（3.7）局部收敛.*x1)(1)(xfCx2)(0 xfC11 在（3.7）中取 ，则称为简化牛顿法简化牛顿法，这类方法计算量省，但只有线性收敛，其几何意义是用平行弦与 轴交点作为 的近似. 如图7-4所示. )(10 xfCx*x图7-412 （2 2） 牛顿下山法牛顿下山法. . 牛顿法收敛性依赖初值 的选取. 如

7、果 偏离所求根 较远，则牛顿法可能发散.0 x0 x*x 例如，用牛顿法求方程 .013 xx（3.8）在 附近的一个根 . 5.1x*x 设取迭代初值 ，用牛顿法公式 5.10 x131231kkkkkxxxxx（3.9）计算得 .32472.1,32520.1,34783.1321xxx迭代3次得到的结果 有6位有效数字. 3x13 但如果改用 作为迭代初值，则依牛顿法公式（3.9）迭代一次得 6.00 x.9.171x这个结果反而比 更偏离了所求的根 . 6.00 x32472.0* x 为了防止迭代发散，对迭代过程再附加一项要求，即具有单调性： .)()(1kkxfxf（3.10）满足

8、这项要求的算法称下山法下山法. 将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度. 将牛顿法的计算结果 14)()(1kkkkxfxfxx与前一步的近似值 适当加权平均作为新的改进值 kx,)1(11kkkxxx（3.11）其中 称为下山因子，（3.11）即为 )10(),1 ,0()()(1kxfxfxxkkkk（3.12）(3.12)称为牛顿下山法牛顿下山法. 选择下山因子时从 开始，逐次将 减半进行试算，直到能使下降条件（3.10）成立为止. 1 若用此法解方程（3.8），当 时由（3.9）求得6.00 x15 ，它不满足条件（3.10）.9.17

9、1x 通过 逐次取半进行试算，当 时可求得 . 此时有 ，而显然 . 32/1140625.11x656643.0)(1xf384.1)(0 xf)()(01xfxf 由 计算 时 , 均能使条件（3.10）成立. 计算结果如下 ： 1x,32xx1.0000086.0)(,32472.1;00667.0)(,32628.1;1866.0)(,36181.1443322xfxxfxxfx 即为 的近似. 一般情况只要能使条件（3.10）成立，则可得到 ，从而使 收敛.4x*x0)(limkkxfkx16四四 重根情形重根情形 设 ，整数 ，则 为方程 的 重根，此时有 )(*)()(xxxxf

10、m0*)(,2xm*x0)(xfm.0*)(,0*)(*)(*)()1(xfxfxfxfmm只要 仍可用牛顿法（3.2）计算，此时迭代函数 0)(kxf)()()(xfxfxxg的导数为 011*)(mxg且 ，所以牛顿法求重根只是线性收敛. 1*)( xg17,)()()(xfxfmxxg则 . 用迭代法 0*)( xg),1 ,0()()(1kxfxfmxxkkkk（3.13）求 重根，则具有2阶收敛，但要知道 的重数 . mm*x 构造求重根的迭代法，还可令 ，若 是 的 重根，则 )(/)()(xfxfx*x0)(xfm,)(*)()()(*)()(xxxxmxxxx若取故 是 的单根

11、.对 用牛顿法，其迭代函数为 *x0)(x)(x18.)()()()()()()()(2xfxfxfxfxfxxxxxg 从而可构造迭代法 ),1 ,0()()()()()(21 kxfxfxfxfxfxxkkkkkkk（3.14）它是二阶收敛的. 例例7.3.3 7.3.3 方程 的根 是二重根，用上述三种方法求根. 04424xx2* x 解解 先求出三种方法的迭代公式： （1） 牛顿法 .4221kkkkxxxx19 （2） 用（3.13）式 .2221kkkkxxxx （3） 用（3.14）式 .2)2(221kkkkkxxxxx取初值 ，计算结果如表7-7. 5.10 x414213

12、562.1414213562.14254976191414215686.1436607143.12411764706.1416666667.1458333333.1132177321xxxxkk）方法（）方法（）方法（三种方法数值结果表20 计算三步，方法（2）及（3）均达到10位有效数字，而用牛顿法只有线性收敛，要达到同样精度需迭代30次. 21五五 弦截法与抛物线法弦截法与抛物线法 用牛顿法求方程（1.1）的根，每步除计算 外还要算 ，当函数 比较复杂时，计算 往往较困难，为此可以利用已求函数值 来回避导数值 的计算. )(kxf)(kxf )( xf)( xf

13、),(),(1kkxfxf)(kxf 1 弦截法弦截法 设 是 的近似根，利用 构造一次插值多项式 ，并用 的根作为新的近似根 . 由于 1,kkxx0)(xf)(),(1kkxfxf)(1xp0)(1xp1kx).()()()(111kkkkkkxxxxxfxfxfxp（5.1）22因此有 ).()()()(111kkkkkkkxxxfxfxfxx（5.2）（5.2）可以看做牛顿公式 )()(1kkkkxfxfxx中的导数 用差商 取代的结果.)(kxf 11)(kkkkxxxfxf 几何意义. 曲线 上横坐标为 的点分别记为 ，则弦线 的斜率等于差商值 , 其方)( xfy 1,kkxx1

14、,kkPP1kkPP11)(kkkkxxxfxf23程是).()()(11kkkkkkxxxxxfxfxfy因之，按（5.2)式求得的 实际上是弦线 与 轴交点的横坐标. 这种算法因此而称为弦截法弦截法. 1kx1kkPPx表7-524 弦截法与切线法（牛顿法）都是线性化方法，但两者有本质的区别. 切线法在计算 时只用到前一步的值 ，而弦截法（5.2），在求 时要用到前面两步的结果 ，因此使用这种方法必须先给出两个开始值 .1kxkx1kx1,kkxx01, xx 例例7.3.4 7.3.4 用弦截法解方程 .01)(xxexf 解解 设取 作为开始值，用弦截法求得的结果见表7-8，比较例7.

15、3.1牛顿法的计算结果可以看出，弦截法的收敛速度也是相当快的. 6.0,5.010 xx56714.0456709.0356532.026.015.0087kxk计算结果表 实际上，弦截法具有超线性的收敛性. 25 定理定理6 6 假设 在根 的邻域 内具有二阶连续导数，且对任意 有 ，又初值 ，那么当邻域充分小时，弦截法（5.2）将按阶 收敛到根 . 这里 是方程 的正根. )( xf*x*:xxx0)( xf10, xx618.1251p*xp012262 2 抛物线法抛物线法 设已知方程 的三个近似根 ，以这三点为节点构造二次插值多项式 ，并适当选取 的一个零点 作为新的近似根，这样确定

16、的迭代过程称抛物线法抛物线法，亦称密勒（密勒（MllerMller）法）法. 21,kkkxxx0)(xf)(2xp)(2xp1kx 在几何上，这种方法的基本思想是用抛物线 与 轴的交点 作为所求根 的近似位置（图7-6). )(2xpy 1kxx*x图7-627插值多项式 ).)(,)(,)()(12112kkkkkkkkkxxxxxxxfxxxxfxfxp有两个零点： ,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）式中 ).(,1211kkkkkkkxxxxxfxxf 问题是该如何确定 ，假定在 三个近似根中， 更接近所求的根 ，为了保证精度，选 （5.3）中较接近 的

17、一个值作为新的近似根 . 为此，只要取根式前的符号与 的符号相同. 1kx21,kkkxxxkx*xkx1kx28例例7.3.5 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)(,1201212xxxxxfxxf代入（5.3）式求得 .56714.0,)(4)(201222223xxxfxfxfxx29 以

18、上计算表明，抛物线法比弦截法收敛得更快. 在一定条件下可以证明，对于抛物线法，迭代误差有下列渐近关系式 .*)(6*)(42.01840.1xfxfeekk 可见抛物线法也是超线性收敛的，其收敛的阶 ,收敛速度比弦截法更接近于牛顿法. 840.1p 从（5.3）看到，即使 均为实数， 也可以是复数，所以抛物线法适用于求多项式的实根和复根. 21,kkkxxx1kx307.6 7.6 解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法 考虑方程组 ,0),(,0),(111nnnxxfxxf（6.1）其中 均为 的多元函数. nff,1),(1nxx 用向量记号记 , (6.1）就可写成 Tn

19、nTn),f,(fF,R),x,(xx11.0)(xF（6.2） 当 ，且 中至少有一个是自变量2n),1(nifi 的非线性函数时，称方程组（6.1）为非线非线性方程组性方程组. ),1(nixi31 非线性方程组求根问题是前面介绍的方程（即 ）求根的直接推广，只要把前面介绍的单变量函数 看成向量函数 则可将单变量方程求根方法推广到方程组（6.2）. 1n)( xf)( xF 若已给出方程（6.2）的一个近似根 ，将函数 的分量 在 用多元函数泰勒展开，并取其线性部分，则可表示为 Tknkkxxx),()()(1)()( xF),1)(nixfi)( kx).)()()()()()(kkkx

20、xxFxFxF令上式右端为零，得到线性方程组 ),()()()()(kkkxFxxxF（6.3）32其中 nnnnnnxxfxxfxxfxxfxxfxxfxxfxxfxxfxF)()()()()()()()()()(212221212111（6.4）称为 的雅可比雅可比(Jacobi)(Jacobi)矩阵矩阵. )( xF 求解线性方程组（6.3）并记解为 ，则得 )1(kx)., 1 , 0()()()(1)()()1(kxFxFxxkkkk（6.5）这就是解非线性方程组（6.2）的牛顿迭代法牛顿迭代法. 33 例例12 12 求解方程组 .052),(,032),(222121221211

21、xxxxfxxxxf给定初值 , 用牛顿法求解. Tx)0.1,5.1()0( 解解 先求雅可比矩阵 .1422821)(,2421)(1212121xxxxxFxxxF由牛顿法（6.5）得 ,5)()(23214228212)(22)(1)(2)(1)(1)(2)(1)(2)()1(kkkkkkkkkkxxxxxxxxxx34即 ).,1 ,0(,)4(25128)(2)(,453)(2)()(1)(2)(2)(2)(12)(12)(2)(2)1(2)(1)(2)(2)(2)(12)(12)(2)(1)1(1kxxxxxxxxxxxxxxxxxxkkkkkkkkkkkkkkkkkk由 逐次迭

22、代得到 Tx)0.1,5.1()0(,)755983.0,488034.1(,)755952.0,488095.1(,)75.0,5.1()3()2()1(TTTxxx 的每一位都是有效数字. )3(x35v拟Newton方程(1)11(1)(0)(1)(0)(2)(1)1(1)111()(1),()()()(2)AfxAsysxxyf xf xAxxA f xANewton取满足其中，若 可逆，就可取的选择多样化，每一种选择都确定一种方法，都称为拟法。36v1.0110101000010(0)(1)(2)(0)(2)(3)01,-=(3),.(-) =,(),()(4),42,(),TTTT

23、TBroydenAAA AusuA A s us sNewtonAA syA syA sthenus syA s sAAs sxNewtonxxAfxxx秩 修改法：对 作适当修改得到取待定则有另一，从拟方程可得故，由用法求利用（ ）和（ ）求再由，求，.37其中 ( 0 )( 0 )( 0 )1000( 0 )(1)( 0 )0(1)( 0 )(1)( 0 )-111(1)( 0 )(1)1,(),(),(),3()()04()()(5)()(xfxAfxHAsHfxxxssfxfxyfxfxHAxxfxf计 算 过 程 ：（ ） 选 取计 算=(2)计 算=-=当在 容 许 误 差 范 围 内时 停 止 计 算 。（ ） 计