数值分析第7章4-6节)

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

2、交点的横坐标)( xfy x图7-3（图7-3). 3 设 是根 的某个近似值，过曲线 上横坐标为 的点 引切线，并将该切线与 轴的交点的横坐标 作为 的新的近似值. kx*x)( xfy kxkPx1kx*x 注意到切线方程为 ).)()(kkkxxxfxfy这样求得的值 必满足（4.1），从而就是牛顿公式（4.2）的计算结果. 1kx 由于这种几何背景，牛顿法也称切线法切线法. 由定理4，可以直接得到牛顿法的收敛性.),1 ,0()()(1kxfxfxxkkkk（4.2）.0)()(kkkxxxfxf（4.1）4,)()()(xfxfxx由于 .)()()()(2xfxfxfx 假定 是

3、的一个单根，)( xf*x即 ，0*)(,0*)(xfxf则由上式知，0*)( x (4.2)的迭代函数为 在根 的邻近是平方收敛的. *x于是依据定理4可以断定，牛顿法 又因 ,*)(*)(*)(xfxfx ),1 ,0()()(1kxfxfxxkkkk（4.2）5故由（2.9）可得 .*)(2*)(*)(*lim21xfxfxxxxkkk （4.3） 例例7 7.01exx（4.4） 解解,1e1kxkkkxxxxk取迭代初值 ，迭代结果列于表7-5中. 5.00 x用牛顿法解方程 这里牛顿公式为 所给方程（4.4）实际上是方程 的等价形式. xx e.!*)()(1pxeeppkk（2.

4、9）656714.0356716.0257102.015.00kxk计算结果5表7 牛顿法的计算步骤： 步骤步骤1 1 准备准备选定初始近似值 ，0 x).(00 xff 步骤步骤2 2 迭代迭代0001/ ffxx迭代一次，得新的近似值 ，1x).(),(1111xffxff 若用不动点迭代到同一精度 可见牛顿法的收敛速度是很快的.要迭代17次.),(00 xff计算 按公式 计算 7则终止迭代，以 作为所求的根；1x 此处 是允许误差，而 21,，时当时当CxxxxCxxx1101101其中 是取绝对误差或相对误差的控制常数，C.1C 步骤步骤4 4 修改修改 如果迭代次数达到预先指定的次

5、数 ，N 步骤步骤3 3 控制控制如果 满足 或 ，1x121f否则转步骤4. 一般可取8或者 ，则方法失败；01f 否则以 代替 转步骤2继续迭代.),(111ffx),(000ffx9 7.4.2 牛顿法应用举例牛顿法应用举例 对于给定的正数 ，应用牛顿法解二次方程 C,02 Cx可导出求开方值 的计算程序 C).(211kkkxCxx（4.5）这种迭代公式对于任意初值 都是收敛的. 00 x 事实上，对（4.5）式施行配方手续，易知 ;)(2121CxxCxkkk10以上两式相除得 .211CxCxCxCxkkkk据此反复递推有 .20011kCxCxCxCxkk（4.6）记 ,00Cx

6、Cxq.)(2121CxxCxkkk11.1222kkqqCCxk 对任意 ，00 x总有 ，1q时 ，Cxk723805.104723805.103723837.102750000.101100kxk计算结果6表7 解解取初值 ，对100 x 按（4.5）式迭代3次115C便得到精度为 的结果610 例例8 8 求 . 115整理（4.6）式，得 故由上式推知，即迭代过程恒收敛. k当（见表7-6). .20011kCxCxCxCxkk（4.6）).(211kkkxCxx（4.5）12 由于公式（4.5）对任意初值 均收敛，并且收敛的速度很快，因此可取确定的初值,如 编成通用程序. 00 x

7、10 x).(211kkkxCxx（4.5）13 7.4.3 简化牛顿法与牛顿下山法简化牛顿法与牛顿下山法 牛顿法的优点是收敛快，缺点一是每步迭代要计算 及 ，计算量较大且有时 计算较困难，)(kxf)(kxf )(kxf 为克服这两个缺点，通常可用下述方法. （1 1） 简化牛顿法，简化牛顿法，.,)(101CxCfxxkkk，（4.7）迭代函数 ).()(xCfxx 二是初始近似 只在根 附近才能保证收敛，如0 x*x0 x给的不合适可能不收敛. 其迭代公式为 也称平行弦法.14 若在根 附近成立 ，即取*x1)(1)(xfCx,2)(0 xfC则迭代法（4.7）局部收敛. 在（4.7）中

8、取 ，则称为简化牛顿法简化牛顿法，)(10 xfC这类方法计算量省，但只有线性收敛， 其几何意义是用平行弦与 轴交点作为 的近似. x*x 如图7-4所示. 图7-4即 )()(01xfxfxxkkk.,1 ,0)(1CxCfxxkkk（4.7）.,1 ,0)(1CxCfxxkkk（4.7）15 （2 2） 牛顿下山法牛顿下山法. . 牛顿法收敛性依赖初值 的选取. 0 x 如果 偏离所求根 较远，则牛顿法可能发散.0 x*x 例如，用牛顿法求方程 .013 xx（4.8）在 附近的一个根 . 5.1x*x 设取迭代初值 ，用牛顿法公式 5.10 x131231kkkkkxxxxx（4.9）计

9、算得 16.32472.1,32520.1,34783.1321xxx迭代3次得到的结果 有6位有效数字. 3x 但如果改用 作为迭代初值，则依牛顿法公式（4.9）迭代一次得 6.00 x.9.171x这个结果反而比 更偏离了所求的根 . 6.00 x32472.0* x 为了防止迭代发散，对迭代过程再附加一项要求，即具有单调性： .)()(1kkxfxf（4.10）满足这项要求的算法称下山法下山法. 131231kkkkkxxxxx（4.9）17 将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度. 将牛顿法的计算结果 )()(1kkkkxfxfxx与前

10、一步的近似值 适当加权平均作为新的改进值 kx,)1(11kkkxxx（4.11）其中 称为下山因子，)0(),1 ,0()()(1kxfxfxxkkkk（4.12）(4.12)称为牛顿下山法牛顿下山法. （4.11）即为 18 选择下山因子时从 开始，逐次将 减半进行试算，1 若用此法解方程（4.8），当 时由（4.9）求得6.00 x直到能使下降条件（4.10）成立为止. ，它不满足条件（4.10）.9.171x 通过 逐次取半进行试算，当 时可求得32/1,140625. 11x此时有 ，656643.0)(1xf显然 . )()(01xfxf384.1)(0 xf而 由 计算 时 ,

11、均能使条件（4.10）成立. 计算结果如下 ： 1x,32xx1.)()(1kkxfxf（4.10）131231kkkkkxxxxx（4.9）.013 xx（4.8）.)()(1kkxfxf（4.10）.)()(1kkxfxf（4.10）19;1866.0)(,36181.122xfx 即为 的近似. 4x*x则可得到 ，从而使 收敛.0)(limkkxfkx一般情况只要能使条件（4.10）成立，;00667.0)(,32628.133xfx.0000086.0)(,32472.144xfx.)()(1kkxfxf（4.10）20 7.4.4 重根情形重根情形 设 ，整数 ，)(*)()(xg

12、xxxfm0*)(,2xgm则 为方程 的 重根，*x0)(xfm.0*)(,0*)(*)(*)()1(xfxfxfxfmm只要 仍可用牛顿法（4.2）计算，此时迭代函数 0)(kxf)()()(xfxfxx的导数为 ，011mx*)(此时有 且 ，所以牛顿法求重根只是线性收敛. 1*)( x),1 ,0()()(1kxfxfxxkkkk（4.2）21,)()()(xfxfmxx则 . 0*)( x),1 ,0()()(1kxfxfmxxkkkk（4.13）求 重根，则具有2阶收敛，但要知道 的重数 . mm*x 构造求重根的迭代法，还可令 ，)(/)()(xfxfx若 是 的 重根，则 *x

13、0)(xfm,)(*)()()(*)()(xgxxxmgxgxxx若取 用迭代法 22)()()(xxxx从而可构造迭代法 ),1 ,0()()()()()(21 kxfxfxfxfxfxxkkkkkkk（4.14）它是2阶收敛的. 故 是 的单根. *x0)(x对它用牛顿法，其迭代函数为 .)()()()()(2xfxfxfxfxfx 23 例例9 9方程 的根 是二重根，04424xx2* x 解解 （1） 牛顿法 .42844423241kkkkkkkkkxxxxxxxxx用上述三种方法求根. 先求出三种方法的迭代公式： （2） 用（4.13）式 .22,221kkkkxxxxm （3）

14、 用（4.14）式 .2)2(221kkkkkxxxxx取初值 ，计算结果如表7-7. 5.10 x),1 ,0()()(1kxfxfmxxkkkk（4.13）),1 ,0()()()()()(21 kxfxfxfxfxfxxkkkkkkk,44)(24xxxf24414213562141421356214254976191341421143814142156861436607143124117647061416666667145833333311321.xxxxkk方法（3）方法（2）方法（1）三种方法数值结果7表7 从结果看出，经过三步计算，方法（2）及（3）均达到10位有效数字，而由于牛

15、顿法只有线性收敛，所以要达到同样精度需迭代30次. 257.5 弦截法与抛物线法弦截法与抛物线法 当函数 比较复杂时，计算 往往较困难，)( xf)(xf 值 的计算. )(kxf 为此可以利用已求函数值 来回避导数),(),(1kkxfxf还要算 .)(kxf 用牛顿法求方程 的根，每步除计算 外，)(kxf0)(xf26 7.5.1 弦截法弦截法 设 是 的近似根，1,kkxx0)(xf利用 )(),(1kkxfxf构造一次插值多项式 ，并用 的根作为新的近似根 . )(1xp0)(1xp1kx，)()()()(kkkkkkxxxxxfxfxfxp111（5.1） 由于 因此有 ，)()(

16、)()(111kkkkkkkxxxfxfxfxx（5.2）27（5.2）可以看作将牛顿公式 )()(1kkkkxfxfxx中的导数 用差商 取代的结果.)(kxf 11)(kkkkxxxfxf 接着讨论几何意义. 曲线 上横坐标为 的点分别记为 ，)( xfy 1,kkxx1,kkPP则弦线 的斜率等于差商值 , 1kkPP11)(kkkkxxxfxf28).()()(11kkkkkkxxxxxfxfxfy按（5.2)式求得的 实际上是弦线 与 轴交点的横坐标. 1kx1kkPPx表7-5这种算法因此而称为弦截法弦截法. 其方程为).()()()(111kkkkkkkxxxfxfxfxx（5.

17、2）29 而弦截法（5.2），在求 时要用到前面两步的结果 ，1kx1,kkxx 弦截法与切线法（牛顿法）都是线性化方法，但两者有本质的区别. 切线法在计算 时只用到前一步的值 .kx1kx因此使用这种方法必须先给出两个开始值 .01, xx 例例1010.01e)(xxxf 解解56714.0456709.0356532.026.015.00kxk计算结果8表7 用弦截法解方程 设取 作为6.0,5.010 xx开始值，用弦截法求得的结果见表7-8，).()()()(111kkkkkkkxxxfxfxfxx（5.2）30 实际上，弦截法具有超线性的收敛性. 比较例7牛顿法的计算结果可以看出，

18、弦截法的收敛速度也是相当快的. 定理定理6 6这里 是方程 的正根. 618.1251p012假设 在根 的邻域 内)(xf*x*:xx且对任意 有 ，x0)( xf,10 xx具有二阶连续导数，那么当邻域充分小时，又初值阶收敛到根 . *xp弦截法（5.2）将按).()()()(111kkkkkkkxxxfxfxfxx（5.2）31 7.5.2 抛物线法抛物线法 设已知方程 的三个近似根 ，21,kkkxxx0)(xf 几何上，这种方法的基本思想是用抛物线与 轴的交点 作为所求根 的近似位置（图7-6). 1kxx*x图7-6以这三点为节点构造二次插值多项式 ,)(2xp 的一个零点 作为新

19、的近似根，)(2xp1kx并适当选取 这样确定的迭代过程称为抛抛物线法物线法，也称密勒（密勒（Mller）法）法.32插值多项式 )(,)(,)()(12112kkkkkkkkkxxxxxxxfxxxxfxfxp有两个零点： ,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）式中 ).(,1211kkkkkkkxxxxxfxxf 问题是该如何确定 .1kx 假定在 三个近似根中， 更接近所求的根 .21,kkkxxxkx*x33 为了保证精度，选（5.3）中较接近 的一个值作为新的近似根 . kx1kx 为此，只要取根式前的符号与 的符号相同. 例例1111.01e)(xxxf

20、用抛物线法求解方程 解解设用表7-8的前三个值 56532.0,6.0,5.0210 xxx作为开始值，计算得 ,093271.0)(,175639.0)(10 xfxf,005031.0)(2xf,68910.2,01xxf,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）567140456709035653202601500.kxk计算结果8表734故 .75694.2)(,1201212xxxxxfxxf代入（5.3）式求得 .56714.0,)(4)(201222223xxxfxfxfxx,83373.2,12xxf.21418.2,012xxxf 以上计算表明，抛物线

21、法比弦截法收敛得更快. 在一定条件下可以证明，对于抛物线法，迭代误差有下列渐近关系式 .*)(6*)(42.01840.1xfxfeekk ,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）35可见抛物线法也是超线性收敛的，其收敛的阶 ,840.1p 从（5.3）看到，即使 均为实数， 也可以是复数，所以抛物线法适用于求多项式的实根和复根. 21,kkkxxx1kx收敛速度比弦截法更接近于牛顿法. ,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）367.6 解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法 考虑方程组 ,0),(,0),(111nnnxxf

22、xxf（6.1）其中 均为 的多元函数. nff,1),(1nxx 用向量记号记 , T1T1R),(,),(nnnffxxFx0.)(xF（6.2）(6.1）就可写成 37 非线性方程组求根问题是前面介绍的方程（即 ）求根的直接推广.1n 若已给出方程（6.2）的一个近似根 ，T1),()()()(knkkxxx将函数 的分量 在 用多元函数)( xF),)(nifi1x)(kx 的非线性函数时，称方程组（6.1）为非线非线性方程组性方程组. ), 1(nixi 当 ，且 中至少有一个是自变量2n), 1(nifi 只要把前面介绍的单变量函数 看成向量函数)( xf，)( xF则可将单变量方程求根方法推广到方程组（6.2）. 泰勒展开，并取其线性部分，则可表示为 .0)(xF（6.2）38令上式右端为零，得到线性方程组 ),()()()()(kkkxFxxx