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

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

2、知識(shí)預(yù)備知識(shí)q 滿足函數(shù)方程 f(x)=0 的x稱為方程(1)的根，或稱為函數(shù)f(x)的零點(diǎn)。如果函數(shù)(x)可分解為 (x)=(xs)mg(x)且g(s )0,則稱s是(x)的m重零點(diǎn)或(x)=0的m重根。當(dāng)m=1時(shí)，稱s是(x)的單根或單零點(diǎn)。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求解非線性方程的根的問題可分為下面幾個(gè)方面求解非線性方程的根的問題可分為下面幾個(gè)方面

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

4、性方程，可能沒有零點(diǎn)，也可能有一個(gè)或若干個(gè)零點(diǎn)，甚至無窮多個(gè)零點(diǎn)。可能有一個(gè)或若干個(gè)零點(diǎn)，甚至無窮多個(gè)零點(diǎn)。根的存在性定理根的存在性定理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, 則至則至 少存在一點(diǎn)少存在一點(diǎn)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, 則恰好只存在一點(diǎn)則恰好只存在一點(diǎn)x x (a,b)(a,b)使得使得 f(x )=0f(x )=0 根的隔離根的隔離求根的隔離區(qū)間的兩種方法求根的隔離區(qū)間的兩種方法q 畫圖法畫圖法n 畫出畫出y y = = f f ( (x x) )的略圖，從而看出曲線與的略圖，從而看出曲線與x x軸交軸交 點(diǎn)的大致位置。點(diǎn)的大致位置。n 也可將也可將f f ( (x x) = 0) = 0分解為分解為 1 1( (x x)= )= 2 2( (x x) )的形式，的形式， 1 1( (x x) )與與 2 2( (x x) )兩

6、曲線交點(diǎn)的橫坐標(biāo)所在的子兩曲線交點(diǎn)的橫坐標(biāo)所在的子 區(qū)間即為含根區(qū)間。區(qū)間即為含根區(qū)間。 例如例如x xlglgx x 1 = 0 1 = 0 可以改寫為可以改寫為lglgx x=1/=1/x x 畫出對(duì)數(shù)曲線畫出對(duì)數(shù)曲線y y=lg=lgx x, ,與雙曲線與雙曲線y y= 1/= 1/x x, ,它們交它們交 點(diǎn)的橫坐標(biāo)位于區(qū)間點(diǎn)的橫坐標(biāo)位于區(qū)間2,32,3內(nèi)內(nèi)xy1023yxxylog畫圖法畫圖法逐步搜索逐步搜索法法n 對(duì)于給定的對(duì)于給定的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é)點(diǎn)：內(nèi)取定節(jié)點(diǎn)：x xi i= =x x0 0ihih ( (i i=0=0，1 1，2 2，n n) )， 從左至右檢查從左至右檢查f f ( (x xi i) )的符號(hào)，如發(fā)現(xiàn)的符號(hào)，如發(fā)現(xiàn)x xi i與端點(diǎn)與端點(diǎn)x x0 0 的函數(shù)值異號(hào)，則得到一個(gè)縮小的有根子區(qū)間的函數(shù)值異號(hào)，則得到一個(gè)縮小的有根子區(qū)間 x xi i-1-1, ,x xi i。n 用逐步搜索法進(jìn)行實(shí)根隔離的關(guān)鍵是選取步長用逐步搜索法進(jìn)行實(shí)根隔離的關(guān)鍵是選取步長h hn 要選擇適當(dāng)要選擇適當(dāng)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)只有一個(gè)內(nèi)只有一個(gè)( (重根視為一個(gè)重根視

9、為一個(gè)) )實(shí)根。實(shí)根。q 二分法的基本思想二分法的基本思想 二分法詳細(xì)步驟二分法詳細(xì)步驟l l 0011 (),().2001.記有根區(qū)間a ,b =a,b,取 中點(diǎn) 并計(jì)算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ù)運(yùn)算， 由區(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 有如下估計(jì)有如下估計(jì)q 因此終止的條件為因此終止的條件為q 二分法終止的條件二分法終止的條件11*)(21kkkkkababxx1kkkkxxorab對(duì)于給定的精度對(duì)于給定的精度 , ,可估計(jì)二分法所需的步數(shù)可估計(jì)二分法所需的步數(shù) k k ：)(log22abkabk二分法的優(yōu)缺點(diǎn)q 優(yōu)點(diǎn)優(yōu)點(diǎn)l 計(jì)算簡單，方法可靠，并保證收斂計(jì)算簡單，方法可靠，并保證收斂 l 對(duì)函數(shù)對(duì)函數(shù) 要求不高，只要連續(xù)即可要求

12、不高，只要連續(xù)即可。q 缺點(diǎn)缺點(diǎn)l 無法求復(fù)根和偶重根無法求復(fù)根和偶重根l 收斂慢收斂慢 l 調(diào)用一次求解一個(gè)調(diào)用一次求解一個(gè) a, ba, b間的多個(gè)根無法求得間的多個(gè)根無法求得 一般求方程的近似根，不大單獨(dú)使用，常用一般求方程的近似根，不大單獨(dú)使用，常用來為其它方法求方程近似根提供好的初值。方程來為其它方法求方程近似根提供好的初值。方程求根最常用的方法是迭代法求根最常用的方法是迭代法。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符號(hào)表kkkkxfxba

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

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

16、=g(x)x0p0 x1p1需要討論的問題 n 首先期望每個(gè)首先期望每個(gè)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 但但若采用方程另一種等價(jià)形式若采用方程另一種等價(jià)形式13 xx，131kkxx建立迭代公式建立迭代公式 32494. 1432472. 1832588. 1332472. 1733086. 1232473. 1635721. 1132476. 155 . 10kkxkxk第二種方法第二種方法仍取迭代初值仍取迭代初值 ，則有，則有 5 .10 x.39.12,375.221xx結(jié)果會(huì)越來越大，不可能趨于某個(gè)極限結(jié)果會(huì)越來越大，不可能趨于某個(gè)極限. . 迭代法的收斂條件迭代法的收斂條件 q 定理定理*10|1kkLxxxxL且滿足上連續(xù)在設(shè)迭代函數(shù),)(bax;)(,)1(b

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

19、件充分條件，非必要條件。在實(shí)際，非必要條件。在實(shí)際 應(yīng)用當(dāng)應(yīng)用當(dāng)中中 條件并不易檢驗(yàn)條件并不易檢驗(yàn)。 q 定義定義 （局部收斂性）（局部收斂性）設(shè)設(shè) 有不動(dòng)點(diǎn)有不動(dòng)點(diǎn) ，)( x*x如果存在如果存在 的某個(gè)鄰域的某個(gè)鄰域*x,*: xxR對(duì)任意對(duì)任意 ，Rx0迭代產(chǎn)生的序列迭代產(chǎn)生的序列,Rxk且收斂到且收斂到 ，*x則稱迭代法則稱迭代法局部收斂局部收斂. .q 定理定理 設(shè)設(shè)s s為為的不動(dòng)點(diǎn)的不動(dòng)點(diǎn), , 在在s s的某個(gè)鄰域內(nèi)連續(xù)的某個(gè)鄰域內(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如果迭代誤差如果迭代誤差 當(dāng)當(dāng) 時(shí)成立下列時(shí)成立下列*xxekkk漸近關(guān)系式漸近關(guān)系式),0(1CCeepkk常數(shù) 若若 p p = 1 = 1 , , 稱稱 x xk k 為為線性收斂線性收斂, , 這時(shí)這時(shí) 0 0 1, 1, 稱稱 x xk k 為為超線性收斂超線性收斂; ; p p=2, =2, 稱其為稱其為平方收斂平方收斂. .收斂階定理 q 數(shù)數(shù)p p的大小反映了迭代法的收斂速度的快慢，的大小反映了迭代法的收斂速度的快慢，P P越大，收越

21、大，收 斂越快斂越快，所以說收斂階是對(duì)迭代法收斂速度的一種度量。，所以說收斂階是對(duì)迭代法收斂速度的一種度量。 q （收斂階定理）（收斂階定理） 對(duì)于迭代過程對(duì)于迭代過程 ，如果，如果 在所求根在所求根 的鄰近連續(xù)，并且的鄰近連續(xù)，并且: : 則該迭代過程在點(diǎn)則該迭代過程在點(diǎn) 鄰近是鄰近是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的一個(gè)近似根，把的一個(gè)近似根，把 f f( (x x) )在在x xk k處處作一階泰勒展開，即用前兩項(xiàng)近似代替作一階泰勒展開，即用前兩項(xiàng)近似代替( )( )( )()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 牛頓迭代公式為特殊的不動(dòng)點(diǎn)迭代。牛頓迭代公式為特

23、殊的不動(dòng)點(diǎn)迭代。 其迭代函數(shù)為其迭代函數(shù)為 ,)()()(xfxfxxNewton迭代法幾何解釋 設(shè)設(shè) 是根是根 的某個(gè)近似值，過曲線的某個(gè)近似值，過曲線 上橫上橫坐標(biāo)為坐標(biāo)為 的點(diǎn)的點(diǎn) 引切線，并將該切線與引切線，并將該切線與 軸的交點(diǎn)的橫軸的交點(diǎn)的橫坐標(biāo)坐標(biāo) 作為作為 的新的近似值的新的近似值. . 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 牛頓法的計(jì)算步驟：步驟步驟1 1 準(zhǔn)備準(zhǔn)備選定初始近似值選定初始近似值 ，0 x),(00 xff計(jì)算計(jì)算 ).(00 xff步驟步驟2 2 迭代迭代按公式按公式0001/ ffxx迭代一次，迭代一次，得新的近似值得新的近似值 ，計(jì)算，計(jì)算1x).(),(1111xffxff步驟步驟3 3 控制控制如果如果 滿足滿足 或或 ，1x121f則終止迭代，以則終止迭代，以 作為所求的根；作為所求的根；1x否則轉(zhuǎn)

25、步驟否則轉(zhuǎn)步驟4 4. 此處此處 是允許誤差，而是允許誤差，而 21,牛頓法的計(jì)算步驟：，時(shí)當(dāng)時(shí)當(dāng)CxxxxCxxx1101101其中其中 是取絕對(duì)誤差或相對(duì)誤差的控制常數(shù)，是取絕對(duì)誤差或相對(duì)誤差的控制常數(shù)，C步驟步驟4 4 修改修改或者或者 ，則方法失??；，則方法失??；01f 否則以否則以 代替代替 轉(zhuǎn)步驟轉(zhuǎn)步驟2 2繼續(xù)迭代繼續(xù)迭代. .),(111ffx),(000ffx如果迭代次數(shù)達(dá)到預(yù)先指定的次數(shù)如果迭代次數(shù)達(dá)到預(yù)先指定的次數(shù) ，Nfunction y=newton(x0)x1=x0fc(x0)/df(x0); n = 1;while (abs(x1 x0)=1.0e6)&(n0 0 S S, ,使對(duì)使對(duì) x x0 0 D D0 0，由牛頓迭代公式產(chǎn)生的序列由牛頓迭代公式產(chǎn)生的序列 x x( (k k) ) D D0 0，且此序列，且此序列超線性超線性收斂于收斂于x x* *；進(jìn)一步，進(jìn)一步，若若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 (