第二節(jié)_牛頓迭代法

1、第三節(jié)第三節(jié) 牛頓迭代法與弦割法牛頓迭代法與弦割法1、牛頓法基本思想、牛頓法基本思想將非線性方程線性化，以線性方程的解逼近非線性方程的解。將非線性方程線性化，以線性方程的解逼近非線性方程的解。將非線性方程將非線性方程線性化，線性化，取取 x0 x*，將將 f (x) 在在 x0 處做一階處做一階Taylor展開(kāi)展開(kāi):20000)(!2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x 之間之間2. 牛頓迭代法的原理牛頓迭代法的原理)*)()(*)(0000 xxxfxfxf ，可將，可將 (x* x0)2 看成看成高階小量高階小量，則有：，則有：如何實(shí)現(xiàn)？如何實(shí)現(xiàn)？*xx取取)(

2、)(*000 xfxfxx xyx*x010 1 2(), ,()kkkkfxxxkfx 只要只要 f C1，每一步迭代都有，每一步迭代都有 而且而且 ，則，則 x*就是就是 f 的根。的根。limkkxx 0()kfx 1x 1x2x000()()()yf xfxxx 1x是如下線性方程的根！是如下線性方程的根！00(,()xfx3. 牛頓迭代法的幾何解釋?zhuān)号ｎD迭代法的幾何解釋?zhuān)悍匠谭匠?的根的根 在幾何上是曲線在幾何上是曲線 與與 x 軸的交軸的交( )0fx *x( )yfx點(diǎn)的橫坐標(biāo)。若點(diǎn)的橫坐標(biāo)。若 是根是根 的一個(gè)近似，過(guò)曲線上橫坐標(biāo)為的一個(gè)近似，過(guò)曲線上橫坐標(biāo)為 kx*xkx的點(diǎn)

3、的點(diǎn) 作曲線作曲線 的切線，則該切線與的切線，則該切線與 x 軸交點(diǎn)的橫坐軸交點(diǎn)的橫坐kP( )yfx標(biāo)即為標(biāo)即為 。1kxxyx*x01x2x00(,()xfx例例2.52.5：寫(xiě)出求寫(xiě)出求 的的牛頓牛頓迭代格式；迭代格式；寫(xiě)出求寫(xiě)出求 的的牛頓牛頓迭代格式迭代格式, ,要求公式中既要求公式中既無(wú)開(kāi)方運(yùn)算，又無(wú)除法運(yùn)算。無(wú)開(kāi)方運(yùn)算，又無(wú)除法運(yùn)算。0()a a 10()aa 解：解： 等價(jià)于求方程等價(jià)于求方程 的正根的正根200()()fxxaa 2110 1 222()(), , ,()kkkkkkkkkfxxaaxxxxkfxxx 2( )fxx 解法一：解法一： 等價(jià)于求方程等價(jià)于求方程

4、 的根的根2100()()()fxxaa 12( )()fxxa 21112()()()()kkkkkkkxfxaxxxfxxa 110 1 22(), , ,kxka 退化為二分法退化為二分法！32( )fxx 解法二：解法二： 等價(jià)于求方程等價(jià)于求方程 的正根的正根2100()()fxaax 21312()()kkkkkkkafxxxxxfxx 2130 1 22(), , ,kkxaxk 設(shè)設(shè) x* 為方程為方程 f (x) = 0的根，在包含的根，在包含x*的某個(gè)開(kāi)區(qū)間內(nèi)的某個(gè)開(kāi)區(qū)間內(nèi) 連連續(xù)，且續(xù)，且 ，則存在，則存在 x* 的鄰域的鄰域 ，使得任取初值使得任取初值 ，由，由牛頓迭代

5、法牛頓迭代法產(chǎn)生的序列產(chǎn)生的序列 以不以不低于低于二階二階的收斂速度收斂于的收斂速度收斂于x*.( *),Bxxx *)(0 xBx ( )fx 0( )fx kx4、牛頓迭代法的局部收斂性定理、牛頓迭代法的局部收斂性定理221 ( )( )( )( )( )fxf x fxxfx 其中其中 ，則，則()()()fxxxfx 201(*)(*)(*)(*)fxfxxfx 收斂收斂 證明：證明：牛頓迭代法牛頓迭代法事實(shí)上是一種事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代特殊的不動(dòng)點(diǎn)迭代*xxekk設(shè)定義定義1. 10pc 若若 存存 在在 實(shí)實(shí) 數(shù)數(shù)和和滿(mǎn)滿(mǎn) 足足1limkkkee c11,21,2則 迭 代

6、法階 收 斂 。，時(shí) 線 性 收 斂超 線 性 收 斂時(shí) 平 方 收 斂ppcpp ,p顯 然越 大 收 斂 速 度 也 就 越 快-(9)3.5迭代法收斂迭代法收斂階與加速收斂階與加速收斂1、迭代法收斂迭代法收斂階與加速收斂階與加速收斂從而確定收斂階呢？如何確定那么,p()*,xx 如如 果果 迭迭 代代 函函 數(shù)數(shù)在在 精精 確確 解解處處 充充 分分 光光 滑滑即即 處處 處處 可可 導(dǎo)導(dǎo)有展開(kāi)作在將,*)(Taylorxx 2*)(!2*)(*)*)(*)()(xxxxxxxxppppxxpxxxpx*)(!*)(*)()!1(*)()(1)1(0*)()1(xp *)(*)(xx如果

7、0*)()(xp而*)()(xxppxxpx*)(!*)()()(1kkxxpkpxxpxx*)(!*)(*)()(pkpxxpx*)(!*)()(*1xxk1)1(*)()!1(*)(pkpxxpx定理定理3-6 . pkkxxxx*1*)()!1(*)(!*)()1()(xxpxpxkpppxxkk的收斂階是即迭代法)(1附近滿(mǎn)足：在根如果迭代法迭代函數(shù)*)(xx階導(dǎo)數(shù)切連續(xù)；存在 px)()1(,0*)()1(xp *)(*)()2(xx0*)()(xp而pxxkk的收斂階是則迭代法)(1)( ,!*)()(kpxp（1）Newton迭代公式在單根情況下至少2階收斂; （2） 設(shè) f(x

8、*)=0, ,且在 x* 的鄰域上 f二次連續(xù)可微 ， 則可得( *)0fx*1*2*()()()2()limnnnxxfxcxxfx 將f(x)在 xn 處作2階Taylor展開(kāi),并將解x*代入212222* 20 )x*x()x( f)(fx)x*x()x( f)(f)x( f)x(fxx)x*x(!)(f)x*x)(x( f)x(f*)x(fnnnnnnnnnnnnnnn 注意到n 在xn 及x*之間,及 , 故*xxnnlim 所以，Newton法至少二階收斂. )x( f)x(f)x( f)(fxxxx*nn*n*n2221*0()()00()()0fxfx二 階 收 斂 若大 于

9、二 階 收 斂 若21222* )x*x()x( f)(fx)x*x()x( f)(f)x( f)x(fxxnnnnnnnnnn 注意到n 在xn 及x*之間,及 ,故*xxnnlim 1|* |lim (0)* |npnnxxccxx *1*2*()()lim()2()kxkxxfxxxfx 例例3.證明迭代法重根的是方程設(shè),)2(0)(*mxfx)()(1kkkkxfxfxx為線性收斂為線性收斂證明證明:故重根的是方程因?yàn)?0)(*mxfx)(*)()(xgxxxfm2,0*)(mxg且所以所以)(xf )(*)()(*)(1xgxxxgxxmmm)(*)()(*)()(*)(1kmkkm

10、kkmkkxgxxxgxxmxgxxx)()(1kkkkxfxfxx)(*)()()(*)(kkkkkkxgxxxmgxgxxx*1xxk)(*)()()(1*)(kkkkkxgxxxmgxgxx*lim1xxxxkkk)(*)()()(1(limkkkkkxgxxxmgxgm11 011,2mm時(shí)重根是線性收斂的該迭代法對(duì))2(m例例4.證明迭代法且設(shè),0)(,0)(afaf)()(1kkkkxfxfxx至少是平方收斂的至少是平方收斂的由定義由定義1注意例注意例4與例與例3的迭代法是相同的的迭代法是相同的,兩例有何區(qū)別兩例有何區(qū)別?證明證明:令令)()()(xfxfxx)(x則則22)()(

11、)()(1xfxfxfxf 2)()()(xfxfxf 0)( a所以所以由定理由定理2該迭代法至少是平方收斂的該迭代法至少是平方收斂的 Newton迭代公式是一種特殊的不動(dòng)點(diǎn)迭代,其迭代函數(shù)為: Newton迭代是局部線性化方法,它在單根附近具有較高的收斂速度. 方法有效前提: : ( )( )( )fxxxfx()0kfx牛頓迭代法的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)： 在單根附近, 牛頓迭代法具有平方收斂的速 度，所以在迭代過(guò)程中只要迭代幾次就會(huì)得到很精 確解。 缺點(diǎn):1. 重根情形下為局部線性收斂; 2. 牛頓迭代法計(jì)算量比較大:因每次迭代除 計(jì)算函數(shù)值外還要計(jì)算微商值; 3. 選定的初值要接近方程的解，否

12、則有可能得 不到收斂的結(jié)果;牛頓迭代法的改進(jìn)缺點(diǎn)克服: 1. 局部線性收斂-改進(jìn)公式或加速 2.每步都要計(jì)算微商值-簡(jiǎn)化Newton迭代法 或弦截法 3. 初值近似問(wèn)題-二分法求初值或”下山算法”方法一方法一. 若已知重?cái)?shù)m(m1),則利用m構(gòu)造新的迭代公式: 此時(shí), , 至少2階收斂. 不實(shí)用: m往往不確定.方法二方法二. 取 ,再對(duì)函數(shù)F(x)用Newton迭代:1()()kkkkfxxxmfx()*()( ),()0fxfxxxmx( )( )( )fxxfx12()()()()()()()kkkkkkkkkkxfxfxxxxxfxfxfx*()( )( )( )()( )xxg xx

13、mg xxxgx2( )( )( )( )( )( )( )( )xfx fxxxxxfxfx fx從而可構(gòu)造出相應(yīng)的迭代法格式為從而可構(gòu)造出相應(yīng)的迭代法格式為12()()()()()kkkkkkkfxfxxxfxfxfx( )x對(duì)對(duì) 構(gòu)造出相應(yīng)的牛頓迭代格式，迭代函數(shù)為構(gòu)造出相應(yīng)的牛頓迭代格式，迭代函數(shù)為若已知根的重?cái)?shù)為若已知根的重?cái)?shù)為 n，可將迭代格式改為，可將迭代格式改為，10 1 2(), , ,()kkkkfxxxnkfx 則則*()0 x ，所以上述格式是平方收斂的。，所以上述格式是平方收斂的。收斂比牛頓迭代法收斂比牛頓迭代法慢慢，且對(duì)，且對(duì)初值要求同樣高。初值要求同樣高。第五節(jié)第五節(jié) 弦割法弦割法x0 x1切線切線 割線割線 切線斜率切線斜率 割線斜率割線斜率10110()()()fxfxfxxx 111()()()()kkkkkkkf xxxxxf xf x 需要需要2個(gè)初值個(gè)初值 x0 和和 x1?；舅枷耄夯舅枷耄号ｎD迭代法牛頓迭代法每一步要計(jì)算每一步要計(jì)算 f 和和 ，為了避免計(jì)算，為了避免計(jì)算導(dǎo)數(shù)值，現(xiàn)用導(dǎo)數(shù)值，現(xiàn)用 f 的差商近似代替微商的差商近似代替微商 ，從而得到，從而得到弦割法弦割法。f f x2Th2.10 局部收斂性局部收斂性 設(shè)設(shè) 表示區(qū)間表示區(qū)間 ， x*為方程為方程 f (x) =0的