第2章 非线性方程(组)的数值解法2

1、第第 2 章章基础教学部数学教研室基础教学部数学教研室 彭彭 晓晓 华华2.4 迭代收敛的加速法迭代收敛的加速法加快收敛速度，减少计算量，是数值计算的重要课题加快收敛速度，减少计算量，是数值计算的重要课题 构造一个更快收敛构造一个更快收敛kx( )xx0 x埃特金埃特金加速方法可用于加快一已知收敛序列加速方法可用于加快一已知收敛序列 的收敛速度，的收敛速度， kx的序列的序列kx设设 是一个线性收敛的序列，收敛于方程是一个线性收敛的序列，收敛于方程 的根的根 .kxx 第一次校正：第一次校正： 设设 是根是根 的某个预测值，的某个预测值， x迭代公式可使迭代公式可使 校正为校正为10()xx0

2、 x由微分中值定理由微分中值定理,有有 100()()( )()xxxxxx 2.4.1埃特金加速法埃特金加速法 其方法是通过收敛较慢的已知序列其方法是通过收敛较慢的已知序列由于在较小的有根区间内，由于在较小的有根区间内， 的变化不大，取的变化不大，取 则有则有( )x0 x其中其中 介于介于 与与 之间之间.( )xL10()xxL xx 第二次校正：第二次校正： x对对 值再校正一次值再校正一次21()xx1x由于由于 21()xxL xxL将其与将其与 上面的式子联立，消去 得 .0121xxxxxxxx数值分析数值分析解非线性方程（组）解非线性方程（组）解出解出 ，得到，得到一次埃特金

3、加速：一次埃特金加速： x对于初始近似值对于初始近似值 ，首先计算，首先计算 10()xx0 x然后，可用上式右端作为然后，可用上式右端作为 的新近似值，记做的新近似值，记做 1x再计算再计算 .22021100210210()22x xxxxxxxxxxxx21()xxx这就是一次埃特金加速过程这就是一次埃特金加速过程.数值分析数值分析解非线性方程（组）解非线性方程（组）埃特金加速算法：埃特金加速算法： 对于更一般的情形对于更一般的情形 ，首先由，首先由 计算计算 12,kkxxkx由此得到埃特金加速迭代公式：由此得到埃特金加速迭代公式：然后作一次加速然后作一次加速 .12121121()(

4、)(),0,1,2kkkkkkkkkkkxxxxxxxxkxxx21121()2kkkkkkkxxxxxxx可以证明，可以证明，*1*lim0kkkxxxx它表明序列它表明序列 的收敛速度比的收敛速度比 的收敛速度快的收敛速度快.，kxkx【注注】 当迭代过程收敛很慢时，一般可当迭代过程收敛很慢时，一般可用埃特金法加速，但有时埃特金法加速可用埃特金法加速，但有时埃特金法加速可能失败，例如当能失败，例如当 起伏很大、初值起伏很大、初值 与根与根 有较大的距离时，埃特金加速就有较大的距离时，埃特金加速就可能失败可能失败.0 x( )xx2.4.2 斯蒂芬森迭代法斯蒂芬森迭代法(Steffensen

5、s Method)：如果把埃特金加速技巧与不动点迭代结合如果把埃特金加速技巧与不动点迭代结合，则可得到如下的斯蒂芬森迭代法则可得到如下的斯蒂芬森迭代法 (),()kkkkyxzy1(),0,1,kkxxk21(),0,1,2kkkkkkkyxxxkzyx实际上公式（实际上公式（2.18）是将不动点迭代法计算两步合）是将不动点迭代法计算两步合并成一步得到的，可将它写成另一种不动点迭代并成一步得到的，可将它写成另一种不动点迭代2 ( )( )( ( )2 ( )xxxxxxx 其中其中对不动点迭代（对不动点迭代（2.19）有以下局部收敛性定理）有以下局部收敛性定理.（2.18）（2.19）（2.2

6、0）【定理定理6】若若 为上式定义的迭代函数为上式定义的迭代函数 的不动点，则的不动点，则 *x( )x则则 为为 的不动点的不动点.反之，若反之，若 为为 的不动点，设的不动点，设 *x( )x*x( )x( )x存在，存在， 则则 是是 的不动点，且该斯蒂芬森迭的不动点，且该斯蒂芬森迭代法是代法是2阶收敛的阶收敛的. *()1x*x( )x例例2-11用斯蒂芬森迭代法求解方程用斯蒂芬森迭代法求解方程 3( )10f xxx 解例解例2-7中已指出迭代中已指出迭代 是发散的是发散的.311kkxx现在利用斯蒂芬森迭代计算，仍取现在利用斯蒂芬森迭代计算，仍取 计算结计算结果见表果见表2-6.

7、3( )1xx表表2-6例例2-11迭代值迭代值计算表明它是收敛的，这说明即使原不动计算表明它是收敛的，这说明即使原不动点迭代法不收敛，用斯蒂芬森迭代法仍可点迭代法不收敛，用斯蒂芬森迭代法仍可能收敛能收敛.至于原来已收敛的不动点迭代法，至于原来已收敛的不动点迭代法，由定理由定理6可知它可达到可知它可达到2阶收敛阶收敛.更进一步还更进一步还可知若原迭代法为可知若原迭代法为 阶收敛，则斯蒂芬森阶收敛，则斯蒂芬森迭代法为迭代法为 阶收敛阶收敛.1.324721.324725 51.327141.327141.325181.325181.324801.324804 41.444351.444351.3

8、47101.347101.328951.328953 32.317282.317281.491401.491401.355651.355652 25.238885.238881.840921.840921.416291.416291 112.396612.39662.375002.375001.51.50 0kykzkxkp1p 例例2-12用斯蒂芬森迭代法求方程用斯蒂芬森迭代法求方程01)(xxexf在在 附近的一个根附近的一个根.0.5x 在例在例7中，迭代过程中，迭代过程 1(0 ,1,)kxkxek解方程的精确解为解方程的精确解为0.56714392.x 取初值取初值 ，迭代计算到，迭

9、代计算到 .00 .5x1 80 .5 6 7 1 4 0 7x利用斯蒂芬森迭代计算，结果见表利用斯蒂芬森迭代计算，结果见表2-7.由表由表2-7可知，经可知，经过过2次迭代次迭代.且且 *51 80 .41 0 xx1 80 .5 6 7 1 4 3 3 1x*720 .21 0 xx加速效果较好加速效果较好.数值分析数值分析解非线性方程（组）解非线性方程（组）kkxkykz0.5671433120.567297860.566870790.5676238810.545239210.606530660.50表2-7例2-12迭代值 运行结果表明迭代成功，达到精度要求运行结果表明迭代成功，达到精

10、度要求.迭代终止条迭代终止条件为：前后两次迭代结果之差是否满足精度，共迭代计件为：前后两次迭代结果之差是否满足精度，共迭代计算算3次；对比例次；对比例2-8，利用不动点迭代计算了，利用不动点迭代计算了18次；显然次；显然Steffensen方法收敛更快方法收敛更快. 思考：在埃特金加速或斯蒂芬森加速法的基础上思考：在埃特金加速或斯蒂芬森加速法的基础上是否能找到更好的收敛速度加速法？是否能找到更好的收敛速度加速法？ 不动点迭代一般理论告诉我们，构造不动点迭代一般理论告诉我们，构造好的迭代函数可使收敛速度提高好的迭代函数可使收敛速度提高.然而迭然而迭代函数的构造方法又各不相同、方法多代函数的构造方

11、法又各不相同、方法多样样.能否找到一种迭代方法能否找到一种迭代方法, ,既结构简单既结构简单, ,收敛速度快收敛速度快, ,又不存在发散的问题？牛顿又不存在发散的问题？牛顿迭代法就是这样一种方法。迭代法就是这样一种方法。2.5.1 牛顿迭代法牛顿迭代法 基本思想是：基本思想是：将非线性函数将非线性函数f f( (x x) )逐步线性化逐步线性化, , 从而将非线性方程从而将非线性方程f f( (x x)=0)=0近似地转化为线性方程近似地转化为线性方程求解。求解。即把非线性方程逐步线性化即把非线性方程逐步线性化.方程方程 的根的根 ，几何意义是曲线，几何意义是曲线与与 轴的交点轴的交点.求曲线

12、与求曲线与 轴的交点没有普遍的公式，轴的交点没有普遍的公式，但直线与但直线与 轴的交点容易计算。轴的交点容易计算。0)(xf*xxxx( )yf x( )yf x( )0f x 基本方法：基本方法：用函数用函数的切线近似曲线的切线近似曲线 ( )yf x，从而用切线方程的根逐步代替从而用切线方程的根逐步代替的根的根。牛顿迭代法的原理：牛顿迭代法的原理： 2)(21)()()(kkkkkxxxfxxxfxfxf忽略高次项忽略高次项, ,用其线性部分作为函数用其线性部分作为函数f(x)f(x)的近似，的近似， )()()(kkkxxxfxfxf 设设 的根的根 , ,则有则有 , ,即即 0)(x

13、f*x0)(*xf0)()(*kkkxxxfxf)()(*kkkxfxfxx)()(1kkkkxfxfxx)2,1 ,0(k将右端取为将右端取为 , ,即即 是比是比 更接近于更接近于 的近似值的近似值 1kx1kxkx*x 对于方程对于方程 , ,设其近似根为设其近似根为 , ,函数函数 可在可在 附近作泰勒展开附近作泰勒展开 0)(xfkxkx( )f x线性化方法：线性化方法：xyx*x00100()()fxxxfxx 1x 2000()()()yf xfxxx1211()()fxxxfx牛顿法也称为切线法牛顿法也称为切线法 牛顿迭代法的牛顿迭代法的几何解释几何解释111( )( )()

14、yf xfxxx（1）（2）()()()kkkyf xfxxx1()()kkkkfxxxfx17)(/ )()(xfxfxx( ),xx)(1kkxx)(x牛顿迭代法的收敛性：牛顿迭代法的收敛性：，则有，则有从而牛顿迭代就是不动点迭代从而牛顿迭代就是不动点迭代因此可以通过考察因此可以通过考察迭代法的收敛性及收敛速度迭代法的收敛性及收敛速度. .如果取如果取的性质，来讨论的性质，来讨论定理定理7 7 设设 是方程是方程 的单根的单根, , 且且f f( (x x) )在在 的某邻域内有连续的二阶导数的某邻域内有连续的二阶导数, , 则牛顿法在则牛顿法在 附近附近局部收敛局部收敛, , 且至少且至

15、少二阶收敛二阶收敛, , 有有 *x0)(xf*x*x*1122*()limlim2()kkkkkkxxfxefxexx 1 1、局部收敛：局部收敛：若在若在x的某个邻域的某个邻域内的每一点，迭代均收敛，称这种形式的收敛为内的每一点，迭代均收敛，称这种形式的收敛为局部收敛局部收敛.:Rxx【定理定理4】 （局部收敛性）（局部收敛性）设设 )(x在在x的邻近连续，的邻近连续，1)(x且且则迭代过程则迭代过程)(1kkxx在在x邻近具有局部收敛性邻近具有局部收敛性. .复习：复习：定义定义 （收敛阶）（收敛阶）：设迭代过程：设迭代过程 收敛于收敛于 的的根根 , ,记迭代误差记迭代误差若存在常数若

16、存在常数p p（p1p1）和和c c（c0c0），），使使 )(1kkxx)(xx*xkkxxe*ceepkkk1lim则称序列则称序列 是是p p 阶收敛的阶收敛的, ,c c 称渐近误差常数。称渐近误差常数。 kx2 2、迭代法的收敛速度、迭代法的收敛速度特别地特别地, , 时称为线性收敛时称为线性收敛, , 时称为平方收敛。时称为平方收敛。 时称为超线性收敛。时称为超线性收敛。 1p 2p 1p 3 3、定理定理5 5 设迭代过程设迭代过程 , , 若若 在所求根在所求根 的邻域连续且的邻域连续且 则迭代过程在则迭代过程在 邻域是邻域是 阶收敛阶收敛的。的。)(1kkxx)()(xp*x

17、0)(, 0)()()(*)(*) 1(* xxxxpp*xp21)(xf)(/ )()(xfxfxx)(1kkxx2)(/)()()(xfxfxfx 223( )( )( )( )( ) /( )2 ( )( ) /( )xf x fxfx fxfxf x fxfx*x0)(xf()0,f x0)(xf0)(/ )()(, 0)( xfxfxx.定理定理7的的证明：证明：（1） 对于对于，取，取则牛顿迭代过程为则牛顿迭代过程为注意到注意到由于由于是是的单根，即的单根，即所以有所以有由由定理定理4知，迭代过程是局部收敛的知，迭代过程是局部收敛的.且由且由定理定理5知，知，迭代过程在点迭代过程在

18、点*x邻近是邻近是2阶收敛的阶收敛的.22)(x*xkxx 22( *)()( *)( *)(*)(*)2!1( *)( *)/( *)(*) .2kkkkxxxxxxxxxfxfxxx1(),kkxx)(*xx21)()(2/ )( xxxfxfxxkk21)(2/ )( xxxfxfxxkk（2） 将将在在处作泰勒展开并代入处作泰勒展开并代入，有，有注意到注意到，得到，得到因此有因此有*1122*()limlim2()kkkkkkxxfxefxexx 证毕证毕 ?0)(0 xf 1000)()(xxfxfx ?01 xx 开 始 输 入 x0,N 1 k k+ 1 k x1 x0 输 出

19、x1 输 出 迭 代 失 败 标 志 结 束 n k N ? n n y 输 出 奇 异 标 志 y y 牛顿迭代法算法实现牛顿迭代法算法实现数值分析数值分析例2-13 用求 x=e-x的根,=10-4解：因 f (x)= x ex 1 , f (x)=ex ( x+1) 建立迭代公式nxnnnxxnnnxexxxeexxxnnn 1)1 (11取x0=0.5,逐次计算得 x1=0.57102, x2=0.56716， x3=0.56714与例2-8相比，牛顿法的收敛速度快。的根的根, ,要求要求20 xxe51| 10kkxx1ln(2)kkxx迭代格式一：迭代格式一：迭代格式二：迭代格式二

20、：121kkxkkkxxexxe取初值取初值x x0 00.00.0, ,计算如下：计算如下：对迭代格式一对迭代格式一: : the iterative number is 27, the numerical solution is 0.442852706对迭代格式二对迭代格式二: : the iterative number is 3, the numerical solution is 0.442854401例例2-12-14 4 用用NewtonNewton法求方程法求方程26例2-13 用牛顿迭代法计算22( )02f xxaa其中迭代公式得及由Newtonxxf2)(21212()0

21、,1,.22nnnnnnxxxxnxx012331.51.41666667,1.4142156861.4142135622xxxxx取，则，。与的精确值相比， 是已有十位有效数字的的近似值。解：*x0 x*x【注】【注】 牛顿迭代过程在牛顿迭代过程在邻近，否则，可能不收敛邻近，否则，可能不收敛. .如下图所示如下图所示最好选在最好选在邻近具有平方收敛速度邻近具有平方收敛速度. .牛顿迭代法的优点：快速收敛性，算法简单、容易实现牛顿迭代法的优点：快速收敛性，算法简单、容易实现. .牛顿迭代法的缺点：牛顿迭代法的缺点：(2)(2)每步迭代要计算每步迭代要计算)(kxf及及)(kxf 计算量较大且有

22、时计算量较大且有时计算较困难。计算较困难。 )(kxf （1 1）因为局部收敛性，所以初值）因为局部收敛性，所以初值Newton法的收敛性依赖于法的收敛性依赖于x0 的选取。的选取。x*x0 x0 x0 为克服这两个缺点，通常可用下述方法为克服这两个缺点，通常可用下述方法.2.5.2 2.5.2 简化牛顿法与简化牛顿法与牛顿下山法牛顿下山法 0( )2Cfx*x1 1、简化牛顿法：、简化牛顿法：1(),kkkxxCf x( )( )xxCf x( )1( )1xCfx简化牛顿法也称简化牛顿法也称平行弦法平行弦法，其迭代公式为，其迭代公式为迭代函数迭代函数即取即取0,C , 1 , 0k若若 在

23、根在根附近成立，则附近成立，则迭代法（迭代法（2.222.22）局部收敛）局部收敛. .（2.222.22）)(10 xfCx*x在（在（2.222.22）中取）中取这类方法计算量省，但只有线性收敛，其几何意义是这类方法计算量省，但只有线性收敛，其几何意义是 用平行弦与用平行弦与 轴交点交点作为 的近似，如图的近似，如图2-6所示所示.，则称为，则称为简化牛顿法简化牛顿法，31 图图2-6 简化牛顿法几何示意简化牛顿法几何示意32013 xx5 . 1x*x5 . 10 x131231kkkkkxxxxx34783. 11x32520. 12x32472. 13x3x6 . 00 x9 .17

24、1x6 . 00 x32472. 1*x例例2-12-14 4在在附近的一个根附近的一个根.解解 1 1） 设取迭代初值设取迭代初值，牛顿法公式为，牛顿法公式为迭代迭代3 3次得到的结果次得到的结果有有6 6位有效数字位有效数字. .作为迭代初值，则依牛顿法公式（作为迭代初值，则依牛顿法公式（2.232.23）迭代一次得）迭代一次得. .这个结果反而比这个结果反而比更偏离了所求的根更偏离了所求的根计算得计算得2 2） 如果改用如果改用用牛顿法求解方程用牛顿法求解方程33通常通常, ,牛顿迭代法的收敛性依赖于初始值的选取牛顿迭代法的收敛性依赖于初始值的选取, ,如果初始值如果初始值偏离所求的根比

25、较远偏离所求的根比较远, ,则牛顿法可能发散。为了防止迭代发散则牛顿法可能发散。为了防止迭代发散, ,我们对牛顿迭代法的迭代过程再附加一项要求我们对牛顿迭代法的迭代过程再附加一项要求, ,即具有单调性即具有单调性)()(1kkxfxf满足这项要求的算法称下山法。满足这项要求的算法称下山法。2、牛顿下山法、牛顿下山法牛顿下山法原理：牛顿下山法原理：将牛顿迭代法与下山法结合起来将牛顿迭代法与下山法结合起来使用使用, ,即在下山法保证函数值下降的前提下即在下山法保证函数值下降的前提下, ,用牛顿用牛顿迭代法加快收敛速度。把这一算法称为牛顿下山法。迭代法加快收敛速度。把这一算法称为牛顿下山法。即即)(

26、)(1kkkkxfxfxx其中其中(01)(01)为下山因子为下山因子 1()()kkkkf xxxfx11(1)kkkxxx牛顿法计算的结果：牛顿法计算的结果：与前一步的近似值与前一步的近似值x xk k适当加权平均作为新的改进值适当加权平均作为新的改进值 下山因子的选择是个逐步探索的过程，设从下山因子的选择是个逐步探索的过程，设从=1开始反复将开始反复将减半进行试算减半进行试算, 即逐次取即逐次取为为,21,21, 12)()(1kkxfxf下山因子的选择：下山因子的选择：从中挑选下山因子，直至找到其中某个从中挑选下山因子，直至找到其中某个使单调性条件使单调性条件成立，则称成立，则称“下山

27、成功下山成功”，否则，否则“下山失败下山失败”，这时需另选初值重算。这时需另选初值重算。363211140625. 11x656643. 0)(1xf384. 1)(0 xf)()(01xfxf1x,32xx136181. 12x1866. 0)(2xf32628. 13x00667. 0)(3xf32472. 14x0000086. 0)(4xf4x*x例例1414中取中取逐次取半进行计算，逐次取半进行计算，时可求得时可求得，此时，此时而而，显然，显然由由计算计算时时均能使下降条件成立，计算结果如下：均能使下降条件成立，计算结果如下：，即为即为的近似的近似. .通过通过当当1x由由计算计算6

28、 . 00 x，它不满足下降条件。，它不满足下降条件。37lim()0,kkf xkx1一般情况只要使下降条件成立，则可一般情况只要使下降条件成立，则可从而使从而使牛顿下山法是目前方程求根的一个牛顿下山法是目前方程求根的一个速度虽然没有牛顿法快，但它对初速度虽然没有牛顿法快，但它对初值的选取范围放宽很多值的选取范围放宽很多. .收敛收敛. .有效方法，当有效方法，当时，时，得到得到它的收敛它的收敛382.5.3 割线法割线法)(kxf )(kxf )(kxf )(xf牛顿迭代法的收敛速度很快，但是每迭代一次，都要计算牛顿迭代法的收敛速度很快，但是每迭代一次，都要计算的值，如果出现的值，如果出现

29、接近于零，可能接近于零，可能不为零，但当不为零，但当时，导数的计算工作量也较大时，导数的计算工作量也较大. .通常希望避免计算导数，通常希望避免计算导数，而导出一个类似牛顿迭代的公式而导出一个类似牛顿迭代的公式. .导致溢出导致溢出. .即使即使较复杂较复杂1kxkkxx,1割线法（割线法（Secant MethodSecant Method）原理）原理：时，由前面算出的时，由前面算出的两点的割线斜率代替导数，可得两点的割线斜率代替导数，可得在牛顿迭代中，为避免计算导数，用经过两点的割线在牛顿迭代中，为避免计算导数，用经过两点的割线来代替切线，即求来代替切线，即求39)(/ )(1kkkkxf

30、xfxx)()()()(111kkkkkkkxxxfxfxfxx代入牛顿迭代公式代入牛顿迭代公式中，有中，有割线法迭代公式割线法迭代公式. )(xfy )(,(),(,(111kkkkkkxfxpxfxp)() 1()()(1kkkkkkxxxxxfxfxfy0y1,kx其割线方程为其割线方程为，割线与割线与的交点记为的交点记为则得到割线法迭代公式则得到割线法迭代公式. .割线法又称为弦截法、割线法又称为弦截法、弦线法弦线法. .过两点过两点割线法的几何意义割线法的几何意义：迭代公式的导数是曲线迭代公式的导数是曲线的割线（弦线）的斜率，的割线（弦线）的斜率，11)()()(kkkkkxxxfx

31、fxf40图图2-7 割线法几何示意割线法几何示意41)(xf*x0)(* xf10,xx*x618. 1*618. 0*1)(/ )(xxxfxfxxkk kkxx,11kk618. 1p如果如果在零点在零点附近有附近有，且初始值，且初始值充分接近充分接近，则割线法的迭代过程是收敛的，其收敛速度为，则割线法的迭代过程是收敛的，其收敛速度为其中其中分别是第分别是第次和第次和第【注注】 割线法具有超线性收敛速度，其收敛阶为割线法具有超线性收敛速度，其收敛阶为连续的二阶导数，连续的二阶导数，次迭代近似值次迭代近似值. .割线法的收敛性：割线法的收敛性：4205 . 0sinxx)()sin(sin

32、)(5 . 0sin1111kkkkkkkkkkxxxxxxxxxx用割线法求方程用割线法求方程解解 割线法迭代公式为割线法迭代公式为在在1.51.5附近的一个根附近的一个根. .6 . 1, 4 . 110 xx,4919426. 12 . 0)9854497. 09995736. 0(2 . 09995736. 01 . 16 . 1)4 . 16 . 1 ()4 . 1sin6 . 1(sin)4 . 16 . 1 (5 . 06 . 1sin6 . 16 . 12x49730. 1,49702. 143xx取初始值取初始值迭代计算，得到迭代计算，得到.例例2-12-15 5 4301x

33、xe6 . 0, 5 . 010 xx56714. 0,56709. 0,56532. 0432xxx用割线法求方程用割线法求方程在在0.50.5附近附近. .用割线法迭代计算，得到用割线法迭代计算，得到比较比较例例2-12-12 2牛顿牛顿法的计算结果可以看出，法的计算结果可以看出，割线法的收敛速度也是相当快的割线法的收敛速度也是相当快的. .解解 取初始值取初始值的根的根例例2-12-16 6 44)()()(*xgxxxfm0)(*xg*x0)(xf2m*(1)*()()()0,mf xfxfx0)(*)(xfm0)(kxf)()()(xfxfxx011)(*mx1)(* x2.5.4

34、2.5.4 求重根的修正牛顿法求重根的修正牛顿法，整数，整数，则则为方程为方程的的重根，此时有重根，此时有只要只要仍可用牛顿法计算，此时迭代函数仍可用牛顿法计算，此时迭代函数的导数为的导数为且且，所以牛顿法求重根只是线性收敛，所以牛顿法求重根只是线性收敛. .设设m45)()()(xfxfmxx0)(* x)()(1kkkkxfxfmxx, 1 , 0km*xm一、一、求重根的修正牛顿法求重根的修正牛顿法1 1，则，则因此利用迭代法因此利用迭代法, ,求求重根，具有重根，具有2 2阶收敛阶收敛. .应用该方法的应用该方法的的重数的重数. .选取选取 （2.282.28）前提是：要知道前提是：要

35、知道46)(/ )()(xfxfx*x0)(xfm)()()()()()(*xgxxxmgxgxxx二、二、求重根的修正牛顿法求重根的修正牛顿法2 2若若是是的的重根，则重根，则，（，（2.292.29）构造求重根的迭代法，还可令构造求重根的迭代法，还可令*x0)(x)()()()()()()()(2xfxfxfxfxfxxxxx )()()()()(21kkkkkkkxfxfxfxfxfxx , 1 , 0k故故是是的单根的单根. .对它用牛顿法，其迭代函数为对它用牛顿法，其迭代函数为从而可构造迭代法从而可构造迭代法，它是二阶收敛的它是二阶收敛的. .方法方法1）方法方法2）方法方法3）11

36、.4583333331.4166666671.41176470621.4366071431.4142156861.41421143831.4254976191.4142135621.414213562kkx1x2x3x表表2-8三种方法数值结果三种方法数值结果计算三步，方法计算三步，方法2）及方法）及方法3）均达到）均达到10位有效数字，而用位有效数字，而用牛顿法只有线性收敛，要达到同样精度需要迭代牛顿法只有线性收敛，要达到同样精度需要迭代30次次.48【注】【注】 求重根的修正牛顿法求重根的修正牛顿法1需要已知根的重数，需要已知根的重数，因此不实用因此不实用.求重根的修正牛顿法求重根的修正牛

37、顿法2需要求函数的二需要求函数的二阶导数，并且当所求根为单根时，不能改善本来已阶导数，并且当所求根为单根时，不能改善本来已经二次收敛的牛顿法经二次收敛的牛顿法.对于实际问题，往往事先并对于实际问题，往往事先并不知道所求根是否是重根，需要通过试算来判断，不知道所求根是否是重根，需要通过试算来判断，如当牛顿法收敛很慢时通常为重根如当牛顿法收敛很慢时通常为重根.小结：小结：)(/ )()(xfxfxx一、牛顿迭代法：一、牛顿迭代法：1 1、牛顿迭代函数：、牛顿迭代函数：2 2、牛顿迭代公式：、牛顿迭代公式：1()()kkkkfxxxfx3 3、牛顿迭代收敛性：、牛顿迭代收敛性：定理定理7 7 设设

38、是方程是方程 的单根的单根, , 且且f f( (x x) )在在 的某邻域内有连续的二阶导数的某邻域内有连续的二阶导数, , 则牛顿法在则牛顿法在 附近附近局部收敛局部收敛, , 且至少且至少二阶收敛二阶收敛, , 有有 *x0)(xf*x*x*1122*()limlim2()kkkkkkxxfxefxexx 0( )2Cfx*x1 1、简化牛顿法：、简化牛顿法：1(),kkkxxCf x( )( )xxCf x( )1( )1xCfx迭代公式：迭代公式：迭代函数：迭代函数：即取即取0,C , 1 , 0k若若 在根在根附近成立，则附近成立，则迭代法（迭代法（2.222.22）局部收敛）局部

39、收敛. .)(10 xfC在（在（2.222.22）中取）中取，则称为，则称为简化牛顿法简化牛顿法，二、简化牛顿法与牛顿下山法二、简化牛顿法与牛顿下山法5104424 xx2*xkkkkxxxx4221kkkkxxxx22212)2(221kkkkkxxxxx5 . 10 x例例1 17 7方程方程的根的根是二重根，用上述三种方法求根是二重根，用上述三种方法求根. .2 2） 用（用（2.282.28）式：）式：3 3） 用（用（2.292.29）式：）式：取初值取初值，计算结果如表，计算结果如表2-8.2-8.解解先求出三种方法的迭代公式先求出三种方法的迭代公式. .1 1） 牛顿法：牛顿法： 将牛顿迭代法与下山法结合起来使用将牛顿迭代法与下山法结合起来使用, ,即在下山即在下山法保证函数值下降的前提下法保证函数值下降的前提下, ,用牛顿迭代法加快收敛用牛顿迭代法加快收敛速度。把这一算法称为牛顿下山法。即速度。把这一算法称为牛顿下山法。即)()(1kkkkxfxfxx其中其中(01)(01)为下山因子为下山因子 1()()kkkkf xxxfx11(1)kkkxxx牛顿法计算的结果：牛顿法计算的结果：与前一步