级牛顿修正PPT课件

1、证明 先证f(x)=0有唯一解. 证Newton序列单调,有界,从而有极限.满满足足设设,0bax , 0)()(00 xfxf考虑由牛顿法得到的x1的特性,因为f(x)连续, 0)()( bfaf所以f(x)=0在a,b上至少有一个解,设为x*.又因为f (x)连续, 0)(, xfbax则f (x)在a,b上恒正或恒负,从而f(x)在a,b上严格单调上升或下降,f(x)=0在a,b上最多只有一个解.因此f(x)=0在a,b内有唯一解x*.(考虑x1与x0、x*的大小关系,进一步讨论f (x1)的符号.),)(! 2)()()(120*1000*xxfxfxfxx 得得另外,)()(0001

2、xfxfxx 比较以上两式,并考虑到 f(x0)与)(1 f 同号,得x1介于x0与x*, 0)()() 1 (00 xfxf)()2(xf 不变号.,)(! 2)()()()(020*10*00*xxfxxxfxfxf 首先由第1页/共17页f (x1)与 f (x0)同号(否则 f(x)=0不是有唯一解)，同时可得. 0)(1 fxf同理由0)(1 fxf得由牛顿法得到的x2必介于x1与x*之间，且f (x2)与f (x1)同号，由此得到的牛顿序列之间， (若, 0)()(00 xfxf则,01xx 若, 0)()(00 xfxf则10 xx )且则有,limbaxxkk 0kkx满足xk

3、+1介于xk与x*之间,从而,0baxkk 且 0kkx又单调、有界序列必有极限，设极限为,x并有界,是单调序列 *x,*x 证*xx 对,)()(1kkkkxfxfxx 两边取 k时的极限,得,)()(xfxfxx 由于, 0)( xf从而, 0)( xf又由f(x)=0在a,b上只有唯一解x*.得.*xx 即.lim*xxkk 最后,由定理7知xk二阶收敛于x*.#第2页/共17页例4用Newton法求解. 0cos xx解首先可以判断解在(0,1)内.xxxfcos)( 又又, 0) 1 (, 01) 0( ff在(0,1)上.0cos xf(恒正)(不变号)则Newton迭代序列单调二

4、阶收敛到0)( xf在(0,1)内的唯一根.*x10 x取取, Newton迭代的计算结果如下表 kkx)(kxf)(kxf 01459697694. 0841470984. 11750363867. 0018923073. 0681904952. 12739085133. 03000046454. 0673632544. 173911289. 00, 0sin1)( xxf表4-2优点收敛速度快 .缺点1. 需要每次计算导数值 f (x)，如果函数f (x)比较复杂，使用牛顿公式不方便 .2. 对初值x0要求苛刻.第3页/共17页5.3 Newton切线法的修正算法1.简化牛顿切线法 思想方

5、法 )()(1kkkkxfxfxx 用常数c 代替牛顿切线法中的 f (xk)简化牛顿切线法公式cxfxxkkk)(1 至少是线性收敛，收敛性当取c = f (xk)时，是二阶收敛.在初始值x0，取c = f (x0) ,c的选取方法在xk附近的一些点上可取c = f (xk) .这样即保证了计算简单又使收敛较快，在某些点上接近平方收敛.2.Newton下山法(修正的Newton法)第4页/共17页用牛顿切线法求方程x 3-x-1= 0在x=1.5附近的一个根 .解 取迭代初值x0=1.5，用牛顿公式 计算结果如表4-3所示 .012341.51.347831.325201.324721.32

6、472 kkx表4-3其中x3=1.32472 的每一位数字都是有效数字. 例5131231 kkkkkxxxxx如果改用 x0=0.6作为初值，迭代一次得x1=17.9, 这个结果反而比x0更偏离了所求的根 x*. 为了防止迭代发散，对迭代过程附加一基本要求,即保证函数值单调下降)()(1kkxfxf ，满足这项要求的算法称下山法.第5页/共17页(1) 下山序列的定义若视|f(x)|为f(x)在x点的高度,则*x是山谷最低点.定义 若序列kx满足)()(1kkxfxf ，称kx是f(x)的一个下山序列.下山序列的极限点,不一定是f(x)0的解.方程f(x)0的解 满足：)(min)(0*x

7、fxfx *x，称 是|f(x)|*x的最小点.注2*1)()(2)()(xxxfffkkkk (2) 收敛的牛顿序列除去有限点外一定是下山序列)()(*111xxfxfkkk 因为中值定理)()(. 11kkkkxfxfxx 2*)(! 2)()()()(. 3kkkkkxxfxxxfxfxf 0)(. 2* xf,)(2)()()(,2*21xfxfxfxfkkk 时时所所以以，当当. )()(,1kkxfxfk 充充分分大大时时于于是是，当当)()()(2)()(221kkkkkxffxfff 第6页/共17页|)(2)(|)(1|)()(|2*1xfxfxfxfxfkkk 又又,时时当

8、当 k,| )(| )(|1都都很很小小与与kkxfxf 会会很很大大，则则|)(1|kxf(3) 下山法引理1,0)(,0)( xfxf若若则一定存在,0, 0时时当当 t成立. )()()(xfxfxftxf )7 .4(分析 该式子实际上是两个函数值的比较,即是点x与邻近点)()(xfxftx 的函数值,而点x与点)()(xfxftx 只差,)()(xfxft 且含有),(xf f(x)的导数由已知考虑用导数的定义,0t即即时,形如:)()()()()()(xfxfxftxfxfxftxf 的导数定义. )()(,1kkxfxfk 充充分分大大时时于于是是，当当第7页/共17页证明 由导

9、数的定义)()()()()()(lim0 xfxfxftxfxfxftxft 得, 0)()()()()()(lim0 xfxfxftxfxfxftxft即. 0)()()()()()(lim0 xfxftxtfxfxfxftxft引理1,0)(,0)0( xff若若则一定存在,0, 0时时当当 t成立. )()()(xfxfxftxf )7 .4(于是由极限的概念,只要,0 t有, )(21)()()()()()(xfxfxftxtfxfxfxftxf , 0 存在, )(21xf 取取第8页/共17页于是由极限的概念,只要,0 t有, )(21)()()()()()(xfxfxftxtfx

10、fxfxftxf 从而, )(2)()1()()(xftxftxfxftxf 则. )()()21()()(xfxftxfxftxf t0#即.0)()()()()()(lim0 xfxftxtfxfxfxftxft, 0 存在, )(21xf 取取第9页/共17页牛顿下山法的定义)()(xfxf 是f(x)在x点的下山方向.在牛顿, 1 , 0 k)8.4(. )()(1kkxfxf 其中1 , 0 kt称为下山因子.说明(1)当1 kt时,)()(1kkkkxfxfxx 牛顿下山法为标准的牛顿法；当0 kt时,*1xxxkk , 1 , 0 k此时 0kkx不收敛于.*x因此为保证收敛性,

11、 tk 不能太小.(2)下山因子tk的一种常用取法先取, 1 kt若已满足, )()(1kkxfxf 则把1 kx作为第k+1次近似值;若不满足,则取,21 kt再判断是否满, )()(1kkxfxf 足足若满足,把1 kx作为k+1次近似值;否则取,41 kt.法中,可以适当选择, 0 kt使kkktxx 1满足,)()(kkxfxf 该方法称为牛顿下山法.第10页/共17页例6求 01)(3 xxxf在1.5附近的根.解若取初值1.5, 0)5 . 1 ( f013)(2 xxf,6)(xxf , 0)5 . 1 ( f满足收敛条件.但若取, 6 . 00 x计算得, 9 .171 x与可

12、能值的差距加大,即使能收敛速度也会很慢.此时用牛顿下山法,设下山因子为t ,131)()(231 kkkkkkkkxxxtxxfxftxx则计算结果如下表此时,656643. 0)(1 xf. )()(01xfxf 则则有有)6.0()6.0(6.0)()(0001ffxfxfxx 计算方法),577350268.031( x,9.1708.0384.16.0 ,140625.1)6.0()6.0(3216.0)()(2100501 ffxfxfxx则则取取,2151 t ktkx)(kxf6 . 0384.10521140625. 16566. 0136681. 11866. 0213262

13、80. 100667. 031324720. 1610711. 841表4-4第11页/共17页3. 重根加速收敛法(推广)定理9、10、11中，, 0)(* xf意味着*x是f(x)=0的单根,假设*x是f(x)=0的m(m1)重根,Newton法能否用?怎样用?是否收敛?(1) 重根处Newton法是收敛的事实上，设*x是f(x)=0的m(m1)重根,即),()()(*xQxxxfm 0)(* xQ),()()()()(*1*xQxxxQxxmxfmm 则当x接近*x时,)()()(xfxfxxg )()()()()()(*1*xQxxxQxxmxQxxxmmm )()()(*xQxQxx

14、mxxx 到第4次时近似值的精度已经相当高了.如表所示,用牛顿下山法,第1次就落入了局部收敛的领域,说明第12页/共17页*xxxx 重根处Newton法局部线性收敛 .且重数越大,收敛越慢.结论 )11)()()(lim)(*mxxxgxgxgxx )()()(xfxfxxg )()()()()()(*1*xQxxxQxxmxQxxxmmm )()()(*xQxQxxmxxx )()()(11*)(*xQxQxxmxxxx m =1时即是牛顿法，此时 是超线性收敛，即二阶收敛.，011 m(2) 加速法l 以Newton法为基本简单迭代 ,用Steffenson方法进行计算可得二阶收敛迭代序

15、列.l 若m已知取迭代函数*).(1111xxmmm )()()(11*xQxQxxm 注 需要预知m的大小. )()()(xfxfmxxg ，此时可以证明0)(* xg,即迭代是平方收敛.)9 . 4(（见牛顿迭代的加速法）（自己证） x第13页/共17页l 若m未知取定义新函数)()()(xfxfxh )10. 4(则,)()()()()(22xfxfxfxfxh 若*x是f(x)的m重根,*x必为h(x)的单根. ),()()(*xQxxxfm 令令0)(* xQ),()()()()(*1*xQxxxQxxmxfmm )()()()()()()(*1*xQxxxQxxmxQxxxhmmm

16、 )()()()()(*xQxxxmQxQxx ).()(*xsxx 0)(* xs)0)(* xQ因此,可用Newton法求h(x)=0的单根.即)()(1kkkkxhxhxx ,)()()()()(2kkkkkkxfxfxfxfxfx , 1 , 0 k)11. 4(h(x)=0的单根即为f(x)=0的重根.且该迭代是二阶收敛的.(定理7)事实上，注这种方法不需要知道重根数，但迭代格式稍微复杂.第14页/共17页已知解 牛顿切线法取x0=1.5,计算结果如表4-5所示 . 牛顿值牛顿值 重根值重根值 01231.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.414213562 kkx表4-5例7经过3次迭代，重根法达到了 10-9, 精确度，是平方收敛速度，而牛顿法是一阶的，要30次迭代才能得到相同的结果. 是方程x 4-