非線性方程組解法

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

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

3、的零點.注：注：()方程的根可能是實數也可能是復數，相應地稱為方程方程的根可能是實數也可能是復數，相應地稱為方程的的實根實根或或復根復根。如果函數如果函數f (x)可因式分解為可因式分解為且且 )()()(xgxxxfm 0)( xg稱稱x*為為函數函數f (x)的的m重零點重零點，或稱為，或稱為方程方程f (x)=0的的m重根重根;當當m時，時，稱稱x*為為函數函數f (x)的的單重零點單重零點，又稱作，又稱作方程方程f (x)=0的的單根單根 ; 如果如果稱稱x*為方程為方程f (x)=0的的m重根重根.，1 m() 重根亦可利用導數來定義重根亦可利用導數來定義(略略)。若存在數若存在數

4、x*滿足滿足 f (x*)=0，則，則x*稱為方程稱為方程記為：記為： f (x)=0求解的特點：求解的特點： 無求解公式，無直接解法無求解公式，無直接解法，難求得精確解。難求得精確解。舉例舉例: :超越方程超越方程1.2 非線性方程非線性方程(組組)求解的特點求解的特點1cos xex 間接法間接法( (迭代法迭代法):):從一個初始近似值出發(fā)從一個初始近似值出發(fā), ,重復某種計算過程重復某種計算過程沒有一定的解法。沒有一定的解法。間接法即迭代法。間接法即迭代法。來來不斷改進近似解不斷改進近似解，有限次改進后有限次改進后, ,計算出一個滿足誤差要求計算出一個滿足誤差要求的的近似解近似解，這種

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

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

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

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

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

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

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

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

13、函數從而函數f( (x) )在區(qū)間在區(qū)間1.0, 1.5上單調連續(xù)上單調連續(xù)， , 0875. 0) 5 . 1 (, 01) 1 ( ff所以函數所以函數f( (x) )在區(qū)間在區(qū)間1.0, 1.5上有唯一根。上有唯一根。 計算過程見表計算過程見表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內有一個根內有一個根,使用二分使用二分法求誤差不大于法求誤差不大于 41021 的根的根, 需二分多少次需二分多少次證證,sin1)(xxxf 令令, 1 , 0時時則則當當 x, 0cos1)( xxf所以所以f( (x) )在在0 , 1上單調減少且連續(xù)。上單調減少且連續(xù)。, 01sin) 1 (, 01)0( ff又又所以所以f( (x) )在在0 , 1上有且只有一個根上有且只有一個根.使用二分法時，誤差限使用二分法時，誤差限)(211abxxnn ,10212141 n28.13214)01(1 ggn則則 所以需二分所以需二分14 次即可次即可.(ln102.3026,ln2

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

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

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

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

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

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

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

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

23、q 令令則則,) 1(,1121111 lkkklkklkkkkkkkkkkyyyyyyyyyyyyyxx )13. 2(該方法稱為該方法稱為反插值法反插值法。)(xfy 有反函數有反函數)(yx 且且).0(* x若若f(x)f(x)在在鄰近嚴格單調鄰近嚴格單調*x)()(,)(,)(,)(111211 lkkklkkkkkkkkkkkyyyyyyyyyyyyyyyyyyyxyq :11* kxkx次次近近似似的的是是若若lkkkxxx ,1個已知近似值，個已知近似值，構造構造1 l注：注： 1 1 當當1 l 時，反插值法完全重合于正割法。時，反插值法完全重合于正割法。2 2 反插值法是局

24、部收斂的反插值法是局部收斂的, ,且收斂階低于且收斂階低于2 2。思考：思考：總結：總結：上上討論拋物線法，但平時很少用拋物線法，因為該方法計算量大，討論拋物線法，但平時很少用拋物線法，因為該方法計算量大，且收斂階不高。且收斂階不高。幾種插值法的條件不同幾種插值法的條件不同。正割法是常用的方法，理論正割法是常用的方法，理論當當2 l 時，反插值法是否是拋物線法時，反插值法是否是拋物線法？解解x=x=g(xg(x) )的簡單迭代法的簡單迭代法3.1 3.1 簡單迭代法公式簡單迭代法公式問題問題: : f(xf(x) )實函數實函數. .求求f(xf(x)=0)=0的近似值的近似值。, 1 , 0

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

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

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

28、im(*xgxgkk , 1 , 0),(1 kxgxkk迭代公式迭代公式)2.3(注注: : 適定適定是是收斂收斂必要條件，即不必要條件，即不適定適定則一定不則一定不收斂收斂。1)(0*xg說明兩點：說明兩點：分別就下列四種情況說明幾何意義：分別就下列四種情況說明幾何意義：kxkx(1)(1)中中的產生。的產生。（2 2）kx何時收斂何時收斂, ,何時發(fā)散。何時發(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迭代法不收斂迭代法不收斂從點從點)(,(000 xgxp的直線交的直線交y=xy=x于點于點出發(fā)出發(fā), ,作平行于作平行于x x軸軸),(),(00 xgxg作平行于作平行于y y 軸的直線交軸的直線交y =y =g(xg(x) )于點于點過該點過該點),(),(001xggxgp即即).(,(111xgxp依次進行下去得到依次進行下去得到,kx且且).(1kkxgx 1. 1. 簡單迭代法簡單迭代法(2)(2)給定給定0kxx 滿足滿足。

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

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

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

33、上另一根, ,則則),(),(*xgxygy 設設*y；且且得得到到的的由由對對*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、 （導數的定義）（導數的定義）) 4 . 3 (xxLxgxg )()(；有有誤誤差差估估計計011*0111:3xxLLxxLxxkkkk )5 . 3()(lim,)(4*1*0 xgxxxxxgkkk 則則存存在在若若證明：證明：注：注：(1)(1)從定理的結論從定理的結論3 3知，知，L L越小收斂越快，越小收斂越快，L L叫做叫做漸進收斂因子漸進收斂因子。(2)(2)定理定理3 3不是必要條件不是必要條件, ,如如 1123)(2102233，在在 xxgxxxx上不滿足定理上不滿足定理3 3的條件（的條件（2 2），實際上），實際上0 x是解，是解， 只要只要0 x取在取在0 0附

35、近，把（附近，把（1 1，1 1）縮小使）縮小使1)( Lxg可以滿足。可以滿足。( (3.43.4) )式的條件較難驗證，常采用導數來代替。即有推論式的條件較難驗證，常采用導數來代替。即有推論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( 不成立時結論是否成立不成立時結論是否成立？不一定不一定因此該推論是充分條件但不是必要條件。因此該推論是充分條件

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

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

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

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

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

41、為12 的近似值，得：的近似值，得：.4142157. 140816912 下證序列下證序列,52,21,0收斂于收斂于. 12 只要證只要證21 x滿足定理滿足定理3 3，即證即證21)( xxg在某個區(qū)間上滿足定理在某個區(qū)間上滿足定理3的條件。的條件。取區(qū)間為取區(qū)間為,21,0列出等價列出等價,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上滿足定理上滿足定理3 3。則迭代法收斂。則迭代法收斂。 即即1.41421571.41421

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

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

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

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

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

47、：出發(fā)出發(fā), ,作序列作序列:kx0 x(2) 從某從某解解x=x=g(xg(x) )的簡單迭代法的簡單迭代法 迭代公式迭代公式2. 2. 收斂性收斂性（定理（定理3及推論及推論1）)(lim*1*xgxxxxkkk 則則有有；,)()1(baxbaxg ,10)2( L使使,baxx 有有xxLxgxg )()(，1)(max, Lxgbax或或若若有有對對迭迭代代)(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( (埃特金埃特金) )加速方法加速方法假設簡單迭代序列假設簡單迭代序列kx,*x線性收斂于線性收斂于即即10,lim*1 ccxxxxkkk)1 .4( (加速收斂技巧加速收斂技巧) )設設,) 1*xxk ( (若等號成立若等號成立, ,則則,*xxk 是精確解是精確解) ), 1 , 0, k., 1 , 0, 02) 212 kxxxkkk( (若等號成立若等號成立, ,則則kx不收斂不收斂. .因為因為kkkxx

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

50、 比原簡單序列比原簡單序列 更快地收斂于更快地收斂于 0kkxkx 0kkx即即)3 . 4(. 0lim* xxxxkkk分析分析: : 該定理的證明用數學分析中證明極限的技巧該定理的證明用數學分析中證明極限的技巧. .證明證明: :,*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 幾何意義幾何意義: :設初值設初值,0 x由迭代法由迭代法: :),(),(1201xgxxgx 由三角形相似由三角形相似, ,得得: :,10301213xxxxxxxx 0122120302xxxxxxxx .2)(0122010 xxxxxx xy xy0*x0 x2x1x),(211xxp),(100 xxp3x10 xx 30 xx 13xx 12xx 過兩點過兩點),(),(211100 xxpxxp作直線作直線 , ,說明說明:該表達式正是埃特金加速收斂的公式該表達式正是埃特金加速收斂的公式, ,0

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

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

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

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

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

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

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

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

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