非線(xiàn)性方程組解法

1、非線(xiàn)性方程非線(xiàn)性方程 (組組) 解法的內(nèi)容解法的內(nèi)容 非線(xiàn)性方程的解法非線(xiàn)性方程的解法 非線(xiàn)性方程非線(xiàn)性方程組組的解法的解法 1. 解法解法牛頓法及牛頓型迭代法（擬牛頓法等牛頓法及牛頓型迭代法（擬牛頓法等) )；搜索法；搜索法；牛頓迭代法；牛頓迭代法； 弦截法；弦截法；多項(xiàng)式方程求根多項(xiàng)式方程求根延拓法；延拓法；最速下降法；最速下降法；2. 簡(jiǎn)單迭代法與牛頓迭代法的收斂性簡(jiǎn)單迭代法與牛頓迭代法的收斂性2.牛頓法、割線(xiàn)法、延拓法等的收斂性牛頓法、割線(xiàn)法、延拓法等的收斂性二分法；二分法； 簡(jiǎn)單迭代法；簡(jiǎn)單迭代法；（牛頓法、劈因子法）（牛頓法、劈因子法）1. 解法解法非線(xiàn)性最小二乘問(wèn)題的計(jì)算方法非線(xiàn)

2、性最小二乘問(wèn)題的計(jì)算方法1 基礎(chǔ)知識(shí)基礎(chǔ)知識(shí)1.1 非線(xiàn)性方程非線(xiàn)性方程(組組)及解的概念及解的概念2.常見(jiàn)的非線(xiàn)性方程常見(jiàn)的非線(xiàn)性方程高次方程高次方程, ,即多項(xiàng)式即多項(xiàng)式方程方程超越方程超越方程 例例1. 產(chǎn)生的背景產(chǎn)生的背景:科學(xué)理論與工程技術(shù)都可化為非線(xiàn)性方程科學(xué)理論與工程技術(shù)都可化為非線(xiàn)性方程(組組)第七章第七章 非線(xiàn)性方程（組）解法非線(xiàn)性方程（組）解法非線(xiàn)性最小二乘問(wèn)題；非線(xiàn)性最小二乘問(wèn)題；非線(xiàn)性積分、微分方程數(shù)值解非線(xiàn)性積分、微分方程數(shù)值解0)2sin( xex; 1cos xex 3.非線(xiàn)性方程的解：非線(xiàn)性方程的解：f (x)=0的根，或稱(chēng)為函數(shù)的根，或稱(chēng)為函數(shù)f (x)的零點(diǎn)

3、的零點(diǎn).注：注：()方程的根可能是實(shí)數(shù)也可能是復(fù)數(shù)，相應(yīng)地稱(chēng)為方程方程的根可能是實(shí)數(shù)也可能是復(fù)數(shù)，相應(yīng)地稱(chēng)為方程的的實(shí)根實(shí)根或或復(fù)根復(fù)根。如果函數(shù)如果函數(shù)f (x)可因式分解為可因式分解為且且 )()()(xgxxxfm 0)( xg稱(chēng)稱(chēng)x*為為函數(shù)函數(shù)f (x)的的m重零點(diǎn)重零點(diǎn)，或稱(chēng)為，或稱(chēng)為方程方程f (x)=0的的m重根重根;當(dāng)當(dāng)m時(shí)，時(shí)，稱(chēng)稱(chēng)x*為為函數(shù)函數(shù)f (x)的的單重零點(diǎn)單重零點(diǎn)，又稱(chēng)作，又稱(chēng)作方程方程f (x)=0的的單根單根 ; 如果如果稱(chēng)稱(chēng)x*為方程為方程f (x)=0的的m重根重根.，1 m() 重根亦可利用導(dǎo)數(shù)來(lái)定義重根亦可利用導(dǎo)數(shù)來(lái)定義(略略)。若存在數(shù)若存在數(shù)

4、x*滿(mǎn)足滿(mǎn)足 f (x*)=0，則，則x*稱(chēng)為方程稱(chēng)為方程記為：記為： f (x)=0求解的特點(diǎn)：求解的特點(diǎn)： 無(wú)求解公式，無(wú)直接解法無(wú)求解公式，無(wú)直接解法，難求得精確解。難求得精確解。舉例舉例: :超越方程超越方程1.2 非線(xiàn)性方程非線(xiàn)性方程(組組)求解的特點(diǎn)求解的特點(diǎn)1cos xex 間接法間接法( (迭代法迭代法):):從一個(gè)初始近似值出發(fā)從一個(gè)初始近似值出發(fā), ,重復(fù)某種計(jì)算過(guò)程重復(fù)某種計(jì)算過(guò)程沒(méi)有一定的解法。沒(méi)有一定的解法。間接法即迭代法。間接法即迭代法。來(lái)來(lái)不斷改進(jìn)近似解不斷改進(jìn)近似解，有限次改進(jìn)后有限次改進(jìn)后, ,計(jì)算出一個(gè)滿(mǎn)足誤差要求計(jì)算出一個(gè)滿(mǎn)足誤差要求的的近似解近似解，這種

5、求解方法稱(chēng)為這種求解方法稱(chēng)為迭代法迭代法。求解的方法：求解的方法：迭代法求解的要求：迭代法求解的要求： l 收斂收斂l 計(jì)算效率計(jì)算效率( (計(jì)算量計(jì)算量) )l 數(shù)值穩(wěn)定性數(shù)值穩(wěn)定性( (計(jì)算機(jī)的舍入誤差計(jì)算機(jī)的舍入誤差) ) 初始值好初始值好迭代公式合適迭代公式合適( (好的好的) ).,lim*)(*)( kxxxxkkk當(dāng)當(dāng)或或并并記記為為1.3 收斂性和收斂階收斂性和收斂階定義定義1成成立立及及點(diǎn)點(diǎn)列列對(duì)對(duì)于于點(diǎn)點(diǎn) 0*2*1*),(kknxxxxx, 0|lim*)( xxkk.*0)(xxkk收收斂斂于于點(diǎn)點(diǎn)則則稱(chēng)稱(chēng)點(diǎn)點(diǎn)列列 序列的收斂性序列的收斂性 序列的收斂階序列的收斂階稱(chēng)稱(chēng)

6、若若, 1 , 0,lim*)(*)( kxxxxkkk(1)(1)線(xiàn)性的線(xiàn)性的, ,若若收收斂斂于于 0kkx定義定義2是是點(diǎn)點(diǎn)*x);1 , 0(|lim*)(*)1( Cxxxxkkk(2)(2)超線(xiàn)性的超線(xiàn)性的, ,若若(3) p 階收斂的階收斂的, ,若若;0|lim*)(*)1( xxxxkkk. 1, 0|lim*)(*)1( pCxxxxpkkk注注 ：= =2時(shí)為二階收斂時(shí)為二階收斂, , 也稱(chēng)為也稱(chēng)為平方平方收斂收斂。2初始近似值的搜索、二分法和插值法初始近似值的搜索、二分法和插值法 2.1逐步搜索法逐步搜索法滿(mǎn)足條件，滿(mǎn)足條件，2. 解決問(wèn)題依據(jù)解決問(wèn)題依據(jù) 連續(xù)函數(shù)介值

7、定理連續(xù)函數(shù)介值定理, ,即若即若f( (x) )滿(mǎn)足條件：滿(mǎn)足條件：即即 a, ,b 內(nèi)至少有方程內(nèi)至少有方程(2.1)的一個(gè)根的一個(gè)根, ,0)()(,)( bfafbaCxf且且, 0)(* xf使使得得稱(chēng)稱(chēng) a, ,b 為為f( (x) )的一個(gè)的一個(gè)含根區(qū)間含根區(qū)間。若非線(xiàn)性方程若非線(xiàn)性方程 f( (x)=0 )=0 (2.1) ba2ba *x1. 問(wèn)題問(wèn)題3. 逐步搜索法思想方法（基本思想）逐步搜索法思想方法（基本思想）根分布如何？如何確定求根區(qū)間？根分布如何？如何確定求根區(qū)間？ 如何求根？如何求根？把含根區(qū)間不斷縮短，把含根區(qū)間不斷縮短，求的近似解。求的近似解。，那么方程是否，

8、那么方程是否有根？有根？ 有根有根則則f( (x) )在在 a, ,b 存在某個(gè)存在某個(gè)x* *0)()(,)( bfafbaCxf且且且使含根區(qū)間之且使含根區(qū)間之間間含有一個(gè)滿(mǎn)足誤差要含有一個(gè)滿(mǎn)足誤差要設(shè)連續(xù)函數(shù)設(shè)連續(xù)函數(shù)f( (x) )的含根區(qū)間為的含根區(qū)間為 a, ,b ，不妨假定不妨假定 f( (a) )，從從出發(fā)出發(fā)，按預(yù)定步長(zhǎng)按預(yù)定步長(zhǎng)h （譬如?。ㄆ┤缛?ax 0NNabh, 為正整數(shù)），一步為正整數(shù)），一步每跨一步進(jìn)行一次根的每跨一步進(jìn)行一次根的“搜索搜索”，即檢查點(diǎn)，即檢查點(diǎn) khaxk 上的函數(shù)值上的函數(shù)值 )(kxf的符號(hào)，一旦發(fā)現(xiàn)的符號(hào)，一旦發(fā)現(xiàn) 處處的的函函數(shù)數(shù)值值異

9、異號(hào)號(hào)，即即處處與與axk, 0)( kxf一步地向右跨，一步地向右跨， 則可確定一個(gè)縮小了的含根區(qū)間則可確定一個(gè)縮小了的含根區(qū)間,1kkxx ，其長(zhǎng)度等于預(yù)，其長(zhǎng)度等于預(yù) 定的步長(zhǎng)定的步長(zhǎng)h。 特別地，可能有特別地，可能有, 0)( kxf這時(shí)這時(shí)xk即為所求的根。即為所求的根。 例例1 方程方程 f( (x)=)=x3- -x-1=0-1=0，利用逐步搜索法確定一個(gè)含根區(qū)間。利用逐步搜索法確定一個(gè)含根區(qū)間。 解解 )0(f在區(qū)間（在區(qū)間（0，2）內(nèi)至少有一個(gè)實(shí)根。）內(nèi)至少有一個(gè)實(shí)根。 設(shè)從設(shè)從x=0=0出發(fā)，取出發(fā)，取h=0.5為步長(zhǎng)向右進(jìn)行根的搜索，為步長(zhǎng)向右進(jìn)行根的搜索， 列表如下列表

10、如下 x 0 0.5 1.0 1.5 2f (x) - - - - - - + + + + 可以看出在可以看出在 1.0, 1.5內(nèi)必有內(nèi)必有唯一唯一根根).0)(5 . 1, 0 . 1( xfx時(shí)時(shí)，當(dāng)當(dāng)4. 具體過(guò)程（方法）具體過(guò)程（方法）)(, 0)2(, 0 xff 2.2 二分法二分法(對(duì)分法或分半法對(duì)分法或分半法)（滿(mǎn)足條件（滿(mǎn)足條件 ）2. 解決問(wèn)題依據(jù)解決問(wèn)題依據(jù) 連續(xù)函數(shù)介值定理連續(xù)函數(shù)介值定理, ,至少存在某個(gè)至少存在某個(gè)即即 a, ,b 內(nèi)至少有方程內(nèi)至少有方程(2.1)(2.1)的一個(gè)根的一個(gè)根, ,稱(chēng)稱(chēng) a, ,b 為為f( (x) ) 0)()(,)( bfafb

11、aCxf且且),(*bax , 0)(* xf使使得得的一個(gè)的一個(gè)含根區(qū)間含根區(qū)間。2*bax 3. 思想方法（基本思想思想方法（基本思想）把含根區(qū)間不斷縮短，使含根區(qū)間之把含根區(qū)間不斷縮短，使含根區(qū)間之間間含有一個(gè)滿(mǎn)足誤差含有一個(gè)滿(mǎn)足誤差要求的近似解。要求的近似解?？紤]非線(xiàn)性方程考慮非線(xiàn)性方程 f( (x)=0 )=0 (2.1)(2.1) ba2ba 并且有并且有 *x2ab 1. 問(wèn)題問(wèn)題);(21)1(000bax 找找中中點(diǎn)點(diǎn)：令令；即即中中點(diǎn)點(diǎn)的的函函數(shù)數(shù)值值計(jì)計(jì)算算：)()2(00 xff (3) 生成含根區(qū)間：生成含根區(qū)間：,0)(0*0 xxxf ，則則若若, 0)()(00

12、 afxf若若,0101bbxa 取取, 0)()(010100 xbaaafxf 取取若若4 4 具體過(guò)程（方法）具體過(guò)程（方法）,00abhbbaa 令令首首先先滿(mǎn)足下式滿(mǎn)足下式: :生成含根區(qū)間生成含根區(qū)間,11ba,)1(0011baba 2)2(11hab 11(3)()()0f af b .,220011bababa得得繼繼續(xù)續(xù)以以上上過(guò)過(guò)程程取取代代以以,11ba且且kibaii, 1 , 0, ，設(shè)設(shè)已已得得含含根根區(qū)區(qū)間間 , 2 , 1,)1(11kibabaiiii , 1 ,0,2)2(kihabiii (3)()() 0,0,1, .iif af bik 0,0,從而

13、函數(shù)從而函數(shù)f( (x) )在區(qū)間在區(qū)間1.0, 1.5上單調(diào)連續(xù)上單調(diào)連續(xù)， , 0875. 0) 5 . 1 (, 01) 1 ( ff所以函數(shù)所以函數(shù)f( (x) )在區(qū)間在區(qū)間1.0, 1.5上有唯一根。上有唯一根。 計(jì)算過(guò)程見(jiàn)表計(jì)算過(guò)程見(jiàn)表2-1表表 2-101234561.0001.25001.31251.32031.50001.37501.34381.32811.25001.37501.31251.34381.32811.32031.3242kkakbkx)(kxf則則x6 = =1.3242為方程根的近似值為方程根的近似值.例例3證明方程證明方程0sin1 xx在區(qū)間在區(qū)間0

14、, 1內(nèi)有一個(gè)根內(nèi)有一個(gè)根,使用二分使用二分法求誤差不大于法求誤差不大于 41021 的根的根, 需二分多少次需二分多少次證證,sin1)(xxxf 令令, 1 , 0時(shí)時(shí)則則當(dāng)當(dāng) x, 0cos1)( xxf所以所以f( (x) )在在0 , 1上單調(diào)減少且連續(xù)。上單調(diào)減少且連續(xù)。, 01sin) 1 (, 01)0( ff又又所以所以f( (x) )在在0 , 1上有且只有一個(gè)根上有且只有一個(gè)根.使用二分法時(shí)，誤差限使用二分法時(shí)，誤差限)(211abxxnn ,10212141 n28.13214)01(1 ggn則則 所以需二分所以需二分14 次即可次即可.(ln102.3026,ln2

15、0.6931). 例例1 ,102 在在x012 x不能求出所有根不能求出所有根,(,(即有可能漏根即有可能漏根) )。例例如圖如圖該點(diǎn)可求出該點(diǎn)可求出, ,改進(jìn)的方法：改進(jìn)的方法：xab但漏掉了四個(gè)點(diǎn)但漏掉了四個(gè)點(diǎn)2.2.不能用于求偶重根、復(fù)根；不能推廣到多元方程組求解不能用于求偶重根、復(fù)根；不能推廣到多元方程組求解. .缺點(diǎn)缺點(diǎn) 的等比級(jí)數(shù)的收斂速度的等比級(jí)數(shù)的收斂速度相同，相同，1.1.收斂速度不快收斂速度不快, ,僅與公比為僅與公比為 21即是線(xiàn)性收斂；即是線(xiàn)性收斂；區(qū)間搜索法等區(qū)間搜索法等. . 1. .理解理解收斂性、收斂階的概念；收斂性、收斂階的概念； 3. .會(huì)用會(huì)用二分法求二

16、分法求非線(xiàn)性方程的近似解及執(zhí)行次數(shù)非線(xiàn)性方程的近似解及執(zhí)行次數(shù)k . . 2. .理解理解逐步搜索法搜索非線(xiàn)性方程解的思想方法逐步搜索法搜索非線(xiàn)性方程解的思想方法, ,理解理解掌握掌握二二作業(yè)作業(yè)1. 用搜索法求方程用搜索法求方程 065. 015. 08 . 123 xxx的有根區(qū)間的有根區(qū)間. 2. 用區(qū)間二分法求方程用區(qū)間二分法求方程 在在1,2的近似根（二分的近似根（二分3次）次）,013 xx并求若近似根準(zhǔn)確到并求若近似根準(zhǔn)確到10-3至少要二分多少次？至少要二分多少次？ 3. 用區(qū)間二分法求方程用區(qū)間二分法求方程在在3,4內(nèi)的根，精確內(nèi)的根，精確074223 xxx到到10-3。

17、分法分法解非線(xiàn)性方程的思想方法；解非線(xiàn)性方程的思想方法； 復(fù)習(xí)：復(fù)習(xí)： 3. 3. 正割法正割法解非線(xiàn)性方程的解非線(xiàn)性方程的思想方法思想方法、迭代公式迭代公式： 2.2. 二分法二分法解解非線(xiàn)性方程的非線(xiàn)性方程的條件條件、思想方法思想方法、執(zhí)行次數(shù)、執(zhí)行次數(shù)k：稱(chēng)稱(chēng)若若, 1 , 0,lim*)(*)( kXXXXkkk(1)(1)線(xiàn)性的線(xiàn)性的, ,若若收收斂斂于于 0kkX(2)(2)超線(xiàn)性的超線(xiàn)性的, ,若若;0lim*)(*)1( XXXXkkk);1 , 0(lim*)(*)1( CXXXXkkk. 1, 0lim*)(*)1( pCpkkXXXXk( (3)3)p p階收斂的階收斂的

18、, ,若若1. 序列的序列的收斂階收斂階：. 12lnln abN0 給定的誤差界給定的誤差界)()()(111kkkkkkkxfxfxfxxxx 是是點(diǎn)點(diǎn)*X為為含含根根區(qū)區(qū)間間,ba2.32.3 拋物線(xiàn)法拋物線(xiàn)法1 1 方法的推導(dǎo)（迭代公式）方法的推導(dǎo)（迭代公式）（二次插值）（二次插值） 設(shè)設(shè)f(x)=0f(x)=0的根為的根為,*x*x（即（即為方程為方程f(x)=0f(x)=0的精確解）的精確解）可由數(shù)據(jù)點(diǎn)可由數(shù)據(jù)點(diǎn)2 , 1 , 0),( ifxikik，構(gòu)造拋物線(xiàn)，構(gòu)造拋物線(xiàn)二階差商二階差商一階差商一階差商牛頓插值牛頓插值)(,)(1kkkkxxfxxfxp )(,112 kkkk

19、kxxxxfxxx)(a1 k次近似次近似,1 kx已已知知，若若kkkkkkfxffxffxf )(,)(,)(1122，k時(shí)時(shí)當(dāng)當(dāng)2 的的是是設(shè)設(shè)*,12xxxxkkk kkk, 1, 2 次近似，次近似，構(gòu)造構(gòu)造用用p(x)p(x)近似近似f(x),f(x),根。根。1 kxkx取取P(x)=0P(x)=0較靠近較靠近的根的根為為f(x)=0的改進(jìn)近似的改進(jìn)近似考慮考慮kkxx 1的最小值，的最小值， 變形變形( (a)a)式式( (插項(xiàng)插項(xiàng)),于是于是,kkxx 得得由由,0)( xp0)()(2 kkkkkxxcxxba則有則有0)()(,)(,12121 kkkkkkkkkkkxx

20、xxxxfxxxxxfxxfkakc)1 (kb)(,11 kkkkkxxcfxx得得由由,0)( xp)(,)(1kkkkxxfxxfxp )(,112 kkkkkxxxxfxxx)(akkxx ,0時(shí)時(shí)當(dāng)當(dāng) kkaf*xxk kkkkkkacabbxx2412 kkkkkkcabbaxx422 ,*xxk 且有且有)1 (0)1()1(2 kkkkkcxxbxxa,4sgn221kkkkkkkkcabbbaxx 取取由此可得（由此可得（2.10）;1kkxx ,0時(shí)時(shí)當(dāng)當(dāng) kkafkkkkkkcabbaxx422 )()(12kkkkkkxxxxcxxc 2 2 局部收斂定理局部收斂定理只

21、要只要,*210 xxxxx 拋物線(xiàn)法產(chǎn)生的迭代序列拋物線(xiàn)法產(chǎn)生的迭代序列kx收斂于收斂于,*x且有且有.)(6)(lim420. 0*840. 1*1*xfxfxxxxkkk 設(shè)設(shè)f(x)f(x)在在*x, 0)(* xf則存在則存在, 0 附近附近3 3次連續(xù)可導(dǎo)，次連續(xù)可導(dǎo)，)(,11 kkkkkkxxcfxxb)(kkxfa fxxxckkkk,21 ,4sgn221kkkkkkkkcabbbaxx )10. 2(繼續(xù)以上過(guò)程，這種生成迭代序列的求根算法稱(chēng)為繼續(xù)以上過(guò)程，這種生成迭代序列的求根算法稱(chēng)為拋物線(xiàn)法拋物線(xiàn)法。定理定理2 2, 3 , 2 k,210 xxx由由給給定定的的可由

22、可由(2.10) 式迭代求更接近式迭代求更接近的近似解的近似解 。*x3x)11. 2(注：注： 1 1 拋物線(xiàn)法可產(chǎn)生實(shí)根，也可產(chǎn)生復(fù)根。拋物線(xiàn)法可產(chǎn)生實(shí)根，也可產(chǎn)生復(fù)根。2 2 更高次的插值多項(xiàng)式很少選用更高次的插值多項(xiàng)式很少選用, ,一是高次插值多項(xiàng)式求根困一是高次插值多項(xiàng)式求根困難難, ,二是其收斂速度不會(huì)太快，即收斂階總低于二是其收斂速度不會(huì)太快，即收斂階總低于2 2。2.42.4* * 反插值法反插值法設(shè)設(shè)f(x)=0f(x)=0的根為的根為.*x由數(shù)據(jù)點(diǎn)由數(shù)據(jù)點(diǎn), 1 , 0),(lixyikik 得得)(y 的的l次插值函數(shù)。次插值函數(shù)。差商差商取取)0(1qxk )()(yy

23、q 令令則則,) 1(,1121111 lkkklkklkkkkkkkkkkyyyyyyyyyyyyyxx )13. 2(該方法稱(chēng)為該方法稱(chēng)為反插值法反插值法。)(xfy 有反函數(shù)有反函數(shù))(yx 且且).0(* x若若f(x)f(x)在在鄰近嚴(yán)格單調(diào)鄰近嚴(yán)格單調(diào)*x)()(,)(,)(,)(111211 lkkklkkkkkkkkkkkyyyyyyyyyyyyyyyyyyyxyq :11* kxkx次次近近似似的的是是若若lkkkxxx ,1個(gè)已知近似值，個(gè)已知近似值，構(gòu)造構(gòu)造1 l注：注： 1 1 當(dāng)當(dāng)1 l 時(shí)，反插值法完全重合于正割法。時(shí)，反插值法完全重合于正割法。2 2 反插值法是局

24、部收斂的反插值法是局部收斂的, ,且收斂階低于且收斂階低于2 2。思考：思考：總結(jié)：總結(jié)：上上討論拋物線(xiàn)法，但平時(shí)很少用拋物線(xiàn)法，因?yàn)樵摲椒ㄓ?jì)算量大，討論拋物線(xiàn)法，但平時(shí)很少用拋物線(xiàn)法，因?yàn)樵摲椒ㄓ?jì)算量大，且收斂階不高。且收斂階不高。幾種插值法的條件不同幾種插值法的條件不同。正割法是常用的方法，理論正割法是常用的方法，理論當(dāng)當(dāng)2 l 時(shí)，反插值法是否是拋物線(xiàn)法時(shí)，反插值法是否是拋物線(xiàn)法？解解x=x=g(xg(x) )的簡(jiǎn)單迭代法的簡(jiǎn)單迭代法3.1 3.1 簡(jiǎn)單迭代法公式簡(jiǎn)單迭代法公式問(wèn)題問(wèn)題: : f(xf(x) )實(shí)函數(shù)實(shí)函數(shù). .求求f(xf(x)=0)=0的近似值的近似值。, 1 , 0

25、),(1 kxgxkk(1)(1)先將先將f(xf(x)=0)=0化為等價(jià)方程化為等價(jià)方程)(xgx )1.3(初始近似初始近似k+1次近似次近似( (迭代公式迭代公式) )2.3(*x若若kx)( xg收斂于收斂于且且連續(xù)連續(xù), ,則則*x是是f(xf(x)=0)=0的根的根。說(shuō)明說(shuō)明: : 由由f(xf(x)=0)=0化成等價(jià)方程化成等價(jià)方程x=x=g(xg(x) )的化法有很多種。的化法有很多種。(1) (1) 如何選取如何選取迭代函數(shù)迭代函數(shù)g(xg(x) )？ (3.2) (3.2)式稱(chēng)為式稱(chēng)為簡(jiǎn)單迭代法簡(jiǎn)單迭代法或或單點(diǎn)迭代法單點(diǎn)迭代法或或單步迭代法單步迭代法。 g(x)稱(chēng)稱(chēng)為為迭

26、代函數(shù)。迭代函數(shù)?；舅枷敕椒ǎ夯舅枷敕椒ǎ撼霭l(fā)出發(fā), ,作序列作序列:kx0 x(2) 從某從某討論的問(wèn)題討論的問(wèn)題: :(2) (2) g(xg(x) )滿(mǎn)足什么條件，迭代序列收斂？收斂速度是多少？滿(mǎn)足什么條件，迭代序列收斂？收斂速度是多少？(3) (3) 如何加速如何加速迭代序列的收斂速度迭代序列的收斂速度？(2)(2)(3)(3)問(wèn)題問(wèn)題: : 由由,)(1 kkxxg求求1 kxkx，然而，然而是否是是否是g(xg(x) )定義域上的值定義域上的值? ?定義定義4 4簡(jiǎn)單迭代法簡(jiǎn)單迭代法(3.2)(3.2)稱(chēng)為稱(chēng)為適定適定的；的；法法(3.2)稱(chēng)為稱(chēng)為收斂收斂的。的。當(dāng)?shù)?dāng)?shù)?

27、3.2)(3.2)收斂時(shí)收斂時(shí), ,極限點(diǎn)極限點(diǎn)又是又是g(xg(x) )的連續(xù)點(diǎn)的連續(xù)點(diǎn), ,則則*x1*lim kkxx的解也稱(chēng)的解也稱(chēng)的不動(dòng)點(diǎn)。的不動(dòng)點(diǎn)。)(xg的不動(dòng)點(diǎn)。的不動(dòng)點(diǎn)。稱(chēng)為稱(chēng)為則則)(xg*x也可理解成：也可理解成：是映射，若是映射，若 滿(mǎn)足滿(mǎn)足)(xg*x),(*xgx 。g(x)把定義域的每個(gè)把定義域的每個(gè)x 映成了映成了g(x)，因此因此)2 .3(的的解解是是即即)2 .3(*xkx保持有界保持有界, ,若迭代序列若迭代序列且全在且全在g(xg(x) )定義域內(nèi)定義域內(nèi), ,則則.lim*xxkk 若進(jìn)一步有若進(jìn)一步有則簡(jiǎn)單迭代則簡(jiǎn)單迭代)(limkkxg )()l

28、im(*xgxgkk , 1 , 0),(1 kxgxkk迭代公式迭代公式)2.3(注注: : 適定適定是是收斂收斂必要條件，即不必要條件，即不適定適定則一定不則一定不收斂收斂。1)(0*xg說(shuō)明兩點(diǎn)：說(shuō)明兩點(diǎn)：分別就下列四種情況說(shuō)明幾何意義：分別就下列四種情況說(shuō)明幾何意義：kxkx(1)(1)中中的產(chǎn)生。的產(chǎn)生。（2 2）kx何時(shí)收斂何時(shí)收斂, ,何時(shí)發(fā)散。何時(shí)發(fā)散。0)(1*xg1)(* xg1)(* xgy)(xgy xy x0 x1x2x0p1p2p00 x1x2x0p1p2pxy 0*xxy)(xgy幾何意義幾何意義 )( xgyxy求求x=x=g(xg(x) )的根的根求求的根的根

29、*x*x1p0 x1x2x0p2p)(xgy xy xy0*x*x0p2p0 x*x1x2x1p)(xgy xy 0 xy*x 迭代法收斂迭代法收斂*xxk迭代法不收斂迭代法不收斂從點(diǎn)從點(diǎn))(,(000 xgxp的直線(xiàn)交的直線(xiàn)交y=xy=x于點(diǎn)于點(diǎn)出發(fā)出發(fā), ,作平行于作平行于x x軸軸),(),(00 xgxg作平行于作平行于y y 軸的直線(xiàn)交軸的直線(xiàn)交y =y =g(xg(x) )于點(diǎn)于點(diǎn)過(guò)該點(diǎn)過(guò)該點(diǎn)),(),(001xggxgp即即).(,(111xgxp依次進(jìn)行下去得到依次進(jìn)行下去得到,kx且且).(1kkxgx 1. 1. 簡(jiǎn)單迭代法簡(jiǎn)單迭代法(2)(2)給定給定0kxx 滿(mǎn)足滿(mǎn)足。

30、, 1 , 0),(1 kxgxkk2. 2. 收斂定理收斂定理定理定理3 3；)(0)(xgxxf (1)方法步驟方法步驟: :( (壓縮不動(dòng)點(diǎn)定理或壓縮映象定理壓縮不動(dòng)點(diǎn)定理或壓縮映象定理) )若迭代函數(shù)若迭代函數(shù)g(xg(x) )滿(mǎn)足滿(mǎn)足) 3 . 3(,)()1(baxbaxg , 10)2( L使使,baxx 有有xxLxgxg )()() 4 . 3(則則；內(nèi)內(nèi)有有唯唯一一解解在在*0,)(1xbaxgx ；且且得得到到的的由由對(duì)對(duì)*10lim,)(,2xxbaxxgxbaxkkkkko ；有有誤誤差差估估計(jì)計(jì)011*0111:3xxLLxxLxxkkkk )5 . 3()(lim

31、,)(4*1*0 xgxxxxxgkkk 則則存存在在若若（收斂程度）（收斂程度）（收斂速度）（收斂速度）分析分析: : 結(jié)論結(jié)論(1)(1)中中)(xgx 有唯一根有唯一根, ,因此想到根的存在性定理因此想到根的存在性定理, ,.zLip連續(xù)條件。連續(xù)條件。(3.4)(3.4)實(shí)際是實(shí)際是證明：證明：且且得得由由作作,)(),1(,)()(10baCxhxxgxh 若等號(hào)成立若等號(hào)成立, ,則表示則表示a a是根或者是根或者b b是根是根, , a,ba,b 上已有根存在了上已有根存在了, ,對(duì)對(duì)于于一般情況一般情況,由根的存在定理，由根的存在定理，0)( xh在在,ba上至少存在一個(gè)根上至

32、少存在一個(gè)根,*x即即)(xgx 在在 a,ba,b 上至少存在一個(gè)根上至少存在一個(gè)根. 0)()(* xxgxh,*x即即, 0)()(, 0)()( bbgbhaagah定理定理3 3 ( (壓縮不動(dòng)點(diǎn)定理或壓縮映象定理壓縮不動(dòng)點(diǎn)定理或壓縮映象定理) )若迭代函數(shù)若迭代函數(shù)g(xg(x) )滿(mǎn)足滿(mǎn)足) 3 . 3(,)()1(baxbaxg , 10)2( L使使,baxx 有有xxLxgxg )()() 4 . 3(則則；內(nèi)內(nèi)有有唯唯一一解解在在*0,)(1xbaxgx 從而從而，*)()(xyLxgygxy 。*xy 下證唯一性，下證唯一性，為為)(xgx 在在 a,ba,b 上另一根

33、上另一根, ,則則),(),(*xgxygy 設(shè)設(shè)*y；且且得得到到的的由由對(duì)對(duì)*10lim,)(,2xxbaxxgxbaxkkkkko 02由條件由條件( (1)1)知知kx適定的，另外適定的，另外，, 1 , 0,)()(*1* kxxLxgxgxxkkk，00* kkkxxLxx。*limxxkk ，030 kkkkkxxxxxx 11*kkkxxxxL 1*)(*xg)(kxg 又又)()(11 kkkkxgxgxx.111*kkkxxLxx )4 . 3(1 kkxxL,01xxLk .101*xxLLxxkk 04).()()(limlim*1*xgxxxgxgxxxxkkkkkk

34、 （導(dǎo)數(shù)的定義）（導(dǎo)數(shù)的定義）) 4 . 3 (xxLxgxg )()(；有有誤誤差差估估計(jì)計(jì)011*0111:3xxLLxxLxxkkkk )5 . 3()(lim,)(4*1*0 xgxxxxxgkkk 則則存存在在若若證明：證明：注：注：(1)(1)從定理的結(jié)論從定理的結(jié)論3 3知，知，L L越小收斂越快，越小收斂越快，L L叫做叫做漸進(jìn)收斂因子漸進(jìn)收斂因子。(2)(2)定理定理3 3不是必要條件不是必要條件, ,如如 1123)(2102233，在在 xxgxxxx上不滿(mǎn)足定理上不滿(mǎn)足定理3 3的條件（的條件（2 2），實(shí)際上），實(shí)際上0 x是解，是解， 只要只要0 x取在取在0 0附

35、近，把（附近，把（1 1，1 1）縮小使）縮小使1)( Lxg可以滿(mǎn)足?？梢詽M(mǎn)足。( (3.43.4) )式的條件較難驗(yàn)證，常采用導(dǎo)數(shù)來(lái)代替。即有推論式的條件較難驗(yàn)證，常采用導(dǎo)數(shù)來(lái)代替。即有推論1 1 ：推論推論1 1 定理定理3 3 中（中（3.43.4）可用下式替代）可用下式替代1)(max, Lxgbax)4 . 3( 證明：證明：只證只證),4 . 3()4 . 3( 因因,baxx xxgxgxg )()()( xxxgbxa )(max.xxL 思考：思考：)4 . 3( 不成立時(shí)結(jié)論是否成立不成立時(shí)結(jié)論是否成立？不一定不一定因此該推論是充分條件但不是必要條件。因此該推論是充分條件

36、但不是必要條件。 若若)4 .3( 不成立時(shí)不成立時(shí),則則需要判斷需要判斷(3.4)(3.4)。注：注：定理定理4 4 （局部收斂定理）（局部收斂定理）鄰鄰域域滿(mǎn)滿(mǎn)足足的的在在不不動(dòng)動(dòng)點(diǎn)點(diǎn)若若 *)(xxg,* xxx有有,)()(*xxLxgxg )7.3(, 10 L則則,*0 xxx由由)(1kkxgx 產(chǎn)生的序列產(chǎn)生的序列kx收斂于收斂于,*x且有誤差估計(jì)：且有誤差估計(jì)：., 1 , 0,0* kxxLxxkk)8 .3(證明：證明：1*1*)()(, 1 kkkxxLxgxgxxk， LxxLxx0*1*實(shí)際計(jì)算中往往只在根實(shí)際計(jì)算中往往只在根因此有局部收斂定理因此有局部收斂定理4

37、4：鄰近討論，鄰近討論，*x， 21*2*LxxLxx，,* xxxk，又又0*1*xxLxxLxxkkk .lim*xxkk kkLxx*說(shuō)明：說(shuō)明：定理中的條件是充分但非必要條件。見(jiàn)定理定理中的條件是充分但非必要條件。見(jiàn)定理3 3的注（的注（2 2）。）。推論推論2 2 若若)(xg在不動(dòng)點(diǎn)在不動(dòng)點(diǎn)*x處可微，而且處可微，而且, 1)(* xg則存在則存在, 0 )(*0 xx當(dāng)當(dāng),*0 xxx時(shí)，由時(shí)，由)(1kkxgx 產(chǎn)生的序列產(chǎn)生的序列kx收斂于收斂于.*x且且).(lim*1*xgxxxxkkk )6 . 3(證明：證明：任取任取, 0)(),1),(* xgLxgL 由由*)(

38、)(lim)(*xxxgxgxgxx 知存在知存在0 ，成立，成立,)()()(* xxxxgxxxgxg即即.,* xxxxxL*) )()()(xxxgxgxg 由定理由定理4 4得證。得證。( (3.73.7) )式的條件較難驗(yàn)證式的條件較難驗(yàn)證, ,常采用導(dǎo)數(shù)來(lái)代替。即有推論常采用導(dǎo)數(shù)來(lái)代替。即有推論2 2 ：,* xxx,)()(*xxLxgxg )7.3(, 10 L 在一定條件下，迭代是高價(jià)收斂的。有定理在一定條件下，迭代是高價(jià)收斂的。有定理5 5：定理定理5 5（高階收斂定理）（高階收斂定理） 若若)(xg在不動(dòng)點(diǎn)在不動(dòng)點(diǎn)*x鄰近有直至鄰近有直至m階的階的連續(xù)導(dǎo)數(shù)，且滿(mǎn)足連續(xù)導(dǎo)

39、數(shù)，且滿(mǎn)足, 0)(, 0)()(*)(*)1(* xgxgxgmm則簡(jiǎn)單迭代法：則簡(jiǎn)單迭代法：.m是局部收斂的，且收斂階為是局部收斂的，且收斂階為)(1kkxgx 分析：分析：已知條件有各階導(dǎo)數(shù)均為已知條件有各階導(dǎo)數(shù)均為0 0, ,因此用泰勒展開(kāi)公式。因此用泰勒展開(kāi)公式。證明：證明： 由推論由推論2，簡(jiǎn)單迭代法是局部收斂的。，簡(jiǎn)單迭代法是局部收斂的。下證收斂階為下證收斂階為.m2*1)(! 21)()()(xxxgxxxgxgxgxkkkk mkkmmkmxxmgxxmxg)(!)()()!1()(*)(1*)1( .)(!)(*)(*mkkmxxmgx ,!)(!)()(*)()(*1mx

40、gmgxxxxmkkmmkk .!)(!)(lim)(lim*)()(*1mxgmgxxxxmkmkmkkk 即即)9 . 3(3 3 用簡(jiǎn)單迭代法求值用簡(jiǎn)單迭代法求值 （舉例）：（舉例）：例例用簡(jiǎn)單迭代法求用簡(jiǎn)單迭代法求2的近似值。的近似值。解：解： 設(shè)設(shè), 12 x則則. 1)2( xx所以所以,求求2的近似值轉(zhuǎn)化為求方程的近似值轉(zhuǎn)化為求方程1) 2( xx 的正根，的正根，方程：方程：,21 xx以以21 xx為迭代函數(shù)，為迭代函數(shù)， 以以00 x為初始近似得到迭代序列：為初始近似得到迭代序列：,408169,16970,7029,2912,125,52,21, 0取取408169作為作

41、為12 的近似值，得：的近似值，得：.4142157. 140816912 下證序列下證序列,52,21,0收斂于收斂于. 12 只要證只要證21 x滿(mǎn)足定理滿(mǎn)足定理3 3，即證即證21)( xxg在某個(gè)區(qū)間上滿(mǎn)足定理在某個(gè)區(qū)間上滿(mǎn)足定理3的條件。的條件。取區(qū)間為取區(qū)間為,21,0列出等價(jià)列出等價(jià),21,021)(,21,0 xxgx取區(qū)間為取區(qū)間為,21,0,21,021)(,21,0 xxgx,21, 0, vu又又.41)2)(2(2121)()(vuvuvuvuvgug )(xg在在21, 0上滿(mǎn)足定理上滿(mǎn)足定理3 3。則迭代法收斂。則迭代法收斂。 即即1.41421571.41421

42、57就是就是2近似值。近似值。4 4 迭代函數(shù)迭代函數(shù)g(xg(x) )的選取方法的選取方法)(0)(xgxxf 選取的選取的g(xg(x ) )必須滿(mǎn)足必須滿(mǎn)足: :(1) (1) 兩方程同解；兩方程同解；(2) (2) 迭代序列收斂于其根。迭代序列收斂于其根。兩種選兩種選g(xg(x) )的方法的方法: :上上假假設(shè)設(shè)在在）,1ba)(xf 存在，存在，,ba為含根區(qū)間為含根區(qū)間, ,11Mm使得使得.,)(01111MmMxfm 設(shè)設(shè) 為正常數(shù)為正常數(shù), , 試用形如試用形如)()(xfxxg 作迭代函數(shù)作迭代函數(shù). . 選取選取 使得使得, 1)(1)( qxfxg )(a對(duì)于某正實(shí)數(shù)

43、對(duì)于某正實(shí)數(shù) 成立成立. .且存在常數(shù)且存在常數(shù), 0 , 11)(11011 qmxfM ,11m 取取式式成成立立。則則)(a)(1)(1xfmxxg 故可用故可用作為迭代函數(shù)作為迭代函數(shù). .則簡(jiǎn)單迭代法收斂于則簡(jiǎn)單迭代法收斂于0)( xf的根的根.*x特別特別, ,時(shí)時(shí)，當(dāng)當(dāng),)(baCxf ,ba 使得使得,)(1Mf .)()()( fxfxxg ( (5 5 牛頓迭代法的變形牛頓迭代法的變形) )2) 2) 假設(shè)已知假設(shè)已知)(xgx *,xba上上有有根根在在, 1)( kxg但但此時(shí)此時(shí))(xg不能作為迭代函數(shù)不能作為迭代函數(shù), ,若若)(xg的反函數(shù)的反函數(shù))(xx 容易求

44、出容易求出, ,可用可用)( x 作為迭代函數(shù)作為迭代函數(shù). .?因?yàn)橐驗(yàn)?(xgx 與與)(xx 同根同根. .此時(shí)可用此時(shí)可用)(1kkxx 求解求解)(xgx 的根的根,*x且該迭代法收斂于且該迭代法收斂于.*x例例 求求01)(3 xxxf在在2 , 1 上的根上的根. .解解: :, 05) 1() 2() 1 ( ff)(xf在在2 , 1 上有根上有根. .方程方程1)(3 xxgx與與0)( xf等價(jià)等價(jià). .但但,2 , 1 , 3)( xxg 故不能用故不能用1)(3 xxg作為迭代函數(shù)作為迭代函數(shù). .然而然而)(xg的反函數(shù)的反函數(shù)31)1()( xx 的導(dǎo)數(shù)的導(dǎo)數(shù)32

45、)1(31)( xx 在在2 , 1 上滿(mǎn)足上滿(mǎn)足, 141431)(03 x 所以可用所以可用)(x 作迭代函數(shù)求作迭代函數(shù)求0)( xf的根的根. .5 5 迭代結(jié)束條件迭代結(jié)束條件1)1)根據(jù)實(shí)際問(wèn)題需要定出解的誤差界根據(jù)實(shí)際問(wèn)題需要定出解的誤差界, 由由 01*1xxLLxxkk定出迭代次數(shù)定出迭代次數(shù).k2)2)用相鄰兩次近似值有多少位有效數(shù)字相同用相鄰兩次近似值有多少位有效數(shù)字相同, ,判斷是否停機(jī)判斷是否停機(jī). .注注: : (1) (1) 編程序時(shí)編程序時(shí), ,要注意結(jié)束條件要注意結(jié)束條件. .(2)(2)定出的定出的k不準(zhǔn)確不準(zhǔn)確, ,因?yàn)橛?jì)算中有舍入誤差，故使因?yàn)橛?jì)算中有舍

46、入誤差，故使迭代次數(shù)迭代次數(shù)比計(jì)算的比計(jì)算的 要大。要大。k 1.1.理解簡(jiǎn)單迭代法的理解簡(jiǎn)單迭代法的思想方法，幾何意義，壓縮不動(dòng)點(diǎn)定理。思想方法，幾何意義，壓縮不動(dòng)點(diǎn)定理。 2. 掌握簡(jiǎn)單迭代法的收斂掌握簡(jiǎn)單迭代法的收斂( (局部局部) )定理定理（定理證明，會(huì)判斷簡(jiǎn)單（定理證明，會(huì)判斷簡(jiǎn)單迭代法是否收斂）迭代法是否收斂）。, 1 , 0),(1 kxgxkk(1)(1) 將將f(xf(x)=0)=0化為等價(jià)方程化為等價(jià)方程；)(xgx *x若若kx)( xg收斂于收斂于且且連續(xù)連續(xù), ,則則*x是是f(xf(x)=0)=0的根的根。1 1 簡(jiǎn)單迭代法的基本思想方法：簡(jiǎn)單迭代法的基本思想方法

47、：出發(fā)出發(fā), ,作序列作序列:kx0 x(2) 從某從某解解x=x=g(xg(x) )的簡(jiǎn)單迭代法的簡(jiǎn)單迭代法 迭代公式迭代公式2. 2. 收斂性收斂性（定理（定理3及推論及推論1）)(lim*1*xgxxxxkkk 則則有有；,)()1(baxbaxg ,10)2( L使使,baxx 有有xxLxgxg )()(，1)(max, Lxgbax或或若若有有對(duì)對(duì)迭迭代代)(xgx 3 3、局部收斂性（定理、局部收斂性（定理4 4及推論及推論2 ）,* xxx有有,)()(*xxLxgxg , 10 L4 4、高階收斂性（定理、高階收斂性（定理5 5）)(lim*1*xgxxxxkkk 則則有有,

48、 1)(* xg或或, 0)(, 0)()(*)(*)1(* xgxgxgmm若若則收斂階為則收斂階為m。迭代法的加速法迭代法的加速法4.1 4.1 AitkenAitken( (埃特金埃特金) )加速方法加速方法假設(shè)簡(jiǎn)單迭代序列假設(shè)簡(jiǎn)單迭代序列kx,*x線(xiàn)性收斂于線(xiàn)性收斂于即即10,lim*1 ccxxxxkkk)1 .4( (加速收斂技巧加速收斂技巧) )設(shè)設(shè),) 1*xxk ( (若等號(hào)成立若等號(hào)成立, ,則則,*xxk 是精確解是精確解) ), 1 , 0, k., 1 , 0, 02) 212 kxxxkkk( (若等號(hào)成立若等號(hào)成立, ,則則kx不收斂不收斂. .因?yàn)橐驗(yàn)閗kkxx

49、x 122則則 如圖示如圖示: : ,112kkkkxxxx kx不收斂于不收斂于 ) ) .*x*x12 kkxx21 kkxxkxx, 0)()(112 kkkkxxxx記序列記序列kx的埃特金加速序列為的埃特金加速序列為.0 kkx., 1 , 0,)(2)(221221 kxxxxxxxxxxkkkkkkkkkk)2 .4(埃特金加速序列埃特金加速序列 0kkx比原簡(jiǎn)單序列比原簡(jiǎn)單序列kx更快地收斂于更快地收斂于.*x二階差分算子二階差分算子定理定理6 6: : 若序列若序列 線(xiàn)性收斂于線(xiàn)性收斂于kx*x10,lim*1 ccxxxxkkk：.*x則則 的埃特金加速序列的埃特金加速序列

50、 比原簡(jiǎn)單序列比原簡(jiǎn)單序列 更快地收斂于更快地收斂于 0kkxkx 0kkx即即)3 . 4(. 0lim* xxxxkkk分析分析: : 該定理的證明用數(shù)學(xué)分析中證明極限的技巧該定理的證明用數(shù)學(xué)分析中證明極限的技巧. .證明證明: :,*xxekk 記記則有則有,lim1ceekkk .lim22ceekkk 由由)2.4(得得*1221*2)(xxxxxxxxxkkkkkkk .2)(1221kkkkkkeeeeee 12) 1(11221* kkkkkkkkeeeeeexxxx則則1122kkkkkkeeeeee ，即，即. 0lim* xxxxkkk# # kccc. 012) 1(1

51、22kkkkkkkxxxxxxx 12212)()2 . 4(*xx *2xxx 幾何意義幾何意義: :設(shè)初值設(shè)初值,0 x由迭代法由迭代法: :),(),(1201xgxxgx 由三角形相似由三角形相似, ,得得: :,10301213xxxxxxxx 0122120302xxxxxxxx .2)(0122010 xxxxxx xy xy0*x0 x2x1x),(211xxp),(100 xxp3x10 xx 30 xx 13xx 12xx 過(guò)兩點(diǎn)過(guò)兩點(diǎn)),(),(211100 xxpxxp作直線(xiàn)作直線(xiàn) , ,說(shuō)明說(shuō)明:該表達(dá)式正是埃特金加速收斂的公式該表達(dá)式正是埃特金加速收斂的公式, ,0

52、3xx 比比2x更接近于更接近于.*x從圖中可以看出從圖中可以看出(1)(1)這里的這里的3x并不是簡(jiǎn)單收斂列并不是簡(jiǎn)單收斂列.3x0kkx中的中的(2)(2)對(duì)某些不收斂的情況對(duì)某些不收斂的情況, ,用埃特金方法用埃特金方法“加速加速”也有可能收斂也有可能收斂. .xy 的交點(diǎn)為的交點(diǎn)為),(33yx與與為為埃埃特特金金序序列列的的元元素素。則則03xx 4.2 4.2 SteffensonSteffenson迭代方法迭代方法 在埃特金加速法中在埃特金加速法中, , 只要有三個(gè)相鄰點(diǎn)就可以進(jìn)行加速只要有三個(gè)相鄰點(diǎn)就可以進(jìn)行加速, ,把把簡(jiǎn)單迭代與埃特金加速方法結(jié)合起來(lái)可建立簡(jiǎn)單迭代與埃特金加

53、速方法結(jié)合起來(lái)可建立SteffensoSteffenso迭代方法迭代方法. .設(shè)設(shè)g(x)g(x)為迭代函數(shù)為迭代函數(shù), ,0, x為初始值為初始值, ,0kkx為迭代序列為迭代序列, ,則迭代則迭代過(guò)程如下過(guò)程如下: :)()(kkkkygzxgy , 1 , 0,)2()(21 kxyzxyxxkkkkkkk )4 .4(并有局部收斂定理。并有局部收斂定理。定理定理8 8 若若*x是是g(x)g(x)的不動(dòng)點(diǎn)的不動(dòng)點(diǎn),g(x),g(x)一次連續(xù)可微一次連續(xù)可微, , 1 , 0)( xg存在存在, ,則存在則存在, 0只要只要,*0 xx由由SteffensoSteffenso方法產(chǎn)生的方

54、法產(chǎn)生的)(*xg kx收斂于收斂于,*x而且收斂階至少為而且收斂階至少為2 2。迭代序列迭代序列從例從例7 7、8 8可以看出收斂速度確實(shí)快?？梢钥闯鍪諗克俣却_實(shí)快。優(yōu)點(diǎn)：優(yōu)點(diǎn)：收斂速度快。收斂速度快。缺點(diǎn)：缺點(diǎn)：計(jì)算量大，一步計(jì)算量大，一步SteffensoSteffenso方法迭代的計(jì)算量相當(dāng)于兩方法迭代的計(jì)算量相當(dāng)于兩步簡(jiǎn)單迭代。步簡(jiǎn)單迭代。理解簡(jiǎn)單迭代法的理解簡(jiǎn)單迭代法的加速收斂方法。加速收斂方法。5 5 解解f(x)=0f(x)=0的的NewtonNewton迭代法迭代法Newton-Newton-RaphsonRaphson法是廣泛應(yīng)用的高效計(jì)算方法。法是廣泛應(yīng)用的高效計(jì)算方法。

55、基本思想基本思想: : 非線(xiàn)性方程局部非線(xiàn)性方程局部線(xiàn)性化線(xiàn)性化 ( (化繁為簡(jiǎn)化繁為簡(jiǎn)) )特點(diǎn)特點(diǎn): : 單根附近具有較高的收斂速度單根附近具有較高的收斂速度5.1 Newton5.1 Newton迭代公式迭代公式 (Newton(Newton法或切線(xiàn)法法或切線(xiàn)法) )1 1 公式公式: :設(shè)非線(xiàn)性方程設(shè)非線(xiàn)性方程0)( xf)1.5(,其精確解或真解為其精確解或真解為.*xf(xf(x) )二次連續(xù)可導(dǎo)二次連續(xù)可導(dǎo), ,kx是是(5.1)(5.1)的第的第k k次近似解。次近似解。的泰勒展開(kāi)式為的泰勒展開(kāi)式為: :2)(! 2)()()()(kkkkxxfxxxfxfxf 其中其中 介于

56、介于x與與kx之間。之間。)()(kkkxxxfxfy 是是)( xf在點(diǎn)在點(diǎn)kx的線(xiàn)性展開(kāi)的線(xiàn)性展開(kāi) ( (線(xiàn)性主部線(xiàn)性主部) )， 用其近似用其近似f(x),f(x),即有即有并設(shè)并設(shè)則則f(x)f(x)在點(diǎn)在點(diǎn)kx0)()()( kkkxxxfxfxf)()(kkkxfxfxx )0)( kxfNewtonNewton迭代公式迭代公式: :)()(1kkkkxfxfxx )3.5(說(shuō)明說(shuō)明: : 公式推導(dǎo)過(guò)程中是用公式推導(dǎo)過(guò)程中是用f(x)f(x)的泰勒展開(kāi)式的的泰勒展開(kāi)式的線(xiàn)性線(xiàn)性部分部分作作為為f(xf(x) )的近似值的近似值, ,因此說(shuō)因此說(shuō)NewtonNewton法是一個(gè)法是一

57、個(gè)逐次線(xiàn)性化逐次線(xiàn)性化方法。方法。把把)()(kkkxfxfxx 作為第作為第K+1K+1次近似解次近似解，即得即得0)()()( kkkxxxfxfxf)()(kkkxfxfxx )0)( kxf)0)( kxf2 2 幾何意義幾何意義設(shè)曲線(xiàn)設(shè)曲線(xiàn)y =f(x)y =f(x)的圖象如圖示的圖象如圖示, ,kx0)( xf是是的的k k次近似次近似, ,曲線(xiàn)曲線(xiàn) y=y=f(xf(x) )上對(duì)上對(duì)應(yīng)的點(diǎn)為應(yīng)的點(diǎn)為),(,(kkxfx過(guò)該點(diǎn)作過(guò)該點(diǎn)作曲線(xiàn)曲線(xiàn)y=f(x)的切線(xiàn)的切線(xiàn)kL交交x x軸于點(diǎn)軸于點(diǎn),1 kx:kL用用)2 . 5()()(kkkxxxfxfy 近似曲線(xiàn)近似曲線(xiàn)y=f(x

58、),y=f(x), 則則kL與與x x軸的交點(diǎn)軸的交點(diǎn)1 kx作為作為f(x)=0f(x)=0的第的第k+1k+1次近似解。次近似解。即由即由(5.2)(5.2)式令式令y=0y=0得得)()(1kkkkxfxfxx )0)( kxf該式就是該式就是NewtonNewton法的迭代公式法的迭代公式, ,因此因此NewtonNewton法也稱(chēng)為法也稱(chēng)為切線(xiàn)法切線(xiàn)法。xyo)( xfy kL*x)(,(kkxfxkx1 kx3 3 牛頓法與簡(jiǎn)單迭代法、正割法的關(guān)系牛頓法與簡(jiǎn)單迭代法、正割法的關(guān)系 若取若取,)()()(xfxfxxg 0)( xf)4 .5( 若若11)()()( kkkkkxxx

59、fxfxf(差商近似代替微商）差商近似代替微商）)()(1kkkkxfxfxx )(1kkxgx )0)( xf即即則則簡(jiǎn)單迭代法簡(jiǎn)單迭代法 (迭代函數(shù)為迭代函數(shù)為g(x)NewtonNewton法法則則正割法正割法NewtonNewton法法)()(1kkkkxfxfxx 即即)()()()(111 kkkkkkkxxxfxfxfxx因此正割法也稱(chēng)為離散的因此正割法也稱(chēng)為離散的NewtonNewton法，法， 或者稱(chēng)為或者稱(chēng)為NewtonNewton法的法的改進(jìn)。改進(jìn)。牛頓法也存在收斂問(wèn)題，并不是對(duì)牛頓法也存在收斂問(wèn)題，并不是對(duì)所有函數(shù)牛頓法都收斂所有函數(shù)牛頓法都收斂。因此有收斂因此有收斂定

60、理。定理。xyo*x)( xfy 1kxkx2kx5.2 Newton5.2 Newton法收斂定理法收斂定理1 1 收斂定理收斂定理定理定理9 9 （NewtonNewton法局部超線(xiàn)性收斂性）法局部超線(xiàn)性收斂性）如果如果f(x)f(x)在解在解*x鄰近連續(xù)鄰近連續(xù) 可導(dǎo)可導(dǎo), ,且且, 0)(* xf則存在則存在,0 只要只要,*0 xxNewtonNewton序列序列超線(xiàn)性超線(xiàn)性收斂于收斂于,*x即即. 0lim*1 xxxxkkk)5.5(牛頓法迭代會(huì)越跑越遠(yuǎn)。牛頓法迭代會(huì)越跑越遠(yuǎn)。 如圖示如圖示: :分析：分析：NewtonNewton迭代公式為迭代公式為,)()(1kkkkxfxf