數(shù)值計(jì)算方法第二章

1、數(shù)值計(jì)算方法數(shù)值計(jì)算方法第二章第二章非線性方程的數(shù)值解法非線性方程的數(shù)值解法 計(jì)算機(jī)與通信工程學(xué)院2本章內(nèi)容安排本章內(nèi)容安排n在實(shí)際中許多方程問題無(wú)法求出公式解在實(shí)際中許多方程問題無(wú)法求出公式解 nn次代數(shù)方程次代數(shù)方程n超越方程超越方程 n需要引進(jìn)能夠達(dá)到一定精度要求的求方程近似需要引進(jìn)能夠達(dá)到一定精度要求的求方程近似值的方法值的方法 0tg xx0sin8889. 4tg25. 0 xx計(jì)算機(jī)與通信工程學(xué)院3本章內(nèi)容安排本章內(nèi)容安排n2.1 初始近似值的搜索初始近似值的搜索n2.2 二分法二分法n2.3 迭代法迭代法n2.4 牛頓迭代法牛頓迭代法n2.5 弦截法弦截法計(jì)算機(jī)與通信工程學(xué)院4

2、2.1 初始近似值的搜索初始近似值的搜索n方程的根方程的根n逐步掃描法逐步掃描法計(jì)算機(jī)與通信工程學(xué)院5方程的根方程的根n代數(shù)方程代數(shù)方程 n對(duì)于一元非線性方程對(duì)于一元非線性方程 f (x)=0 ,如果如果f (x) 為代數(shù)多項(xiàng)為代數(shù)多項(xiàng)式式 則稱則稱f (x)=0 為代數(shù)方程為代數(shù)方程 n超越方程超越方程 n超越方程包括指數(shù)方程、對(duì)數(shù)方程和三角方程等超越方程包括指數(shù)方程、對(duì)數(shù)方程和三角方程等 n方程的根方程的根0111.axaxaxannnn計(jì)算機(jī)與通信工程學(xué)院6方程的根方程的根n如果存在如果存在x*使使f (x*)=0 ，則稱，則稱x*是方程的解或根，是方程的解或根，也稱也稱x*是函數(shù)是函數(shù)

3、f (x) 的零點(diǎn)或根的零點(diǎn)或根n重根重根n如果函數(shù)如果函數(shù) f (x) 可分解為可分解為 其中其中m是大于是大于1的正整數(shù)，則稱的正整數(shù)，則稱x*是方程是方程f (x)=0 的的m重根重根 n重根的判斷條件重根的判斷條件n設(shè)函數(shù)設(shè)函數(shù)f (x) 有有m階連續(xù)導(dǎo)數(shù)，方程階連續(xù)導(dǎo)數(shù)，方程f (x)=0 有有m重根重根x*的充要條件是的充要條件是0*)(),(*)()(xgxgxxxfm計(jì)算機(jī)與通信工程學(xué)院7方程的根方程的根n例例2.1.1：求：求x=0是方程是方程 的幾重的幾重根？根？n解：解：因此，因此，x=0是是 的三重根的三重根0*)(, 0*)(.*)( *)()() 1(xfxfxfx

4、fmm0221)(22xxexfx0)0(,221)(22fxxexfx0) 0( ,422)( 2fxexfx0)0( , 44)( 2fexfx08)0( ,8)( 2fexfx0221)(22xxexfx計(jì)算機(jī)與通信工程學(xué)院8方程的根方程的根n方程求根需要解決的問題方程求根需要解決的問題n根的存在性：方程是否有根，如果有根，有幾個(gè)根？根的存在性：方程是否有根，如果有根，有幾個(gè)根？ n根的隔離：找出有根區(qū)間，把有根區(qū)間分成較小的根的隔離：找出有根區(qū)間，把有根區(qū)間分成較小的子區(qū)間，每個(gè)子區(qū)間有一個(gè)根，將有根區(qū)間內(nèi)的任子區(qū)間，每個(gè)子區(qū)間有一個(gè)根，將有根區(qū)間內(nèi)的任一點(diǎn)都看成該根的一個(gè)初始近似值一

5、點(diǎn)都看成該根的一個(gè)初始近似值n根的精確化：對(duì)已知根的初始近似值，逐步精確化根的精確化：對(duì)已知根的初始近似值，逐步精確化 n求根的步驟求根的步驟n判斷根是否存在，若存在，確定根的某個(gè)初始近似判斷根是否存在，若存在，確定根的某個(gè)初始近似值值 計(jì)算機(jī)與通信工程學(xué)院9方程的根方程的根n將初始近似值逐步加工成滿足精度要求的結(jié)果將初始近似值逐步加工成滿足精度要求的結(jié)果 n有根區(qū)間有根區(qū)間 n如果方程在區(qū)間如果方程在區(qū)間a, b內(nèi)至少有一個(gè)根，則稱內(nèi)至少有一個(gè)根，則稱a, b為為有根區(qū)間有根區(qū)間 n隔根區(qū)間隔根區(qū)間n如果方程在區(qū)間如果方程在區(qū)間a, b內(nèi)恰有一個(gè)根，則稱內(nèi)恰有一個(gè)根，則稱a, b為隔為隔根區(qū)

6、間根區(qū)間 n根的隔離根的隔離n尋找隔根區(qū)間尋找隔根區(qū)間a, b的步驟，叫做根的隔離的步驟，叫做根的隔離 計(jì)算機(jī)與通信工程學(xué)院10方程的根方程的根n定理定理2.1：設(shè)函數(shù)：設(shè)函數(shù)f (x)在區(qū)間在區(qū)間a, b上連續(xù)，如果上連續(xù)，如果f (a) f (b) 0，則方程，則方程f (x) = 0在在a, b內(nèi)至少有內(nèi)至少有一實(shí)根一實(shí)根x* n定理定理2.2：設(shè)函數(shù)：設(shè)函數(shù)f (x)在區(qū)間在區(qū)間a, b上是單調(diào)連續(xù)上是單調(diào)連續(xù)函數(shù)，并且函數(shù)，并且f (a) f (b) 0，則方程，則方程f (x) = 0在在a, b上有且僅有一實(shí)根上有且僅有一實(shí)根x* 計(jì)算機(jī)與通信工程學(xué)院11方程的根方程的根n尋找有

7、根區(qū)間（隔根區(qū)間）的方法尋找有根區(qū)間（隔根區(qū)間）的方法n畫圖法畫圖法n逐步掃描法逐步掃描法abx*f(x)0 xhx 0計(jì)算機(jī)與通信工程學(xué)院12逐步掃描法逐步掃描法n實(shí)現(xiàn)步驟實(shí)現(xiàn)步驟 n設(shè)單值連續(xù)函數(shù)設(shè)單值連續(xù)函數(shù)f(x)在有根區(qū)間在有根區(qū)間a, b，從左端點(diǎn)，從左端點(diǎn)x = a出發(fā)，按某個(gè)預(yù)先選定的步長(zhǎng)出發(fā)，按某個(gè)預(yù)先選定的步長(zhǎng)h一步一步地向右跨一步一步地向右跨 n每跨一步都檢驗(yàn)每步起點(diǎn)每跨一步都檢驗(yàn)每步起點(diǎn)x0和終點(diǎn)和終點(diǎn)x0 + h的函數(shù)值的函數(shù)值n如果如果 那么所求的根那么所求的根x*必在必在x0與與x0+h之間之間 0)()(00hxfxf計(jì)算機(jī)與通信工程學(xué)院13逐步掃描法逐步掃描法

8、n例例2.1.2：考察方程：考察方程 利用逐步掃描法確定一個(gè)有根區(qū)間利用逐步掃描法確定一個(gè)有根區(qū)間 n解：注意到解：注意到f (0) 0，知，知f (x)至少有一個(gè)至少有一個(gè)正的實(shí)根正的實(shí)根 設(shè)從設(shè)從x = 0出發(fā)，取出發(fā)，取h = 0.5為步長(zhǎng)向右進(jìn)行根的掃描為步長(zhǎng)向右進(jìn)行根的掃描 因此在區(qū)間（因此在區(qū)間（1, 1.5）內(nèi)必有實(shí)根）內(nèi)必有實(shí)根 01)(3xxxfx00.51.01.5f (x) 的符號(hào)的符號(hào)計(jì)算機(jī)與通信工程學(xué)院142. 2 二分法二分法n二分法的基本思想二分法的基本思想n首先，假定方程首先，假定方程f (x) = 0在區(qū)間在區(qū)間a, b內(nèi)有唯一的實(shí)內(nèi)有唯一的實(shí)根根x*n就是將

9、方程根所在的區(qū)間平分為兩個(gè)小區(qū)間，判斷就是將方程根所在的區(qū)間平分為兩個(gè)小區(qū)間，判斷根屬于哪個(gè)小區(qū)間；把有根的小區(qū)間再平分為二，根屬于哪個(gè)小區(qū)間；把有根的小區(qū)間再平分為二，再判斷根所在的更小的區(qū)間，對(duì)分；重復(fù)這一過程，再判斷根所在的更小的區(qū)間，對(duì)分；重復(fù)這一過程，最后求出所要的近似值最后求出所要的近似值 n二分法的步驟二分法的步驟n1計(jì)算計(jì)算f (x)在有解區(qū)間在有解區(qū)間a, b端點(diǎn)處的函數(shù)值端點(diǎn)處的函數(shù)值 f (a) ，f (b)n2計(jì)算計(jì)算f (x)在區(qū)間中點(diǎn)處的值在區(qū)間中點(diǎn)處的值f (x0) 計(jì)算機(jī)與通信工程學(xué)院152. 2 二分法二分法n3判斷若判斷若f (x0) = 0，則，則 即是根

10、，否則檢驗(yàn)：即是根，否則檢驗(yàn)：n（1）若）若f (x0)與與f (a)異號(hào)，則知根位于區(qū)間異號(hào)，則知根位于區(qū)間a, x0，以，以x0代替代替b；n（2）若）若f (x0)與與f (a)同號(hào)，則知根位于區(qū)間同號(hào)，則知根位于區(qū)間x0, b，x0代代替替a n反復(fù)執(zhí)行步驟反復(fù)執(zhí)行步驟2、3，便可得到一系列有根區(qū)間：，便可得到一系列有根區(qū)間：a, b, a1, b1, , ak, bk, ，其中每個(gè)區(qū)間都是前，其中每個(gè)區(qū)間都是前一個(gè)區(qū)間的一半，因此區(qū)間長(zhǎng)度為一個(gè)區(qū)間的一半，因此區(qū)間長(zhǎng)度為20bax)(21ababkkk計(jì)算機(jī)與通信工程學(xué)院162. 2 二分法二分法n二分法的誤差估計(jì)二分法的誤差估計(jì)n由

11、于由于 只要有根區(qū)間只要有根區(qū)間ak+1, bk+1的長(zhǎng)度小于預(yù)先給定的誤差的長(zhǎng)度小于預(yù)先給定的誤差 ，那么就可以取，那么就可以取 作為所求根作為所求根x*的第的第k+1次近似值。其誤差估計(jì)為次近似值。其誤差估計(jì)為 )(21kkkbax)(211*abxxkk11*)(21kkkkkababxx計(jì)算機(jī)與通信工程學(xué)院172. 2 二分法二分法n例例2.2.1：證明：證明1-x-sinx=0 在在0, 1內(nèi)有一個(gè)根，內(nèi)有一個(gè)根，使用二分法求誤差不大于使用二分法求誤差不大于 的根要二分多少的根要二分多少次？次？n證：令證：令 f(x)=1-x-sinx，f(x) 是連續(xù)函數(shù)是連續(xù)函數(shù) f (x) =

12、-1-cosx, x0,1 f(x)在在0, 1單調(diào)減少單調(diào)減少 又又 f(0)=10 ， f(1)=-sin10 f (1) = -7 0，由定理，由定理2.1知方程知方程在在0, 1中必有一實(shí)根，現(xiàn)將原方程改為同解方程中必有一實(shí)根，現(xiàn)將原方程改為同解方程 由此得迭代格式由此得迭代格式n取初始值取初始值x0 = 1，可逐次算得，可逐次算得 x1 = 0.4771 x2 = 0.3939 0210)(xxxf210 xx)2lg( xx)2lg(1kkxx計(jì)算機(jī)與通信工程學(xué)院30迭代過程的收斂性迭代過程的收斂性 x6 = 0.3758 x7 = 0.3758n因?yàn)橐驗(yàn)閤6和和x7已趨于一致，所

13、以取已趨于一致，所以取x7 = 0.3758為原方程為原方程在在0, 1內(nèi)的一個(gè)根的近似值內(nèi)的一個(gè)根的近似值n一個(gè)方程的迭代格式不唯一，且迭代也不總是收斂一個(gè)方程的迭代格式不唯一，且迭代也不總是收斂的，如上述方程也可改寫成的，如上述方程也可改寫成 得迭代格式得迭代格式 經(jīng)過驗(yàn)證，該迭代公式不收斂經(jīng)過驗(yàn)證，該迭代公式不收斂210 xx2101kxkx計(jì)算機(jī)與通信工程學(xué)院31全局收斂性全局收斂性n定義定義2.1：對(duì)任意初值：對(duì)任意初值 x0 a,b，如果按照迭代，如果按照迭代格式格式xk+1=(xk)生成的序列生成的序列 xk a,b，則該迭，則該迭代格式映內(nèi)。代格式映內(nèi)。 n例例2.3.3：求方

14、程：求方程x=e-x 在在0.5附近的根附近的根n解：解：將方程改寫為將方程改寫為x=-lnx，而，而lnx的定義域?yàn)椋ǖ亩x域?yàn)椋?，），當(dāng)?。?，當(dāng)取x0=0.5時(shí)，進(jìn)行迭代可得時(shí)，進(jìn)行迭代可得x1=0.693, x2=0.3666, x3=1.0034, x4=-0.0034?？梢姟？梢妜4已經(jīng)超過已經(jīng)超過了了lnx的定義域，迭代不能繼續(xù)，此格式不映內(nèi)。的定義域，迭代不能繼續(xù)，此格式不映內(nèi)。n不僅考慮映內(nèi)性，為使迭代法有效，還必須保不僅考慮映內(nèi)性，為使迭代法有效，還必須保證它的收斂性證它的收斂性計(jì)算機(jī)與通信工程學(xué)院32計(jì)算機(jī)與通信工程學(xué)院33全局收斂性全局收斂性n定理定理2.3：設(shè)函數(shù)：設(shè)

15、函數(shù)(x) 在在a,b上具有連續(xù)的一階上具有連續(xù)的一階導(dǎo)數(shù)，且滿足導(dǎo)數(shù)，且滿足（1）當(dāng)）當(dāng)x a, b時(shí)，時(shí)， (x) a, b（2）當(dāng)任意）當(dāng)任意x a, b，存在，存在0 L 1，使，使 則方程則方程x= (x)在在a, b上有唯一的根上有唯一的根x*,且對(duì)任意且對(duì)任意初值初值x0 a, b時(shí)，迭代序列時(shí)，迭代序列xk+1=(xk)(k = 0, 1, )收斂于收斂于x*。1)( Lx計(jì)算機(jī)與通信工程學(xué)院34全局收斂性全局收斂性n證明：先證明根的唯一性證明：先證明根的唯一性構(gòu)造連續(xù)函數(shù)構(gòu)造連續(xù)函數(shù) ，根據(jù)條件，根據(jù)條件(1)可以得到可以得到由函數(shù)的連續(xù)性定理可知，存在由函數(shù)的連續(xù)性定理可知

16、，存在x*a,b，使使 ，也就是存在解，即，也就是存在解，即假設(shè)有兩個(gè)解假設(shè)有兩個(gè)解 ，則，則根據(jù)中值定理有根據(jù)中值定理有從而有從而有xxx)()(0)()(aaa0)()(bbb0*)(*)(xxx*)(*xx,*,baxx)(*),(*xxxx,),*)( )(*)(*baxxxxxx0)( 1)*(xx計(jì)算機(jī)與通信工程學(xué)院35全局收斂性全局收斂性根據(jù)條件根據(jù)條件(2)有有 所以所以 ，即，即 ，也就是解唯一。，也就是解唯一。 設(shè)設(shè)x*是方程的根，即是方程的根，即x*= (x*)，由拉格朗日定理，由拉格朗日定理 因?yàn)橐驗(yàn)? L 1，由，由 知知 即即 xk+1 = (xk)收斂收斂)( )

17、()(*1*kkkxxxxxx0*11*2*1*)( )()(xxLxxLxxLxxxxxxkkkkkk0lim1kkL)(01*kxxk1| )( |x0*xxxx *計(jì)算機(jī)與通信工程學(xué)院36全局收斂性全局收斂性n定理定理2.4：設(shè)在區(qū)間：設(shè)在區(qū)間a,b方程方程 x= (x) 有根有根x*，并，并且對(duì)且對(duì) 有有| (x)| 1，則對(duì)于任意，則對(duì)于任意x0(x*) a,b ,迭代過程迭代過程 xk+1 = (xk)一定發(fā)散。一定發(fā)散。n推論推論2.1：在定理：在定理3的條件下，有誤差估計(jì)式的條件下，有誤差估計(jì)式,bax11*kkkxxLLxx011*xxLLxxkk計(jì)算機(jī)與通信工程學(xué)院37全局

18、收斂性全局收斂性n證：證： 即即 已知已知L1，因此有，因此有 只要只要 充分小，就可以保證充分小，就可以保證 足夠小足夠小 因此可用條件因此可用條件 來(lái)控制迭代過程的結(jié)束來(lái)控制迭代過程的結(jié)束 11*kkkkkxxxxLxxLxx)*(1kkkxxxxL1*)1 (kkkxxLxxL11*kkkxxLLxx1kkxxkxx *1kkxx計(jì)算機(jī)與通信工程學(xué)院38全局收斂性全局收斂性 即即)( )()(21211kkkkkkxxxxxx21kkxxL.11*2121kkkkkxxlLxxLLxx011xxLLk011*xxLLxxkk計(jì)算機(jī)與通信工程學(xué)院39全局收斂性全局收斂性n迭代法的終點(diǎn)判斷迭

19、代法的終點(diǎn)判斷n只要相鄰兩次迭代值的偏差充分小，就能保證迭代只要相鄰兩次迭代值的偏差充分小，就能保證迭代值足夠準(zhǔn)確，因而用值足夠準(zhǔn)確，因而用|x k- x k-1| 控制迭代過程的結(jié)控制迭代過程的結(jié)束束計(jì)算機(jī)與通信工程學(xué)院40全局收斂性全局收斂性n例例2.3.4：對(duì)方程：對(duì)方程 xex-1=0構(gòu)造收斂的迭代格式并構(gòu)造收斂的迭代格式并求其根，要求精度求其根，要求精度10-5 n解：設(shè)解：設(shè)f(x)=xex-1, 則則 f(0)=-10 因此因此f(x)=0在（在（0，1）內(nèi)有根）內(nèi)有根 又又 因此方程因此方程f(x)=0在在(0, )內(nèi)僅有一根內(nèi)僅有一根 令令 在在0,1上，上， 因此因此 x=

20、e-x 收斂收斂 取取x0=0.5進(jìn)行迭代，計(jì)算結(jié)果如下表所示進(jìn)行迭代，計(jì)算結(jié)果如下表所示 0)1 ()( xexeexfxxxxex)(1| )( |xex 1 , 0 1 ,1)(ex計(jì)算機(jī)與通信工程學(xué)院41全局收斂性全局收斂性kxkkxk00.500000100.56690710.606531110.56727720.545239129.56706730.579703130.56718640.560065140.56711950.571172150.56715760.564863160.56713570.568438170.56714880.566409180.56714190.5675

21、60計(jì)算機(jī)與通信工程學(xué)院42全局收斂性全局收斂性 取取x*0.56714 n例例2.3.5：用迭代法求方程：用迭代法求方程 x3-2x-5=0 的最小正的最小正根根n解：解： 取正根區(qū)間取正根區(qū)間2,3，迭代格式，迭代格式 不滿足收斂定理不滿足收斂定理 5171810000007. 0567148. 0567141. 0 xxx0 01 12 23 3 f(x)-5-5-6-6-1-116 16 3115)2kkxx（2233( ),( )13.512maxxxxx 計(jì)算機(jī)與通信工程學(xué)院43全局收斂性全局收斂性n將原方程改寫成將原方程改寫成 迭代格式迭代格式 收斂收斂 取初值取初值x0=2.5

22、 進(jìn)行迭代，結(jié)果如下所示進(jìn)行迭代，結(jié)果如下所示 3(25)xx2332( )25,( )(25),3xxxx3125kkxx3 , 2)(x計(jì)算機(jī)與通信工程學(xué)院44全局收斂性全局收斂性 取方程的根取方程的根 x*= 2.0946 計(jì)算機(jī)與通信工程學(xué)院全局收斂性全局收斂性n例例2.3.6：求方程：求方程 x3-3x+1=0 在在0, 0.5內(nèi)的根，內(nèi)的根，精確到精確到10-5 45計(jì)算機(jī)與通信工程學(xué)院46局部收斂性局部收斂性n定義定義2.2： 如果存在如果存在x* 的某個(gè)鄰域的某個(gè)鄰域: |x-x*| ，使迭代過程使迭代過程 xk+1 = (xk)對(duì)于任意初值對(duì)于任意初值 x0 均均收斂，則稱迭

23、代過程收斂，則稱迭代過程xk+1 = (xk)在根在根x* 附近具附近具有局部收斂性。有局部收斂性。 n定理定理2.5： 設(shè)設(shè) (x)在在x= (x)的根的根x* 鄰域有連續(xù)的鄰域有連續(xù)的一階導(dǎo)數(shù)，且有一階導(dǎo)數(shù)，且有 | (x*) |1，則迭代格式，則迭代格式 xk+1 = (xk)在根在根x*附近具有局部收斂性。附近具有局部收斂性。 n證明證明:由于由于 | (x*) |1 ，存在充分小的鄰域：，存在充分小的鄰域： |x-x*| ，使下式成立，使下式成立 | (x) | L1計(jì)算機(jī)與通信工程學(xué)院局部收斂性局部收斂性 根據(jù)微分中值定理根據(jù)微分中值定理 由于由于 (x*) =x*，又當(dāng)，又當(dāng)x時(shí)

24、時(shí)，因此，因此n由定理由定理2.3的條件的條件(1)可以斷定可以斷定xk+1 = (xk)對(duì)于任意對(duì)于任意x0均收斂均收斂n已知根的初值已知根的初值x0在根在根 x*鄰域，又根據(jù)鄰域，又根據(jù)(x)的連的連續(xù)性，則可采用續(xù)性，則可采用 |(x0) | 1 來(lái)代替來(lái)代替|(x* ) | 1，判斷迭代的收斂性，判斷迭代的收斂性 47*)( *)()(xxxx| *| *| *)(|xxxxLxx計(jì)算機(jī)與通信工程學(xué)院48局部收斂性局部收斂性n例例2.3.7：迭代過程：迭代過程 ，當(dāng)局部收斂，當(dāng)局部收斂到到 時(shí)，確定時(shí)，確定C的值的值n解：迭代函數(shù)解：迭代函數(shù) 當(dāng)局部收斂到當(dāng)局部收斂到 時(shí)，時(shí)， 有有

25、)5(21kkkxcxx5)5()(2xcxxcxx21)( 51521)5( c15211c051c計(jì)算機(jī)與通信工程學(xué)院49局部收斂性局部收斂性n例例2.3.8：對(duì)方程：對(duì)方程x3-x2-1=0在初值在初值x0=1.5附近建立附近建立收斂的迭代格式，并求解，要求精確到小數(shù)點(diǎn)收斂的迭代格式，并求解，要求精確到小數(shù)點(diǎn)后后4位位 n解：構(gòu)造迭代公式，寫出方程的等價(jià)形式解：構(gòu)造迭代公式，寫出方程的等價(jià)形式 迭代格式為迭代格式為 321xx3211kkxx322) 1(32)( xxx14558. 0)( 5 . 100 xx計(jì)算機(jī)與通信工程學(xué)院50局部收斂性局部收斂性迭代收斂迭代收斂 ，計(jì)算過程如下

26、，取，計(jì)算過程如下，取x*x9=1.4656，此時(shí)，此時(shí) kxk|xk+1-xk|0 01.51.51 11.481241.481240.0187630.0187632 21.472711.472710.008530.008533 31.468821.468820.003890.003894 41.467051.467050.001770.001775 51.466241.466240.000810.000816 61.465881.465880.000360.000367 71.465701.465700.000180.000188 81.465631.465630.000070.00007

27、9 91.465601.465600.000030.000034891021 xx計(jì)算機(jī)與通信工程學(xué)院51局部收斂性局部收斂性n迭代的計(jì)算步驟迭代的計(jì)算步驟n確定確定 f(x)=0的等價(jià)形式的等價(jià)形式 x= (x) ，選初值，選初值x0 ，判斷，判斷收斂性收斂性| (x0) |1n由公式由公式 x1 = (x0) 計(jì)算計(jì)算x1n如果如果|x 1- x 0| 則停止計(jì)算，取則停止計(jì)算，取x*= x1 ；否則令；否則令x 0 =x 1 ，重復(fù)步驟，重復(fù)步驟2和和3，直到計(jì)算停止，直到計(jì)算停止 n例例2.3.9：給定函數(shù)：給定函數(shù)f(x) ，設(shè)迭代程，設(shè)迭代程 選取選取值，使在值，使在 f(x)=0

28、 的單根附近收斂的單根附近收斂 )(1kkkxfxx計(jì)算機(jī)與通信工程學(xué)院迭代過程的收斂速度迭代過程的收斂速度n迭代過程的收斂速度，是指在接近收斂時(shí)迭代迭代過程的收斂速度，是指在接近收斂時(shí)迭代誤差的下降速度誤差的下降速度n定義定義2.3：設(shè)迭代過程：設(shè)迭代過程 xk+1 = (xk)收斂于收斂于 x = (x)的根的根x*，令迭代誤差，令迭代誤差ek=xk-x*，如果存在常，如果存在常數(shù)數(shù)p(p1)和和c(c0)，使，使則稱序列則稱序列 xk是是p階收斂的，階收斂的，c稱漸近誤差常數(shù)。稱漸近誤差常數(shù)。52計(jì)算機(jī)與通信工程學(xué)院迭代過程的收斂速度迭代過程的收斂速度n定理定理2.6：對(duì)迭代過程：對(duì)迭代

29、過程 xk+1 = (xk) ，如果，如果 (p)(x)在所求根在所求根x*的鄰域連續(xù)，且的鄰域連續(xù)，且 則迭代過程在則迭代過程在x*鄰域是鄰域是p階收斂的。階收斂的。n證：由于證：由于 (x*) =0，即在，即在x*鄰域鄰域| (x*) |1 ，所以，所以xk+1 = (xk) 具有局部收斂性。具有局部收斂性。 將將 (xk)在在x*處泰勒展開到處泰勒展開到p-1階階53計(jì)算機(jī)與通信工程學(xué)院迭代過程的收斂速度迭代過程的收斂速度 將已知的將已知的 代入代入n由于由于xk+1 = (xk) , x*= (x*) ， 那么有那么有54計(jì)算機(jī)與通信工程學(xué)院迭代過程的收斂速度迭代過程的收斂速度n例例2

30、.3.10：迭代過程：迭代過程 收斂于收斂于 時(shí)，問其收斂速度。時(shí)，問其收斂速度。n解：因?yàn)榻猓阂驗(yàn)?所以所以n將將 代入代入n因此因此 xk是二階收斂的是二階收斂的55計(jì)算機(jī)與通信工程學(xué)院迭代過程的收斂速度迭代過程的收斂速度n例例2.3.11：設(shè)：設(shè) ，要使迭代過程，要使迭代過程xk+1 = (xk) 至少平方收斂到至少平方收斂到 ，確定，確定a的的值值56計(jì)算機(jī)與通信工程學(xué)院57迭代的加權(quán)法加速迭代的加權(quán)法加速n加權(quán)法加權(quán)法 n設(shè)設(shè) xk是根是根x* 的某近似值，取的某近似值，取 ，由中值定理由中值定理 其中其中 x*, xk，假定，假定 () 變化不大，設(shè)變化不大，設(shè) () c ，有，有

31、 1(),()kkxxxx1()()( )()kkkxxxxxx 1()kkxxc xx1kkxcxxcx1111kkcxxxcc計(jì)算機(jī)與通信工程學(xué)院58迭代的加權(quán)法加速迭代的加權(quán)法加速 取取 即即11111kkkcxxxcc)(111kkkcxxcx計(jì)算機(jī)與通信工程學(xué)院59迭代的加權(quán)法加速迭代的加權(quán)法加速n例例2.3.12：用加權(quán)法加速技術(shù)求方程：用加權(quán)法加速技術(shù)求方程x=e-x 在在0.5附近的一個(gè)根附近的一個(gè)根 n解：因?yàn)樵诮猓阂驗(yàn)樵趚0=0.5附近附近 所以加速迭代公式所以加速迭代公式 可以寫成可以寫成6 . 0| )( 5 . 05 . 05 . 0eexx)6 . 0(6 . 11

32、1kxkxexk計(jì)算機(jī)與通信工程學(xué)院60迭代的加權(quán)法加速迭代的加權(quán)法加速計(jì)算結(jié)果如下表所示計(jì)算結(jié)果如下表所示 kxkkxk00.530.56714310.56658240.56714320.567132計(jì)算機(jī)與通信工程學(xué)院612.4 牛頓迭代法牛頓迭代法n迭代公式的建立迭代公式的建立n牛頓迭代法的幾何意義牛頓迭代法的幾何意義n牛頓迭代法的收斂性牛頓迭代法的收斂性n牛頓迭代法的修正牛頓迭代法的修正計(jì)算機(jī)與通信工程學(xué)院62迭代公式的建立迭代公式的建立n已知方程已知方程f (x) = 0的一個(gè)近似根的一個(gè)近似根x0，把，把f (x)在在x0處作泰勒展開處作泰勒展開n取前兩項(xiàng)來(lái)近似代替取前兩項(xiàng)來(lái)近似代

33、替f (x) ，則得近似的線性方，則得近似的線性方程程n設(shè)設(shè)f (x0) 0 ，解之得，解之得 200000)(! 2)()( )()(xxxfxxxfxfxf0)( )(000 xxxfxf)( )(000 xfxfxx計(jì)算機(jī)與通信工程學(xué)院63迭代公式的建立迭代公式的建立n取取x作為原方程作為原方程f (x) = 0的近似根的近似根x1，即，即n再重復(fù)用上述方法得再重復(fù)用上述方法得n一般地，有迭代公式一般地，有迭代公式)( )(0001xfxfxx), 2, 1, 0()( )(1kxfxfxxkkkk)( )(1112xfxfxx計(jì)算機(jī)與通信工程學(xué)院64牛頓迭代法的幾何意義牛頓迭代法的幾何

34、意義n當(dāng)求得當(dāng)求得x*的近似值的近似值xk以后，過曲線以后，過曲線y= f (x) 上對(duì)上對(duì)應(yīng)點(diǎn)（應(yīng)點(diǎn)（xk, f (xk)）作）作f (x) 的切線，其切線方程為的切線，其切線方程為 n求此切線方程和求此切線方程和x軸的交點(diǎn)，即得軸的交點(diǎn)，即得x*的新的近似的新的近似值值xk+1必須滿足方程必須滿足方程n即牛頓法的迭代公式即牛頓法的迭代公式 的計(jì)算結(jié)果的計(jì)算結(jié)果 )( )(kkkxxxfxfy0)( )(kkkxxxfxf)( )(1kkkkxfxfxx計(jì)算機(jī)與通信工程學(xué)院65牛頓迭代法的幾何意義牛頓迭代法的幾何意義計(jì)算機(jī)與通信工程學(xué)院66例題例題n例例2.4.1：用牛頓迭代法求：用牛頓迭代

35、法求 x=e-x 在在0.5附近的根附近的根n 解：由解：由x=e-x ，有，有xex-1=0由牛頓迭代公式由牛頓迭代公式 可知可知取取x0=0.5，計(jì)算結(jié)果如下所示：，計(jì)算結(jié)果如下所示： xxxeexf)( 01)(xxexfkxkkxkxxkkkxexxexeexxxkkkk111計(jì)算機(jī)與通信工程學(xué)院67例題例題kxkkxk00.530.56714329110.57102044040.56714329020.567155560計(jì)算機(jī)與通信工程學(xué)院68例題例題n例例2.4.2：造平方根表，用牛頓迭代法計(jì)算：造平方根表，用牛頓迭代法計(jì)算 n解：令解：令 ，則，則x2-a=0, 求求 等價(jià)于求等

36、價(jià)于求f (x)= x2-a=0 的正實(shí)根，因?yàn)榈恼龑?shí)根，因?yàn)?f (x)= 2x ，由牛頓迭代公式得由牛頓迭代公式得 當(dāng)當(dāng)a=115時(shí)，取初值時(shí)，取初值 x0=10，迭代，迭代4次可得次可得10，10.7500，10.723837，10.723805， 10.723805axaa211() ,0,1,2,22kkkkkkxaaxxxkxx723805.10115 計(jì)算機(jī)與通信工程學(xué)院69例題例題n例：用牛頓迭代法求例：用牛頓迭代法求3a計(jì)算機(jī)與通信工程學(xué)院70牛頓迭代法的收斂性牛頓迭代法的收斂性n定理定理2.7：設(shè)：設(shè) f (x*)=0， f (x*) 0， f (x*) 在在x*鄰域連續(xù)，

37、則牛頓迭代法在鄰域連續(xù)，則牛頓迭代法在x*局部收斂，局部收斂，且至少且至少2階收斂。并有階收斂。并有n證：證：因?yàn)橐驗(yàn)閒 (x*)=0 ，而，而f (x*) 0 ，在，在x*鄰域，則鄰域，則12()lim2()kkkefxefx計(jì)算機(jī)與通信工程學(xué)院71牛頓迭代法的收斂性牛頓迭代法的收斂性 因?yàn)橐驗(yàn)閒 (x)在在x*鄰域連續(xù)，則牛頓迭代法局部收斂，鄰域連續(xù)，則牛頓迭代法局部收斂，當(dāng)當(dāng)f (x*) 0時(shí)時(shí)， (x*) 0 ，牛頓迭代法在，牛頓迭代法在x*鄰鄰域?yàn)槎A收斂。域?yàn)槎A收斂。 計(jì)算機(jī)與通信工程學(xué)院牛頓迭代法的收斂性牛頓迭代法的收斂性72計(jì)算機(jī)與通信工程學(xué)院73牛頓迭代法的修正牛頓迭代法的

38、修正n牛頓迭代法對(duì)初值的要求較高：要求初值牛頓迭代法對(duì)初值的要求較高：要求初值x0充分接近充分接近x*才能保證局部收斂性。如果才能保證局部收斂性。如果初值初值x0偏離偏離x*較遠(yuǎn)，那么牛頓迭代法可能較遠(yuǎn)，那么牛頓迭代法可能發(fā)散或收斂很慢。發(fā)散或收斂很慢。n例例2.4.4：用牛頓迭代法求方程：用牛頓迭代法求方程f (x) = x3 x 1 = 0在在x= 1.5附近的根。附近的根。n解：構(gòu)造牛頓迭代公式解：構(gòu)造牛頓迭代公式312131kkkkkxxxxx計(jì)算機(jī)與通信工程學(xué)院74牛頓迭代法的修正牛頓迭代法的修正分別取初值分別取初值1.5和和0.6進(jìn)行迭代計(jì)算，結(jié)果如下所示：進(jìn)行迭代計(jì)算，結(jié)果如下所

39、示： k (初值初值1.5) (初值初值0.6) 0 1.5 0.6 1 1.34783 17.9 2 1.32520 11.9468 3 1.32472 7.986 計(jì)算機(jī)與通信工程學(xué)院牛頓迭代法的修正牛頓迭代法的修正n牛頓下山法就是擴(kuò)大初值范圍的修正牛頓法，牛頓下山法就是擴(kuò)大初值范圍的修正牛頓法，為了防止初值的選取造成迭代發(fā)散或迭代值偏為了防止初值的選取造成迭代發(fā)散或迭代值偏離所求根而采用的一種對(duì)初值離所求根而采用的一種對(duì)初值x0的修正措施。的修正措施。n要求迭代過程對(duì)所選的初值能達(dá)到使函數(shù)值單要求迭代過程對(duì)所選的初值能達(dá)到使函數(shù)值單調(diào)下降，也就是要滿足下山條件調(diào)下降，也就是要滿足下山條件

40、n將牛頓迭代法的計(jì)算結(jié)果將牛頓迭代法的計(jì)算結(jié)果75)()(1kkxfxf計(jì)算機(jī)與通信工程學(xué)院牛頓迭代法的修正牛頓迭代法的修正 與前一步的近似值與前一步的近似值xk適當(dāng)加權(quán)平均作為新的改適當(dāng)加權(quán)平均作為新的改進(jìn)值進(jìn)值xk+1n將上述兩式合并可得牛頓下山法的迭代公式將上述兩式合并可得牛頓下山法的迭代公式 其中其中 是一個(gè)參數(shù)，是一個(gè)參數(shù)， 的選取應(yīng)滿足的選取應(yīng)滿足0 1 ， 為下山因子下界為下山因子下界。開始時(shí)可簡(jiǎn)單地取開始時(shí)可簡(jiǎn)單地取 = 1，然后逐步分半減少，然后逐步分半減少76), 2, 1, 0()( )(1kxfxfxxkkkk計(jì)算機(jī)與通信工程學(xué)院77牛頓迭代法的修正牛頓迭代法的修正n牛

41、頓下山法的步驟牛頓下山法的步驟（1）選取初始近似值）選取初始近似值x0；（2）取下山因子）取下山因子 = 1；（3）計(jì)算）計(jì)算（4）計(jì)算）計(jì)算f (x1)，并比較，并比較| f (x1)| 與與 | f (x0)|的大小的大小 若若| f (x1)| | f (x0)| ，把，把x1帶到牛頓迭代公式帶到牛頓迭代公式中進(jìn)行迭代；中進(jìn)行迭代； 若若 | f (x1)| | f (x0)| ，則當(dāng)，則當(dāng) 計(jì)算過程結(jié)束計(jì)算過程結(jié)束，重新選擇一個(gè)，重新選擇一個(gè)x0進(jìn)行牛頓下山；否則當(dāng)進(jìn)行牛頓下山；否則當(dāng) ，則將下山因子縮小一半，取則將下山因子縮小一半，取 /2代入，并轉(zhuǎn)向（代入，并轉(zhuǎn)向（3）重復(fù)計(jì)算）重

42、復(fù)計(jì)算)( )(0001xfxfxx計(jì)算機(jī)與通信工程學(xué)院78牛頓迭代法的修正牛頓迭代法的修正n例例2.4.5：求方程：求方程f (x) = x3 x 1 = 0在在1.5附附近的一個(gè)根近的一個(gè)根n解：解：已知方程已知方程f (x) = x3 x 1 = 0的一個(gè)根為的一個(gè)根為x* = 1.32472，若取初值，若取初值x0 = 0.6，用牛頓法，用牛頓法計(jì)算計(jì)算 反而比反而比x0 = 0.6更偏離根更偏離根x*。若改用牛頓下山法。若改用牛頓下山法 計(jì)算，仍取計(jì)算，仍取x0 = 0.6，計(jì)算結(jié)果如下表計(jì)算結(jié)果如下表9 .17)( )(0001xfxfxx)( )(1kkkkxfxfxx計(jì)算機(jī)與通信工程學(xué)院79牛頓迭代法的修正牛頓迭代法的修正k xkf(xk)| f(xk+1)| f(xk)|010.6-1.3841117.95716否否1/29.25781否否1/44.925114否否1/82.762517.319否否1/161.681252.0709否否1/321.140625-0.625是是211.366810.1866311.326286.6710-341