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

1、第三節(jié)第三節(jié) 牛頓迭代法與弦割法牛頓迭代法與弦割法1、牛頓法基本思想、牛頓法基本思想將非線性方程線性化，以線性方程的解逼近非線性方程的解。將非線性方程線性化，以線性方程的解逼近非線性方程的解。將非線性方程將非線性方程線性化，線性化，取取 x0 x*，將將 f (x) 在在 x0 處做一階處做一階Taylor展開展開:20000)(!2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x 之間之間2. 牛頓迭代法的原理牛頓迭代法的原理)*)()(*)(0000 xxxfxfxf ，可將，可將 (x* x0)2 看成看成高階小量高階小量，則有：，則有：如何實現(xiàn)？如何實現(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. 牛頓迭代法的幾何解釋：牛頓迭代法的幾何解釋：方程方程 的根的根 在幾何上是曲線在幾何上是曲線 與與 x 軸的交軸的交( )0fx *x( )yfx點的橫坐標。若點的橫坐標。若 是根是根 的一個近似，過曲線上橫坐標為的一個近似，過曲線上橫坐標為 kx*xkx的點

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

4、 的根的根2100()()()fxxaa 12( )()fxxa 21112()()()()kkkkkkkxfxaxxxfxxa 110 1 22(), , ,kxka 退化為二分法退化為二分法！32( )fxx 解法二：解法二： 等價于求方程等價于求方程 的正根的正根2100()()fxaax 21312()()kkkkkkkafxxxxxfxx 2130 1 22(), , ,kkxaxk 設設 x* 為方程為方程 f (x) = 0的根，在包含的根，在包含x*的某個開區(qū)間內(nè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 收斂收斂 證明：證明：牛頓迭代法牛頓迭代法事實上是一種事實上是一種特殊的不動點迭代特殊的不動點迭代*xxekk設定義定義1. 10pc 若若 存存 在在 實實 數(shù)數(shù)和和滿滿 足足1limkkkee c11,21,2則 迭 代

6、法階 收 斂 。，時 線 性 收 斂超 線 性 收 斂時 平 方 收 斂ppcpp ,p顯 然越 大 收 斂 速 度 也 就 越 快-(9)3.5迭代法收斂迭代法收斂階與加速收斂階與加速收斂1、迭代法收斂迭代法收斂階與加速收斂階與加速收斂從而確定收斂階呢？如何確定那么,p()*,xx 如如 果果 迭迭 代代 函函 數(shù)數(shù)在在 精精 確確 解解處處 充充 分分 光光 滑滑即即 處處 處處 可可 導導有展開作在將,*)(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附近滿足：在根如果迭代法迭代函數(shù)*)(xx階導數(shù)切連續(xù)；存在 px)()1(,0*)()1(xp *)(*)()2(xx0*)()(xp而pxxkk的收斂階是則迭代法)(1)( ,!*)()(kpxp（1）Newton迭代公式在單根情況下至少2階收斂; （2） 設 f(x

8、*)=0, ,且在 x* 的鄰域上 f二次連續(xù)可微 ， 則可得( *)0fx*1*2*()()()2()limnnnxxfxcxxfx 將f(x)在 xn 處作2階Taylor展開,并將解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.證明迭代法重根的是方程設,)2(0)(*mxfx)()(1kkkkxfxfxx為線性收斂為線性收斂證明證明:故重根的是方程因為,0)(*mxfx)(*)()(xgxxxfm2,0*)(mxg且所以所以)(xf )(*)()(*)(1xgxxxgxxmmm)(*)()(*)()(*)(1kmkkm

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

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

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

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