1、數(shù) 值 分 析1 1 誤差來(lái)源與種類誤差來(lái)源與種類上節(jié)知識(shí)要點(diǎn)回顧上節(jié)知識(shí)要點(diǎn)回顧: (1) 模型誤差模型誤差(2) 參數(shù)誤差參數(shù)誤差(3) 截?cái)嗾`差截?cái)嗾`差(4) 舍入誤差舍入誤差2 絕對(duì)誤差和相對(duì)誤差絕對(duì)誤差和相對(duì)誤差定義定義設(shè)某量的準(zhǔn)確值為設(shè)某量的準(zhǔn)確值為x, 是是x的近似值，的近似值，x 如果如果 稱稱 為為 的的絕對(duì)誤差限絕對(duì)誤差限.,exx x 顯然顯然,xxx常記為常記為.xx exx為為 的的絕對(duì)誤差絕對(duì)誤差，簡(jiǎn)稱誤差，簡(jiǎn)稱誤差.x 稱稱定義定義 設(shè)某量的準(zhǔn)確值為設(shè)某量的準(zhǔn)確值為x, 是是x的近似值，的近似值，x 如果如果 稱稱 為為 的的相對(duì)誤差限相對(duì)誤差限.,rre r x

2、 為為 的的相對(duì)誤差相對(duì)誤差，記做，記做 .x 稱稱ex re 3 有效數(shù)字有效數(shù)字定義定義: 設(shè)設(shè)x為準(zhǔn)確值，為準(zhǔn)確值， 是是x的近似值，且的近似值，且x 12(0.) 10 ,mnxa aa 其中其中m為整數(shù)，為整數(shù)，110,naaa 為為0,1,9中一個(gè)數(shù)字中一個(gè)數(shù)字. 如果如果x 誤差滿足誤差滿足 即即 誤差不超過(guò)誤差不超過(guò)1|10,2m nxxx 某位的半個(gè)單位某位的半個(gè)單位. 稱該位到稱該位到 的第一位非零數(shù)的第一位非零數(shù)字為字為 的有效數(shù)字，即的有效數(shù)字，即 有有n位有效數(shù)字位有效數(shù)字.x x x 注注 當(dāng)當(dāng) 是是x的的 按四舍五入原則得到的近似按四舍五入原則得到的近似x 1na

3、 數(shù)，則數(shù)，則 具有具有n位有效數(shù)字位有效數(shù)字 .x 4.有效數(shù)字和相對(duì)誤差之間的關(guān)系有效數(shù)字和相對(duì)誤差之間的關(guān)系:定理定理1設(shè)設(shè)x的近似數(shù)為的近似數(shù)為120.10 ,mnxa aa 如果如果 具有具有n位有效數(shù)字位有效數(shù)字,則則 的相對(duì)誤差限為的相對(duì)誤差限為x x (1)11|102nrxxexa 其中其中 ；反之，；反之， 10a (1)11|102(1)nrxxexa 如果如果 的相對(duì)誤差滿足的相對(duì)誤差滿足x 則則 至少具有至少具有n位有效數(shù)字位有效數(shù)字.x 5. 5. 條件數(shù)與病態(tài)問(wèn)題條件數(shù)與病態(tài)問(wèn)題定義定義 對(duì)于前向誤差和后向誤差，其相對(duì)誤差對(duì)于前向誤差和后向誤差，其相對(duì)誤差之比的絕

4、對(duì)值稱為計(jì)算函數(shù)之比的絕對(duì)值稱為計(jì)算函數(shù)f(x)的的條件數(shù)條件數(shù)( ( )( *)( *)*(*)*pyf xf xf xyCxxxxx 近似計(jì)算公式為近似計(jì)算公式為*( *)( *)pxfxCf x 當(dāng)條件數(shù)較大時(shí)，可能會(huì)出現(xiàn)前向誤差當(dāng)條件數(shù)較大時(shí)，可能會(huì)出現(xiàn)前向誤差很大的情況，通常稱這類問(wèn)題為很大的情況，通常稱這類問(wèn)題為病態(tài)問(wèn)題病態(tài)問(wèn)題.6. 6. 數(shù)值計(jì)算中需要注意的問(wèn)題數(shù)值計(jì)算中需要注意的問(wèn)題(1) 避免兩個(gè)相近的數(shù)相減避免兩個(gè)相近的數(shù)相減(2) 防止大數(shù)防止大數(shù)“吃掉吃掉”小數(shù)小數(shù)(3) 簡(jiǎn)化計(jì)算步驟，減少運(yùn)算次數(shù)簡(jiǎn)化計(jì)算步驟，減少運(yùn)算次數(shù)(4) 避免誤差的積累與傳播避免誤差的積累與

5、傳播誤差呈遞增形式誤差呈遞增形式,稱這類算法是稱這類算法是不穩(wěn)定的不穩(wěn)定的;誤差逐步遞減，這樣的算法稱為誤差逐步遞減，這樣的算法稱為穩(wěn)定的算法穩(wěn)定的算法7. 二分法二分法令令 取區(qū)間中點(diǎn)取區(qū)間中點(diǎn)00,aa bb0002abx 若若00() ()0f af x 則則1010,;aa bx若若00() ()0f bf x 則則1010,;ax bb若若00() ()0f af x 則已得到方程的根則已得到方程的根.問(wèn)題：?jiǎn)栴}：( )0f x 為一非線性方程，為一非線性方程， , a b* , . . ( *)0.xa b s t f x為有根區(qū)間，求為有根區(qū)間，求 基本思想：基本思想： 如此下去

6、如此下去,不斷縮小有根區(qū)間不斷縮小有根區(qū)間,直到達(dá)到給定直到達(dá)到給定精度精度.因此有因此有0011,kka ba bab()/2kkkxab那么令那么令即即*limkkxx 并且序列并且序列 的收斂性與初始區(qū)間無(wú)關(guān)的收斂性與初始區(qū)間無(wú)關(guān).kx所以所以二分法是大范圍收斂二分法是大范圍收斂的的.1|*| ()/2()/2kkkkxxbaba 則則預(yù)先給定誤差精度預(yù)先給定誤差精度 當(dāng)當(dāng)12kba 時(shí)時(shí), 停止計(jì)算停止計(jì)算算法步驟算法步驟(1) 取初始有根區(qū)間取初始有根區(qū)間a,b,和精度要求和精度要求 ； (2) 若若 則停止計(jì)算；則停止計(jì)算；,2ba (3) 取取 ，若，若2bax ( ) ( )0

7、,f a f x 則則 b=x；否則否則a=x；(4) 轉(zhuǎn)轉(zhuǎn)(2).例例 用二分法計(jì)算方程用二分法計(jì)算方程 在在0, 0.5內(nèi)具有內(nèi)具有5位有效數(shù)字的根，它的絕對(duì)誤差限位有效數(shù)字的根，它的絕對(duì)誤差限是多少？至少需要對(duì)分多少次才能達(dá)到精度？是多少？至少需要對(duì)分多少次才能達(dá)到精度？4310 xx解解 由有效數(shù)字定義可知，絕對(duì)誤差限是由有效數(shù)字定義可知，絕對(duì)誤差限是5110 .2 要使要使5111022kba 52111022k 16k例例 用二分法計(jì)算方程用二分法計(jì)算方程 在在1, 2內(nèi)內(nèi)具有具有4位有效數(shù)字的根，它的絕對(duì)誤差限是位有效數(shù)字的根，它的絕對(duì)誤差限是多少？至少需要對(duì)分多少次才能達(dá)到精度

8、？多少？至少需要對(duì)分多少次才能達(dá)到精度？310 xx解解 由有效數(shù)字定義可知，絕對(duì)誤差限是由有效數(shù)字定義可知，絕對(duì)誤差限是3110 .2 要使要使3111022kba 31102k 10k二分法的優(yōu)缺點(diǎn)二分法的優(yōu)缺點(diǎn)(1) 簡(jiǎn)單易用，大范圍收斂簡(jiǎn)單易用，大范圍收斂?jī)?yōu)點(diǎn)：優(yōu)點(diǎn)：(2) 對(duì)對(duì) f (x) 要求不高，只要連續(xù)即可要求不高，只要連續(xù)即可缺點(diǎn)：缺點(diǎn)：(1) 無(wú)法求復(fù)根及重根無(wú)法求復(fù)根及重根(2) 收斂速度太慢收斂速度太慢 第二章第二章 解非線性方程的數(shù)值方法解非線性方程的數(shù)值方法一、一、 二分法二分法二、二、 迭代法迭代法三、三、 Newton法法 將給定方程將給定方程f(x)=0轉(zhuǎn)化成

9、等價(jià)方程轉(zhuǎn)化成等價(jià)方程 ( ) ( 1 2. )xx 二、二、 迭代法迭代法1 迭代法的基本思想迭代法的基本思想:若若x*是是f(x)的根的根, 即即 ,則有則有*()0f x *()xx 稱稱x*為函數(shù)為函數(shù) 的一個(gè)的一個(gè)不動(dòng)點(diǎn)不動(dòng)點(diǎn).( )x 設(shè)設(shè)x0是一個(gè)近似解，可以構(gòu)造序列是一個(gè)近似解，可以構(gòu)造序列1 0,1,2 ( (2.2 ) ) kkkxx 迭代法迭代法(2.2)稱為簡(jiǎn)單迭代法或單點(diǎn)迭代法稱為簡(jiǎn)單迭代法或單點(diǎn)迭代法.稱函數(shù)稱函數(shù) 為為迭代函數(shù)迭代函數(shù).( )x 簡(jiǎn)單迭代法簡(jiǎn)單迭代法(2.2), 若迭代序列若迭代序列xk保持有界保持有界,全在全在 定義域內(nèi)定義域內(nèi);且有且有( )x

10、 *limkkxx 稱迭代法是稱迭代法是收斂的收斂的. 此時(shí)此時(shí), ,由由 的連續(xù)性可得的連續(xù)性可得即即 x* = (x*)，即即x*是是 的不動(dòng)點(diǎn)，也就是的不動(dòng)點(diǎn)，也就是f (x)的零點(diǎn)。的零點(diǎn)。 1limlim(lim)kkkkkkxxx ，建立迭代格式 解：改寫方程為解：改寫方程為 求方程x3-2x-3=0在1,2內(nèi)的根.例例 332 xx3123kkxx取初值x0=1.9 ,計(jì)算得：kxkkxk0123451.91.894536471.893521141.893332331.893297221.893290696789101.893289471.893289251.893289211.

11、893289201.89328920 由計(jì)算結(jié)果有|x10 x9|10-8, 因此可取 x* x10 1.89328920 。 方程也可改寫成x=(x3-3)/2, 建立迭代格式 xk+1=(xk3-3)/2 , k=0,1,2, 仍取初值x0=1.9, 則有 x1=1.9295, x2=2.0917, x3=3.0760, x4=13.0529xk, 此迭代格式是發(fā)散的。30111.51,(0,1,2,). kkxxxk （），kxk012345671.51.357211.330861.325881.324941.324761.324731.3247231012(2) 1,1.5, 2.37

12、5,12.39, .kkxxxxx 例例 求求x3-x-1=0在在1.5附近的根附近的根x*解解xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1x0p0 x1p1 x0p0 x1p1x0p0 x1p1x2 不動(dòng)點(diǎn)迭代法的幾何解釋不動(dòng)點(diǎn)迭代法的幾何解釋2 收斂定理和誤差估計(jì)收斂定理和誤差估計(jì)定理定理1 設(shè)設(shè) 在在a, b上有連續(xù)的一階導(dǎo)數(shù)上有連續(xù)的一階導(dǎo)數(shù),且且( )x (1) 有有 , ,xa b ( );axb (2)|( ) |1,xL , ;xa b 則有則有(1) 函數(shù)函數(shù) 在在a ,b上存在唯一

13、的不動(dòng)點(diǎn)上存在唯一的不動(dòng)點(diǎn)x*( )x 由迭代公式由迭代公式(2.2)得到的序列得到的序列(2)0 , ,xa bkx都收斂到方程的根都收斂到方程的根x*10|1kkLxxxxL (3)*11|1kkkxxxxL (4)證明證明:(1) 先證明存在性先證明存在性, 令令( )( )h xxx 由條件由條件(1)可知可知( )( )0, ( )( )0h aaah bbb由連續(xù)函數(shù)根的存在定理由連續(xù)函數(shù)根的存在定理,必必* , . .xa b s th(x*)=0，即即*()xx 再證明唯一性再證明唯一性,設(shè)設(shè) 也是一個(gè)解也是一個(gè)解,即即( )xx x 那么那么*| | ()( ) | |( )

14、() |xxxxxxL xx 因?yàn)橐驗(yàn)長(zhǎng)1, 所以有所以有*xx (2) 由條件由條件(2)和和Lagrange中值定理得中值定理得*1| | ()()| kkxxxx 因?yàn)橐驗(yàn)長(zhǎng)1, 所以當(dāng)所以當(dāng) 時(shí)時(shí), 有有 k 0.kL (3)和和(4) 利用利用(2)的方法的方法*1|( )()| kxx *1|kL xx 2*2| kLxx *0|kLxx1121| | | kpkkpkpkpkpkkxxxxxxxx 10|1kkpkLxxxxL 2111210| |kkkkkkkxxL xxLxxLxx1211(1)|1|1ppkkkkLLLxxxxL 令令 即分別得即分別得,p *11|1kkk

15、xxxxL *10|1kkLxxxxL 定理定理1的幾點(diǎn)說(shuō)明的幾點(diǎn)說(shuō)明(i) 通常將條件通常將條件(1)稱為映內(nèi)性；稱為映內(nèi)性；(ii) 條件條件(2)也可以改為：存在常數(shù)也可以改為：存在常數(shù)L且且0L1使得使得| ( )( ) |, , xyL xyx ya b結(jié)論仍然成立結(jié)論仍然成立, 這個(gè)條件通常稱為壓縮性；這個(gè)條件通常稱為壓縮性；(iii) 結(jié)論結(jié)論(3)說(shuō)明說(shuō)明 的誤差大概是常數(shù)的誤差大概是常數(shù)*|kxx 乘上乘上Lk, 但是一般但是一般L未知未知;(iv) 結(jié)論結(jié)論(4)說(shuō)明說(shuō)明 與與 有關(guān)有關(guān)*|kxx 1|kkxx 因此得到迭代法的終止條件因此得到迭代法的終止條件1|kkxx

16、3 一般迭代法的算法一般迭代法的算法算法：算法：(1) 取初始點(diǎn)取初始點(diǎn)x0,最大迭代次數(shù)最大迭代次數(shù)N和精度要求和精度要求, 并置并置k=0；(2) 計(jì)算計(jì)算1();kkxx (3) 若若 則停止計(jì)算；則停止計(jì)算；1|,kkxx (4) 若若k=N, 則停止計(jì)算；否則則停止計(jì)算；否則k=k+1, 轉(zhuǎn)轉(zhuǎn)(2). 求方程xex-1=0在0.5附近的根,精度要求=10-3。解解 可以驗(yàn)證方程xex-1=0在區(qū)間0.5,0.61內(nèi)僅有一個(gè)根。例例 改寫方程為x=e-x ,建立迭代格式, 2 , 1 , 0,1kexkxk由于(x)=e-x ,在0.5,0.61上有|(x)|e-0.50.6 1，且(

17、x)0.5,0.61，所以迭代法收斂。 取x0=0.5,得kxk|xk-xk-1|kxk|xk-xk-1|0123450.50.606530.545240.579700.560060.571170.106530.061290.034460.019640.011116789100.564860.568440.566410.567560.566910.006310.003580.002030.001150.00065 所以,取近似根x*x10=0.56691滿足精度要求。 如果精度要求為=10-5, 則由LxxLkln)1 (ln0195.196 . 0ln10653. 0104 . 0ln5可知

18、,需要迭代20次。 實(shí)際上,方程在0.55,0.6上有唯一根，而此時(shí)|(x)|e-0.550.581. 若取L=0.58，則有 注意：這里迭代次數(shù)20是充分的但不是必要的。LxxLkln)1 (ln0150.42 10lnln0.5818.60.10653可知, 只需迭代19次。4 局部收斂定理局部收斂定理迭代序列迭代序列xk在區(qū)間在區(qū)間a,b上的收斂性通常稱為上的收斂性通常稱為全局收斂性全局收斂性. 實(shí)際應(yīng)用只在不動(dòng)點(diǎn)實(shí)際應(yīng)用只在不動(dòng)點(diǎn)x*的鄰近考的鄰近考察收斂性，稱為察收斂性，稱為局部收斂性局部收斂性.定義定義 設(shè)設(shè) 有不動(dòng)點(diǎn)有不動(dòng)點(diǎn)x*,如果存在如果存在x*的某個(gè)鄰域的某個(gè)鄰域( )x

19、*:|,Rxx 對(duì)任意的對(duì)任意的 迭代迭代(2.2)產(chǎn)生的產(chǎn)生的0 xR 序列序列 且收斂到且收斂到x*,則稱則稱(2.2)局部收斂局部收斂.kxR 證明證明 由連續(xù)函數(shù)的性質(zhì)由連續(xù)函數(shù)的性質(zhì),存在存在x*的某個(gè)鄰域的某個(gè)鄰域*:|,Rxx 對(duì)任意的對(duì)任意的 有有xR |( ) |1xL 而而*| ( )| | ( )() | |xxxxL xxxx根據(jù)定理根據(jù)定理1可以斷定迭代過(guò)程可以斷定迭代過(guò)程(2.2)對(duì)任意初對(duì)任意初值值 均收斂均收斂.0 xR 定理定理2 若若x*為迭代函數(shù)為迭代函數(shù) 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn), 在在x*( )x ( )x 的某個(gè)鄰域內(nèi)有連續(xù)導(dǎo)數(shù)的某個(gè)鄰域內(nèi)有連續(xù)導(dǎo)數(shù),且且

20、則則*|() | 1,x 迭代法迭代法(2.2)局部收斂局部收斂.21(1) 3( *)2 311; kkkxxxx ，13(2) ( *)1; kkxxx ，2113(3) (3)( *)10.134; 42kkkxxxx ，113(4) ()( *)0.2kkkxxxx ，例例 只用四則運(yùn)算不用開方求方程只用四則運(yùn)算不用開方求方程x2-3=0的根的根*3x 解解kxk迭代法迭代法(1) 迭代法迭代法(2) 迭代法迭代法(3)迭代法迭代法(4)0123 ? x0 x1 x2 x3 ?23987?21.521.5?21.751.734751.732631?21.751.7321431.7320

21、51?(1)和和(2)發(fā)散，發(fā)散， (3)和和(4)收斂收斂.例例 設(shè)設(shè)2( )(5),xxa x 試討論試討論a的取值范圍的取值范圍使迭代公式使迭代公式(2.2)局部收斂到局部收斂到*5x 解解 因?yàn)橐驗(yàn)?( )(5)xxa x 所以所以 由定理由定理2可知只需可知只需( )12,xax *|() | 1x 即即|12 5 | 1a105a 所以當(dāng)所以當(dāng) 時(shí)時(shí),迭代公式收斂迭代公式收斂.105a5 迭代收斂的階迭代收斂的階則稱該迭代為則稱該迭代為p 階收斂階收斂. . ( (C為常數(shù)為常數(shù)) )(1) (1) 當(dāng)當(dāng)p =1時(shí)稱為時(shí)稱為線性收斂線性收斂，此時(shí)，此時(shí)00C 1和和p =1且且C=

22、0時(shí)稱為時(shí)稱為超線性收斂超線性收斂. .定義定義 設(shè)迭代設(shè)迭代 收斂到收斂到 的不動(dòng)的不動(dòng)點(diǎn)點(diǎn)x*. 記記ek = xk x*，若若1|lim0|kpkkeCe 1()kkxx ( )x 例例: (1) 二分法線性收斂二分法線性收斂;(2)不動(dòng)點(diǎn)迭代中，若不動(dòng)點(diǎn)迭代中，若 則則線性收斂線性收斂*()0 x 解解: (2) 不動(dòng)點(diǎn)迭代中第不動(dòng)點(diǎn)迭代中第k+1步的誤差為：步的誤差為：*11| |*| |()()|kkkexxxx*1lim| lim()()1kkkkkexe *|()|(,)kkkkxxxx *|()|(,)kkkkexx *(1)*()*(1) (),(2) ()()()0,(3

23、) ()0ppxxxxxx ()*11lim()!pkpkkexep 則則定理定理3 設(shè)迭代設(shè)迭代 若若 在在x*的某的某1(),kkxx ()( )px 鄰域內(nèi)連續(xù)并滿足鄰域內(nèi)連續(xù)并滿足即該迭代法是即該迭代法是p階收斂的。階收斂的。*1()*()()()()() .()!kkkppkkxxxxxxxxp 證明：證明： 根據(jù)泰勒展開有根據(jù)泰勒展開有( )*1()()!ppkkkxxxxp ()*11lim()!pkpkkexep 6 迭代加速迭代加速若若 則迭代公式則迭代公式(2.2)只是線性收斂。只是線性收斂。*()0,x 迭代加速方法可對(duì)線性收斂的簡(jiǎn)單迭代迭代加速方法可對(duì)線性收斂的簡(jiǎn)單迭代

24、法起到加速作用。法起到加速作用。取初始點(diǎn)取初始點(diǎn)x0,令令 那么那么00()yx *00*0*0()()( )()()yxxxxxL xx *00000111()1LxyxLLLyyxL 由此得加速迭代公式由此得加速迭代公式1()1kkkkLxyyxL 此加速法的優(yōu)點(diǎn)：此加速法的優(yōu)點(diǎn)：迭代速度快；迭代速度快；此加速法的缺點(diǎn)：此加速法的缺點(diǎn)：迭代公式中有待定的迭代公式中有待定的L,使用不方便。使用不方便。令令 得到得到0000(),()yxzy*0000(),()yxL xxzxL yx*00*00yxxxzxyx2*000000()2yxxxzyx Steffensen迭代加速法迭代加速法*2

25、*000()()()yxzxxx由此得由此得Steffensen加速法加速法21(),()()2kkkkkkkkkkkyxzyyxxxzyx 0,1,k Steffensen加速法是平方收斂的加速法是平方收斂的.注注：果第：果第k步發(fā)生步發(fā)生zk-2yk+xk=0, 就終止計(jì)算就終止計(jì)算, 取取x* xk 。 分別用簡(jiǎn)單迭代法和Steffensen加速算法例例求方程 在 附近的根。1.60.99cosxx2 *(1.585471802)x 解：解：簡(jiǎn)單迭代法迭代公式簡(jiǎn)單迭代法迭代公式11.6 0.99coskkxx Steffensen迭代公式：迭代公式：21(),()()2kkkkkkkkk

26、kkyxzyyxxxzyx k簡(jiǎn)單迭代法簡(jiǎn)單迭代法kSteffensen迭代法迭代法xk|xk-xk-1|xk|xk-xk-1|012341.570801.61.571091.599711.571380.02920.028910.028620.028330121.57079631.585472581.585471800.014676280.00000078取取x0= /2, 計(jì)算結(jié)果如下計(jì)算結(jié)果如下: Newton迭代法是求方程根的重要方法迭代法是求方程根的重要方法之一之一,其最大優(yōu)點(diǎn)是在方程的單根附近具有其最大優(yōu)點(diǎn)是在方程的單根附近具有平方收斂平方收斂,而且而且Newton迭代法還可用來(lái)求方

27、迭代法還可用來(lái)求方程的重根、復(fù)根及非線性方程組。程的重根、復(fù)根及非線性方程組。三、三、 Newton法法1 Newton法基本思想法基本思想2( )( )()()()()2!kkkkff xf xfxxxxx 設(shè)設(shè)xk是是f (x)=0的近似根的近似根, ,將將f (x)在在xk一階一階Taylor 展開展開: :( ( 在在xk和和x之間之間) )*0()f x *()()()kkkf xfxxx *()()kkkf xxxfx 當(dāng)當(dāng) f (x) 0時(shí)時(shí), , , ,于是于是 即為即為Newton迭代公式迭代公式.1()()kkkkf xxxfx xyx*xkxk+1Newton法的幾何意義

28、法的幾何意義()()()kkkyf xfxxx Newton法的本質(zhì)就是不斷用切線來(lái)近似曲法的本質(zhì)就是不斷用切線來(lái)近似曲線，因此線，因此Newton法也成為法也成為切線法切線法.1()0()kkkkf xyxxfx 2 Newton法的算法法的算法(1) 取初始點(diǎn)取初始點(diǎn)x0,最大迭代次數(shù)最大迭代次數(shù)N和精度要求和精度要求置置k=0;(2) 計(jì)算計(jì)算1();()kkkkf xxxfx (3) 若若 則停止計(jì)算則停止計(jì)算;1|kkxx (4) 若若k=N則停止計(jì)算則停止計(jì)算;否則置否則置k=k+1,轉(zhuǎn)轉(zhuǎn)(2).Newton 法可以看作下面的不動(dòng)點(diǎn)迭代：法可以看作下面的不動(dòng)點(diǎn)迭代：1()kkxx

29、其中其中( )( )( )f xxxfx 2( ) ( )( )( )f x fxxfx (x*) = 0 (若若f(x*)=0,f(x*)0，即，即x*是單根）是單根）Newton 法至少法至少二階局部收斂二階局部收斂3 Newton法收斂性法收斂性定理定理4 設(shè)設(shè)f(x)在其零點(diǎn)在其零點(diǎn)x*的某個(gè)鄰域內(nèi)二階連的某個(gè)鄰域內(nèi)二階連續(xù)可導(dǎo)且續(xù)可導(dǎo)且f(x) 0，則存在，則存在x*的的某個(gè)某個(gè) 鄰域鄰域N(x*) =x*- , x* + , 使得對(duì)使得對(duì) x0 N(x*)，Newton法產(chǎn)生的序列以法產(chǎn)生的序列以不低于不低于二階的收斂速度收斂二階的收斂速度收斂到到 x* . .證明證明 (略略)N

30、ewton 法也可以看作一類特殊的加速迭代法也可以看作一類特殊的加速迭代1()1()1()1()kkkkkkxxxxxx （ (x) = x - -f (x)）取x0=0.5,計(jì)算結(jié)果如下:例例4 用Newton迭代法求方程xex-1=0在0.5附近的根,精度要求=10-5. 解解 Newton迭代格式為11,0,1,2,1kkkkxkkkxxkxkkkx exxex exexkx kxk(xk)|xk-xk-1|012340.50.571020440.567155570.567143290.56714329-0.175639360.010747510.000033930.0000000003

31、0.00000000030.071020440.003864870.000012280.00000000 從結(jié)果可見從結(jié)果可見 ,Newton迭代法迭代迭代法迭代3次已獲得次已獲得精確到小數(shù)點(diǎn)后五位的近似解精確到小數(shù)點(diǎn)后五位的近似解,迭代迭代4次已獲得次已獲得精確到小數(shù)點(diǎn)后八位的近似解精確到小數(shù)點(diǎn)后八位的近似解.與一般迭代法比與一般迭代法比較可見較可見Newton迭代法收斂的確實(shí)快迭代法收斂的確實(shí)快.例 設(shè)計(jì)一個(gè)二階收斂算法計(jì)算設(shè)計(jì)一個(gè)二階收斂算法計(jì)算 (a 0).a解：轉(zhuǎn)化為求解：轉(zhuǎn)化為求 x2-a = 0 的正根的正根Newton 迭代：迭代：221()()22kkkkkkkkkf xxa

32、xaxxxfxxx 212kkkxaxaax 22222kkkkkxaxaxaxx 1212kkkxaxxa 12 a二階收斂二階收斂取取x0=1.7，計(jì)算得：，計(jì)算得：2133222kkkkkkxxxxxx 所以取x3=1.732050808 3kxk|xk-xk-1|01231.71.7323529411.7320508341.7320508080.0323529410.0003021070.000000026例例 用Newton迭代法求解解 對(duì)方程x2-3=0應(yīng)用Newton迭代法： 的近似值,要求=10-7。3設(shè)設(shè)x*是是f(x)的的m(m 2)重根重根, Newton法是否收斂？法是

33、否收斂？*(1)*()*()()()0, ()0mmf xfxfxfx Taylor 展式展式()*11( )()()!mmf xfxxm ()*121( )()()(1)!mmfxfxxm ()*231( )()()(2)!mmfxfxxm 4 重根情況重根情況*()*()*2132()*1211()()()()!(2)!lim1()()(1)!mmmmxxmmfxxfxxmmfxxm 所以所以Newton 迭代：迭代：( )( )( )f xxxfx *2*( ) ( )()lim( )lim( )xxxxf x fxxxfx 111m 線性收斂線性收斂, 且重?cái)?shù)且重?cái)?shù)m越高越高, 收斂越

34、慢收斂越慢.提高收斂速度提高收斂速度但但m通常無(wú)法預(yù)先知道！通常無(wú)法預(yù)先知道！法一：取法一：取 ( )( )(2)( )f xxxmmfx *()0 x 二階收斂二階收斂注注: 推導(dǎo)過(guò)程與前面類似推導(dǎo)過(guò)程與前面類似.法二：將求法二：將求f(x)的重根轉(zhuǎn)化為求另一個(gè)函數(shù)的重根轉(zhuǎn)化為求另一個(gè)函數(shù) 的單根的單根. . 構(gòu)造針對(duì)構(gòu)造針對(duì) (x) 的具有二階收斂的的具有二階收斂的Newton迭代：迭代： 2( )( ) ( )( )( )( )( ) ( )xf x fxxxxxfxf x fx 令令 ，則，則x*是是 (x)的單重根的單重根. . ( )( )( )f xxfx 例例 取初始點(diǎn)取初始點(diǎn)x0=1.5, 分別用分別用Newton法和求重根法和求重根的兩種方法計(jì)算的兩種方法計(jì)算 f(x)=(x+ +1)(x- -1)2=0解解 (1) Newton法迭代公式法迭代公式1(1)(1)31kkkkkxxxxx k012345xk1.51.2727 1.1441 1.0744 1.0378