數(shù)值分析課件chap7非線性方程組的求解

1、非線性方程求根非線性方程求根q ( )0f x 例如：非線性有限元問題、非線性斷裂問題、及其它例如：非線性有限元問題、非線性斷裂問題、及其它非線性力學問題、電路問題、電力系統(tǒng)計算、醫(yī)學、非線性力學問題、電路問題、電力系統(tǒng)計算、醫(yī)學、生命學、天氣預報、非線性規(guī)劃、經(jīng)濟問題等生命學、天氣預報、非線性規(guī)劃、經(jīng)濟問題等。 描述工程和科學技術(shù)實際問題的數(shù)學模型，通常都難以描述工程和科學技術(shù)實際問題的數(shù)學模型，通常都難以 獲得根的簡單易用的顯式表達式，因此，要研究求近似獲得根的簡單易用的顯式表達式，因此，要研究求近似 根的方法，并討論這些方法的收斂性和收斂速度根的方法，并討論這些方法的收斂性和收斂速度預備

2、知識預備知識q 滿足函數(shù)方程 f(x)=0 的x稱為方程(1)的根，或稱為函數(shù)f(x)的零點。如果函數(shù)(x)可分解為 (x)=(xs)mg(x)且g(s )0,則稱s是(x)的m重零點或(x)=0的m重根。當m=1時，稱s是(x)的單根或單零點。q 定理定理 假設(shè)函數(shù)假設(shè)函數(shù)y=f(x)y=f(x)在在x=sx=s的某一鄰域內(nèi)充分可的某一鄰域內(nèi)充分可 微，則微，則s s是方程是方程f(x )=0f(x )=0的的m m重根的充分必要條件是重根的充分必要條件是0)(, 0)()()()()1(sfsfsfsfmm求解非線性方程的根的問題可分為下面幾個方面求解非線性方程的根的問題可分為下面幾個方面

3、：q l 根的存在性根的存在性l 根的隔離根的隔離l 根的精確化根的精確化q 非線性方程根的存在性非常復雜。非線性方程根的存在性非常復雜。l 對于代數(shù)方程即多項式方程，其根的對于代數(shù)方程即多項式方程，其根的個數(shù)與代數(shù)方程個數(shù)與代數(shù)方程的次數(shù)相同的次數(shù)相同。而且理論上已證明，對于次數(shù)。而且理論上已證明，對于次數(shù)n=4n=4的多項的多項式方程式方程, ,它的根可以用公式表示它的根可以用公式表示, ,而而次數(shù)大于次數(shù)大于5 5的多項式方的多項式方程程, ,它的根一般不能用解析表達式表達。它的根一般不能用解析表達式表達。示示. .l 對于超越方程或其他非線性方程，可能沒有零點，也對于超越方程或其他非線

4、性方程，可能沒有零點，也可能有一個或若干個零點，甚至無窮多個零點。可能有一個或若干個零點，甚至無窮多個零點。根的存在性定理根的存在性定理q 定理定理1 1. .( (根的存在定理根的存在定理) ) 假設(shè)函數(shù)假設(shè)函數(shù)y=f(x)y=f(x) C C a,ba,b , ,且且f(a)f(b)0, f(a)f(b)0, 則至則至 少存在一點少存在一點x x (a,b)(a,b)使得使得f(x )=0. f(x )=0. ( (并稱區(qū)間并稱區(qū)間( (a,b)a,b)為有根區(qū)間為有根區(qū)間).). q 定理定理2 2. .（根的唯一性）（根的唯一性） 假設(shè)函數(shù)假設(shè)函數(shù)y=f(x)y=f(x)在在 a,ba

5、,b 上單調(diào)連續(xù)上單調(diào)連續(xù), ,且且 f(a)f(b)0,f(a)f(b)0, 則恰好只存在一點則恰好只存在一點x x (a,b)(a,b)使得使得 f(x )=0f(x )=0 根的隔離根的隔離求根的隔離區(qū)間的兩種方法求根的隔離區(qū)間的兩種方法q 畫圖法畫圖法n 畫出畫出y y = = f f ( (x x) )的略圖，從而看出曲線與的略圖，從而看出曲線與x x軸交軸交 點的大致位置。點的大致位置。n 也可將也可將f f ( (x x) = 0) = 0分解為分解為 1 1( (x x)= )= 2 2( (x x) )的形式，的形式， 1 1( (x x) )與與 2 2( (x x) )兩

6、曲線交點的橫坐標所在的子兩曲線交點的橫坐標所在的子 區(qū)間即為含根區(qū)間。區(qū)間即為含根區(qū)間。 例如例如x xlglgx x 1 = 0 1 = 0 可以改寫為可以改寫為lglgx x=1/=1/x x 畫出對數(shù)曲線畫出對數(shù)曲線y y=lg=lgx x, ,與雙曲線與雙曲線y y= 1/= 1/x x, ,它們交它們交 點的橫坐標位于區(qū)間點的橫坐標位于區(qū)間2,32,3內(nèi)內(nèi)xy1023yxxylog畫圖法畫圖法逐步搜索逐步搜索法法n 對于給定的對于給定的f f ( (x x) )，設(shè)有根區(qū)間為設(shè)有根區(qū)間為 A A, ,B B ，從從x x0 0= =A A 出發(fā)，以步長出發(fā)，以步長h h=(=(B B

7、- -A A)/)/n n( (n n是正整數(shù)是正整數(shù)) )，在，在 A A, ,B B 內(nèi)取定節(jié)點：內(nèi)取定節(jié)點：x xi i= =x x0 0ihih ( (i i=0=0，1 1，2 2，n n) )， 從左至右檢查從左至右檢查f f ( (x xi i) )的符號，如發(fā)現(xiàn)的符號，如發(fā)現(xiàn)x xi i與端點與端點x x0 0 的函數(shù)值異號，則得到一個縮小的有根子區(qū)間的函數(shù)值異號，則得到一個縮小的有根子區(qū)間 x xi i-1-1, ,x xi i。n 用逐步搜索法進行實根隔離的關(guān)鍵是選取步長用逐步搜索法進行實根隔離的關(guān)鍵是選取步長h hn 要選擇適當要選擇適當h h ，使之既能把根隔離開來，工

8、作量又使之既能把根隔離開來，工作量又 不太大。不太大。q 逐步搜索法逐步搜索法二分法二分法 Bisectionq 在方程求根的方法中，最直觀、最簡單的方法就在方程求根的方法中，最直觀、最簡單的方法就 是二分法。是二分法。q 給定方程給定方程f(x)=0,f(x)=0,設(shè)設(shè)f(x)f(x)在區(qū)間在區(qū)間 a,ba,b連續(xù)連續(xù), ,且且f(a)f(b)0,f(a)f(b)0, 則方程則方程f(x)f(x)在在( (a,b)a,b)內(nèi)至少有一根內(nèi)至少有一根, ,為便于討論為便于討論, ,不妨設(shè)方不妨設(shè)方 程程f(x)=0f(x)=0在在( (a,b)a,b)內(nèi)只有一個內(nèi)只有一個( (重根視為一個重根視

9、為一個) )實根。實根。q 二分法的基本思想二分法的基本思想 二分法詳細步驟二分法詳細步驟l l 0011 (),().2001.記有根區(qū)間a ,b =a,b,取 中點 并計算abxf x 111101011110111101110():()0,() ()0,;,.2. 判斷的值若則 為根；若取=即否則取=即f xf xxf xf aaa b xa baxax b ba bx b k-1k-1kkk-1k-1kkkkk-1k-1k-1,2()0,()(a)0,abkkkkkk3. 繼續(xù)運算， 由區(qū)間,構(gòu)造區(qū)間,并得到：若則為所求的根;若則取a ,b =,;否則, 可取a ,b =,.kabab

10、abxxf xxf xfxx l 11*(a) () ()01(b) ()2(c) .,.;,()0,(,),lim,limkkkkkkkkkkkkkkf af bbabaababxf xxabaxb 0 00 01 11 1k kk k0 01 1k k0 01 1k k這這樣樣就就得得到到一一系系列列閉閉區(qū)區(qū)間間： a a , , b b ， a a , , b b ，. . . . . . a a , , b b , , . . . . . . , , k k= =0 0, , 1 1, , 2 2, , . . . . . . . . , ,并并滿滿足足：a aa aa ab bb b

11、b b即即滿滿足足并并且且*,limkkkxxx 二分法終止的條件二分法終止的條件)(kxfq 如下條件終止，可否如下條件終止，可否 ？這不能保證精確值的精度！這不能保證精確值的精度！x x*q 有如下估計有如下估計q 因此終止的條件為因此終止的條件為q 二分法終止的條件二分法終止的條件11*)(21kkkkkababxx1kkkkxxorab對于給定的精度對于給定的精度 , ,可估計二分法所需的步數(shù)可估計二分法所需的步數(shù) k k ：)(log22abkabk二分法的優(yōu)缺點q 優(yōu)點優(yōu)點l 計算簡單，方法可靠，并保證收斂計算簡單，方法可靠，并保證收斂 l 對函數(shù)對函數(shù) 要求不高，只要連續(xù)即可要求

12、不高，只要連續(xù)即可。q 缺點缺點l 無法求復根和偶重根無法求復根和偶重根l 收斂慢收斂慢 l 調(diào)用一次求解一個調(diào)用一次求解一個 a, ba, b間的多個根無法求得間的多個根無法求得 一般求方程的近似根，不大單獨使用，常用一般求方程的近似根，不大單獨使用，常用來為其它方法求方程近似根提供好的初值。方程來為其它方法求方程近似根提供好的初值。方程求根最常用的方法是迭代法求根最常用的方法是迭代法。function y=erfen(fun,a,b,esp)Matlab programif feval(fun, a)*feval(fun, b)esp if feval(fun,a)*feval(fun,c

13、)0 b = c ; c = ( a+b) / 2 ; elseif feval(fun,c)*feval(fun,b)0 a = c ; c = ( a+b) / 2 ; else y = c ; end n= n+1 ; endy = c ;elseif feval(fun,a) = 0 y = a ; elseif feval(fun,b) = 0 y = b ; end01)(3xxxf3242.13203.063203.13281.153281.13438.143438.13125.133125.1375.12375.125.1125.15.10.10)(17符號表kkkkxfxba

14、k不動點迭代法q 迭代法的迭代法的基本思想基本思想是一種逐次逼近的方法，首先是一種逐次逼近的方法，首先 給定一個粗糙的初值，然后用同一個迭代公式，給定一個粗糙的初值，然后用同一個迭代公式， 反復校正這個初值，直到滿足預先給出的精度要求。反復校正這個初值，直到滿足預先給出的精度要求。q 迭代法的基本步驟迭代法的基本步驟f (x) = 0等價變換等價變換f (x) 的根的根x= (x) (x)的不動點的不動點從一個初值從一個初值 x0 出發(fā)出發(fā)，計算計算 x1 = (x0), x2 = (x1), , xk+1 = (xk), 若若 收斂，即存在收斂，即存在 x x* * 使得使得 ，且且 連續(xù)，

15、則由連續(xù)，則由 可可知知 x* = (x* )，即即x x* *是是 的不動點，也就是的不動點，也就是f f 的根。的根。 0kkx*limxxkk kkkkxgx limlim1)., 1 , 0()(1kxxkk不動點迭代法定義定義：迭代公式迭代公式 x xk k+1+1= = ( (x xk k) ) ( (k k= 0,1, ) = 0,1, ) 被被稱為求解方程稱為求解方程 f f( (x x)=0 )=0 的的不動點迭代法不動點迭代法，其中，其中( (x x) )稱為稱為迭代函數(shù)迭代函數(shù)。q q 迭代法的幾何含義迭代法的幾何含義y) :)(xyxyxx交點即真根。xyy = xsy

16、=g(x)x0p0 x1p1需要討論的問題 n 首先期望每個首先期望每個x xk k都在都在 ( (x x) )的定義域上的定義域上, ,保持有界而保持有界而 且收斂到精確解且收斂到精確解; ;n 如何選取適合的迭代函數(shù)如何選取適合的迭代函數(shù) ( (x x) ;) ;n 迭代函數(shù)迭代函數(shù) ( (x x) )迭代滿足什么條件迭代滿足什么條件, ,迭代序列收斂到迭代序列收斂到 精確解精確解, ,收斂速度如何收斂速度如何; ; H 。5 . 101)(03附近的根在求方程xxxxfl 設(shè)將原方程改寫成下列形式設(shè)將原方程改寫成下列形式 . 13xx據(jù)此建立迭代公式據(jù)此建立迭代公式 ).,2, 1 ,0

17、(131kxxkkl 但但若采用方程另一種等價形式若采用方程另一種等價形式13 xx，131kkxx建立迭代公式建立迭代公式 32494. 1432472. 1832588. 1332472. 1733086. 1232473. 1635721. 1132476. 155 . 10kkxkxk第二種方法第二種方法仍取迭代初值仍取迭代初值 ，則有，則有 5 .10 x.39.12,375.221xx結(jié)果會越來越大，不可能趨于某個極限結(jié)果會越來越大，不可能趨于某個極限. . 迭代法的收斂條件迭代法的收斂條件 q 定理定理*10|1kkLxxxxL且滿足上連續(xù)在設(shè)迭代函數(shù),)(bax;)(,)1(b

18、xabax時當有且滿足存在一正數(shù),10,)2(baxLL1212()()xxL xx1 .( ) , *2 .oxa bx則 函數(shù)在上存在唯一的不動點此迭代法一定收斂，且有如下估計式*11|1kkkxxxxL 注注 q 條件條件(2)(2)可用更強更便于應用的條件代替可用更強更便于應用的條件代替: q 由誤差估計可以得到迭代終止的條件由誤差估計可以得到迭代終止的條件 , 1)(Lxkkxx1q 由誤差估計可以知道由誤差估計可以知道L越小，收斂越快越小，收斂越快以及以及迭代迭代最最 少次數(shù)少次數(shù) LxxLnln)1 (ln01可得到： 局部收斂性局部收斂性 q 前述定理條件為前述定理條件為充分條

19、件充分條件，非必要條件。在實際，非必要條件。在實際 應用當應用當中中 條件并不易檢驗條件并不易檢驗。 q 定義定義 （局部收斂性）（局部收斂性）設(shè)設(shè) 有不動點有不動點 ，)( x*x如果存在如果存在 的某個鄰域的某個鄰域*x,*: xxR對任意對任意 ，Rx0迭代產(chǎn)生的序列迭代產(chǎn)生的序列,Rxk且收斂到且收斂到 ，*x則稱迭代法則稱迭代法局部收斂局部收斂. .q 定理定理 設(shè)設(shè)s s為為的不動點的不動點, , 在在s s的某個鄰域內(nèi)連續(xù)的某個鄰域內(nèi)連續(xù), , 且且| | 1, |= 1.0e 6 ) &( n=1000 ) x = x1 ; x1=g(x); n = n+1 ;endx

20、1nmatlab program 收斂階(描述收斂速度) q 設(shè)迭代過程設(shè)迭代過程 收斂于方程收斂于方程 )(1kkxx)( xx的根的根 ，*x如果迭代誤差如果迭代誤差 當當 時成立下列時成立下列*xxekkk漸近關(guān)系式漸近關(guān)系式),0(1CCeepkk常數(shù) 若若 p p = 1 = 1 , , 稱稱 x xk k 為為線性收斂線性收斂, , 這時這時 0 0 1, 1, 稱稱 x xk k 為為超線性收斂超線性收斂; ; p p=2, =2, 稱其為稱其為平方收斂平方收斂. .收斂階定理 q 數(shù)數(shù)p p的大小反映了迭代法的收斂速度的快慢，的大小反映了迭代法的收斂速度的快慢，P P越大，收越

21、大，收 斂越快斂越快，所以說收斂階是對迭代法收斂速度的一種度量。，所以說收斂階是對迭代法收斂速度的一種度量。 q （收斂階定理）（收斂階定理） 對于迭代過程對于迭代過程 ，如果，如果 在所求根在所求根 的鄰近連續(xù)，并且的鄰近連續(xù)，并且: : 則該迭代過程在點則該迭代過程在點 鄰近是鄰近是P P階收斂的階收斂的。)(1kkxx)()(xp*(1)*()()()0pxxx0)(*)(xp*x*x 上述定理說明，迭代過程的收斂速度依賴于迭代函數(shù)上述定理說明，迭代過程的收斂速度依賴于迭代函數(shù) 的選取的選取. . )( xNewton迭代法q q 具體而言： 設(shè)設(shè)x xk k是非線性方程是非線性方程 f

22、 f( (x x)=0)=0的一個近似根，把的一個近似根，把 f f( (x x) )在在x xk k處處作一階泰勒展開，即用前兩項近似代替作一階泰勒展開，即用前兩項近似代替( )( )( )()kkkf xf xf xx x則近似方程轉(zhuǎn)化為則近似方程轉(zhuǎn)化為 ()()()0kkkf xfxxx設(shè) ，上式解為( )0fx ()()kkkf xxxfxNewton迭代法 于是方程于是方程 f f( (x x)=0)=0的新的近似根的新的近似根x xk k+1+1，可得，可得牛頓迭牛頓迭代公式代公式q 1()0,1,2,()kkkkf xxxkfxq 牛頓迭代公式為特殊的不動點迭代。牛頓迭代公式為特

23、殊的不動點迭代。 其迭代函數(shù)為其迭代函數(shù)為 ,)()()(xfxfxxNewton迭代法幾何解釋 設(shè)設(shè) 是根是根 的某個近似值，過曲線的某個近似值，過曲線 上橫上橫坐標為坐標為 的點的點 引切線，并將該切線與引切線，并將該切線與 軸的交點的橫軸的交點的橫坐標坐標 作為作為 的新的近似值的新的近似值. . kx*x)( xfy kxkPx1kx*x 注意到切線方程為注意到切線方程為 ).)()(kkkxxxfxfy牛頓法的收斂性 q 定理定理 設(shè)f(xf(x* *)=0, ,)=0, ,且在且在 x x* * 的鄰域的鄰域 上上 存在存在, , 連續(xù)連續(xù), ,則可得則可得 (1) (1)Newt

24、onNewton迭代公式在迭代公式在單根情況下至少單根情況下至少2 2階局部收斂階局部收斂. . (2) (2)( *)0fxf*1* 2*()()()2()limnnnxxfxcxxfxq 牛頓法的計算步驟：步驟步驟1 1 準備準備選定初始近似值選定初始近似值 ，0 x),(00 xff計算計算 ).(00 xff步驟步驟2 2 迭代迭代按公式按公式0001/ ffxx迭代一次，迭代一次，得新的近似值得新的近似值 ，計算，計算1x).(),(1111xffxff步驟步驟3 3 控制控制如果如果 滿足滿足 或或 ，1x121f則終止迭代，以則終止迭代，以 作為所求的根；作為所求的根；1x否則轉(zhuǎn)

25、步驟否則轉(zhuǎn)步驟4 4. 此處此處 是允許誤差，而是允許誤差，而 21,牛頓法的計算步驟：，時當時當CxxxxCxxx1101101其中其中 是取絕對誤差或相對誤差的控制常數(shù)，是取絕對誤差或相對誤差的控制常數(shù)，C步驟步驟4 4 修改修改或者或者 ，則方法失?。?，則方法失??；01f 否則以否則以 代替代替 轉(zhuǎn)步驟轉(zhuǎn)步驟2 2繼續(xù)迭代繼續(xù)迭代. .),(111ffx),(000ffx如果迭代次數(shù)達到預先指定的次數(shù)如果迭代次數(shù)達到預先指定的次數(shù) ，Nfunction y=newton(x0)x1=x0fc(x0)/df(x0); n = 1;while (abs(x1 x0)=1.0e6)&(n0 0 S S, ,使對使對 x x0 0 D D0 0，由牛頓迭代公式產(chǎn)生的序列由牛頓迭代公式產(chǎn)生的序列 x x( (k k) ) D D0 0，且此序列，且此序列超線性超線性收斂于收斂于x x* *；進一步，進一步，若若F F( (x x) )在在S S內(nèi)內(nèi)2 2次連續(xù)可微，則次連續(xù)可微，則序列序列 x x( (k k) ) 至少是至少是平方收斂平方收斂的的. .求方程組求方程組F F( (x x)=0)=0的解的解x x* *, ,可使用下迭代公式可使用下迭代公式: : F F (