牛頓法弦截法課件

1、7.4 -7.5 牛頓法及其推廣 /* Newton Method */一、牛頓迭代法的公式一、牛頓迭代法的公式二、牛頓迭代法的改進(jìn)與推廣二、牛頓迭代法的改進(jìn)與推廣原理：原理：將非線性方程線性化將非線性方程線性化泰勒展開泰勒展開 /* Taylors expansion */取取 x0 x* ，將，將 f(x*) 在在 x0 做一階泰勒展開做一階泰勒展開:20000)*(! 2)()*)()(*)(xxfxxxfxfxf 在在 x0 和和 x*之間。之間。將將 (x* x0)2看成高階小量，則有：看成高階小量，則有：一、牛頓迭代法的公式一、牛頓迭代法的公式)*)()(*)(0000 xxxfx

2、fxf )()(*000 xfxfxx 線性線性 /* linear */xyx*x0)()(1kkkkxfxfxx 只要只要 每一步迭代都每一步迭代都有有f ( xk ) 0， 而而且且 ，則則 x*就是就是 f 的根。的根。*limxxkk 牛頓迭代法的基本思想牛頓迭代法的基本思想將非線性方程將非線性方程 f(x)=0 的求根問題歸結(jié)的求根問題歸結(jié)為計(jì)算一系列線性方程的求根問題。為計(jì)算一系列線性方程的求根問題。 牛頓迭代法的計(jì)算步驟牛頓迭代法的計(jì)算步驟(1)(1)給出初始近似根給出初始近似根 x0 及精度及精度；)()(0001xfxfxx (3)(3)若若 ，轉(zhuǎn)向，轉(zhuǎn)向(4)(4)， 否

3、則否則 ，轉(zhuǎn)向，轉(zhuǎn)向(2);(2); 01xx10 xx (4)(4)輸出滿足精度的根輸出滿足精度的根 x1 ，結(jié)束。，結(jié)束。(2)(2)計(jì)算計(jì)算例例 00002. 023xx用牛頓迭代法求方程用牛頓迭代法求方程01 xxe在在 x=0.5 =0.5 附近的根。取附近的根。取解解其牛頓迭代公式為其牛頓迭代公式為kxkkkxexxxk 11取初值取初值 x0 0=0.5 =0.5 ，迭代結(jié)果見下表，迭代結(jié)果見下表易見易見故故567. 03 xxk 0 1 2 3xk 0.5 0.57102 0.56716 0.5671400005. 0 k 0 1 2 3 xk 0.880000 0.88468

4、8 0.884675 0.884675例例 2 2 計(jì)算計(jì)算 的近似值的近似值, , =10=10-6-6 x0 0=0.88=0.880.782650.78265解：令解：令 x= =問題轉(zhuǎn)化為求問題轉(zhuǎn)化為求f( (x)=)=x2 2-0.78265=0-0.78265=0 的正根的正根由牛頓迭代公式由牛頓迭代公式xk+1= xk-(xk)/(xk)= xk/2+0.78265/2xk迭代結(jié)果迭代結(jié)果滿足了精度要求滿足了精度要求,故故0.782650.884675設(shè)設(shè) f C2a, b，若，若 x* 為為 f (x) 在在a, b上的根，上的根，且且 f (x*) 0，則存在，則存在 x*

5、的鄰域的鄰域*)(xB *)(0 xBx *)(2*)()*(*lim21xfxfxxxxkkk 定理定理（局部收斂性局部收斂性）Newtons Method產(chǎn)生的序列產(chǎn)生的序列 xk 收斂到收斂到x*，且滿足，且滿足使得任取初值使得任取初值 Newtons Method 有有 ，只要，只要 就有就有 p 2。重根是線性收斂的。重根是線性收斂的。*)(2*)(|lim21xfxfeekkk 0*)( xf證明：證明： Newtons Method 事實(shí)上是一種特事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代，其中殊的不動(dòng)點(diǎn)迭代，其中)()()(xfxfxxg 10*)(*)(*)(*)(2xfxfxfxg局部收

6、斂局部收斂則則 由泰勒展開：由泰勒展開：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(! 2)()()(*kkkkkkxxxffxfxfxx 1 kx)(2)()*(*21kkkkxffxxxx 在單根在單根 /*simple root */ 附近收斂快附近收斂快只要只要 f (x*) 0，則令，則令 可得結(jié)論?？傻媒Y(jié)論。 kNewtons Method 收斂性依賴于收斂性依賴于x0 的的選取選取x*x0 x0 x0注注 (1) (1) 牛頓法要求初值充分接近根以保牛頓法要求初值充分接近根以保證局部收斂性。證局部收斂性。(2)(2)牛頓迭代法的主要優(yōu)點(diǎn)是收斂

7、較快，牛頓迭代法的主要優(yōu)點(diǎn)是收斂較快，是平方收斂的缺點(diǎn)是公式中需要求是平方收斂的缺點(diǎn)是公式中需要求 f(x) 的導(dǎo)數(shù)。若的導(dǎo)數(shù)。若 f(x)比較復(fù)雜，則使用牛頓比較復(fù)雜，則使用牛頓公式就大為不便。公式就大為不便。 重根重根 /* multiple root */ 加速收斂法：加速收斂法：?jiǎn)栴}問題1: 若若 ，Newtons Method 是否仍收斂？是否仍收斂？0*)( xf設(shè)設(shè) x*是是 f 的的 n 重根，則：重根，則：因?yàn)橐驗(yàn)?Newtons Method 事實(shí)上是一種特殊事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭的不動(dòng)點(diǎn)迭，其中其中)()()(xfxfxxg 二、牛頓迭代法的改進(jìn)與推廣二、牛頓迭代法的

8、改進(jìn)與推廣/* improvement and generalization */)(*)()(xqxxxfn 0*)( xq且且 22*)(*)(*)(*)(1|*)(|xfxfxfxfxg111 nK1: 有局部收斂性，但重?cái)?shù)有局部收斂性，但重?cái)?shù) n 越高，收斂越高，收斂越慢。越慢。則則問題問題2: 如何加速重根的收斂？如何加速重根的收斂？K2: 將求將求 f 的重根轉(zhuǎn)化為求另一函數(shù)的單根。的重根轉(zhuǎn)化為求另一函數(shù)的單根。?令令)()()(xfxfx 則則 f 的重根的重根 = = 的單根。的單根。 下山法下山法 /* Descent Method */ Newtons Method 局部微

9、調(diào)：局部微調(diào)：原理：原理：若由若由 xk 得到的得到的 xk+1 不能使不能使 | f | 減小，減小，則在則在 xk 和和 xk+1 之間找一個(gè)更好的點(diǎn)之間找一個(gè)更好的點(diǎn) ，使，使得得 1 kx)()(1kkxfxf xkxk+1,)1(1kkxx 1, 0 )()()1()()(1kkkkkkkkxfxfxxxfxfxx = 1 時(shí)就是時(shí)就是Newtons Method 公式。公式。 當(dāng)當(dāng) = 1 代入效果不好時(shí)，將代入效果不好時(shí)，將 減半計(jì)算。減半計(jì)算。 。 弦截法弦截法 /* Secant Method */ Newtons Method 一步要計(jì)算一步要計(jì)算 f 和和 f ，相，相當(dāng)

10、于當(dāng)于2個(gè)函數(shù)值，比較費(fèi)時(shí)?，F(xiàn)用個(gè)函數(shù)值，比較費(fèi)時(shí)?，F(xiàn)用 f 的值近的值近似似 f ，可少算一個(gè)函數(shù)值。，可少算一個(gè)函數(shù)值。x0 x1切線切線/* tangent line */割線割線/* secant line */切線斜率切線斜率 割線斜率割線斜率11)()()( kkkkkxxxfxfxf)()()(111 kkkkkkkxfxfxxxfxx需要需要 2 個(gè)初值個(gè)初值 x0 和和 x1 。收斂比收斂比Newtons Method 慢，且對(duì)初慢，且對(duì)初值要求同樣高。值要求同樣高。弦截法與牛頓法相比較弦截法與牛頓法相比較相同之處：相同之處：都是線性化方法都是線性化方法不同之處：不同之處：牛

11、頓法在計(jì)算牛頓法在計(jì)算x xk+1k+1時(shí)只用到前時(shí)只用到前一步的值一步的值x xk k，故這種方法稱為，故這種方法稱為單點(diǎn)迭代法單點(diǎn)迭代法。而弦截法在求而弦截法在求x xk+1k+1時(shí)要用到前兩步的值時(shí)要用到前兩步的值x xk k和和x xk-1k-1，因此這種方法稱為，因此這種方法稱為多點(diǎn)迭代法多點(diǎn)迭代法。有關(guān)弦截法的收斂速度有關(guān)弦截法的收斂速度與牛頓法相比，弦截法的收斂速度也是與牛頓法相比，弦截法的收斂速度也是比較快的。可以證明，弦截法具有超線比較快的?？梢宰C明，弦截法具有超線性收斂速度，收斂階為性收斂速度，收斂階為618. 1)51(21 p即即)( , 0|618. 11 kcxxxxkk例例用弦截法求方程用弦截法求方程01 xxe在在x=0.5附近的根。取附近的根。取解解取取x0=0.5，x1=0.6作為初始近似作為初始近似根，令根，令0)( xexxf其弦截法迭代公式為其弦截法迭代公式為)()(1111 kkxxkkxkkkxxeexxexxxkkk00005. 0 迭代結(jié)果見下表迭代結(jié)果見下表k 0 1 2 3 4 xk 0.5 0.6 0.56754 0.56715 0.56714 00001. 034xx易見易見故故