數值計算方法第二章

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

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

3、f (x) 的零點或根的零點或根n重根重根n如果函數如果函數 f (x) 可分解為可分解為 其中其中m是大于是大于1的正整數，則稱的正整數，則稱x*是方程是方程f (x)=0 的的m重根重根 n重根的判斷條件重根的判斷條件n設函數設函數f (x) 有有m階連續(xù)導數，方程階連續(xù)導數，方程f (x)=0 有有m重根重根x*的充要條件是的充要條件是0*)(),(*)()(xgxgxxxfm計算機與通信工程學院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計算機與通信工程學院8方程的根方程的根n方程求根需要解決的問題方程求根需要解決的問題n根的存在性：方程是否有根，如果有根，有幾個根？根的存在性：方程是否有根，如果有根，有幾個根？ n根的隔離：找出有根區(qū)間，把有根區(qū)間分成較小的根的隔離：找出有根區(qū)間，把有根區(qū)間分成較小的子區(qū)間，每個子區(qū)間有一個根，將有根區(qū)間內的任子區(qū)間，每個子區(qū)間有一個根，將有根區(qū)間內的任一點都看成該根的一個初始近似值一

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

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

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

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

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

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

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

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

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

14、程：求方程x=e-x 在在0.5附近的根附近的根n解：解：將方程改寫為將方程改寫為x=-lnx，而，而lnx的定義域為（的定義域為（0，），當?。斎0=0.5時，進行迭代可得時，進行迭代可得x1=0.693, x2=0.3666, x3=1.0034, x4=-0.0034?？梢??？梢妜4已經超過已經超過了了lnx的定義域，迭代不能繼續(xù)，此格式不映內。的定義域，迭代不能繼續(xù)，此格式不映內。n不僅考慮映內性，為使迭代法有效，還必須保不僅考慮映內性，為使迭代法有效，還必須保證它的收斂性證它的收斂性計算機與通信工程學院32計算機與通信工程學院33全局收斂性全局收斂性n定理定理2.3：設函數：設

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

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

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

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

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

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

21、60計算機與通信工程學院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 計算機與通信工程學院43全局收斂性全局收斂性n將原方程改寫成將原方程改寫成 迭代格式迭代格式 收斂收斂 取初值取初值x0=2.5

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

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

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

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

26、，取，計算過程如下，取x*x9=1.4656，此時，此時 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計算機與通信工程學院51局部收斂性局部收斂性n迭代的計算步驟迭代的計算步驟n確定確定 f(x)=0的等價形式的等價形式 x= (x) ，選初值，選初值x0 ，判斷，判斷收斂性收斂性| (x0) |1n由公式由公式 x1 = (x0) 計算計算x1n如果如果|x 1- x 0| 則停止計算，取則停止計算，取x*= x1 ；否則令；否則令x 0 =x 1 ，重復步驟，重復步驟2和和3，直到計算停止，直到計算停止 n例例2.3.9：給定函數：給定函數f(x) ，設迭代程，設迭代程 選取選取值，使在值，使在 f(x)=0

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

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計算機與通信工程學院迭代過程的收斂速度迭代過程的收斂速度 將已知的將已知的 代入代入n由于由于xk+1 = (xk) , x*= (x*) ， 那么有那么有54計算機與通信工程學院迭代過程的收斂速度迭代過程的收斂速度n例例2

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

31、 1(),()kkxxxx1()()( )()kkkxxxxxx 1()kkxxc xx1kkxcxxcx1111kkcxxxcc計算機與通信工程學院58迭代的加權法加速迭代的加權法加速 取取 即即11111kkkcxxxcc)(111kkkcxxcx計算機與通信工程學院59迭代的加權法加速迭代的加權法加速n例例2.3.12：用加權法加速技術求方程：用加權法加速技術求方程x=e-x 在在0.5附近的一個根附近的一個根 n解：因為在解：因為在x0=0.5附近附近 所以加速迭代公式所以加速迭代公式 可以寫成可以寫成6 . 0| )( 5 . 05 . 05 . 0eexx)6 . 0(6 . 11

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

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

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

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

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

37、則牛頓迭代法在鄰域連續(xù)，則牛頓迭代法在x*局部收斂，局部收斂，且至少且至少2階收斂。并有階收斂。并有n證：證：因為因為f (x*)=0 ，而，而f (x*) 0 ，在，在x*鄰域，則鄰域，則12()lim2()kkkefxefx計算機與通信工程學院71牛頓迭代法的收斂性牛頓迭代法的收斂性 因為因為f (x)在在x*鄰域連續(xù)，則牛頓迭代法局部收斂，鄰域連續(xù)，則牛頓迭代法局部收斂，當當f (x*) 0時時， (x*) 0 ，牛頓迭代法在，牛頓迭代法在x*鄰鄰域為二階收斂。域為二階收斂。 計算機與通信工程學院牛頓迭代法的收斂性牛頓迭代法的收斂性72計算機與通信工程學院73牛頓迭代法的修正牛頓迭代法的

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

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 計算機與通信工程學院牛頓迭代法的修正牛頓迭代法的修正n牛頓下山法就是擴大初值范圍的修正牛頓法，牛頓下山法就是擴大初值范圍的修正牛頓法，為了防止初值的選取造成迭代發(fā)散或迭代值偏為了防止初值的選取造成迭代發(fā)散或迭代值偏離所求根而采用的一種對初值離所求根而采用的一種對初值x0的修正措施。的修正措施。n要求迭代過程對所選的初值能達到使函數值單要求迭代過程對所選的初值能達到使函數值單調下降，也就是要滿足下山條件調下降，也就是要滿足下山條件

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

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

42、復計算)( )(0001xfxfxx計算機與通信工程學院78牛頓迭代法的修正牛頓迭代法的修正n例例2.4.5：求方程：求方程f (x) = x3 x 1 = 0在在1.5附附近的一個根近的一個根n解：解：已知方程已知方程f (x) = x3 x 1 = 0的一個根為的一個根為x* = 1.32472，若取初值，若取初值x0 = 0.6，用牛頓法，用牛頓法計算計算 反而比反而比x0 = 0.6更偏離根更偏離根x*。若改用牛頓下山法。若改用牛頓下山法 計算，仍取計算，仍取x0 = 0.6，計算結果如下表計算結果如下表9 .17)( )(0001xfxfxx)( )(1kkkkxfxfxx計算機與通信工程學院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