數(shù)值分析 第7章 非線性方程求根

1、數(shù)理學(xué)院數(shù)理學(xué)院SCHOOL OF MATHEMATICS AND PHYSICS7 .1 方程求根與二分法方程求根與二分法7 .2 迭代法及其收斂性迭代法及其收斂性7 .3 迭代收斂的加速方法迭代收斂的加速方法7 .4 牛頓法牛頓法7 .5 弦截法與拋物線法弦截法與拋物線法7 .6 解非線性方程組的牛頓迭代法解非線性方程組的牛頓迭代法Ch7 非線性方程求根非線性方程求根7.1方程求根與二分法方程求根與二分法 在實(shí)際問(wèn)題中在實(shí)際問(wèn)題中,經(jīng)常要求方程經(jīng)常要求方程 f (x) = 0. (1.1)滿足此方程的解滿足此方程的解x, 稱為方程的根稱為方程的根,也稱也稱x是函數(shù)是函數(shù)f(x)的零點(diǎn)的零點(diǎn)

2、.如果函數(shù)如果函數(shù)f(x)可以寫成可以寫成f(x)=(x- x*)mg(x),其中其中g(shù)( x*) 0.當(dāng)當(dāng)m1時(shí)，稱時(shí)，稱x*為方程為方程(1.1)的的m重根或稱重根或稱x*是函數(shù)是函數(shù)f(x)的的m重零點(diǎn)重零點(diǎn);當(dāng)當(dāng)m=1時(shí)，稱時(shí)，稱x*為方程為方程(1.1)的單根或稱的單根或稱x*是函數(shù)是函數(shù)f(x)的的單重零點(diǎn)單重零點(diǎn).當(dāng)當(dāng)f(x)為一般連續(xù)函數(shù)為一般連續(xù)函數(shù)(超越函數(shù)超越函數(shù))時(shí)，就稱時(shí)，就稱f(x)=0為超越方程為超越方程.如果如果f為多項(xiàng)式為多項(xiàng)式),0()()(01110aaxaxaxaxpxfnnnn(1.2)則稱此方程為代數(shù)方程則稱此方程為代數(shù)方程. 對(duì)于一次、二次代數(shù)方程

3、，可以求出精確解，而對(duì)于三次以對(duì)于一次、二次代數(shù)方程，可以求出精確解，而對(duì)于三次以上的代數(shù)方程和超越方程，沒(méi)有通用的技術(shù)來(lái)求出精確解，這就上的代數(shù)方程和超越方程，沒(méi)有通用的技術(shù)來(lái)求出精確解，這就需要用數(shù)值方法求出方程的近似解。需要用數(shù)值方法求出方程的近似解。 一般地一般地,一次方程稱為線性方程一次方程稱為線性方程,而二次以上的代數(shù)方程而二次以上的代數(shù)方程或超越方程稱為非線性方程或超越方程稱為非線性方程.原理：原理：若若 f Ca, b，且，且 f (a) f (b) 0，即兩個(gè)端點(diǎn)值異號(hào)，即兩個(gè)端點(diǎn)值異號(hào)，且且f（x）在區(qū)間）在區(qū)間a，b上嚴(yán)格單調(diào)，則利用閉區(qū)間上上嚴(yán)格單調(diào)，則利用閉區(qū)間上連續(xù)

4、函數(shù)的性質(zhì)，可知連續(xù)函數(shù)的性質(zhì)，可知f（x）在）在 a, b上存在唯一的上存在唯一的零點(diǎn)，其幾何意義如下圖：零點(diǎn)，其幾何意義如下圖：分離區(qū)間：分離區(qū)間：許多方程往往有兩個(gè)以上的根，在某個(gè)區(qū)間許多方程往往有兩個(gè)以上的根，在某個(gè)區(qū)間a，b上，如果方程在此區(qū)間內(nèi)只含一個(gè)根，我們稱此區(qū)間為方程的上，如果方程在此區(qū)間內(nèi)只含一個(gè)根，我們稱此區(qū)間為方程的分離區(qū)間。分離區(qū)間。x*abf(a)f(b)x*abf(a)f(b)曲線曲線y=f(x)與與x軸的交點(diǎn)就是軸的交點(diǎn)就是f(x)的零點(diǎn)的零點(diǎn). 用描述的方法用描述的方法,或稱搜索的方法或稱搜索的方法,先確定搜索區(qū)間的下界先確定搜索區(qū)間的下界a,選擇搜索步長(zhǎng)選擇

5、搜索步長(zhǎng)h,然后求出然后求出f(a), f(a+h), , f(a+nh), 遇到遇到f(a+kh), f(a+(k+1)h)異號(hào)異號(hào),可知區(qū)間可知區(qū)間a+kh, a+(k+1)h內(nèi)有根內(nèi)有根.從而可以加密搜索步長(zhǎng)進(jìn)行搜索從而可以加密搜索步長(zhǎng)進(jìn)行搜索,提高密度提高密度.a,b如何確定如何確定?h選多大合適選多大合適?h過(guò)大則可能會(huì)漏掉根過(guò)大則可能會(huì)漏掉根.a+kha+(k+1)hhh過(guò)大過(guò)大,漏掉了兩個(gè)根漏掉了兩個(gè)根. h過(guò)小過(guò)小,則計(jì)算量很大則計(jì)算量很大,如要求精度達(dá)到如要求精度達(dá)到0.001,則在長(zhǎng)度為則在長(zhǎng)度為1的的搜索區(qū)間中搜索區(qū)間中,要計(jì)算要計(jì)算1000個(gè)函數(shù)值個(gè)函數(shù)值,欲使精度提高

6、一倍欲使精度提高一倍,計(jì)算量就計(jì)算量就要增加要增加10倍倍.例例1求方程求方程 f(x)=x3-11.1x2+38.8x-41.77=0的有根區(qū)間的有根區(qū)間.解解 根據(jù)有根區(qū)間定義，對(duì)方程的根進(jìn)行搜索計(jì)算，結(jié)果如下表根據(jù)有根區(qū)間定義，對(duì)方程的根進(jìn)行搜索計(jì)算，結(jié)果如下表方程的三個(gè)有根區(qū)間為方程的三個(gè)有根區(qū)間為1,2,3,4,5,6. x0123456f(x)-+-+方程根的搜索程序如下：方程根的搜索程序如下：function k,r=zhubuss(a,b,h,tol)% 輸入的量- a和b是閉區(qū)間a,b的左、右端點(diǎn)；%-h是步長(zhǎng)；%-tol是預(yù)先給定的精度.% 運(yùn)行后輸出的量-k是搜索點(diǎn)的個(gè)數(shù)

7、；% - r是方程 在a,b上的實(shí)根的近似值，其精度是tol；X=a:h:b;Y=funs(X);n=(b-a)/h+1;m=0;X(n+1)=X(n);Y(n+1)=Y(n);for k=2:n X(k)=a+k*h;Y(k)=funs(X(k); sk=Y(k)*Y(k-1); if sk=0, m=m+1;r(m)=X(k); end xielv=(Y(k+1)-Y(k)*(Y(k)-Y(k-1); if (abs(Y(k)tol)&( xielv k,r=zhubuss(0,6,0.001,0.0001)運(yùn)行后輸出的結(jié)果運(yùn)行后輸出的結(jié)果k = 6001r = 2.09700000000

8、000， 3.91800000000000， 5.08600000000000，原理：原理：若若 f Ca, b，且，且 f (a) f (b) 0，即兩個(gè)端點(diǎn)值異號(hào)，即兩個(gè)端點(diǎn)值異號(hào)，且且f（x）在區(qū)間）在區(qū)間a，b上嚴(yán)格單調(diào)，則利用閉區(qū)間上上嚴(yán)格單調(diào)，則利用閉區(qū)間上連續(xù)函數(shù)的性質(zhì)，可知連續(xù)函數(shù)的性質(zhì)，可知f（x）在）在 a, b上存在唯一的上存在唯一的零點(diǎn)，其幾何意義如下圖：零點(diǎn)，其幾何意義如下圖：x*abf(a)f(b)x*abf(a)f(b)7.1.2 二分法二分法一、二分法的具體計(jì)算過(guò)程一、二分法的具體計(jì)算過(guò)程,baCf 設(shè)設(shè),現(xiàn)求方程現(xiàn)求方程f(x)=0在區(qū)間在區(qū)間a,b 上的根上

9、的根.設(shè)函數(shù)設(shè)函數(shù)f(x)滿足滿足, 0)()(bfaf不妨設(shè)不妨設(shè). 0)(, 0)(bfaf第一步第一步: 取區(qū)間中點(diǎn)取區(qū)間中點(diǎn),2ba 計(jì)算區(qū)間中點(diǎn)的函數(shù)值計(jì)算區(qū)間中點(diǎn)的函數(shù)值),2(baf如果如果, 0)2(baf則則2ba就是方程的根就是方程的根x*.x*ab2ba區(qū)間的左端點(diǎn)為區(qū)間的左端點(diǎn)為a,右端點(diǎn)為右端點(diǎn)為,2ba 記為記為2,11babaa下一步在區(qū)間下一步在區(qū)間,11ba內(nèi)繼續(xù)進(jìn)行內(nèi)繼續(xù)進(jìn)行,11ba是原來(lái)區(qū)間的一半是原來(lái)區(qū)間的一半.如果如果, 0)2(baf則在區(qū)間則在區(qū)間2,baa上上,f(x)在兩個(gè)端點(diǎn)的在兩個(gè)端點(diǎn)的函數(shù)值異號(hào)函數(shù)值異號(hào),于是原方程在區(qū)間于是原方程在區(qū)

10、間2,baa內(nèi)有根內(nèi)有根(如圖如圖)如果如果, 0)2(baf則在區(qū)間則在區(qū)間,2bba上上,f(x)在兩個(gè)端點(diǎn)的在兩個(gè)端點(diǎn)的函數(shù)值異號(hào)函數(shù)值異號(hào),于是原方程在區(qū)間于是原方程在區(qū)間內(nèi)有根內(nèi)有根(如圖如圖),2bbaab2ba區(qū)間的左端點(diǎn)為區(qū)間的左端點(diǎn)為,2ba 記為記為.,211bbbaa下一步在區(qū)間下一步在區(qū)間,11ba內(nèi)繼續(xù)進(jìn)行內(nèi)繼續(xù)進(jìn)行,11ba是原來(lái)區(qū)間的一半是原來(lái)區(qū)間的一半.右端點(diǎn)為右端點(diǎn)為b.第二步第二步(如第一步如第一步,采用類推的方法采用類推的方法)求求f(x)在區(qū)間在區(qū)間a1,b1的中點(diǎn)的中點(diǎn)211ba 的函數(shù)值的函數(shù)值),2(11baf如果如果, 0)2(11baf如果如果

11、, 0)2(11baf則原方程在區(qū)間則原方程在區(qū)間2,111baa內(nèi)有根內(nèi)有根.并檢驗(yàn)其正負(fù)號(hào)并檢驗(yàn)其正負(fù)號(hào),則為根則為根,此種情況很少此種情況很少.記為記為.2,11212babaa如果如果, 0)2(11baf則在區(qū)間則在區(qū)間,2111bba 上上, 原方程有根原方程有根.,212112bbbaa記為記為,2211nnbabababa于是，得到于是，得到,1122bababa其區(qū)間寬度為：其區(qū)間寬度為：).(41)(211122ababab象這樣繼續(xù)進(jìn)行第三步，第四步，象這樣繼續(xù)進(jìn)行第三步，第四步，區(qū)間寬度每次縮小，區(qū)間寬度每次縮小一半，得到區(qū)間序列一半，得到區(qū)間序列此時(shí)，此時(shí)，, 0)(

12、)(nnbfaf原方程在區(qū)間原方程在區(qū)間,nnba內(nèi)有根，內(nèi)有根，區(qū)間寬度為區(qū)間寬度為,2nnnabab;2*nnnbaxx此時(shí)，近似值的誤差小于該區(qū)間寬度的一半此時(shí)，近似值的誤差小于該區(qū)間寬度的一半1*22| nnnnababxx(1.3)當(dāng)當(dāng)n足夠大時(shí)，如果此時(shí)的區(qū)間寬度已達(dá)到精度要求，則足夠大時(shí)，如果此時(shí)的區(qū)間寬度已達(dá)到精度要求，則以區(qū)間的中點(diǎn)作為以區(qū)間的中點(diǎn)作為x*的近似值，即的近似值，即如果要求如果要求,|* xxn則要求則要求 )(211abn兩邊取對(duì)數(shù)，得兩邊取對(duì)數(shù)，得 ln2ln)1()ln( nab則則)1ln)(ln(2ln11 abn如果精度要求提高，如果精度要求提高，由

13、于由于,1024210 如要求誤差縮小千分之一，則要求多計(jì)算次如要求誤差縮小千分之一，則要求多計(jì)算次二、計(jì)算流程二、計(jì)算流程根據(jù)精度要求可事先計(jì)算出需要執(zhí)行步驟數(shù)根據(jù)精度要求可事先計(jì)算出需要執(zhí)行步驟數(shù)n.初態(tài)：初態(tài)：f (a) f (b) 0, disp(注意：ya*yb0,請(qǐng)重新調(diào)整區(qū)間端點(diǎn)a和b.), returnendmax1=-1+ceil(log(b-a)- log(abtol)/ log(2); % ceil是方向取整for k=1: max1+1a;ya=fun(a); b;yb=fun(b); x=(a+b)/2; yx=fun(x); wuca=abs(b-a)/2; k=k

14、-1;k,a,b,x,wuca,ya,yb,yxif yx=0a=x; b=x;elseif yb*yx0b=x;yb=yx;elsea=x; ya=yx;endif b-a abtol , return, endendk=max1; x; wuca; yx=fun(x);7.2 迭代法迭代法 /* Fixed-Point Iteration */f (x) = 0 x = (x)等價(jià)變換等價(jià)變換f (x) 的根的根(x) 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn)從一個(gè)初值從一個(gè)初值 x0 出發(fā)，計(jì)算出發(fā)，計(jì)算 x1 = (x0), x2 = (x1), , xk+1 = (xk), 若若 收斂，即存在收斂，即存在

15、x* 使得使得 ，且，且連續(xù)，則由連續(xù)，則由 可知可知 x* = (x* )，即，即x* 是是 的不動(dòng)點(diǎn)，也就是的不動(dòng)點(diǎn)，也就是f 的根。的根。 0kkx*limxxkk kkkkxx limlim1(2.1)(2.2) 是一種逐次逼近法是一種逐次逼近法,其基本思想是將隱式方程其基本思想是將隱式方程(2.1)歸結(jié)歸結(jié)為一組顯式的計(jì)算公式為一組顯式的計(jì)算公式(2.2). 迭代過(guò)程實(shí)質(zhì)上是一個(gè)逐步顯示化的過(guò)程迭代過(guò)程實(shí)質(zhì)上是一個(gè)逐步顯示化的過(guò)程.例例3 求方程求方程01)(3xxxf在在5 . 10 x附近的根附近的根. 解解 若將方程改寫為若將方程改寫為, ,構(gòu)造迭代法構(gòu)造迭代法13 xx, 1

16、 , 0, 131kxxkk由由可知，可知，顯然不收斂顯然不收斂. . ,39.12,375. 2, 5 . 1210 xxxkx若將方程改為若將方程改為，構(gòu)造迭代法，構(gòu)造迭代法計(jì)算結(jié)果見表計(jì)算結(jié)果見表7-2.7-2. 3/1) 1( xx, 1 , 0,) 1(3/11kxxkk表表 7 72 2 例題表明構(gòu)造迭代法例題表明構(gòu)造迭代法(2.2)(2.2)，必須使迭代序列，必須使迭代序列xk 收斂，收斂，才能求得方程才能求得方程(2.1)(2.1)的解的解x*. .下面給出解的存在唯一性和迭下面給出解的存在唯一性和迭代收斂性定理代收斂性定理.從結(jié)果看它是收斂的，且從結(jié)果看它是收斂的，且6位有效

17、數(shù)字位有效數(shù)字32472. 187 xx即為根即為根x*的近似值的近似值.( I ) 當(dāng)當(dāng) x a, b 時(shí)，時(shí)， (x) a, b；( II ) 0 L 1 使得使得 | (x) | L 1 對(duì)對(duì) x a, b 成立。成立。則任取則任取 x0 a, b，由，由 xk+1 = (xk) 得到的序列得到的序列 收斂收斂于于(x) 在在a, b上的唯一不動(dòng)點(diǎn)。并且有誤差估計(jì)式：上的唯一不動(dòng)點(diǎn)。并且有誤差估計(jì)式：定理定理考慮方程考慮方程 x = (x), (x) Ca, b, 若若 0kkx|11|*|1kkkxxLxx |1|*|01xxLLxxk ( k = 1, 2, )且存在極限且存在極限

18、*lim1xxxxxkkk k證明：證明： (x) 在在a, b上存在不動(dòng)點(diǎn)？上存在不動(dòng)點(diǎn)？令令xxxf )()( bxa )( ,0)()( aaaf 0)()( bbbf )(xf有根有根 不動(dòng)點(diǎn)唯一？不動(dòng)點(diǎn)唯一？反證：若不然，設(shè)還有反證：若不然，設(shè)還有 ，則，則)(xx ),*( )()(*)(xxxx xx*在在和和之間。之間。 *xx0)(1)( xx* 而而xx*1| )(| ?|11|*|1kkkxxLxx |*|*|*|*|11kkkkkkxxLxxxxxxxx 當(dāng)當(dāng)k 時(shí)，時(shí)， xk 收斂到收斂到 x* ？ |*|kxx|*| )(| )(*)(|111 kkkxxxx 0|

19、*|.|*|01 xxLxxLkk ?|1|*|01xxLLxxkk |.| )(| )()(|011111xxLxxLxxxxxxkkkkkkkkkk ?*lim1xxxxxkkk *)(*)*)(lim*lim1xxxxxxxxxkkkkkkk xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1定理?xiàng)l件非必要條件，可將定理?xiàng)l件非必要條件，可將a, b縮小，定義縮小，定義局部收局部收斂性斂性：若在：若在 x* 的某的某 鄰域鄰域 B = x | |

20、 x x* | 有有 C1a, b 且且 | (x*) | k,piancha,xdpiancha,xk= diedai1(2,5)function k,piancha,xdpiancha,xk=diedai1(x0,k)% 輸入的量輸入的量-x0是初始值是初始值,k是迭代次數(shù)是迭代次數(shù)x(1)=x0; for i=1:k x(i+1)=fun1(x(i);%程序中調(diào)用的程序中調(diào)用的fun1.m為函數(shù)為函數(shù)y=(x) piancha= abs(x(i+1)-x(i); xdpiancha=piancha/( abs(x(i+1)+eps); i=i+1;xk=x(i);(i-1) pianch

21、a xdpiancha xkendif (piancha 1)&(xdpiancha0.5)&(k3) disp(此迭代序列發(fā)散，請(qǐng)重新輸入新的迭代公式此迭代序列發(fā)散，請(qǐng)重新輸入新的迭代公式) return; end if (piancha 0.001)&(xdpiancha3) disp(祝賀您！此迭代序列收斂，且收斂速度較快祝賀您！此迭代序列收斂，且收斂速度較快) return; endp=(i-1) piancha xdpiancha xk;三次迭代分別為：三次迭代分別為：定義定義設(shè)迭代設(shè)迭代 xk+1 = (xk) 收斂到收斂到(x) 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn) x*。設(shè)設(shè) ek = xk x*

22、，若，則稱該迭代為若，則稱該迭代為p 階收斂階收斂。0|lim1 Ceepkkk 一般一般 Fixed-Point Iteration 有有 ，稱為，稱為線線 性收斂性收斂 /* linear convergence */，這時(shí)，這時(shí) p = 1，0 C 1，稱為超線性收斂，稱為超線性收斂， p 2，稱為平方收斂。，稱為平方收斂。0|*)(|lim1 xeekkk 定理定理 設(shè)設(shè) x* 為為x = (x) 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn)，若，若 ，p 2； ，且，且 ，則，則 xk+1 = (xk) 在在 內(nèi)內(nèi) p 階收斂。階收斂。*)(xBCp 0*)(.*)()1( xxp 0*)()( xp *)(x

23、B 證明：證明：pkkpkkkxxpxxxxxgx*)(!)(.*)*)(*)()()(1 x*k C3.13.1 Aitken 加速：加速：xyy = xy = (x)x*x0P(x0, x1)x1x2x P(x1, x2)21020102)(xxxxxxx 7.3 迭代收斂的加速方法迭代收斂的加速方法) , (xxxxxxxxxx1201可以證明：可以證明：0lim*xxxxkkk一般地有：一般地有：2112()2KKKKKKKxxxxxxx .),(,),(,),(),(,34123012010 xxxxxxxxxxx 比比 收斂得略快。收斂得略快。 Kx Kxfunction k,xk

24、,yk,p= Aitken (x0,tol, ddmax)x(1)=x0;for i=1: ddmax x1(i+1)=fun(x(i); x2(i+1)=fun(x1(i+1); x(i+1)=x2(i+1)-(x2(i+1)-x1(i+1)2/(x2(i+1)-2*x1(i+1)+ x(i); piancha=abs(x(i+1)-x(i); xdpiancha= piancha/( abs(x(i+1)+eps); i=i+1; xk=x(i);yk=fun(x(i); if (pianchatol)|(xdpianchaddmax disp(迭代次數(shù)超過(guò)給定的最大值ddmax) k=i

25、-1; xk=x(i); yk=fun(x(i); m=0,1:i-1; p=m,x1,x2,x; return;endm=0,1:i-1; p=m,x1,x2,x;例：用艾特肯加速方法求例：用艾特肯加速方法求 02xex在在0.85附近的一個(gè)近似根，要求精度附近的一個(gè)近似根，要求精度 .106在在MATLAB工作窗口輸入程序工作窗口輸入程序 k,xk,yk,p= Aitken(0.85,1e-6, 100).Steffensen加速迭代法加速迭代法不動(dòng)點(diǎn)迭代不動(dòng)點(diǎn)迭代(2.2)通常只有線性收斂，有時(shí)甚至不收斂，為加速迭通常只有線性收斂，有時(shí)甚至不收斂，為加速迭代法的收斂性通?？刹捎么ǖ氖諗?/p>

26、性通?？刹捎肧teffensen加速迭代加速迭代. 設(shè)設(shè)x* 為為x = (x)不動(dòng)點(diǎn)不動(dòng)點(diǎn) ，記記 *xxkk利用中值定理有利用中值定理有 )()()(*11kkkkkkkxxxxxxxx 于是有C)大，設(shè))若，依賴)通, ( k (.* kkkkxxx 變化不變化不于于常常之間之間與與在在)()(*1*2*1xxCxxxxCxxkkkk從上兩式消去從上兩式消去C，則得，則得*1*1*2xxxxxxxxkkkk 或或2*1*2)(）（）（xxxxxxkkk解得解得 kkkkkkkkkkkkxxxxxxxxxxxxx12211222*2)(2若記若記, 1 , 0,2)(12211kxxxxx

27、xxkkkkkkk(3.1) 用序列用序列作為不動(dòng)點(diǎn)作為不動(dòng)點(diǎn)的新近似，一般說(shuō)，它比迭代法的新近似，一般說(shuō)，它比迭代法(2.2)kx*x收斂更快，實(shí)際上迭代法收斂更快，實(shí)際上迭代法(3.1)可改為可改為 , 1 , 0,2)()(),(21kxyzxyxxyzxykkkkkkkkkkk (3.2) 稱為稱為Steffensen迭代法，它是將原不動(dòng)點(diǎn)迭代迭代法，它是將原不動(dòng)點(diǎn)迭代(2.2)計(jì)算兩次計(jì)算兩次合并成一步得到，可改為另一種不動(dòng)點(diǎn)迭代法合并成一步得到，可改為另一種不動(dòng)點(diǎn)迭代法 其中其中 并有以下局部收斂定理并有以下局部收斂定理. L, 1 , 0),(1kxxkkxxgxggxxgxx)

28、(2)()()(2定理定理若若為為(3.4)定義的函數(shù)定義的函數(shù)的不動(dòng)點(diǎn)，則的不動(dòng)點(diǎn)，則為為g的不動(dòng)點(diǎn)的不動(dòng)點(diǎn).反之，若反之，若且且則則是是的不動(dòng)點(diǎn)且迭代法的不動(dòng)點(diǎn)且迭代法(3.3)*x*x為為g的不動(dòng)點(diǎn)的不動(dòng)點(diǎn),設(shè)設(shè)g(x)存在，存在，*x, 1)( *xg*x是二階收斂的是二階收斂的例例5 在例在例3中求方程中求方程的第一種迭代的第一種迭代(2.3)是不收斂的，試用是不收斂的，試用Steffensen迭代法求解迭代法求解.解解 式式(2.3)中中,現(xiàn)用式現(xiàn)用式(3.2)迭代，結(jié)果見表迭代，結(jié)果見表-4.表表74它是收斂的，此例表明，即使對(duì)它是收斂的，此例表明，即使對(duì)(2.2)不收斂的迭代法

29、，用不收斂的迭代法，用Steffensen加速迭代加速迭代(3.2)仍可能收斂仍可能收斂.01)(3xxxf1)(3 xxg7.4 牛頓法牛頓法 /* Newton - Raphson Method */原理：原理：將非線性方程線性化將非線性方程線性化 Taylor 展開展開 /* Taylors expansion */取取 x0 x*，將將 f (x)在在 x0 做一階做一階Taylor展開展開:20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x 之間。之間。將將 (x* x0)2 看成高階小量，則有：看成高階小量，則有：)*)()(*)(0000 xxx

30、fxfxf )()(*000 xfxfxx 線性線性 /* linear */xyx*x0)()(1kkkkxfxfxx 只要只要 f C1，每一步迭代都有，每一步迭代都有f ( xk ) 0， 而而 ，則，則 x*就是就是 f 的根。的根。*limxxkk 定理定理 （收斂的充分條件收斂的充分條件）設(shè)）設(shè) f C2a, b，若，若(1) f (a) f (b) 0；則則Newtons Method產(chǎn)生的序列產(chǎn)生的序列 xk 收斂到收斂到f (x) 在在 a, b 的的唯一根。唯一根。有根有根根唯一根唯一產(chǎn)生的序列單調(diào)有產(chǎn)生的序列單調(diào)有界，保證收斂。界，保證收斂。定理定理 （局部收斂性局部收斂

31、性）設(shè)）設(shè) f C2a, b，若，若 x* 為為 f (x) 在在a, b上的根，且上的根，且 f (x*) 0，則存在，則存在 x* 的鄰域的鄰域 使得任取初使得任取初值值 ，Newtons Method產(chǎn)生的序列產(chǎn)生的序列 xk 收斂到收斂到x*，且滿足且滿足*)(xB *)(0 xBx *)(2*)()*(*lim21xfxfxxxxkkk 證明：證明：Newtons Method 事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代 其中其中 ，則，則)()()(xfxfxxg 10*)(*)(*)(*)(2xfxfxfxg收斂收斂由由 Taylor 展開：展開：2)*(!2)()

32、*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(! 2)()()(*kkkkkkxxxffxfxfxx 1 kx)(2)()*(*21kkkkxffxxxx 只要只要 f (x*) 0，則令，則令 可得結(jié)論?？傻媒Y(jié)論。 k在在單根單根 /*simple root */ 附近收斂快附近收斂快 Newtons Method 收斂性依賴于收斂性依賴于x0 的選取。的選取。x*x0 x0 x0例例7 用牛頓法解方程用牛頓法解方程:01xxe解：這里的牛頓公式為：解：這里的牛頓公式為：,11kxkkkxexxxk取初值取初值x0=0.5,迭代結(jié)果列于表迭代結(jié)果列于表7-7中。中。表表7-

33、7 計(jì)算結(jié)果計(jì)算結(jié)果kxk00.510.5710220.5671630.56714function k,xk,yk,piancha,xdpiancha=newtonqx(x0,tol,ftol,gxmax)x(1)=x0; for i=1: gxmax x(i+1)=x(i)-fnq(x(i)/(dfnq(x(i)+eps); piancha=abs(x(i+1)-x(i); xdpiancha= piancha/( abs(x(i+1)+eps); i=i+1;xk=x(i);yk=fnq(x(i); (i-1) xk yk piancha xdpianchaif (abs(yk)ftol)

34、&(pianchatol)|(xdpianchagxmax disp(請(qǐng)注意：迭代次數(shù)超過(guò)給定的最大值gxmax。) k=i-1; xk=x(i);(i-1) xk yk piancha xdpiancha return;end (i-1),xk,yk,piancha,xdpiancha;function f=dfnq(x)f=(1+x)*exp(x);function f=fnq(x)f=x*exp(x)-1k,xk,yk,piancha,xdpiancha=newtonqx(0.5,0.001, 0.001,100)7.4.3 簡(jiǎn)化牛頓法與牛頓下山法簡(jiǎn)化牛頓法與牛頓下山法牛頓法的優(yōu)點(diǎn)是收斂

35、快，缺點(diǎn)是：牛頓法的優(yōu)點(diǎn)是收斂快，缺點(diǎn)是： 一是每步迭代要計(jì)算一是每步迭代要計(jì)算f ( xk ) 及及f( xk ) , 計(jì)算量較大計(jì)算量較大且有時(shí)且有時(shí)f( xk )計(jì)算較困難計(jì)算較困難; 二是初始近似二是初始近似x0只在根只在根x* 附近才能保證收斂附近才能保證收斂, 如如x0 給的不合適可能不收斂給的不合適可能不收斂為克服這兩個(gè)缺點(diǎn)為克服這兩個(gè)缺點(diǎn), 通?？捎孟率龇椒ㄍǔ？捎孟率龇椒?(1 ) 簡(jiǎn)化牛頓法簡(jiǎn)化牛頓法, 也稱平行弦法也稱平行弦法.其迭代公式為其迭代公式為xk+1 = xk - Cf ( xk ) C 0 , k = 0 , 1 , . ( 4 .7)迭代函數(shù)迭代函數(shù) ( x

36、 ) = x - C f ( x) . 若若 |( x ) | = | 1 - C f( x ) | 1 , 即取即取0 C f( x ) 2 .在根在根x* * 附近成立附近成立, 則迭代法則迭代法( 4. . 7) 局部收斂局部收斂.在( 4. 7 ) 中取C =1/f( x0 ), 則稱為簡(jiǎn)化牛頓法, 這類方法計(jì)算量省這類方法計(jì)算量省, 但只有線性收斂但只有線性收斂, 其幾何意義是用平其幾何意義是用平行弦與行弦與x 軸交點(diǎn)作為軸交點(diǎn)作為x * * 的近似的近似.如圖如圖7 - -4 所示所示. 圖 7 -4(2 ) 牛頓下山法牛頓下山法.牛頓法收斂性依賴初值牛頓法收斂性依賴初值x0 的選

37、取的選取.如果如果x0 偏離偏離所求根所求根x* * 較遠(yuǎn)較遠(yuǎn), 則牛頓法可能發(fā)散則牛頓法可能發(fā)散.例如, 用牛頓法求解方程 x3 - x - 1 = 0 . (4 .8 )此方程在x = 1 .5 附近的一個(gè)根x*設(shè)取迭代初值x0 = 1. 5 , 用牛頓法公式( 4 .9)計(jì)算得x1 = 1 .34783 , x2 = 1 .32520 , x3 = 1 .32472 .迭代3 次得到的結(jié)果x3 有6 位有效數(shù)字.,131231kkkkkxxxxx 但是但是, 如果改用如果改用x0 = 0 .6 作為迭代初值作為迭代初值, 則依牛頓法公則依牛頓法公式式(4. . 9 )迭代一次得迭代一次得

38、x1 = 17 .9 .這個(gè)結(jié)果反而比這個(gè)結(jié)果反而比x0 = 0 .6 更偏離了所求的根更偏離了所求的根x* * = 1. .32472 . 為了防止迭代發(fā)散為了防止迭代發(fā)散, 我們對(duì)迭代過(guò)程再附加一項(xiàng)要求我們對(duì)迭代過(guò)程再附加一項(xiàng)要求, 即具即具有單調(diào)性有單調(diào)性:| f ( xk+1 ) | | f ( xk ) | . (4 .10)滿足這項(xiàng)要求的算法稱下山法滿足這項(xiàng)要求的算法稱下山法. 將牛頓法與下山法結(jié)合起來(lái)使用將牛頓法與下山法結(jié)合起來(lái)使用, 即在下山法保證函數(shù)即在下山法保證函數(shù)值穩(wěn)定下降的前提下值穩(wěn)定下降的前提下, 用牛頓法加快收斂速度用牛頓法加快收斂速度.為此為此, 我我們將牛頓法的

39、計(jì)算結(jié)果們將牛頓法的計(jì)算結(jié)果)()(1kkkkxfxfxx與前一步的近似值與前一步的近似值xk 適當(dāng)加權(quán)平均作為新的改進(jìn)值適當(dāng)加權(quán)平均作為新的改進(jìn)值,)1 (11kkkxxx其中其中(0 1 )稱為下山因子稱為下山因子, (4 .11) 即為即為(4 .11), 1 , 0,)()(1kxfxfxxkkkk(4 .12)稱為牛頓下山法稱為牛頓下山法. 選擇下山因子時(shí)從選擇下山因子時(shí)從= 1 開始開始, 逐次將逐次將減半進(jìn)行試算減半進(jìn)行試算, 直直到能使下降條件到能使下降條件( 4. .10 ) 成立為止成立為止.若用此法解方程若用此法解方程(4. .8 ) , 當(dāng)當(dāng)x0 = 0. .6 時(shí)由時(shí)

40、由( 4. .9 ) 求得求得x1 = 17. .9 , 它不滿足條件它不滿足條件( 4. .10 ) , 通過(guò)通過(guò) 逐次取半進(jìn)行試算逐次取半進(jìn)行試算, 當(dāng)當(dāng) =1/32時(shí)可求得時(shí)可求得x1 = 1. .140625 .此時(shí)有此時(shí)有f ( x1 ) = - 0.656643 , 而而f ( x0 ) = - 1. .384 ,顯然顯然| f ( x1 ) | | f ( x0 ) | .一般情況只要能使條件( 4. 10 )成立, 則可得到從而使 xk 收斂. 由x1 計(jì)算x2 , x3 , 時(shí)= 1 , 均能使條件(4.10) 成立.計(jì)算結(jié)果如下: x2 = 1 .36181 , f ( x

41、2 ) = 0 .1866; x3 = 1 .32628 , f ( x3 ) = 0 .00667; x4 = 1 .32472 , f ( x4 ) = 0 .0000086 . x4 即為x* 的近似., 0)(limkkxf 7.4.47.4.4重根重根 /* multiple root */ 加速收斂法：加速收斂法：Q1: 若若 ，Newtons Method 是否仍收斂？是否仍收斂？0*)( xf設(shè)設(shè) x* 是是 f 的的 n 重根，則：重根，則：)(*)()(xqxxxfn 0*)( xq因?yàn)橐驗(yàn)?Newtons Method 事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代，事實(shí)上是一種特殊的不動(dòng)

42、點(diǎn)迭代，其中其中 ，則，則)()()(xfxfxxg 22*)(*)(*)(*)(1|*)(|xfxfxfxfxg111 nA1: 有局部收斂性，但重?cái)?shù)有局部收斂性，但重?cái)?shù) n 越高，收斂越慢。越高，收斂越慢。Q2: 如何加速重根的收斂？如何加速重根的收斂？A2: 將求將求 f 的重根轉(zhuǎn)化為求另一函數(shù)的單根。的重根轉(zhuǎn)化為求另一函數(shù)的單根。令，則令，則 f 的重根的重根 = = 的單根。的單根。)()()(xfxfx 則則 故x* 是( x) = 0 的單根.對(duì)它用牛頓法, 其迭代函數(shù)為,)()()()()()(*xgxxxmgxgxxx 從而可構(gòu)造迭代法(4 .14)它是二階收斂的.)()()

43、()()()()()(2xfxfxfxfxfxxxxx ), 1 , 0()()()()()(21 kxfxfxfxfxfxxkkkkkkk 例9 方程x4 - 4 x2 + 4 = 0 的根x* = 2是二重根, 用上述三種方法求根. 解 先求出三種方法的迭代公式: (1 ) 牛頓法kkkkxxxx4221 (2 ) 用( 4. 13 )式kkkkxxxx2221 (3 ) 用( 4. 14 )式2)2(221kkkkkxxxxx取初值x0 = 1 .5 , 計(jì)算結(jié)果如表7 -9 .表表7-9 三種方法數(shù)值結(jié)果三種方法數(shù)值結(jié)果 計(jì)算三步計(jì)算三步, 方法方法( 2) 及及( 3 ) 均達(dá)到均達(dá)

44、到10 位有效數(shù)字位有效數(shù)字, 而用而用牛頓法只有線性收斂牛頓法只有線性收斂, 要達(dá)到同樣精度需迭代要達(dá)到同樣精度需迭代30 次次. 7.5.1 7.5.1 弦弦截法截法 /* Secant Method */ ：Newtons Method 一步要計(jì)算一步要計(jì)算 f 和和 f ，相當(dāng)于，相當(dāng)于2個(gè)函數(shù)值，個(gè)函數(shù)值，比較費(fèi)時(shí)?，F(xiàn)用比較費(fèi)時(shí)。現(xiàn)用 f 的值近似的值近似 f ，可少算一個(gè)函數(shù)值。，可少算一個(gè)函數(shù)值。x0 x1切線切線 /* tangent line */割線割線 /* secant line */切線斜率切線斜率 割線斜率割線斜率11)()()( kkkkkxxxfxfxf)()(

45、)(111 kkkkkkkxfxfxxxfxx需要需要2個(gè)初值個(gè)初值 x0 和和 x1。收斂比收斂比Newtons Method 慢，且對(duì)初值要求同樣高。慢，且對(duì)初值要求同樣高。7. 5 弦截法與拋物線法弦截法與拋物線法(5.2 ) 弦截法與切線法弦截法與切線法(牛頓法牛頓法)都是線性化方法都是線性化方法, 但兩者有本質(zhì)的區(qū)但兩者有本質(zhì)的區(qū)別別.切線法在計(jì)算切線法在計(jì)算xk+1 時(shí)只用到前一步的值時(shí)只用到前一步的值xk , 而弦截法而弦截法(5.2 ) , 在求在求xk+1 時(shí)要用到前面兩步的結(jié)果時(shí)要用到前面兩步的結(jié)果xk , xk-1 , 因此使用這種方因此使用這種方法必須先給出兩個(gè)開始值法

46、必須先給出兩個(gè)開始值x0 , x1 . 例10 用弦截法解方程 f ( x) = xex - 1 = 0 . 解 設(shè)取設(shè)取x0 = 0 .5 , x1 =0. .6 作為開作為開始值始值, 用弦截法求得的結(jié)果見表用弦截法求得的結(jié)果見表7 - -10 , 比較例比較例7 牛頓法的計(jì)算結(jié)果可牛頓法的計(jì)算結(jié)果可以看出以看出, 弦截法的收斂速度也是相弦截法的收斂速度也是相當(dāng)快的當(dāng)快的.表7-10 計(jì)算結(jié)果function k,piancha,xdpiancha,xk,yk=gexian (x01,x02,tol,ftol,gxmax)x(1)=x01;x(2)=x02;for i=2: gxmax u

47、(i)= fnq(x(i)*(x(i)-x(i-1); v(i)= fnq(x(i)-fnq(x(i-1); x(i+1)=x(i)- u(i)/( v(i); piancha=abs(x(i+1)-x(i); xdpiancha= piancha/( abs(x(i+1)+eps); i=i+1; xk= x(i);yk=fnq(x(i); (i-2) piancha xdpiancha xk yk if (abs(yk)ftol)&( piancha tol)|(xdpianchagxmaxdisp(請(qǐng)注意：迭代次數(shù)超過(guò)給定的最大值gxmax.)k=i-2; xk=x(i);yk=fnq(

48、x(i); return;endfunction f=fnq(x)f=x*exp(x)-1k,piancha,xdpiancha,xk,yk=gexian (0.5,0.6,0.001,0.001,100) 7.5.27.5.2拋物線法拋物線法： 設(shè)已知方程f ( x) = 0 的三個(gè)近似根xk , xk-1 , xk-2 , 我們以這三點(diǎn)為節(jié)點(diǎn)構(gòu)造二次插值多項(xiàng)式p2 ( x) , 并適當(dāng)選取p2 ( x ) 的一個(gè)零點(diǎn)xk+1 作為新的近似根, 這樣確定的迭代過(guò)程稱拋物線法,亦稱密勒(Mller )法.在幾何圖形上, 這種方法的基本思想是用拋物線y = p2 ( x ) 與x 軸的交點(diǎn)xk+

49、1 作為所求根x * 的近似位置(圖7 -7 ) .圖 7-7 現(xiàn)在推導(dǎo)拋物線法的計(jì)算公式.插值多項(xiàng)式p2 ( x ) = f ( xk ) + f xk ,xk-1 ( x - xk )+ f xk , xk-1 , xk-2 ( x - xk ) ( x - xk-1 ) . 有兩個(gè)零點(diǎn):,)(4)(22121kkkkkkkxxxfxfxfxx= f xk , xk-1 + f xk , xk-1 , xk-2 ( xk - xk-1 ). 為了從為了從( 5. .3 ) 式定出一個(gè)值式定出一個(gè)值xk+1 , 我們需要討論根式前我們需要討論根式前正負(fù)號(hào)的取舍問(wèn)題正負(fù)號(hào)的取舍問(wèn)題. 在在xk

50、 , xk-1 , xk-2 三個(gè)近似根中三個(gè)近似根中, 自然假定自然假定xk 更接近所求的根更接近所求的根x * * , 這時(shí)這時(shí), 為了保證精度為了保證精度, 我們選式我們選式( 5. .3)中較接近中較接近xk 的一個(gè)值作為的一個(gè)值作為新的近似根新的近似根xk+1 .為此為此, 只要取根式前的符號(hào)與只要取根式前的符號(hào)與的符號(hào)相同的符號(hào)相同. 例例11 用拋物線法求解方程用拋物線法求解方程f ( x ) = xex - 1 = 0 . 解解 設(shè)用表設(shè)用表7 -10 的前三個(gè)值的前三個(gè)值x0 = 0 .5 , x1 = 0 .6 , x2 = 0 .56532 作為開始值作為開始值, 計(jì)算得

51、計(jì)算得 f ( x0 ) = - 0 .175639 , f ( x1 ) = - 0. .093271 , f ( x2 ) = - 0. . 005031 , f x1 , x0 = 2 .68910 , f x2 , x1 = 2 .83373 , f x2 , x1 , x0 = 2 .21418 .故= f x2 , x1 + f x2 , x1 , x0 ( x2 - x1 ) = 2 .75694 .代入(5. 3 )式求得 以上計(jì)算表明, 拋物線法比弦截法收斂得更快.56714. 0,)(4)(201222223xxxfxfxfxxfunction k,piancha,xdpi

52、ancha,xk,yk=paowu(x1,x2, x3,tol,ftol,gxmax)X=x1, x2, x3;for i=1: gxmaxh0= X(1)- X (3); h1= X (2)- X (3); u0= fnq (X (1)- fnq (X (3) ); u1= fnq (X (2)- fnq (X (3); c= fnq (X (3);fenmu= h02* h1- h12* h0; afenzi= u0* h1- u1* h0;bfenzi= u1*h02-u0*h12; a= afenzi/ fenmu; b= bfenzi/ fenmu; deta=b2-4*a*c; c

53、ha=abs(X(3)-X(1),abs(X(3)-X(2),abs(X(2)- X(1);piancha =min(cha); xdpiancha= piancha/( abs (X(3)+eps);if deta0disp(提示：根的判別式值為負(fù)數(shù).),detakf=sqrt(deta);elseif deta=0disp(提示：根的判別式值為零.),detakf=0;elsedisp(提示：根的判別式值為正數(shù).),detakf=sqrt(deta);endif b0 detakf=- detakf;endz=-2*c/(b+ detakf);xk= X(3)+ z;q1= xk - X

54、(1); q2= xk - X (2); q3= xk - X (3);if abs(q2) abs(q1)X1=X(2), X(1), X(3); X= X1;Y= fnq(X);endif abs(q3) abs(q1)X2=X(1), X(3), X(2); X= X2;Y= fnq(X);endX(3)= xk; Y(3)=fnq(X(3);yk= Y(3); i piancha xdpiancha xk yk if (abs(yk)ftol)&( piancha tol)|(xdpianchagxmax disp(請(qǐng)注意：迭代次數(shù)超過(guò)給定的最大值gxmax,請(qǐng)重新輸入初始值x1,x2

55、,x3) return;endP=i,piancha,xdpiancha,xk,yk;function f=fnq(x)f=x.*exp(x)-1然后在然后在MATLAB工作窗口輸入程序工作窗口輸入程序 k,piancha,xdpiancha,xk,yk= paowu (0.5,0.6, 0.56532,1e-4, 1e-4,100)7.6 非線性方程組的數(shù)值解法非線性方程組的數(shù)值解法 7.6.1 非線性方程組非線性方程組考慮方程組考慮方程組, 0),(, 0),(, 0),(21212211nnnnxxxfxxxfxxxf（7.1） 其中其中f1 , , f n 均為均為( x1 , , x

56、n )的多元函數(shù)的多元函數(shù). 若用向若用向量記號(hào)記量記號(hào)記x=( x1 , , xn )T Rn , F= ( f1 , , f n ) T , (7. .1 )就可寫成就可寫成F( x) = 0 . ( 7 .2)當(dāng)當(dāng)n2 , 且且fi ( i = 1 , , n)中至少有一個(gè)是自變量中至少有一個(gè)是自變量xi ( i = 1 , , n)的非線性函數(shù)時(shí)的非線性函數(shù)時(shí), 則稱方程組則稱方程組( 7. .1 )為為非線性方程組非線性方程組. 非線性方程組非線性方程組(7.1)(7.1)求根問(wèn)題是前面介紹的方程求根問(wèn)題是前面介紹的方程(即即n = 1 ) 求根的直接推廣求根的直接推廣, 實(shí)際上只要

57、把前面介紹的單變量函數(shù)實(shí)際上只要把前面介紹的單變量函數(shù)f ( x )看成向量函數(shù)看成向量函數(shù)F( x) 則可將單變量方程求根方法推廣到方程則可將單變量方程求根方法推廣到方程組組(7.2 ) .為此設(shè)向量函數(shù)為此設(shè)向量函數(shù)F(x)定義在區(qū)域定義在區(qū)域,0DxRDn若若),()(0lim0 xFxFxx則稱則稱F(x)在在x0連續(xù)，即對(duì)任意實(shí)數(shù)連續(xù)，即對(duì)任意實(shí)數(shù), 0使得對(duì)滿足使得對(duì)滿足0|x-x0|的的xD,有有|F(x)-F(x0)|.如果如果F(x)在在D上每點(diǎn)都連續(xù)，則稱上每點(diǎn)都連續(xù)，則稱F(x)在域在域D上連續(xù)上連續(xù)。向量函數(shù)向量函數(shù)F(x)的導(dǎo)數(shù)的導(dǎo)數(shù)F(x)稱為稱為F的雅可比矩陣，它

58、表示為的雅可比矩陣，它表示為 1212221212111)()()()()()()()()()(xxfxxfxxfxxfxxfxxfxxfxxfxxfxFnnnnn（7.3）7.6.2 多變量方程的不動(dòng)點(diǎn)迭代法多變量方程的不動(dòng)點(diǎn)迭代法為了求解方程組(7.2),可將它改寫為x=(x),(7.4) 如果x* D，滿足x* =(x* ),稱x* 為函數(shù)的不動(dòng)點(diǎn)，也就是方程組(7.2)的一個(gè)解。根據(jù)(7.4)構(gòu)造的迭代法xk+1 =(xk ),k=0,1,(7.5)稱為不動(dòng)點(diǎn)迭代法， 為迭代函數(shù)。類似于n=1時(shí)的單個(gè)方程有下面的定理。(1)存在閉集假設(shè)：?DD 0及實(shí)數(shù)L(0,1)，使;,|,|)(0)(|0DyxyxLyx ?則在D0有唯一不動(dòng)點(diǎn)x* ，且對(duì)任意x0 D0, 由迭代法（7.5）生成的序列x(k)收斂到x* ，并有誤差估計(jì). |1|)0()1()(*xxLLxxkk(7.6)(7.7)定理定理7 函數(shù)定義在區(qū)域,nRD (2)對(duì)任意xD0,有(x) D0, 定理定理8 設(shè)在定義域內(nèi)有不動(dòng)點(diǎn)x* ， 的分量函數(shù)有連續(xù)偏導(dǎo)數(shù)且 (x* )1, (7.8) 則存在x* 的一個(gè)鄰域S，對(duì)任意x0