非線性方程組迭代法

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

2、數，則方程f(x)=0是一個非線性方程。若f(x)=0是一個方程組，且其中至少存在一個方程是非線性的，則稱方程組是非線性方程組。本章介紹一些常用的求解非線性方程和非線性方程組近似根的迭代方法。5.1根的搜索根的存在性：設函數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，其長度為b-a=匕對有根區(qū)間a,b施1111211行同樣的手續(xù)，并反復二分下去，得到一系列有根區(qū)間a,boa,boa,boL二a,boL1122kk其中a,b的長度

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

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

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

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

7、像原理可得迭代序歹列x=9(x)收斂于不動點x*；k+1k由于xxk+1k9(x)-9(xkk-1Llx-xkk-1(5.2.6)據此反復遞推得：x-xLkx-xk+1k10。從而對任意正整數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進一步，對任意正整數p又有(5.2.7)101L1上式中令pTa，注意到limxpgk+p由此可見，只要相鄰兩次計算結果的偏差足夠小，即可保證近似值xkXXk+1k具有足夠的精度，因此可以通過檢查XX|來判斷迭代過程應否終止k+1kI實際應用迭代法時，通常在所求根*的鄰近進行考察，研究所謂局部收斂性定義5.2.1若存在x*的某個鄰域R:x-x*8,使迭代過程=申(x)對于TOC o 1-5 h zk+1k任意初值xeR均收斂，則

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

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

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

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

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

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

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

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

17、(5.3.4)成立.下山因子的選擇是個逐步探索的過程533簡化牛頓法、弦截法與拋物線法牛頓法在求x時不但要求給出函數值f(x),而且要提供導數值廣(x)當k+1kk函數f比較復雜時,提供它的導數值往往是有困難的下面介紹一些避免求導數的方法。簡化牛頓法：這種方法的基本思想是利用一個固定常數M豐0代替迭代過程中每點的導數值,公式為x=x-),通常取M=ff(x)。TOC o 1-5 h zk+1kM0弦截法設x,x是f(x)=0的近似根，利用f(x),f(x)構造一次插值多項式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 這樣導出的迭代公式(5.3.6)可以看作牛頓公式x=x-一中的導數f(x)k+1kff(x)kk用差商f5)-f5-11取代的結果.x-xkk-1弦截法與切線法(牛頓法)都是線性化方法，但二者有本質的區(qū)別切線法在計算x時只用到前一步的值x，而弦截法在求x時要用到前面兩步的

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

20、求根x*的近似位置.2k+1第5章非線性方程（組）迭代法Renchun-li,XidianUniversityPage of3111/15/20187:13:31AM5.4非線性方程組的迭代法5.4.1一般迭代法及其收斂條件般地，一元非線性方程的迭代解法都可以推廣到多元非線性方程組。設有非線性方程組212n(5.4.1)n1,x,L,x2n)=0將方程組變形為等價形式：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)計算，可得一向量序列（k）在一定條件下向量序列收斂到原方程組的解。設D為含有根x*=C*,x*,L,x)的閉域，一般情況下，D是以根x*為中心的12n超長方體：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則有下述三個使迭代法收斂的充分條件(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因為a=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)稱為向量值函數，其中f(x)=f(x,x,x)。ii12n設x(k)=Ck),x(k),L,x(k)是方程組(541)的一組近似解，把它的左端在x(k)處12n用多元函數的泰勒展式展開，然后取線性部分，便得方程組(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如果它的系數矩陣這是關于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淋為向量函數F(兀)的Jacobi矩陣，記作Fr