非線性方程組迭代法

1、Renchun-li,XidianUniversityPage of3111/15/20187:13:31AM第5章非線性方程（組）迭代法第5章非線性方程（組）迭代法內(nèi)容根的搜索迭代法的構(gòu)造及收斂性方程求根的牛頓迭代法*非線性方程組的迭代法第5章非線性方程(組)迭代法Renchun-li,XidianUniversityPage of3111/15/20187:13:31AM數(shù)學(xué)物理中許多問(wèn)題常歸結(jié)為求解非線性方程或非線性方程組.例如在最優(yōu)化問(wèn)題minF(x)中，設(shè)函數(shù)F(x)在區(qū)間I上嚴(yán)格凸并可微，且xelFx)=f(x)，則求其極小點(diǎn)等價(jià)于求解方程f(x)=0的根；若f(x)是一個(gè)非線性函

2、數(shù)，則方程f(x)=0是一個(gè)非線性方程。若f(x)=0是一個(gè)方程組，且其中至少存在一個(gè)方程是非線性的，則稱方程組是非線性方程組。本章介紹一些常用的求解非線性方程和非線性方程組近似根的迭代方法。5.1根的搜索根的存在性：設(shè)函數(shù)f(x)eCa,b，且f(a)f(b)0，記a=x,b=b，方程的根x*g(a,b)；010111Y如果f(x)-f(a)0，記a=a,b=x，方程的根x*g(a,b)。.011011因此，新的有根區(qū)間為a,b，其長(zhǎng)度為b-a=匕對(duì)有根區(qū)間a,b施1111211行同樣的手續(xù)，并反復(fù)二分下去，得到一系列有根區(qū)間a,boa,boa,boL二a,boL1122kk其中a,b的長(zhǎng)度

3、為：b-a=匕aT0(當(dāng)kTa時(shí))。kkkk2k上述結(jié)果表明，如果二分過(guò)程無(wú)限地繼續(xù)下去，這些區(qū)間最終必將收縮于f(x)=0的根x*只要二分足夠多次(即k充分大)，就能保證有b一ax*xbakkkW時(shí),In2滿足精度為的要求。k5.2非線性方程的迭代法5.2.1建立迭代公式基本思想：將一元方程f(x)=0等價(jià)變形為如下不動(dòng)點(diǎn)方程x=9(x).(5.2.1)選取一個(gè)初始近似解X，構(gòu)造不動(dòng)點(diǎn)迭代公式0 x=9(x),k=0,1,2,Lk+1k求得迭代序列x。如果x收斂，則極限點(diǎn)是9(x)的不動(dòng)點(diǎn)X*(即滿足kkx*=9(x*)，也是f(x)=0的根.幾何意義如圖例5.2.1用迭代法求方程x3-x-

4、1=0在區(qū)間11,2的實(shí)數(shù)根，誤差不超過(guò)io-5。解根的存在唯一性：設(shè)f(x)=x3-x-1，貝f(-1)-f=(-1)-50,xe(1,2),所以方程x3-x-1=0在區(qū)間(1,2)內(nèi)有唯一的實(shí)數(shù)根x*(2)構(gòu)造迭代公式：將方程等價(jià)變形為：x=3廳TT，則迭代公式x=3!x+1(k=0,1,L2).k+1k(3)取迭代初始值x=1.5，迭代結(jié)果見(jiàn)表。若取6位有效數(shù)字，貝吐與x完全078相同，這時(shí)可近似認(rèn)為迭代序列已經(jīng)收斂到了極限點(diǎn)，并將x作為方程的近似解.8表5.2.1kxkkxk01.551.3247611.3572161.3247321.3308671.3247231.3258881.3

5、247241.32494但若對(duì)方程做另一種等價(jià)變形：x=x3-】，并建立迭代公式k+i=Xk3-1初值仍取x=1.5，則有x=2.375,x=12.39,L.012顯然，繼續(xù)迭代下去不收斂，稱迭代公式?jīng)_二疔+T是發(fā)散的.5.2.2迭代的收斂性：考察一般情形下迭代過(guò)程x=,(x)收斂的條件k+1k分析：設(shè)方程x=9(x)在區(qū)間a,b內(nèi)有根x*,由微分中值定理xk+1-X*=9(x)-9(x*)kk其中g(shù)是x*與x之間某一點(diǎn)，只要xea,b,則匕ea,b。kk若存在常數(shù)L,且0L1，則使得Vxea,b都有9(x)L.=9(x)-9(x*)Lx-x(5.2.2)x-x*k+1反復(fù)遞推有x-xLx-*

6、x從而limx=x*。k0k注意，上述分析實(shí)際上要求p(x)是a,b上的壓縮映像。定理5.2.1若函數(shù)9(x)eDa,b，且滿足：(5.2.3)(5.2.4)Vxea,b有，a9(x)b存在正數(shù)L1，對(duì)Vxea,b，有|p(x)L1則有方程X=9(x)在a,b有唯一不動(dòng)點(diǎn)x*；迭代過(guò)程x=9(x)對(duì)于任意初值xea,b均收斂于x*；k+1k0誤差估計(jì)式x-x*Lx-xk1-L10或x-x*Lx-xk1Lkk-1(5.2.5)證明：設(shè)g(x)=x-9(x)，由零點(diǎn)定理以及函數(shù)的單調(diào)性，可知=9(x)在a,b有唯一不動(dòng)點(diǎn)x*；由于9(x)9(y)9纟)|卩yLfy(0L1)，9是壓縮映射，由壓縮映

7、像原理可得迭代序歹列x=9(x)收斂于不動(dòng)點(diǎn)x*；k+1k由于xxk+1k9(x)-9(xkk-1Llx-xkk-1(5.2.6)據(jù)此反復(fù)遞推得：x-xLkx-xk+1k10。從而對(duì)任意正整數(shù)p，有第5章非線性方程(組)迭代法Renchun-li,XidianUniversityPage of3111/15/20187:13:31AMRenchun-li,XidianUniversityPage of3111/15/20187:13:31AM第5章非線性方程（組）迭代法X一XX一X+k+pk/k+pk+p1X一Xk+p-1弋+p2Lk+pi+Lk+p-2+L+Lk)X-X+L+X一Xk+1kX

8、一X0=X*即得式(5.2.5).XXClp-i+Lp-2+L+1)x-xk+pkk+ik1XX.1一Lk+1kTa矢口：X*X1|X一X.k1L1k+1k在上式中令p進(jìn)一步，對(duì)任意正整數(shù)p又有(5.2.7)101L1上式中令pTa，注意到limxpgk+p由此可見(jiàn)，只要相鄰兩次計(jì)算結(jié)果的偏差足夠小，即可保證近似值xkXXk+1k具有足夠的精度，因此可以通過(guò)檢查XX|來(lái)判斷迭代過(guò)程應(yīng)否終止k+1kI實(shí)際應(yīng)用迭代法時(shí)，通常在所求根*的鄰近進(jìn)行考察，研究所謂局部收斂性定義5.2.1若存在x*的某個(gè)鄰域R:x-x*8,使迭代過(guò)程=申(x)對(duì)于TOC o 1-5 h zk+1k任意初值xeR均收斂，則

9、稱迭代過(guò)程x=cp(x)在根x*鄰近具有局部收斂性.0k+1k定理5.2.2(迭代過(guò)程局部收斂的一個(gè)充分條件)設(shè)x*為方程x=(x)的根，/(x)在x*的鄰近連續(xù)且/C*)1，則迭代過(guò)程x=(x)在x*鄰近具有局部收斂性.k+1k例5.2.2求方程f(x)=x-e-x=0在0,1內(nèi)的根，要求精度=10-5.解因?yàn)閒(0)0,且廣(x)=1+e-x0，所以方程在(0,1)內(nèi)僅有一個(gè)根。用二分法進(jìn)行簡(jiǎn)單的搜索，將求根區(qū)間縮小為(0.5,0.6)。建立不動(dòng)點(diǎn)方程x=e-x，構(gòu)造迭代公式x=e-xk(k=0,12,L)。k+1選初始點(diǎn)x=0.5,顯然在根的鄰近，C-x)沁0.61時(shí)稱為超線性收斂，p=

10、2時(shí)稱為平方收斂顯然，p越大，收斂越快。k+1k定理5.2.3（迭代過(guò)程p階收斂的充分條件）對(duì)于迭代過(guò)程x=（x），如果cp（p）（x）在所求根x*的鄰近連續(xù)，并且C*）=）=L=（p-i）（x*）=0；且申（p）C*）h0則該迭代過(guò)程在點(diǎn)x*鄰近是p階收斂的.第5章非線性方程(組)迭代法Renchun-li,XidianUniversityPage of3111/15/20187:13:31AM5.2.3迭代公式的加速設(shè)x是根x*的某個(gè)預(yù)測(cè)值，用迭代公式計(jì)算一次得0 x=申(x)，10由微分中值定理有：x*-x=fC*)-申(x)=0(g)C*-x),100其中g(shù)介于x*與x之間假設(shè)cp(x

11、)改變不大，近似地取某個(gè)近似值,由(5.2.8)0()x*xuLx*x丿，101L可得x*uIx_x。再將上式代入(5.2.8)的右端，得到1L11L0 x*xU厶(xx)11L10類似于(527)，此式可看作是用近似x*的后驗(yàn)誤差估計(jì)。利用此誤差對(duì)x11進(jìn)行校正，將校正值記作x,2)=01Lx一x1L1一L(5.2.9)更一般地，將每次利用迭代公式計(jì)算的值利用后驗(yàn)誤差進(jìn)行一次校正,則有下述加速迭代方案：廠迭代：x=申(x)k+1k校正：x=x+厶(xx)(5.2.10)k+1k+11Lk+1k例5.2.3利用上面加速迭代方案求解方程x=e-x(oxe-x=0).解選初始點(diǎn)x=0.5,在根的鄰

12、近,C-x)-0.6=L，對(duì)應(yīng)加速迭代系統(tǒng)如下:0 xk+1xk+1=exk,0.6=xxxk+11.6+k1).k迭代結(jié)果見(jiàn)下表：表5.2.3kxkxk00.510.606530.5665820.567460.5671330.567150.56714與例5.2.2相比，這里只要迭代3次即可得到相同精度的結(jié)果，加速的效果是相當(dāng)顯著的但上述加速方案需要知道關(guān)于迭代函數(shù)(x)導(dǎo)數(shù)的信息L,而在實(shí)際中往往難以得到這一信息，造成實(shí)際使用不便，因此需要消除進(jìn)而可以構(gòu)造出不需要求出L的校正一改進(jìn)系統(tǒng)如：埃特金(Aitken)方法。該方法除了能夠加快收斂速度,有時(shí)還能將不收斂的迭代公式改進(jìn)為收斂的公式.5.

13、3方程求根的牛頓法5.3.1牛頓迭代公式及其收斂性設(shè)非線性函數(shù)f(x)的一個(gè)近似零點(diǎn)x，用f(x)在該點(diǎn)的Taylor展開(kāi)式的線性0部分來(lái)近似f(x)，即f(x)沁f(x)+廣(x)(x-x)000故f(x)=0近似等價(jià)于f(x)+f(x)(x-x)=0，解出x，并記作為x，即00f(x)x=x-0_x10ff(x)0如此反復(fù)，得到求解非線性方程f(x)=0的迭代公式(5.3.1)f(x)x=xk(k=0,1,2L)k+ikfx)k稱為牛頓迭代公式。顯然，牛頓迭代公式要求在根*的某個(gè)鄰域內(nèi)ff(x)主0。牛頓迭代法的幾何意義：用f(x)在點(diǎn)x處的切線y=f(x)+f(x)(x-x)kkkk與x

14、做的交點(diǎn)，作為下一個(gè)迭代點(diǎn)x，因此牛頓法也稱為切線法。定理5.3.1(牛頓迭代公式的收斂性)假設(shè)x堤f(x)的單重根，f(x)在根的鄰域A:x-x*8內(nèi)具有二階連續(xù)導(dǎo)數(shù)，且對(duì)任意xeA有f(x)H0，又初值xeA，則當(dāng)鄰域A充分小時(shí)，牛頓法5.3.1)具有2階收斂速度.0例5.3.1用牛頓法解方程xex-1=0解設(shè)f(x)=xex-1，其牛頓公式為x=x-._-訊。取迭代初值x=0.5，k+1k1+x0kRenchun-li,XidianUniversityPage of3111/15/20187:13:31AM第5章非線性方程（組）迭代法迭代結(jié)果迭代為x=0.57102,x=0.56716,

15、x=0.56714。123實(shí)際上，本例所給方程是例5.2.2中方程x=e-x的等價(jià)形式，與例5.2.2的計(jì)算結(jié)果相比可以看出，牛頓法的收斂速度是相當(dāng)快的5.3.2牛頓下山法牛頓法是局部收斂的其收斂性依賴于初值x的選取，如果x偏離所求的根00 x*較遠(yuǎn)，則牛頓法可能發(fā)散例如，用牛頓法求方程x3x1=0在x=1.5附近的根x*設(shè)取初值x=1.5，用牛頓公式0 x3x1x=xkkk+1k3x21k計(jì)算得：x=1.34783,x=1.32520,x=1.32472迭代3次得到的結(jié)果x有6位1233有效數(shù)字但是，如果改用x=0.6作為迭代初值，則用上面牛頓公式迭代一次0第5章非線性方程(組)迭代法Ren

16、chun-li,XidianUniversityPage of3111/15/20187:13:31AM得x=17.9，這個(gè)結(jié)果反而比x=0.6更偏離了所求的根x*=1.32472.10為了防止迭代發(fā)散，對(duì)迭代過(guò)程附加單調(diào)性要求:(5.3.4)f(x)vf(x)|k+1k滿足這項(xiàng)要求的算法稱為下山法.將牛頓法與下山法結(jié)合起來(lái)使用，即可在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度為此，將牛頓法的計(jì)算結(jié)果f(x)x=x-Lak+lkff(x)k與前一步的近似值x適當(dāng)加權(quán)平均作為新的改進(jìn)值k(5.3.5)x=九x+(1九)xk+1k+1k其中九(0X1)稱為下山因子，下山因子應(yīng)保證單調(diào)性

17、(5.3.4)成立.下山因子的選擇是個(gè)逐步探索的過(guò)程533簡(jiǎn)化牛頓法、弦截法與拋物線法牛頓法在求x時(shí)不但要求給出函數(shù)值f(x),而且要提供導(dǎo)數(shù)值廣(x)當(dāng)k+1kk函數(shù)f比較復(fù)雜時(shí),提供它的導(dǎo)數(shù)值往往是有困難的下面介紹一些避免求導(dǎo)數(shù)的方法。簡(jiǎn)化牛頓法：這種方法的基本思想是利用一個(gè)固定常數(shù)M豐0代替迭代過(guò)程中每點(diǎn)的導(dǎo)數(shù)值,公式為x=x-),通常取M=ff(x)。TOC o 1-5 h zk+1kM0弦截法設(shè)x,x是f(x)=0的近似根，利用f(x),f(x)構(gòu)造一次插值多項(xiàng)式kk-1kk-1p(x),并用p(x)=0的根作為f(x)=0新的近似根x由于11k+1p(x)=f(x)+f(xk)-f

18、(xk-1)(x-x), HYPERLINK l bookmark159 o Current Document 1kx-xkkk-1因此有xk+1f(x)xk-f(x)-f(x)kk-1(5.3.6)x-xTOC o 1-5 h zkk-1 HYPERLINK l bookmark163 o Current Document 這樣導(dǎo)出的迭代公式(5.3.6)可以看作牛頓公式x=x-一中的導(dǎo)數(shù)f(x)k+1kff(x)kk用差商f5)-f5-11取代的結(jié)果.x-xkk-1弦截法與切線法(牛頓法)都是線性化方法，但二者有本質(zhì)的區(qū)別切線法在計(jì)算x時(shí)只用到前一步的值x，而弦截法在求x時(shí)要用到前面兩步的

19、結(jié)果k+1kk+1x,x，因此使用這種方法必須先給出兩個(gè)開(kāi)始值,xkk-101例534用弦截法解方程f(x)解設(shè)取x=0.5,x=0.6作為開(kāi)始值，用弦截法求得的結(jié)果x=0.5632,012x=0.56709,x=0.56714。比較例5.3.1牛頓法的計(jì)算結(jié)果可以看出，弦截法的34收斂速度也是相當(dāng)快的拋物線法已知方程f(x)=0的三個(gè)近似根x,x,x,以這三點(diǎn)為節(jié)點(diǎn)構(gòu)造二次插值多kk-1k-2項(xiàng)式p(x),并適當(dāng)選取p(x)的一個(gè)零點(diǎn)x作為新的近似根，這樣確定的迭代22k+1過(guò)程稱拋物線法，亦稱密勒(Mfiller)法在幾何圖形上，這種方法的基本思想是用拋物線y=p(x)與x軸的交點(diǎn)x作為所

20、求根x*的近似位置.2k+1第5章非線性方程（組）迭代法Renchun-li,XidianUniversityPage of3111/15/20187:13:31AM5.4非線性方程組的迭代法5.4.1一般迭代法及其收斂條件般地，一元非線性方程的迭代解法都可以推廣到多元非線性方程組。設(shè)有非線性方程組212n(5.4.1)n1,x,L,x2n)=0將方程組變形為等價(jià)形式：x=申(x,x,L,x)1112n(5.4.2)x=9(x,x,L,x)2212nMx=9nn(x,x,L,x)第5章非線性方程(組)迭代法Renchun-li,XidianUniversityPage of3111/15/20

21、187:13:31AM由此建立迭代公式X（k+1）=申11Cx（k）,x（k）,L,x（k）X（k+1）=申V2212nw（k）,x（k）,L,x（k）12nk=0,1,2,L（5.4.3）X（k+1）=申3nMCx（k）,x（k）,L,x（k）12n選取一組初值x(o),x(o),L,x(o)后，按迭代公式(5.4.3)計(jì)算，可得一向量序列（k）在一定條件下向量序列收斂到原方程組的解。設(shè)D為含有根x*=C*,x*,L,x)的閉域，一般情況下，D是以根x*為中心的12n超長(zhǎng)方體：x-x*d（=1,2,L,n），或超球體:iiir。x=（x,x,L,x12n第5章非線性方程（組）迭代法Rench

22、un-li,XidianUniversityPage of3111/15/20187:13:31AMi,j=1,2,L,na=maxijxeDSXj則有下述三個(gè)使迭代法收斂的充分條件(1)a=max工a1；ijj=1=max1in1jni=1a1；(3)ij=工Ya21iji=1j=1例5.4.1求解非線性方程組呼%壽1-0，取初值（X（o）,x（o）=（1.2,1.7加。Ixx3x4=012122則解2二dx12dx21133x(x+4)2它們?cè)贑（0）,x（0）處的值為d申dx2(1.2,1.7)=0.3637122=-0.2935,1(1.2,1.7)dx2(1.2,1.7)=0.098

23、于是a=0,a=0.3637,1112因?yàn)閍=maxa+a,a+a11122122a=0.2935,a=0.0982122=max).3637,0.3915=).3915i所以迭代公式：字的近似解為x(i7)=(1.234275,1.661526)TRenchun-li,XidianUniversityPage of3111/15/20187:13:31AM第5章非線性方程(組)迭代法5.4.2牛頓迭代法將一元非線性方程的牛頓法推廣到高維情形，即得非線性方程組的牛頓迭代公式。令f(x)x0_F(x)=f(x)2,x=1x2,0=0MMMf(x)nxn0則方程組(5.4.1)可寫為向量形式(5.

24、4.4)F(兀)=0F(x)稱為向量值函數(shù)，其中f(x)=f(x,x,x)。ii12n設(shè)x(k)=Ck),x(k),L,x(k)是方程組(541)的一組近似解，把它的左端在x(k)處12n用多元函數(shù)的泰勒展式展開(kāi)，然后取線性部分，便得方程組(5.4.1)的近似方程組第5章非線性方程（組）迭代法Renchun-li,XidianUniversityPage of3/5/2087:3:3AM(、dfCx(k),x(k),L,x(k)TOC o 1-5 h zfx(k),x(k),L,x(k)+才i12Ax(k)=0(i=1,2,L)(545)i12nQxj冃j如果它的系數(shù)矩陣這是關(guān)于Ax(k)二x-x(k)(i二1,2,L,n)的線性方程組，iiF(x)二Vf(x)t1Vf(x)T2M曾axaxMLL乞ax2ax2M645.Vf(x)TnQfnQxnQfQfTQxQx12非奇異，則可解得Renchun-li,XidianUniversityPage of3111/15/20187:13:31AM第5章非線性方程(組)迭代法Ax(k)1Ax(k)2MAx(k)ndx1dx1Mdfndx1df1dx2df22dx2Mdfndx2df1dxndf2dxnMdfndxn-1(5.4.7)iii矩陣(546淋為向量函數(shù)F(兀)的Jacobi矩陣，記作Fr