級牛頓修正PPT課件

1、證明 先證f(x)=0有唯一解. 證Newton序列單調(diào),有界,從而有極限.滿滿足足設(shè)設(shè),0bax , 0)()(00 xfxf考慮由牛頓法得到的x1的特性,因為f(x)連續(xù), 0)()( bfaf所以f(x)=0在a,b上至少有一個解,設(shè)為x*.又因為f (x)連續(xù), 0)(, xfbax則f (x)在a,b上恒正或恒負(fù),從而f(x)在a,b上嚴(yán)格單調(diào)上升或下降,f(x)=0在a,b上最多只有一個解.因此f(x)=0在a,b內(nèi)有唯一解x*.(考慮x1與x0、x*的大小關(guān)系,進(jìn)一步討論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又單調(diào)、有界序列必有極限，設(shè)極限為,x并有界,是單調(diào)序列 *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)內(nèi).xxxfcos)( 又又, 0) 1 (, 01) 0( ff在(0,1)上.0cos xf(恒正)(不變號)則Newton迭代序列單調(diào)二

4、階收斂到0)( xf在(0,1)內(nèi)的唯一根.*x10 x取取, Newton迭代的計算結(jié)果如下表 kkx)(kxf)(kxf 01459697694. 0841470984. 11750363867. 0018923073. 0681904952. 12739085133. 03000046454. 0673632544. 173911289. 00, 0sin1)( xxf表4-2優(yōu)點(diǎn)收斂速度快 .缺點(diǎn)1. 需要每次計算導(dǎo)數(shù)值 f (x)，如果函數(shù)f (x)比較復(fù)雜，使用牛頓公式不方便 .2. 對初值x0要求苛刻.第3頁/共17頁5.3 Newton切線法的修正算法1.簡化牛頓切線法 思想方

5、法 )()(1kkkkxfxfxx 用常數(shù)c 代替牛頓切線法中的 f (xk)簡化牛頓切線法公式cxfxxkkk)(1 至少是線性收斂，收斂性當(dāng)取c = f (xk)時，是二階收斂.在初始值x0，取c = f (x0) ,c的選取方法在xk附近的一些點(diǎn)上可取c = f (xk) .這樣即保證了計算簡單又使收斂較快，在某些點(diǎn)上接近平方收斂.2.Newton下山法(修正的Newton法)第4頁/共17頁用牛頓切線法求方程x 3-x-1= 0在x=1.5附近的一個根 .解 取迭代初值x0=1.5，用牛頓公式 計算結(jié)果如表4-3所示 .012341.51.347831.325201.324721.32

6、472 kkx表4-3其中x3=1.32472 的每一位數(shù)字都是有效數(shù)字. 例5131231 kkkkkxxxxx如果改用 x0=0.6作為初值，迭代一次得x1=17.9, 這個結(jié)果反而比x0更偏離了所求的根 x*. 為了防止迭代發(fā)散，對迭代過程附加一基本要求,即保證函數(shù)值單調(diào)下降)()(1kkxfxf ，滿足這項要求的算法稱下山法.第5頁/共17頁(1) 下山序列的定義若視|f(x)|為f(x)在x點(diǎn)的高度,則*x是山谷最低點(diǎn).定義 若序列kx滿足)()(1kkxfxf ，稱kx是f(x)的一個下山序列.下山序列的極限點(diǎn),不一定是f(x)0的解.方程f(x)0的解 滿足：)(min)(0*x

7、fxfx *x，稱 是|f(x)|*x的最小點(diǎn).注2*1)()(2)()(xxxfffkkkk (2) 收斂的牛頓序列除去有限點(diǎn)外一定是下山序列)()(*111xxfxfkkk 因為中值定理)()(. 11kkkkxfxfxx 2*)(! 2)()()()(. 3kkkkkxxfxxxfxfxf 0)(. 2* xf,)(2)()()(,2*21xfxfxfxfkkk 時時所所以以，當(dāng)當(dāng). )()(,1kkxfxfk 充充分分大大時時于于是是，當(dāng)當(dāng))()()(2)()(221kkkkkxffxfff 第6頁/共17頁|)(2)(|)(1|)()(|2*1xfxfxfxfxfkkk 又又,時時當(dāng)

8、當(dāng) k,| )(| )(|1都都很很小小與與kkxfxf 會會很很大大，則則|)(1|kxf(3) 下山法引理1,0)(,0)( xfxf若若則一定存在,0, 0時時當(dāng)當(dāng) t成立. )()()(xfxfxftxf )7 .4(分析 該式子實際上是兩個函數(shù)值的比較,即是點(diǎn)x與鄰近點(diǎn))()(xfxftx 的函數(shù)值,而點(diǎn)x與點(diǎn))()(xfxftx 只差,)()(xfxft 且含有),(xf f(x)的導(dǎo)數(shù)由已知考慮用導(dǎo)數(shù)的定義,0t即即時,形如:)()()()()()(xfxfxftxfxfxftxf 的導(dǎo)數(shù)定義. )()(,1kkxfxfk 充充分分大大時時于于是是，當(dāng)當(dāng)?shù)?頁/共17頁證明 由導(dǎo)

9、數(shù)的定義)()()()()()(lim0 xfxfxftxfxfxftxft 得, 0)()()()()()(lim0 xfxfxftxfxfxftxft即. 0)()()()()()(lim0 xfxftxtfxfxfxftxft引理1,0)(,0)0( xff若若則一定存在,0, 0時時當(dāng)當(dāng) 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點(diǎn)的下山方向.在牛頓, 1 , 0 k)8.4(. )()(1kkxfxf 其中1 , 0 kt稱為下山因子.說明(1)當(dāng)1 kt時,)()(1kkkkxfxfxx 牛頓下山法為標(biāo)準(zhǔn)的牛頓法；當(dāng)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.法中,可以適當(dāng)選擇, 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、能值的差距加大,即使能收斂速度也會很慢.此時用牛頓下山法,設(shè)下山因子為t ,131)()(231 kkkkkkkkxxxtxxfxftxx則計算結(jié)果如下表此時,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的單根,假設(shè)*x是f(x)=0的m(m1)重根,Newton法能否用?怎樣用?是否收斂?(1) 重根處Newton法是收斂的事實上，設(shè)*x是f(x)=0的m(m1)重根,即),()()(*xQxxxfm 0)(* xQ),()()()()(*1*xQxxxQxxmxfmm 則當(dāng)x接近*x時,)()()(xfxfxxg )()()()()()(*1*xQxxxQxxmxQxxxmmm )()()(*xQxQxx

14、mxxx 到第4次時近似值的精度已經(jīng)相當(dāng)高了.如表所示,用牛頓下山法,第1次就落入了局部收斂的領(lǐng)域,說明第12頁/共17頁*xxxx 重根處Newton法局部線性收斂 .且重數(shù)越大,收斂越慢.結(jié)論 )11)()()(lim)(*mxxxgxgxgxx )()()(xfxfxxg )()()()()()(*1*xQxxxQxxmxQxxxmmm )()()(*xQxQxxmxxx )()()(11*)(*xQxQxxmxxxx m =1時即是牛頓法，此時 是超線性收斂，即二階收斂.，011 m(2) 加速法l 以Newton法為基本簡單迭代 ,用Steffenson方法進(jìn)行計算可得二階收斂迭代序

15、列.l 若m已知取迭代函數(shù)*).(1111xxmmm )()()(11*xQxQxxm 注 需要預(yù)知m的大小. )()()(xfxfmxxg ，此時可以證明0)(* xg,即迭代是平方收斂.)9 . 4(（見牛頓迭代的加速法）（自己證） x第13頁/共17頁l 若m未知取定義新函數(shù))()()(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)事實上，注這種方法不需要知道重根數(shù)，但迭代格式稍微復(fù)雜.第14頁/共17頁已知解 牛頓切線法取x0=1.5,計算結(jié)果如表4-5所示 . 牛頓值牛頓值 重根值重根值 01231.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.414213562 kkx表4-5例7經(jīng)過3次迭代，重根法達(dá)到了 10-9, 精確度，是平方收斂速度，而牛頓法是一階的，要30次迭代才能得到相同的結(jié)果. 是方程x 4-