1006014248高潔線性方程組的極小殘余算法

1、學(xué)校代碼10722分類號學(xué)號1006014248密級公開咸陽師范學(xué)院本科畢業(yè)論文線性方程組的廣義極小殘余算法（中、英文）TheGeneralizedMinimalResidualAlgorithminsystemoflinearequations作者姓名高潔數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)名稱學(xué)科門類指導(dǎo)教師提交論文日期成績評定理學(xué)馬欣榮2014年4月線性方程組的廣義極小殘余算法（即GMRES算法）高潔（咸陽師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院陜西咸陽712000）摘要伴隨科學(xué)技術(shù)的進(jìn)步與快速發(fā)展，大規(guī)模稀疏線性方程組的求解成為很多問題的解決方法之一，然而一種求解大型非對稱線性方程組有效的迭代方法之一就是廣義極小殘余

2、算法。本文章就是通過對線性方程組的學(xué)習(xí)及相應(yīng)矩陣?yán)碚撝R的了解，探究Krylov子空間上廣義極小殘余算法的基本理論。首先，介紹線性方程的一些基本概念，定理和問題；下來為研究做一些準(zhǔn)備工作，了解投影法的基本思想和Krylov子空間；文章的最后給出了在Galerkin原理之下的廣義極小殘余算法和在其他方面的一些應(yīng)用。關(guān)鍵詞：線性方程組；廣義極小殘余算法；Krylov子空間法；投影法；正交；矩陣。TheGeneralizedMinimalResidualAlgorithmInSystemOfLinearEquations(asGMRESalgorithm)GaoJie(SchoolofMathema

3、ticsandInformationScience,XianYangNormalUniversity,ShanXiXianYang712000)AbstractWiththerapiddevelopmentofscienceandtechnology,moreandmoreproblemstosolvinglarge-scalesparselinearequations,however,generalizedminimalresidualalgorithmisakindofnonsymmetriclinearequationiterativemethod.Inthispaper,through

4、studyoflinearequationsandthecorrespondingmatrixtheoryknowledgeunderstanding,studyKrylovsubspaceonthebasictheoryofgeneralizedminimalresidualalgorithm.Firstofall,introducessomebasicconceptsoflinearequations,theoremsandproblems;Downanddosomepreparationworkforstudy,understandthebasicideasandKrylovsubspa

5、ceprojection;FinallyundertheGalerkinprincipleofgeneralizedminimalresidualalgorithmanditsapplicationinotheraspects.KeyWords:linearequations;GMRESalgorithm;Krylovsubspacemethods;projectionmethod;Orthogonality;matrix.摘要IAbstractn目錄田1引言12線性方程組12.1 線性方程組的定義12.2 線性方程組的三種表示形式12.3 線性方程組的求解問題23基本理論31.1 投影方法的

6、基本思想31.2 Krylov子空間的簡介54 GMRES算法的理論64.1 Galerkin原理64.2 Arnoldi算法74.3 GMRES算法105 GMRES(m)算法在其他方面的應(yīng)用145.1 在離散不適定問題中的應(yīng)用145.2 求解三維第一類Fredholm積分方程15總結(jié)17參考文獻(xiàn)18謝辭191引言數(shù)學(xué)研究的主要對象之一是線性方程的研究，它有著嚴(yán)謹(jǐn)?shù)睦碚?，和獨特的解決問題的方法，也可以應(yīng)用于各個領(lǐng)域的多種實際問題的處理，并且在這快速發(fā)展信息的社會中，尤其是工程計算技術(shù)和科學(xué)水平的發(fā)展，有著越來越多的復(fù)雜的大型的問題，在需要解決的這些諸多問題的同時更重要的是需要求解一些大規(guī)模離

7、散不適定的線性方程組，并且例如有：有限差分，有限元素值的求解，數(shù)理方程的反問題等等，快速高效的求解這幾類方程成為數(shù)學(xué)研究之中矩陣與數(shù)值代數(shù)研究的主要熱點之一。在1986年，由M.H.Schltz和Y.Saad兩位著名數(shù)學(xué)家提出的關(guān)于基于Galerkin原理的GMRES(m)算法，并且此算法是一種求解非對稱線性適定方程組的Krylov子空間投影法，而且是采用正交投影或斜投影之一在子空間上產(chǎn)生迭代向量進(jìn)行的計算。因為廣義極小殘余算法是關(guān)于基于Krylov向量的完全化正交化，所以在于對應(yīng)的Krylov子空間有且只能求出一個近似解或著擬最小殘值。在且加上以該算法計算的所需要的內(nèi)存量和計算量較少等優(yōu)勢，

8、所以在社會上目前廣泛應(yīng)用于各種工程應(yīng)用領(lǐng)域的各種問題。本文章在矩陣論與數(shù)值代數(shù)的基礎(chǔ)上主要研究線性方程組的一個迭代方法，即廣義極小殘余算法的理論與應(yīng)用。2線性方程組2.1 線性方程組的定義2.1.1 線性方程組指各個方程關(guān)于未知量均為一次的方程組。2.1.2 齊次線性方程組指對于一般線性方程組來說，常數(shù)項均為零。2.1.3 非齊次線性方程組指對于一般線性方程組來說，常數(shù)項不全為零。2.2 線性方程組的三種表示形式2.2.1 一般形式的表示一般線性方程組是指形如即為312X2ainXn'b32lXl+322X2+32nXn=b?(2.1)I3m1X1am2X23mnXn=bm的方程組，其

9、中Xi,X2,，是指n個未知量，m是指該方程組所包含的方程的個數(shù),aj(i=1,2,，m;j=1,2,，n)是方程組的系數(shù)，bj(j=1,2,，m)是常數(shù)項。并且由(2.1)式可以看出，一個線性方程組的確定是完全由方程組的系數(shù)和常數(shù)項所確定，且在下方程組的常數(shù)項寫在方程等式的右邊。2.2.2 向量形式的表示可以表示為：X1al1II比1.其中1-|：尸2j3m1_2.2.3矩陣形式的表示可以表示為：其中A=(1,2,:于此特別的，如果方程組中1X22Xn3123n1IIII322.an,n：,i3m2_j3mn_AX=b(),X=(X1,X2,Xrb=0,則可以把AX=bn=b(2.2)b1b

10、b2屋I-bm.(2.3)T卡作為齊次線性方程組，而如果方程組中b¥o,則可以把AX=b稱作非齊次線性方程組。2.3 線性方程組的求解問題2.3.1 一般方程組一般的小型的線性方程組可以利用解的性質(zhì)與Cr3mer法則求解，解決一些相關(guān)問題。2.3.2 特殊系數(shù)方程組對于方程AX=b的系數(shù)矩陣具有某些特殊的性質(zhì)，例如：系數(shù)矩陣A對稱正定；1D1H有性質(zhì)即存在交換矩陣P,使得PAP=rD1其中D和D2為兩個對稱矩陣；H矩陣，則可以根據(jù)這些加在系數(shù)矩陣A上的條件，采用SOR和SSOR迭代，最速下降法等方法求解。2.3.3大型一般條件方程組對于求解大型線性方程組且方程的系數(shù)矩陣不在具有某些特

11、殊性質(zhì)，即力圖在最一般的條件下，討論AX=b的求解問題，這就是本文章主要研究的線性方程組的求解問題，我們只假定方程中的系數(shù)矩陣是一個非奇異矩陣。3基本理論3.1投影方法的基本思想假設(shè)需要求解如（2.3）式方程組，其中的系數(shù)矩陣A是大型非對稱矩陣，并且還是非奇異的矩陣。假定A和b都是實矩陣，且令Vm=v1,v2，vml是n維空間中一組m個線性無關(guān)的向量，Km=span（Vi,V2,，Vm）是Vi,V2,，Vm所張成的子空間。則其的基本思想就是找一個（2.3）式的近似解X（m）且使得：X（m）-Km（AX（m）-b）-LVjj-1,2,ml.（3.1.1）令X（m）=Vm#m）,其Y（m）是一個m

12、維向量，則（3.1.1）式可以改寫為VnTAVmY（m）=VnTb（3.1.2）假設(shè)（3.1.2）有唯一解，則可通過求解一個m個未知數(shù)的方程，得到Y(jié)（m）,從而得到X的一個近似解X(m)。例1.11-1101A=110,V2=01,b=2231一-00一-31根據(jù)以上可直接計算得到對應(yīng)的（3.1.2）式為I 11II i22（3.1.3）可以得到，轉(zhuǎn)化為（3.1.3）式的方程組無解。所以為了避免出現(xiàn)這一算法上的困難，不得不假設(shè)所取Vm使得（3.1.2）式有唯一解c例2.如何選Vm,使得算法在計算機上可非常有效的實現(xiàn)？答：令Um表示在子空間Km上的正交投影算子，且假設(shè)bWKm,將可以在下面的推論

13、中看出，所假設(shè)的不難實現(xiàn)。用正交投影算子的符號，方程（3.1.1）可改寫為XfKm1（m）（3.1.4）二m（AX（m）-b）=0為方便理論分析，再引入算子兒,其代表口mA并限制在定義域只在Km之上，這樣找近似解X（m）就變?yōu)榍蠼釧mX-b0（3.1.5）的問題，其中因為假設(shè)bWKm,所以可得nbb=b。由以上可得到的近似解與（2.3）式的精確解（X"）之間存在著誤差值，具體有多大的誤差？我們先看以下引理：引理1令路=gmA（I-0m）巴則方程（3.1.4）式滿足-b-Am-mX二工1-（-二m）X-（3.1.6）證明：b-AmX：=b-mA-mX"=b-mAX-C-mX=

14、-mA（'-m）X又因I-Rm是一個投影算子，所以-b-Am-mX-=-mA(-m)(-m)X-三rm二(-二m)X一引理證完。為推導(dǎo)誤差結(jié)果，所以在假設(shè)Am是可逆的，且<=gAm1g下，有如下定理：定理1gX”-X(m)-3+41g(I-口m)X*g成立。證明：因為Am是可逆的，且X(m)滿足(3.1.5)式，所以X(m)-mX-=Amb-Am-mX")又因X(m)wKm,所以nmX(m)=X(m)。則根據(jù)(3.1.6)式，有g(shù)rim(X*-X(m)gWKmm*1-小/%(3.1.7)又X*-X(m)=(i-nm)X*+nmX*-Xm)并且上式右端兩個向量彼此正交，于

15、是X-X(m)一2=-(-.-m)X-2-m(X"-X(m)-2在由(3.1.7)可以得到：gX*-X(m)g</十席g(I-口m)Xr(3.1.8)定理證完。但是根據(jù)(3.1.8)式，不能完全說明X(m)是某種意義下的近似解。3.2Krylov子空間的簡介對(2.3)式大型線性方程組，可取X0wRn為任意向量，且令X=X0+z,則(2.3)式可化為Az=ro(3.2.1)其r0=b-AX。對一個固定整數(shù)m>0,令左右空間分別為Lm=AKm,Km=Span(r0,Ar0,，A%(3.2.2)在子空間Km中找(3.2.1)的近似解Zm,并且使得(3.2.3)zm=VmYm&

16、#39;Kmrm=b-AXm=ro-Azm_LmVm=m,V2,，Vm是在學(xué)習(xí)了Arnoldi算法后利用Arnoldi過程（下面講到）的方法構(gòu)造出來的右空間Km的正交基矩陣。4GMRES算法的理論4.1Galerkin原理給定任意X。wRn,令X=X0+z,則方程組（2.3）等價于Az=0（4.1.1）其r。=b-AX。則需要求解的線性方程組（4.1.1）的Galerkin原理如下所述（在以下文章中規(guī)定所有的向量的范數(shù)為2,AWRnxn,bwRn）:設(shè)Rn中有兩個m維子空間0和Lm的基分別為V:和叫普，找方程組（4.1.1）的近似解Zm-Km,使得（ro-AZm）lLm,即（r。AZm）1Wi

17、（i=1,2,m）（4.1.2）構(gòu)造矩陣Vm=（V1,V2,，）和Wm=（W,W2,，Wm）,由Zm可得Zm=1V1-2V2''-mVm=VmYm其中ym=（2,Jm）TWRm。則（4.1.2）式可寫為WT（r。-AZm）=。即WT（。AVy=。（i=1,2，,m）或W；（。-AVY）=。TT也是（WmAVm）ym=Wmr。（4.1.3）如果WAVm可逆，則有T.1TYm=（W>Vm）r。從而有Zm=Vm(MAVm),Mr0(4.1.4)根據(jù)以上原理，可以建立求解方程組(2.3)的迭代格式。任給定Xwr1記X0=X(0),過程如下：對k=0,1,2，(1)r0=bAX0,

18、由方程組(4.1.3)解出Ym,計算V(k1)k(1X=XVmym(4.1.5)(2) X0=X(k相繼續(xù)(1)。對于以上所述，如果對于其中某個k出現(xiàn)W】AVm不可逆的情況，則稱此算法的計算發(fā)生中斷，所以在這種情況下一般需要更換X(0)進(jìn)行重新計算。4.2Arnoldi算法適當(dāng)?shù)倪x取m和X(0),使得r0,A不力畿性無關(guān)。一般選取Lm=Km=Sparfr。Ar0，Amr。,胺照下面Arnoldi過程構(gòu)造它的標(biāo)準(zhǔn)正交基vj,在這組正交基下，方程組(4.1.3)的系數(shù)矩陣和右端項有比較簡單的形狀。m1Arnoldi過程設(shè)r0,ArO,，Ar0線性無關(guān)，構(gòu)造：0(1) V1=,V1=0-1。-(2)

19、 v2=Av1-h11Vl要求V2-LV1,可得1=AV),V1。V2#0,否則r0,Ar0線性相關(guān)。1h2廣-v2-,V2hV21;2(3) v3;Av2-h22V2一hl2V1要求V3-LVi,可得hi2=Av2,Vi(i=1,2).%,0,否則r0,Ar0,A2r0線性相關(guān)。一二h32=-V3-',V3hVJ23m.1(m)vm=AvmJ-hi,mJvii1要求vm1vi,可得hi,m=Avm,，vi(i=1,2，,m-1).心#0,否則0,人石，人心r0線性無關(guān)。1hv-v=hvj1 'm,m-1Vm,vm1'mm,-vr1i;m(m+1)vm1=Avm一him

20、viiJ要求vm書,vi,可得him=Avm,vi(i=1,2，,m-1)1hm1,m-&vm卡k0時，vmHhm書,mvm書.于是可以得到Km的一組標(biāo)準(zhǔn)正交基vlM，以及vm41，Km在看其中的誤差分析：定理2對于m>0,若ym為方程組（4.2.3）的唯一解，則Zm=Vmym(4.2.1)滿足在0Az|二h1,mT扁ym證明：根據(jù)之前介紹的Arnoldi過程，在此利用Arnoldi過程的矩陣表示形式可以得到0-AZm=r0-AVmHm：eT、.，二_r0-(VmHmhm-1,mvmem)Hm-e1_(r0-Vme1)-hm1,mvm1(emHmel)Thm1,mvm1(emym

21、)當(dāng)v：”0時，|vm|=1,上面式子兩端取范數(shù)既得（4.2.4）式；當(dāng)vm4!=0時，hm+m=0,上式成為r。-AZm=0,兩端取范數(shù)也可以得到（4.2.4）式。該定理表明，對某m,如Hm可逆，則h4=0,即Jm書=0時，Zm=Z*成立。m1,m原理型Arnoldi算法在此需要通過增大其中的m來確定Zm,并且使得舐A。g6(名0為其所指定的誤差界)。算法的計算步驟如下：(1)給定XowRn,計算ro=bAXo.(2)對相應(yīng)的m=l,由以上所述的Arnoldi過程求出V。及心中(1=1,2,)。Hm不可逆時，算法產(chǎn)生中斷，更換X(0)繼續(xù)(1)。Hm可逆時，求解Hmy=Pe得到y(tǒng)m,并計算Z

22、m=VmYm.(3) Vm書=0時，X*=X0+Zm停止。Vm書00時，若g0AZmg<名，取X*%X0+Zm停止。若甑-Azm金W，用l+1代替l繼續(xù)(2)。該算法用于求解大型方程組(n喧1)時，但對于一般m也需要相當(dāng)大，從而計算量相當(dāng)大，為了克服這一缺點，其中一個辦法就是固定m,只對Zm進(jìn)行修正的迭代方法，即下面的循環(huán)型算法。循環(huán)型Arnoldi算法在此需要通過固定m來迭代計算Zm,并且使得打°-Azm名。計算步驟如下：(1)給定mgn,選取X(0)正Rn,計算r(0)=bAX(0),記r。=r(0)。(2)用原理型Arnoldi算法求出Zm=Vmym.形成迭代X(k由)=

23、X(k)十zm或著嚴(yán))=r(k)Azm(k=0,1,2,)(3) gr(k*g<a時，X*X(k*)停止。gr(k+)g=時,r0=r(k+1)繼續(xù)(2)。在該算法中，由于mgn,所以計算Zm的工作量不是很大，但當(dāng)k21時，如果原理型Arnoldi算法產(chǎn)生中斷，則所有計算全部白做。雖然循環(huán)型Arnoldi算法有效，但其收斂速度有時會超過共腕梯度方法。4.3GMRES算法因為在之前所講到的Arnoldi算法中有中斷的一些問題難以解決，并且在此理論上也很難分析其收斂性，所以有了其解決其缺點的方法，其中之一就是有效的GMRES算法。選取m及X。使得0,AU，次俄性無關(guān)，因為A可逆，所以2mKm

24、=spn,r0Ar,mA）rAr。，Ar。,，Ar。也線性無關(guān)。構(gòu)造2mLm=spanoAr井r,?，攔找方程組（4.1.1）的近似解心WKm,使彳#（r。-A。）1Lm,可轉(zhuǎn)化為如下最小二乘問題定理3對于m。，ZmWKm滿足（r。-AZm）-LLm的充要條件是r。一Azm=mknaz證明：必要性若ZmKm滿足（r。-AZm），Lm,則對任意的ZKm22r。-Az=（r。-AZm）-A（Z-Zm）有22=r。-AZm-2r。-AZm,A（z-Zm）A（z-Zm）|因為ZmWKm,Z-Km,所以（Z-。尸（，即有數(shù)組ki,卜2,，km,使得z-zm=kir。k2Ar。kmAm'r。A（z

25、-Zm）=kiAr。k2A2r。kmAmrg從而A（z-Zm）=Lm。于是由（r。-AZm）-LLm可得r。_AZm,A（z-Zm）=。2222因此r。-Az|r。-Azm|A（z-加|；|r。Azm22充分性若卜。-AZm|=mnr。-Az|,則對任意的v£Km和口亡R有z-km22f（二）=r。-A（Zm=v）=（r。-Azm）-:Avr。-AZm-2ar。-AZm,Av+a1|Av|22fG）.r°-AZm=f（。）一'_由此可以得到£（。）=。，即r。Az,AvQ對任意的w-Lm,存在數(shù)組G,C2,，”,使得w=CiAr。C2A2r。CmAmr。:

26、ACr。C2Ar。7Am7。）m1特別的，取v=qr0-cAr0CmArKm則有r0-AZm,w=r0-AZm,Av=0因此(0-AZm)_LLm。根據(jù)定理3,可以建立確定Zm的極小化方法。就是利用之前所講到的Arnoldi過程并m利用其來構(gòu)造Km的標(biāo)準(zhǔn)正父基V。1及Vm+1,在引進(jìn)對應(yīng)的矩陣Hm.Thm-1,memHmh彳eTm-1,m5Hm則(4.2.1)可以寫為A%=(4Vm1)其中Vm.1=(Vm4.i).設(shè)ZWKm,則有唯一的列向量yWRm,使得Z=Vmy。由于10-Az|=|r0-AVmy|=/。-4日丫|=|Vm由(P0-HmH=|P0-Hmy|(0日於卡)所以k0-AZmll=

27、瓊*0-Az|=屋"%rHmy|(4.3.1)由矩陣的廣義逆及其應(yīng)用中定理可以得到(4.3.1)式的極小范數(shù)解為ym=Hm(Pe),或者Zm=VmH；(Pe),因此，GMRES算法不會產(chǎn)生中斷。原理型GMRES算法在此需要通過增大其中的m來確定對應(yīng)的使得射0-AZmg<名。計算步驟如下：(1)給定X。wRn,計算r0=b-AX。及P=卜。|o(2)在此對于m=l,則可以由Arnoldi過程求出&及Hm(I=1,2，)(3)求解minpei-Hmy|得到y(tǒng)m。yR(4)計算Zm=Vmymogr0A#g<名，取X*忠Xo+Zm停止groAzmg至e,用+1代替l繼續(xù)(

28、2)。當(dāng)m=n時，由(ro-Azm)1Lm=Rm可得r°-AZm=0,即原理型GMRES算法可以給出方程組(4.1.1)的精確解Z”，從而可以得到方程組(2.3)的精確值X*。但對于大型方程組(n>1),m很大時，計算量增大，為了解決這一缺點，有下面的循環(huán)型GMRES算法。循環(huán)型GMRES算法在此需要通過固定其中的m來迭代計算Zm,使得go-A。名。計算步驟如下：(1)給定mgn,選取x(0)wRn,計算r(o)=bAX(0),記r。=r(o)。(2)由Arnoldi過程求出(vj及Hm。(3)求解哂IPe-Hmy得到y(tǒng)m,并計算Zm=VmYm。y二R(4)形成迭代過程X(k*

29、)=X(k)+Zm,或者(k-1)k()r=r-AZm(k=0,1,2,)(5) gr(k41)g<'時，XlX(k41)停止。(k1)(k1)，g(時，ro-r繼續(xù)(2)。在循環(huán)型GMRES算法中，選擇m和求解mirj|pe-Hmy|是計算的兩個重要問題，y-R用GMRES(m)代表循環(huán)型GMRES算法。011例3設(shè)A=|,b=|，用GMRES(m)求解方程組AX=b。-10一1,記ro=r(),求出解：取x(0)=P，計算r(0)=b-AX(0)oHlJ-,?二、/21_2因為|Pg-H1y|=2+y,所以極小點為y=0。于是4=My=從而x(1)=X(0)/=X(由該例題可

30、以看出，不是任意選取m都能使GMRES(m)收斂，但是，如果對方程組(2的系數(shù)矩陣A附加一定的條件，且取m適當(dāng)大時，GMRES(m)可以是收斂。定理4在線性方程組中對于形如方程組(2.3)的線性方程組，如果系數(shù)矩陣A相似于一個對角矩陣，則存在一個充分大的m,并且使得GMRES(m)收斂。在來看觀隨艙-Hmy|的求解問題：由于。,Ar。,，Amr。線性無關(guān)，所以ym111rankVm=m。又A可逆，所以rank(AVm)=m。在由AW=%Hm可以得到ranknH=,怏而1的列向量組線性無關(guān)。根據(jù)矩陣的QR分解理論，可以存在一個m+1階的正交矩陣Q(是有限個Givens矩陣的乘積或者是有限個Hou

31、seholder矩陣的乘積)，使得qH其中T為m階可逆上三角矩陣。m0記Q(Pq)=(q；'-,Cm,cm+)T,根據(jù)Q的正交性，有一|2IBe-Hmy=愴'Hmy=：-Ty十扁|由此可以得到：mRn|Pei-Hmy|的解ym是方程組Ty=C,，Cm)T的唯一解，而且°自-Hmym-Cm由。5GMRES(m)算法在其他方面的應(yīng)用5.1 在離散不適定問題中的應(yīng)用1 .離散不適定問題就是指類似于上述線性方程組(2.3)的線性方程組的求解問題或著是最小二乘問題min|b-AX2,如果在下面的兩個條件中任意成立其中的一個就被稱為是離散不適定問題：(1)線性方程組中的系數(shù)矩陣A

32、的條件數(shù)很大，或者系數(shù)矩陣A的最大奇異值與最小奇異值的比值很大；(2)線性方程組中的系數(shù)矩陣A的奇異值逐漸下降趨于零。2 .求解該不適定問題的GMRES(m)算法對于方程(2.3),在矩陣A的條件數(shù)非常大時，為不適定方程，選取合適的正則參數(shù)，利用正則化方法把(2.3)式轉(zhuǎn)化為(ATA+«I)x=ATb(5.1.1)且記A=ATA+a|h=ATb,其中AT是A的轉(zhuǎn)置，則方程(5.1.1)變?yōu)锳x=b(5.1.2)利用GMRES(m)算法求解不適定問題(5.1.2),算法如下：(1)初始化輸入相應(yīng)的A,9,和其初始向量X0,通過最大迭代次數(shù)m以及精度要求*,則可以的迭代的初始值為0=X1

33、-A%B=卜0"=0Vi=Vi(2) Arnoldi過程1)正交化hj=vTA4i=1,2,，j司士=A1Vj£h”j=1,2；",mi1hj+,j=vj+|22)標(biāo)準(zhǔn)化如果hjHj<2,則繼續(xù)步驟(5);否則Vj書=?j由/hj札j,j=j+1,繼續(xù)步驟(2)中的正交化。3)求解新的Vj書和Hj-h1-八，tVj書=(VJ,Vj4l)Hj=|hj=(h1j,h2j,匚hij)-j出-(j書)Xj(3)解最小二乘問題|m|=哂|昵-Hmym|(5.1得ym，Xm=%+Hmym。(4)如果卜m|T|X-Abm|f則輸出Xm。(5) 0=/J。=m，%=rm/|

34、m|，則轉(zhuǎn)為步驟(2)。5.2三維第一類Fredholm積分方程的求解1.三維第一類Fredholm積分方程fdb例如：T(f)=K(s,u,v,x,y,z)f(x,y,z)dxdydz=g(s,u,v)eca(5.2.1)其中：x,y,zw以uR3,s,u,vwc2uR3,稱為三維第一類Fredholm積分方程。根據(jù)數(shù)值積分公式可將式(5.2.1)寫為如下矩陣形式：Af=g(5.2.2)2.三維第一類Fredholm積分方程求解的GMRES(m)算法在上述的線性方程組(5.2.2)中，設(shè)其中的系數(shù)矩陣A為n階方陣，g,f亡Rn,對于定的初始向量f。，令r0=g-Af。，取Krylov子空間K

35、m=Spanfr。,Ar。,，Am'r。利用上面所敘述的GMRES(m)算法求解三維第一類Fredholm積分方程，算法如下：求gmWKm,使得，km卜卜0-Afm卜minIIr0-AfL(5.2.3)、m且將fm=f。+。作為式(5.2.2)的近似解，選取過程如下所述：對初始值f0wRn,第m步的問題是求解:(5.2.4)力(x)=u-Af2在m維的超平面fo+Km(A,ro)上極小值點為fm,且r°=u-Af0,則：fm=fo+A可作為式(5.2.2)的近似解。加上上面所訴述的三維第一類Fredholm積分方程的不適定性，所以可以把正則化方法與廣義極小殘余算法結(jié)合運用，使

36、得計算簡單，先將(5.2.2)式轉(zhuǎn)化為：(ATA+3)f=ATg(5.2.5)記為AJ=g1(其中Ai=ATA+aI,g=ATg),口>0為正則化參數(shù)。則轉(zhuǎn)化為利用GMRES(m)算法求解該方程，計算步驟如下：(1)初始化在此輸入相應(yīng)的A和g然后在選擇合適的力乏Rn,最后輸入其最大迭代次數(shù)m和誤差精度6,計算r0=g1-Af0,v1=r0/卜0;(2)Arnoldi過程(得到vi；和Hm)1)正交化hj=vTAvi-1,2,jvj1=AVj-'hjVij=1,2,mi=1hjfTlvj22)標(biāo)準(zhǔn)化如果hj41,j<6,則繼續(xù)步驟(4);否則Vj書=?+/hjHj,j=j+1

37、,繼續(xù)步驟(2)中的正交化。3)求解新的V書和Hj-HV書=M,Vj由)Hj=；一0(3)解最小二乘問題hjhj1,j,(j1)jhj=(h1j,h2j,hj)T|rmprniri|r0|ei-Hmym|,得到y(tǒng)和口=fo+vmymy二r(4)計算km|=|忖1一Alfm|,如果|rm|<5,停止，輸出fm；否則，rm=%,f0=fm，V=1m/kl,繼續(xù)步驟(2)?？偨Y(jié)四年的大學(xué)生活馬上就要結(jié)束了，想想剛剛還是學(xué)校的新生，忽然又成了學(xué)校的畢業(yè)生，時間過的真的很快，人生就是這般匆匆。在這期間有苦有甜，有淚有笑，豐富而充實的度過了美好的大學(xué)，刻苦努力和勤奮學(xué)習(xí)讓我學(xué)會了很多，也為這最后的學(xué)

38、習(xí)成果一畢業(yè)論文奠定了基礎(chǔ)，可以更好的完成。2013年12月，我的畢業(yè)論文準(zhǔn)備開始了，從開始到現(xiàn)在，基本上完成了。從開始的盲目無措，毫無頭緒，到找到論文的感興趣方向，慢慢著手，最后通過各種文獻(xiàn)的研究讓自己有了論文的思路和框架，直到論文初稿完成。在這期間讓我明白了有努力就有回報，幾個多月的汗水換來了畢業(yè)設(shè)計的最終完成，并且對學(xué)術(shù)研究有了不一樣的認(rèn)識，學(xué)會了很多東西。剛開始拿到“線性方程組的廣義極小殘余算法”這個論文題目，心都涼了，根本不知道是什么知識，也不知道要看哪方面的書籍，不知如何下手。我將這一困難告訴了老師，老師很細(xì)心很詳細(xì)的給我做了指導(dǎo)，告訴我這是哪方面的內(nèi)容，哪些書籍對我的寫作有幫助。

39、于是就立刻著手收集各種資料，使我對自己現(xiàn)在的研究方向和方法有了一點掌握。1月初到3月下旬，從開始搜集資料到寫論文，每星期都去圖書館，不斷查資料，有時候想要放棄，但在老師的指導(dǎo)和同學(xué)的幫助下還是堅持下來了，同時不斷的整理資料，使我對這個題目從了解到深知。在之后的階段中，寫論文初稿，可是遇到一些公式編輯等的難題，一些軟件不太熟悉，自己認(rèn)真的一點點的摸索在請教老師和同學(xué)，也使自己對文章有了新的認(rèn)識，并且發(fā)現(xiàn)了很多不足，最終順利的完成了。當(dāng)我終于完成了所有的論文任務(wù)后感覺整個人都很累，可是當(dāng)自己看著電腦熒屏上的畢業(yè)論文時，心里是甜的是滿足的，覺得所做的一切的努力都值了。這次畢業(yè)論文的完成過程更讓我欣喜，它不僅是一次創(chuàng)新，更是讓我熟悉了在大學(xué)里學(xué)到的知識，并且很好的運用到現(xiàn)實生活中。這幾個月的論文寫作是我在大學(xué)生活中的一個總結(jié)，也是一個開始，在我徜徉書海查找資料的日子里，面對無數(shù)書本，最難忘的就是每次找到資料時的激動和興奮。在整個的論文寫作過程中，讓我學(xué)到了新的知識，增長了見識，并且在以后的學(xué)習(xí)和生活中，我也會堅持學(xué)習(xí)專業(yè)知識，做