工程數(shù)學(xué)-計(jì)算方法-第二張-方程求根

1、1計(jì) 算 方 法湖南大學(xué)電氣與信息工程學(xué)院郭斯羽華中科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 計(jì)算方法課程組 制湖南大學(xué)電氣與信息工程學(xué)院 科學(xué)與工程計(jì)算方法及應(yīng)用課程組 修改第第2 2章章 方程求根方程求根22 方程求根2.0 0 引言引言2.1 二分法二分法2.3 牛頓牛頓(Newton)法法2.4 迭代過(guò)程的加速方法迭代過(guò)程的加速方法2.2 迭代法迭代法3方程是在科學(xué)研究中不可缺少的工具方程是在科學(xué)研究中不可缺少的工具,方程求解是科學(xué)計(jì)算中一個(gè)重要的研究對(duì)象方程求解是科學(xué)計(jì)算中一個(gè)重要的研究對(duì)象.幾百年前就已經(jīng)找到幾百年前就已經(jīng)找到了代數(shù)方程中二次至了代數(shù)方程中二次至四次方程的求解公式四次方程的求解公式;

2、但是但是,對(duì)于更高次數(shù)對(duì)于更高次數(shù)的代數(shù)方程目前仍的代數(shù)方程目前仍無(wú)有效的精確解法無(wú)有效的精確解法;對(duì)于無(wú)規(guī)律的非代數(shù)方程的求解也無(wú)精確解法對(duì)于無(wú)規(guī)律的非代數(shù)方程的求解也無(wú)精確解法.因此因此, 研究非線性方程的數(shù)值解法成為必然研究非線性方程的數(shù)值解法成為必然.()0fx 本節(jié)主要研究單根區(qū)間上方程求根的各種近似算法本節(jié)主要研究單根區(qū)間上方程求根的各種近似算法.2 2 方程求根方程求根引言引言 4320 xaxbxc 2323231 / 33 / 21123329279540(|);sgn()()32cos(),3arccos(/) ;322cos(),3342cos(),33AaxBaabaa

3、bcAand Bif BAobtainw hereBABelsewxAaxAaxAhereBA 令令求根公式求根公式5本章討論非線性方程本章討論非線性方程 的求根問(wèn)題，的求根問(wèn)題，( )0f x 1110( )(0)nnnnnf xa xaxa xaa1. 1. 其中一類特殊的問(wèn)題就是多項(xiàng)式方程的求根。其中一類特殊的問(wèn)題就是多項(xiàng)式方程的求根。 2. 2. 另一類就是超越方程的求根。另一類就是超越方程的求根。 ( )( ) 10cos x cosh x 6 方程 的根 又稱為 的零點(diǎn),它使若 , 可表示為 ，其中 為正整數(shù)，且 。 當(dāng) 時(shí)，稱 為單根，若 稱 為 的 重根，或 的 重零點(diǎn)。 若

4、是 的 重零點(diǎn)且 充分光滑，則( )0f x ( )0f x *x( )f x*()0f x*()0f x*( )()( )mf xxxg xm*()0g x1m *x1m *xm( )f x( )f x*(1)*()*()()()0,()0mmf xfxfxfxm*xm( )g x( )f x( )f x基本概念基本概念7求求 f (x) = 0 的根的根原理：原理：若若 f Ca, b，且，且 f (a) f (b) 0，則，則 f 在在 (a, b) 上必有一根。上必有一根。2.1 2.1 二分法二分法 yxbaf (x)x*稱 為方程的有根區(qū)間。 , a b8 給定有根區(qū)間給定有根區(qū)間

5、 a, b ( f(a) f(b) 0) 和和 精度精度 或或 1. 令令 x = (a+b)/22. 如果如果 b a 或或 f (x) , 停機(jī)，輸出停機(jī)，輸出 x3. 如果如果 f (a) f (x) 0 , 則令則令 b = x，否則令，否則令 a = x, 返回第返回第1步步用二分法求根，通常先給出用二分法求根，通常先給出 f (x) 草圖以確定根的大概位置。草圖以確定根的大概位置。 2.1 2.1 二分法二分法算法構(gòu)造算法構(gòu)造abx1x2abx*9記記 a1 = a, b1 = b, 第第 k 步的有根區(qū)間為步的有根區(qū)間為 ak , bk 11224kkkkkkkbababaxxx

6、 112kba對(duì)于給定的精度對(duì)于給定的精度 ,可估計(jì)二分法所需的步數(shù)可估計(jì)二分法所需的步數(shù) k ：2kba2log,bak取取2logbak 簡(jiǎn)單易用簡(jiǎn)單易用 無(wú)法求復(fù)根及偶重根無(wú)法求復(fù)根及偶重根 對(duì)對(duì) f (x) 要求不高，只要連續(xù)即可收斂要求不高，只要連續(xù)即可收斂 收斂速度慢收斂速度慢 2.1 2.1 二分法二分法誤差分析誤差分析10 例例1: 用二分法求方程用二分法求方程 在區(qū)間在區(qū)間(1,2)內(nèi)內(nèi) 的實(shí)根的實(shí)根, 要求誤差限為要求誤差限為 。01523 xx2102.1 2.1 二分法二分法例題分析例題分析11.11.21.31.41.51.61.71.81.92-4-3-2-1012

7、3453( )251f xxx11 解：令解：令 f (1)0 記記 I0=1,2 , x0 =(1+2)/2=1.5 因?yàn)橐驗(yàn)?f (x0) f (1)0 得得 I1=1.5, 2 , x1 =(1.5+2)/2=1.75 f (x1) f (1.5)0 得得 I2=1.5, 1.75 , x2 =(1.5+1.75)/2=1.625 . I6=1.681875, 1.6875, I7=1.671875, 1.679688 b7 - a7=0.7813 10-2 10-2 x* x7 =1.6758 例例1: 用二分法求方程用二分法求方程 在區(qū)間在區(qū)間(1,2)內(nèi)內(nèi) 的實(shí)根的實(shí)根, 要求誤差

8、限為要求誤差限為 。01523 xx210152)(3xxxf2.1 2.1 二分法二分法例題分析例題分析12例例2：求求 在在 (1, 1.5) 的實(shí)根的實(shí)根,要求誤差不超過(guò)要求誤差不超過(guò)0.005。3()10fxxx 2.1 2.1 二分法二分法算法步驟算法步驟11.051.11.151.21.251.31.351.41.451.5-1-0.8-0.6-0.4-0.200.20.40.60.813( )10f xxx 13例例2：求求 在在 (1, 1.5) 的實(shí)根的實(shí)根,要求誤差不超過(guò)要求誤差不超過(guò)0.005。3()10fxxx STEP 0輸入輸入 a, b, eps, delta ,

9、 fa=f (a) , fb=f (b)STEP 1 x=(a+b)/2 , fx=f (x)STEP 2 判斷：判斷：|b-a|eps or | f x | delta 若是，若是，goto step 4 ;否則，執(zhí)行下一步否則，執(zhí)行下一步STEP 3 若若 fb*fx0,則則 a=x 否則否則 b=x. goto step 1STEP 4 輸出輸出 x, fx, 停機(jī)停機(jī).2.1 2.1 二分法二分法算法步驟算法步驟14function xvect,xdif,fx,nit=bisect(a,b,toll,nmax,fun)err=toll+1; nit=0; xvect=; fx=; xd

10、if=;while (nit toll) nit=nit+1; c=(a+b)/2; x=c; fc=feval(fun,x); xvect=xvect;x; fx=fx;fc; x=a; if (fc*feval(fun,x) 0) a=c; else b=c; end; err=abs(b-a); xdif=xdif;err;endreturn fun=inline(2*x.3-5*x-1); xvect,xdif,fx,nit=bisect(1,2,0.01,50,fun)x值 區(qū)間長(zhǎng) 函數(shù)值 1.2500 0.2500 -0.29691.3750 0.1250 0.22461.3125

11、 0.0625 -0.05151.3438 0.0313 0.08261.3281 0.0156 0.01461.3203 0.0078 -0.01871.3242 0.0039 -0.002115abab1kkxx( )f x或或不能保證不能保證 x 的精的精度度x*xx*程序算法說(shuō)明程序算法說(shuō)明: :16f (x) = 0 等價(jià)變換等價(jià)變換f (x) 的根的根 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn)()xx ()x 2.2 2.2 方程求根方程求根不動(dòng)點(diǎn)迭代法不動(dòng)點(diǎn)迭代法基本原理基本原理00.20.40.60.811.21.41.61.8201020304050606()xfex 32371gxx fg 323

12、71 6(0)xxxex 17f (x) = 0 等價(jià)變換等價(jià)變換f (x) 的根的根 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn)思路思路從一個(gè)初值從一個(gè)初值 x0 出發(fā)，計(jì)算出發(fā)，計(jì)算 x1 = (x0), x2 = (x1), , xk+1 = (xk), 若若 收斂，即存在收斂，即存在 x* 使得使得 ，且，且 連續(xù)，則由連續(xù)，則由 可知可知 x* = (x* )，即，即x* 是是 的不動(dòng)點(diǎn)，也就是的不動(dòng)點(diǎn)，也就是 f 的根。的根。 0kkx*limxxkk 1limlimkkkkxx ()xx ()x 2.2 2.2 方程求根方程求根不動(dòng)點(diǎn)迭代法不動(dòng)點(diǎn)迭代法基本原理基本原理18 將將 轉(zhuǎn)化為轉(zhuǎn)化為 的方法有多種

13、多樣，的方法有多種多樣，例：例： 在在 上可有以下方法：上可有以下方法： (1) (1) (2) (2) (3) (3) (4) (4)取取 , ,有的收斂、有的發(fā)散、有的快、有的慢。有的收斂、有的發(fā)散、有的快、有的慢。( )0f x ( )xx32( )4100f xxx1,232410 xxxx3 1/2(1/2)(10)xx1/2(10/4 )xxx1/210/(4)xx01.5x 19xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1 201

14、23xx將原方程化為等價(jià)方程將原方程化為等價(jià)方程12301xx112312xx312323xx552.2 2.2 迭代法迭代法算例分析算例分析3210 xx例如例如: : 用迭代法求解方程用迭代法求解方程解解1:1:00 x取初值取初值顯然迭代法發(fā)散顯然迭代法發(fā)散2100 x30121xx仍取初值仍取初值3217937.031221xx327937.19644.0 x2 = 0.9644x3 = 0.9940 x4 = 0.9990 x5 = 0.9998x6 = 1.0000 x7 = 1.0000依此類推依此類推, ,得得已經(jīng)收斂已經(jīng)收斂, ,故原方程的解為故原方程的解為0000.1x同樣

15、的方程同樣的方程不同的迭代格式不同的迭代格式有不同的結(jié)果有不同的結(jié)果什么形式的迭代法什么形式的迭代法能夠收斂呢能夠收斂呢? ?迭代函數(shù)的構(gòu)造有關(guān)迭代函數(shù)的構(gòu)造有關(guān)312xx (2) (2) 如果將原方程化為等價(jià)方程如果將原方程化為等價(jià)方程3210 xx22例如：求方程 在 附近的根3( )10f xxx 01.5x *x2.2 2.2 迭代法迭代法算例分析算例分析2 223解：將方程改寫(xiě)為解：將方程改寫(xiě)為 ， 由此建立迭代公式：由此建立迭代公式： 計(jì)算結(jié)果如下表計(jì)算結(jié)果如下表例如：求方程 在 附近的根3( )10f xxx 01.5x *x311(0,1,2,)kkxxk0 01 12 23

16、34 45 56 67 78 81.51.5 1.357211.35721 1.330861.33086 1.325881.32588 1.324941.32494 1.324761.32476 1.324731.32473 1.324721.32472 1.324721.32472kxk31xx2.2 2.2 迭代法迭代法算例分析算例分析2 2這是一個(gè)收斂的不動(dòng)點(diǎn)迭代格式這是一個(gè)收斂的不動(dòng)點(diǎn)迭代格式. .24也有不收斂的迭代公式，如對(duì)于同樣的問(wèn)題，如果將方程改也有不收斂的迭代公式，如對(duì)于同樣的問(wèn)題，如果將方程改寫(xiě)為令一種迭代公式寫(xiě)為令一種迭代公式 ，仍取初值，仍取初值 ，則迭代，則迭代發(fā)散。

17、發(fā)散。 為此，需要研究為此，需要研究 的存在性及迭代法的收斂性。的存在性及迭代法的收斂性。例如：求方程 在 附近的根3( )10f xxx 01.5x *x31xx01.5x ( )xx2.2 2.2 迭代法迭代法算例分析算例分析2 225 設(shè)設(shè) 滿足以下兩個(gè)條件：滿足以下兩個(gè)條件：(1) (1) 對(duì)任意的對(duì)任意的 ，有，有 (2) (2) 存在存在 ，使對(duì)任意，使對(duì)任意 都有都有則則 在在 上存在唯一的不動(dòng)點(diǎn)上存在唯一的不動(dòng)點(diǎn) 。2.2 2.2 方程求根方程求根迭代法的收斂性迭代法的收斂性定理定理( (存在性存在性) ) , xa b( )axb01L, , x yC a b( )( )xy

18、L xy( ) x*x , a b( ) , xC a b26證明：證明：先證不動(dòng)點(diǎn)的存在性。若先證不動(dòng)點(diǎn)的存在性。若 或或 ，則則 或或 就是不動(dòng)點(diǎn)。就是不動(dòng)點(diǎn)。 因此由因此由 可設(shè)可設(shè) 及及 ， 定義函數(shù)定義函數(shù) ，顯然，顯然 且滿足且滿足 由函數(shù)的連續(xù)性可知由函數(shù)的連續(xù)性可知, , 存在存在 使使 ，即即 ， 即為即為 的不動(dòng)點(diǎn)。的不動(dòng)點(diǎn)。2.2 2.2 方程求根方程求根迭代法的收斂性迭代法的收斂性*x( )aa( )bbab( )axb( )aa( )bb( )( )f xxx( )( )0,( )( )0f aaaf bbb( ) , f xC a b*( , )xa b*()0f

19、x*x( ) x27再證唯一性。設(shè)再證唯一性。設(shè) 及及 都是都是 的不動(dòng)點(diǎn)，的不動(dòng)點(diǎn)，則由定理的條件則由定理的條件(2)(2)，得到，得到矛盾，故矛盾，故 的不動(dòng)點(diǎn)是唯一的。的不動(dòng)點(diǎn)是唯一的。 證畢證畢*1x*2 , xa b( ) x*12121212()()xxxxL xxxx( ) x28定理定理2 2：( (收斂的充分條件收斂的充分條件) ) 設(shè)設(shè) 滿足定理滿足定理1 1的兩個(gè)條件，則對(duì)任意的兩個(gè)條件，則對(duì)任意 ，由，由 得到的迭代序列得到的迭代序列 收斂到收斂到 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn) ，并有誤差估計(jì)，并有誤差估計(jì)( ) , xC a b0 , xa b1()kkxx kx*x( ) x*

20、101kkLxxxxL29證明：設(shè)證明：設(shè) 是是 在在 上的唯一不動(dòng)點(diǎn)，由條上的唯一不動(dòng)點(diǎn)，由條件件1 1可知可知 ，再由條件，再由條件2 2得得因因 ，故當(dāng)，故當(dāng) 時(shí)，序列時(shí)，序列 收斂到收斂到 。由迭代公式可得由迭代公式可得據(jù)此反復(fù)遞推，得到據(jù)此反復(fù)遞推，得到于是對(duì)任意正整數(shù)，有于是對(duì)任意正整數(shù)，有在上式令在上式令 ，注意到，注意到 即得到結(jié)果。證畢即得到結(jié)果。證畢111()()kkkkkkxxxxL xx110kkkxxL xx1121121010()1kpkkpkpkpkpkkkpkpkkxxxxxxxxLLLxxLxxLp *limkppxx* , xa b( ) x , a b ,

21、 kxa b*110()()kkkkxxxxL xxL xx01Lk kx*x30 根據(jù)定理根據(jù)定理2 2的結(jié)論，對(duì)于給定的計(jì)算精度，迭代次數(shù)是可以的結(jié)論，對(duì)于給定的計(jì)算精度，迭代次數(shù)是可以預(yù)先確定的，但由于公式中含有常數(shù)預(yù)先確定的，但由于公式中含有常數(shù) ，使得計(jì)算迭代次數(shù)，使得計(jì)算迭代次數(shù)較為復(fù)雜，根據(jù)估計(jì)式較為復(fù)雜，根據(jù)估計(jì)式我們得到：我們得到：令令 ，得到，得到由此可知，只要相鄰兩次計(jì)算結(jié)果的偏差由此可知，只要相鄰兩次計(jì)算結(jié)果的偏差 足夠小即可足夠小即可保證近似值保證近似值 有足夠的精度。有足夠的精度。111()()kkkkkkxxxxL xxL112112111(1)1k pkk pk

22、 pk pk pkkppkkkkxxxxxxxxLLxxxxL p*111kkkxxxxL1kkxxkx31 對(duì)于定理中的條件對(duì)于定理中的條件2 2，在實(shí)際使用時(shí)，如，在實(shí)際使用時(shí)，如果果 且對(duì)任意的且對(duì)任意的 有有則由中值定理可知?jiǎng)t由中值定理可知 有有它表明定理中條件它表明定理中條件2 2可由可由 替代替代。1( ) , xC a b , xa b( )1xL, , x ya b( )( )( )(),( , )xyxyL xya b ( )1xL32迭代法迭代法 就收斂就收斂, 即要求即要求定理指出定理指出,1|)(|Lx11kkxxLL只要只要因此因此, ,當(dāng)當(dāng)LLxxkk11迭代就可以

23、終止迭代就可以終止, ,kx只要構(gòu)造的迭代函數(shù)滿足只要構(gòu)造的迭代函數(shù)滿足1()kkxx|*|kxx此時(shí)雖收斂此時(shí)雖收斂但不一定是唯一根但不一定是唯一根對(duì)于預(yù)先給定的誤差對(duì)于預(yù)先給定的誤差 可以作為方程的近似解可以作為方程的近似解33由于由于因此因此 為有根區(qū)間為有根區(qū)間由于由于 則則用迭代法求方程的近似解用迭代法求方程的近似解, ,精確到小數(shù)點(diǎn)后精確到小數(shù)點(diǎn)后6 6位位0210 xex本題迭代函數(shù)有兩種構(gòu)造形式本題迭代函數(shù)有兩種構(gòu)造形式102)(1xexx)102ln()(2xxx1|( ) |x10 xe2|( ) |x10210 x0,xe 2100 x2 .0 x0.2110e102)(

24、1xexx因此采用迭代函數(shù)因此采用迭代函數(shù)0,x ,10 xe2102x0,0.2 5例如例如: :解解: :時(shí)時(shí)2.2 2.2 迭代法迭代法算例分析算例分析3 334取初值取初值 00 x 10201xex1 .0d1 = 0.1000000d2 = -0.0105171d3 = 0.1156e-002d4 = -0.1265e-003d5 = 0.1390e-004d6 = -0.1500e-005d7 = 0.1000e-006由于由于|d7| =0.1000e-0061e-6因此原方程的解為因此原方程的解為x7 = 0.090525*xx1 = 0.1000000 x2 = 0.089

25、4829x3 = 0.0906391x4 = 0.0905126x5 = 0.0905265x6 = 0.0905250 x7 = 0.09052511020 xex1()(2) /10kxkkxxe35定義定義 設(shè)迭代過(guò)程設(shè)迭代過(guò)程 收斂于方程收斂于方程 的根的根 ，如果迭代誤差，如果迭代誤差 , ,當(dāng)當(dāng) 時(shí)時(shí) 成立下列漸進(jìn)關(guān)系式成立下列漸進(jìn)關(guān)系式則稱該迭代過(guò)程是則稱該迭代過(guò)程是 階收斂的階收斂的. .特別地，特別地， 時(shí)稱線性收斂，時(shí)稱線性收斂， 時(shí)稱超線性收斂，時(shí)稱超線性收斂， 時(shí)稱平方收斂時(shí)稱平方收斂。2.2 2.2 迭代法的收斂速度迭代法的收斂速度( )xx*x*kkxxk 1(0)

26、kpkCp1p 1p 2p 1()kkxx36 定義定義1 1：設(shè)：設(shè) 有不動(dòng)點(diǎn)有不動(dòng)點(diǎn) ，如果存在，如果存在 的某個(gè)領(lǐng)的某個(gè)領(lǐng)域域 ，對(duì)任意，對(duì)任意 ，迭代公式，迭代公式 產(chǎn)生的序列產(chǎn)生的序列 收斂到收斂到 ，則稱該迭代法局部收，則稱該迭代法局部收斂。斂。 ( ) x*x*x*:Rxx0 xR1()kkxx kxR*x局部收斂性局部收斂性37 設(shè)設(shè) 為為 的不動(dòng)點(diǎn)，的不動(dòng)點(diǎn)， 在在 的某個(gè)的某個(gè)鄰域連續(xù)，且鄰域連續(xù)，且 ，則迭代法，則迭代法 收斂。收斂。*x( ) x( ) x*()1x1()kkxx*x定理定理: :38 設(shè)設(shè) 為為 的不動(dòng)點(diǎn)，的不動(dòng)點(diǎn)， 在在 的某個(gè)的某個(gè)領(lǐng)域連續(xù)，且領(lǐng)域

27、連續(xù)，且 ，則迭代法，則迭代法 收斂。收斂。證明：由連續(xù)函數(shù)的性質(zhì)，存在證明：由連續(xù)函數(shù)的性質(zhì)，存在 的某個(gè)領(lǐng)域的某個(gè)領(lǐng)域 ，使對(duì)任意，使對(duì)任意 成立成立 ，此外，對(duì)于任意此外，對(duì)于任意 ，總有，總有 ，這是因?yàn)檫@是因?yàn)橛谑强蓴喽ǖ^(guò)程對(duì)于任意的初值收斂于是可斷定迭代過(guò)程對(duì)于任意的初值收斂. .*x( ) x( ) x*()1x1()kkxx*x*:RxxxR( )1xLxR( )xR*( )( )()xxxxL xxxxxR定理定理: :39全局收斂與局部收斂全局收斂與局部收斂p 定理的條件保證了不動(dòng)點(diǎn)迭代的定理的條件保證了不動(dòng)點(diǎn)迭代的全局收斂性全局收斂性。即迭代的收斂性與初始點(diǎn)的選取無(wú)關(guān)

28、。即迭代的收斂性與初始點(diǎn)的選取無(wú)關(guān)。p 這種在這種在 x* 的鄰域內(nèi)具有的收斂性稱為的鄰域內(nèi)具有的收斂性稱為局部收斂性局部收斂性。定理中的條件定理中的條件 | (x) | L 1 可以適當(dāng)放寬可以適當(dāng)放寬(2) (x) 在在 x* 的某個(gè)鄰域內(nèi)連續(xù)，且的某個(gè)鄰域內(nèi)連續(xù)，且 | (x*) | 1由由 (x) 的連續(xù)性及的連續(xù)性及 | (x*) | 1 即可推出：即可推出：存在存在 x* 的的某個(gè)某個(gè) 鄰域鄰域 N(x*) =x*- , x* + , 使得對(duì)使得對(duì) x N(x*)都有都有| (x) | L 1, 則由則由 x0 N(x*) 開(kāi)始開(kāi)始的迭代都收斂。的迭代都收斂。40 對(duì)于迭代過(guò)程對(duì)于

29、迭代過(guò)程 ，如果，如果 在根在根 的鄰近連續(xù)，并且的鄰近連續(xù)，并且 (1)(1)則該迭代過(guò)程在點(diǎn)則該迭代過(guò)程在點(diǎn) 鄰近是鄰近是 階收斂的。階收斂的。 *(1)*()*()()()0,()0ppxxxx*x1()kkxx*x( )( )pxxp定理定理41 注意到注意到 由上式得到由上式得到因此對(duì)迭代誤差，當(dāng)因此對(duì)迭代誤差，當(dāng) 時(shí)有時(shí)有這表明迭代過(guò)程這表明迭代過(guò)程 確實(shí)為確實(shí)為 階收斂。證畢階收斂。證畢 由于由于 ，可以斷定迭代過(guò)程，可以斷定迭代過(guò)程 具有局部收斂性。具有局部收斂性。 再將再將 在根在根 處做泰勒展開(kāi)，得到處做泰勒展開(kāi)，得到*x*()0 x1()kkxx()kx證明證明: :(

30、)*( )()()() ,!ppkkxxxxpkx*x1(),kkxx*(),xx( )*1( )()!ppkkxxxxpk ( )*1()!pkpkxp1()kkxxp在在 與與 之間，之間，422.3 牛頓牛頓(Newton)法法第第1 1節(jié)節(jié) 牛頓法的基本思想牛頓法的基本思想第第2節(jié)節(jié) 牛頓法的收斂速度牛頓法的收斂速度第第3節(jié)節(jié) 牛頓下山法牛頓下山法第第4節(jié)節(jié) 算例分析算例分析43取取 x0 x*，將將 f (x)在在 x0 做一階做一階Taylor展開(kāi)展開(kāi):20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x 之間。之間。將將 (x* x0)2 看成高階

31、小量，則有：看成高階小量，則有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx 1()()kkkkf xxxfx 1.1.原理：原理：將非線性方程將非線性方程 ( )0f x 逐步線性化而形成迭代公式逐步線性化而形成迭代公式. 2.3 Newton2.3 Newton迭代法迭代法基本思想基本思想44xyx*x0)()(1kkkkxfxfxx 只要只要 f C 1，每一步迭代都有，每一步迭代都有 f ( xk ) 0， 而且而且 ，則，則 x* 就是就是 f 的根。的根。*limxxkk 000()*()f xxxfx 2. 2. 牛頓法牛頓法幾何意義幾何意義45牛

32、頓迭代法牛頓迭代法1: 初始化初始化. x0 , M,置置i:=02: 如果如果| f(xi ) | ，則停止，則停止. 3: 計(jì)算計(jì)算 xi+1:=xi - f (xi) / f (xi)4: 如果如果|xi+1-xi| or | f (xi) | ，則停止，則停止.5: i:=i+1, 轉(zhuǎn)至轉(zhuǎn)至3.1()()iiiif xxxfx 3. 3. 牛頓法的算法構(gòu)造牛頓法的算法構(gòu)造46例例1： 利用牛頓迭代法求解利用牛頓迭代法求解 f(x)=ex-1.5-tan-1x 的零點(diǎn)。的零點(diǎn)。初始點(diǎn)初始點(diǎn)x0=-7.0 47例例1： 利用牛頓迭代法求解利用牛頓迭代法求解 f(x)=ex-1.5-tan-

33、1x 的零點(diǎn)。的零點(diǎn)。初始點(diǎn)初始點(diǎn)x0=-7.0 解：解： f (x0)=-0.70210-1，f (x)=ex-(1+x2)-1 計(jì)算迭代格式計(jì)算迭代格式: 計(jì)算結(jié)果如下表：計(jì)算結(jié)果如下表：(取取|f(x) |=10-10)k x f (x) 0 -7.0000 -0.07018881 -10.6771 -0.02256662 -13.2792 -0.004366023 -14.0537 -0.000239024 -14.1011 -7.99585e-0075 -14.1013 -9.00833e-0121()()kkkkf xxxfx NewtonMethod_PPT45NewtonMet

34、hod_PPT4548Newtons Method 收斂性依賴于收斂性依賴于x0 的選取。的選取。x*x0 x0 x0算法說(shuō)明算法說(shuō)明: :49設(shè)設(shè) f C2a, b，若，若(1) f (a) f (b) 0； 則則Newtons Method產(chǎn)生的序列產(chǎn)生的序列 xk 收斂到收斂到f (x) 在在 a, b 的唯一根。的唯一根。有根有根根唯一根唯一產(chǎn)生的序列單調(diào)有產(chǎn)生的序列單調(diào)有界，保證收斂。界，保證收斂。Newton Method收斂的充分條件收斂的充分條件50 設(shè)設(shè) f C2a, b，若，若 x* 為為 f (x) 在在a, b上的根，上的根，且且 ，則存在，則存在 x* 的鄰域的鄰域

35、, 使得任取使得任取初值初值 , Newtons Method產(chǎn)生的序列產(chǎn)生的序列 xk 收斂收斂到到x*，且滿足，且滿足*)(xB *)(0 xBx 12*( *)lim(*)2( *)kkkxxfxxxfx 定理定理*()0fx Newton Method局部局部收斂性收斂性51證明：證明：Newtons Method 事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代 其中其中 ，則，則)()()(xfxfxxg 10*)(*)(*)(*)(2xfxfxfxg收斂收斂由由 Taylor 展開(kāi)：展開(kāi)：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(!

36、 2)()()(*kkkkkkxxxffxfxfxx 1 kx)(2)()*(*21kkkkxffxxxx 只要只要 f (x*) 0，則令，則令 可得結(jié)論?？傻媒Y(jié)論。 k 52 割線法割線法Newtons Method 一步要計(jì)算一步要計(jì)算 f 和和 f ，相當(dāng)于，相當(dāng)于2個(gè)函數(shù)值，個(gè)函數(shù)值，比較費(fèi)時(shí)?，F(xiàn)用比較費(fèi)時(shí)?，F(xiàn)用 f 的值近似的值近似 f ，可少算一個(gè)函數(shù)值。，可少算一個(gè)函數(shù)值。x0 x1切線切線 割線割線 切線斜率切線斜率 割線斜率割線斜率11)()()( kkkkkxxxfxfxf)()()(111 kkkkkkkxfxfxxxfxx需要需要2個(gè)初值個(gè)初值 x0 和和 x1。收斂

37、比收斂比Newtons Method 慢，且對(duì)初值要求同樣高。慢，且對(duì)初值要求同樣高。53 下山法下山法 Newtons Method 局部微調(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ì)算。減半

38、計(jì)算。542.4 2.4 迭代過(guò)程的加速方法迭代過(guò)程的加速方法 有的迭代過(guò)程雖然收斂，但速度很慢，因此迭代過(guò)有的迭代過(guò)程雖然收斂，但速度很慢，因此迭代過(guò)程的加速是一個(gè)重要課題。程的加速是一個(gè)重要課題。p 二分法線性收斂二分法線性收斂p 不動(dòng)點(diǎn)迭代中不動(dòng)點(diǎn)迭代中，若若 (x*) 0，則，則11*()( *)( )kkkkexxxxe取極限得取極限得1|lim|( *) |0|krkkexe線性收斂線性收斂例如例如: :55 設(shè)設(shè) 是根是根 的某個(gè)近似值，用迭代公式校正一次的某個(gè)近似值，用迭代公式校正一次得得 ，而由微分中值定理，有，而由微分中值定理，有其中其中 介于介于 與與 之間。之間。2.4

39、 2.4 迭代過(guò)程的加速方法迭代過(guò)程的加速方法假設(shè)假設(shè) 改變不大，近似地取某個(gè)改變不大，近似地取某個(gè) ，則有，則有若將校正值若將校正值 再校正一次，又得再校正一次，又得0 x*x10()xx*100()()( )()xxxxxx *x0 x( )xL*10()xxL xx10()xx*21()xxL xx埃特金加速收斂方法埃特金加速收斂方法56在兩式中消去在兩式中消去 ，得到，得到由此推得：由此推得：L*01*21xxxxxxxx22*021100210210()22x xxxxxxxxxxxx在計(jì)算了在計(jì)算了 及及 之后，可用上式右端作為之后，可用上式右端作為 的新近似的新近似記作記作 ，一般情形是由，一般情形是由 計(jì)算計(jì)算 ， ，記，記該方法稱為該方法稱為埃特金加速方法埃特金加速方法。 1x2x*x1xkx1kx2kx2221112()() /(0,1,)2kkkkkkkkkkxxxxxxxk