數(shù)值分析7-4,5(牛頓法,弦截法)

1、7.4 -7.5 牛頓法及其推廣 /* Newton Method */一、牛頓迭代法的公式一、牛頓迭代法的公式二、牛頓迭代法的改進與推廣二、牛頓迭代法的改進與推廣原理：原理：將非線性方程線性化將非線性方程線性化泰勒展開泰勒展開 /* 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é)為計算一系列線性方程的求根問題。為計算一系列線性方程的求根問題。 牛頓迭代法的計算步驟牛頓迭代法的計算步驟(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)計算計算例例 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 計算計算 的近似值的近似值, , =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 事實上是一種特事實上是一種特殊的不動點迭代，其中殊的不動點迭代，其中)()()(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)點是收斂較快，牛

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

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

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

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

11、算牛頓法在計算x xk+1k+1時只用到前時只用到前一步的值一步的值x xk k，故這種方法稱為，故這種方法稱為單點迭代法單點迭代法。而弦截法在求而弦截法在求x xk+1k+1時要用到前兩步的值時要用到前兩步的值x xk k和和x xk-1k-1，因此這種方法稱為，因此這種方法稱為多點迭代法多點迭代法。有關(guān)弦截法的收斂速度有關(guān)弦截法的收斂速度與牛頓法相比，弦截法的收斂速度也是與牛頓法相比，弦截法的收斂速度也是比較快的?？梢宰C明，弦截法具有超線比較快的?？梢宰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易見易見故故