1.2,牛頓法,弦截法ppt課件

1、7.4 -7.5 牛頓法及其推廣 /* Newton Method */一、牛頓迭代法的公式一、牛頓迭代法的公式二、牛頓迭代法的改進(jìn)與推廣二、牛頓迭代法的改進(jìn)與推廣原理：將非線性方程線性化原理：將非線性方程線性化泰勒展開(kāi)泰勒展開(kāi) /* Taylors expansion */取取 x0 x* ，將，將 f(x*) 在在 x0 做一階泰勒展開(kāi)做一階泰勒展開(kāi):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 f(x)=0 的求根問(wèn)題歸的求根問(wèn)題歸結(jié)為計(jì)算一系列線性方程的求根問(wèn)題。結(jié)為計(jì)算一系列線性方程的求根問(wèn)題。 牛頓迭代法的計(jì)算步驟牛頓迭代法的計(jì)算步驟(1)(1)給出初始近似根給出初始近似根 x0 x0 及精度及精度；)()(0001xfxfxx (3)(3)假設(shè)假設(shè) ，

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

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

5、根，且 f (x*) 0，則存在，則存在 x* 的鄰域的鄰域*)(xB *)(0 xBx *)(2*)()*(*lim21xfxfxxxxkkk 定理定理（局部收斂性）（局部收斂性）Newtons Method產(chǎn)生的序列產(chǎn)生的序列 xk 收斂到收斂到x*，且滿足，且滿足使得任取初值使得任取初值 Newton Newtons Method s Method 有有 ，只要，只要 就有就有 p p 2 2。重根是線性收斂的。重根是線性收斂的。*)(2*)(|lim21xfxfeekkk 0*)( xf證明：證明： Newton Newtons Method s Method 事實(shí)上是一種特事實(shí)上是一

6、種特殊的不動(dòng)點(diǎn)迭代，其中殊的不動(dòng)點(diǎn)迭代，其中)()()(xfxfxxg 10*)(*)(*)(*)(2xfxfxfxg局部收斂局部收斂那那么么 由泰勒展開(kāi)：由泰勒展開(kāi)：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(! 2)()()(*kkkkkkxxxffxfxfxx 1 kx)(2)()*(*21kkkkxffxxxx 在單根在單根 /*simple root */ 附近收斂附近收斂快快只要只要 f (x*) 0，則令，則令 可得結(jié)論?？傻媒Y(jié)論。 kx*x0 x0 x0注注 (1) (1) 牛頓法要求初值充分接近根以保牛頓法要求初值充分接近根以保證局部收斂

7、性。證局部收斂性。(2)(2)牛頓迭代法的主要優(yōu)點(diǎn)是收斂較快，牛頓迭代法的主要優(yōu)點(diǎn)是收斂較快，是平方收斂的缺點(diǎn)是公式中需要求是平方收斂的缺點(diǎn)是公式中需要求 f(x) f(x) 的導(dǎo)數(shù)。假設(shè)的導(dǎo)數(shù)。假設(shè) f(x) f(x)比較復(fù)雜，則使用牛比較復(fù)雜，則使用牛頓公式就大為不便。頓公式就大為不便。 重根重根 / /* * multiple root multiple root * */ / 加速收斂法：加速收斂法：?jiǎn)栴}問(wèn)題1: 假設(shè)假設(shè) ，Newtons Method 是否仍收斂？是否仍收斂？0*)( xf設(shè)設(shè) x*是是 f 的的 n 重根，那么：重根，那么：因?yàn)橐驗(yàn)?Newtons Method

8、事實(shí)上是一種特殊事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭，的不動(dòng)點(diǎn)迭，其中其中)()()(xfxfxxg 二、牛頓迭代法的改進(jìn)與推廣二、牛頓迭代法的改進(jìn)與推廣/* improvement and generalization */)(*)()(xqxxxfn 0*)( xq且且 22*)(*)(*)(*)(1|*)(|xfxfxfxfxg111 nK1: 有局部收斂性，但重?cái)?shù)有局部收斂性，但重?cái)?shù) n 越高，收斂越高，收斂越慢。越慢。那么那么問(wèn)題問(wèn)題2: 如何加速重根的收斂？如何加速重根的收斂？K2: 將求將求 f 的重根轉(zhuǎn)化為求另一函數(shù)的單根。的重根轉(zhuǎn)化為求另一函數(shù)的單根。?令令)()()(xfxfx 那么

9、那么 f f 的重根的重根 = = 的單根。的單根。 下山法下山法 / /* * Descent Method Descent Method * */ / Newton Newtons Method s Method 局部微調(diào)：局部微調(diào)：原理：若由原理：若由 xk xk 得到的得到的 xk+1 xk+1 不能使不能使 | f | | f | 減小，則在減小，則在 xk xk 和和 xk+1 xk+1 之間找一個(gè)更好的之間找一個(gè)更好的點(diǎn)點(diǎn) ，使得，使得 1 kx)()(1kkxfxf xkxk+1,)1(1kkxx 1, 0 )()()1()()(1kkkkkkkkxfxfxxxfxfxx 弦截

10、法弦截法 / /* * Secant Method Secant Method * */ / Newtons Method 一步要計(jì)算一步要計(jì)算 f 和和 f ，相當(dāng)于，相當(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 Me

11、thod 慢，且對(duì)初慢，且對(duì)初值要求同樣高。值要求同樣高。弦截法與牛頓法相比較弦截法與牛頓法相比較相同之處：都是線性化方法相同之處：都是線性化方法不同之處：牛頓法在計(jì)算不同之處：牛頓法在計(jì)算xk+1xk+1時(shí)只用到前時(shí)只用到前一步的值一步的值xkxk，故這種方法稱為單點(diǎn)迭代法。，故這種方法稱為單點(diǎn)迭代法。而弦截法在求而弦截法在求xk+1xk+1時(shí)要用到前兩步的值時(shí)要用到前兩步的值xkxk和和xk-1xk-1，因此這種方法稱為多點(diǎn)迭代，因此這種方法稱為多點(diǎn)迭代法。法。有關(guān)弦截法的收斂速度有關(guān)弦截法的收斂速度與牛頓法相比，弦截法的收斂速度也是與牛頓法相比，弦截法的收斂速度也是比較快的?？梢宰C明，弦

12、截法具有超線比較快的?？梢宰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àn)下表迭代結(jié)果見(jiàn)下表k 0 1 2 3 4 xk 0.5 0.6 0.56754 0.56715 0.56714 00001. 034xx易見(jiàn)