數(shù)值分析共軛梯度法解方程組課程設(shè)計(jì)

課程設(shè)計(jì)報(bào)告課程名稱數(shù)值分析程序設(shè)計(jì)課題名稱共軛梯度法求線性方程組數(shù)值解專業(yè)信息與計(jì)算科學(xué)班級(jí)0802學(xué)號(hào)200810010229姓名馬丙韶指導(dǎo)教師聶存云2011年6

湖南工程學(xué)院課程設(shè)計(jì)任務(wù)書課程名稱面向?qū)ο蟪绦蛟O(shè)計(jì)課題共軛梯度法求線性方程組數(shù)值解專業(yè)班級(jí)信息與計(jì)算科學(xué)0802班學(xué)生姓名馬丙韶學(xué)號(hào)200810010229指導(dǎo)老師聶存云審批任務(wù)書下達(dá)日期2010年6月19日任務(wù)完成日期2011年6月26日一、設(shè)計(jì)內(nèi)容與設(shè)計(jì)要求1．設(shè)計(jì)內(nèi)容：對(duì)課程《計(jì)算方法》中的常見算法進(jìn)行綜合設(shè)計(jì)或應(yīng)用〔具體課題題目見后面的供選題目〕。2．設(shè)計(jì)要求：課程設(shè)計(jì)報(bào)告正文內(nèi)容問(wèn)題的描述及算法設(shè)計(jì)；算法的流程圖〔要求畫出模塊圖〕；算法的理論依據(jù)及其推導(dǎo)；相關(guān)的數(shù)值結(jié)果〔通過(guò)程序調(diào)試)，；數(shù)值計(jì)算結(jié)果的分析；附件〔所有程序的原代碼，要求對(duì)程序?qū)懗霰匾淖⑨尅?。書寫格式a．要求用A4紙打印成冊(cè)b．正文格式：一級(jí)標(biāo)題用3號(hào)黑體,二級(jí)標(biāo)題用四號(hào)宋體加粗,正文用小四號(hào)宋體;行距為22。c．正文的內(nèi)容:正文總字?jǐn)?shù)要求在3000字左右〔不含程序原代碼〕。d．封面格式如下頁(yè)。考核方式指導(dǎo)老師負(fù)責(zé)驗(yàn)收程序的運(yùn)行結(jié)果，并結(jié)合學(xué)生的工作態(tài)度、實(shí)際動(dòng)手能力、創(chuàng)新精神和設(shè)計(jì)報(bào)告等進(jìn)行綜合考評(píng)，并按優(yōu)秀、良好、中等、及格和不及格五個(gè)等級(jí)給出每位同學(xué)的課程設(shè)計(jì)成績(jī)。具體考核標(biāo)準(zhǔn)包含以下幾個(gè)局部：a．平時(shí)出勤〔占10%〕b．系統(tǒng)需求分析、功能設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及程序總體結(jié)構(gòu)合理與否〔占10%〕c．程序能否完整、準(zhǔn)確地運(yùn)行，個(gè)人能否獨(dú)立、熟練地調(diào)試程序〔占40%〕d．設(shè)計(jì)報(bào)告〔占30%〕注意：不得抄襲他人的報(bào)告〔或給他人抄襲〕，一旦發(fā)現(xiàn)，成績(jī)?yōu)榱惴帧．獨(dú)立完成情況〔占10%〕。課程驗(yàn)收要求a．判定算法設(shè)計(jì)的合理性，運(yùn)行相關(guān)程序，獲得正確的數(shù)值結(jié)果。b．答復(fù)有關(guān)問(wèn)題。c．提交課程設(shè)計(jì)報(bào)告。d．提交軟盤〔源程序、設(shè)計(jì)報(bào)告文檔〕。e．依內(nèi)容的創(chuàng)新程度，完善程序情況及對(duì)程序講解情況打分。三、進(jìn)度安排班級(jí)：信息與計(jì)算科學(xué)：0801、0802、0803主講教師：聶存云輔導(dǎo)教師：聶存云時(shí)間安排：第18周星期一8時(shí)：30分——11時(shí)：30分星期二8時(shí)：30分——11時(shí)：30分星期四8時(shí)：30分——11時(shí)：30分星期五8時(shí)：30分——11時(shí)：30分目錄一、 引言 51.1線性方程組的研究背景 51.2線性方程組的求解中存在的問(wèn)題分析 6二、 算法及算法分析 62.1共軛梯度法理論依據(jù)及推導(dǎo) 62.2共軛梯度法算法流程圖 8三、 共軛梯度法解線性方程組 8四、 結(jié)果分析 9五、 附錄 9引言1.1線性方程組的研究背景在自然科學(xué)和工程實(shí)際應(yīng)用中，有許多問(wèn)題的求解最終都轉(zhuǎn)化為線性方程組的求解問(wèn)題。例如曲線擬合中常用的最小二乘法、樣條函數(shù)插值、解非線性方程組、求解偏微分方程的差分法、有限元法和邊界元法以及目前工程實(shí)踐中普遍存在的反演問(wèn)題等。鑒于線性方程組問(wèn)題在理論上的重要性和在工程實(shí)際應(yīng)用中的大量存在，多年來(lái)人們?cè)谶@方面做了廣泛深入的研究和探討，并取得了許多有價(jià)值的成果。然而，由于模型誤差、測(cè)量誤差、計(jì)算誤差〔舍入誤差〕等各種形式誤差的存在，常常使獲得的線性方程組中的系數(shù)矩陣和非齊次項(xiàng)信息具有某種程度的近似性〔即擾動(dòng)性〕，這種近似性顯然會(huì)使得線性方程組的求解不大容易得到真實(shí)的理論解。此時(shí)，不同的求解方法由于〔迭代〕運(yùn)算機(jī)理不一樣，求解過(guò)程中誤差積累程度就不一樣，因此必然會(huì)使得不同求解方法得到的解具有不同的逼近真解的誤差程度，尤其對(duì)那些具有病態(tài)性的方程組而言，許多現(xiàn)有的方法是失效的，因?yàn)樗鼈儾痪哂锌共B(tài)性，因而它們求得的解將完全失真。1.2線性方程組的求解中存在的問(wèn)題分析在線性代數(shù)中，我們一般采用的是順序消去法，即我們常說(shuō)的高斯消去法，它是一種實(shí)現(xiàn)方法簡(jiǎn)便，易于操作的處理方法。然而，對(duì)于由于舍入誤差的存在，在求解一些病態(tài)線性方程組問(wèn)題時(shí)，該種方法計(jì)算的結(jié)果會(huì)明顯偏離于問(wèn)題的理論值，這樣一來(lái)，我們計(jì)算的結(jié)果不可能表現(xiàn)出問(wèn)題的根本屬性，因而，我們對(duì)選主元的高斯消去法進(jìn)行了研究，與傳統(tǒng)的高斯消去法相比，選主元的高斯消去法的舍入誤差相對(duì)較小，得到的結(jié)果精度更能滿足實(shí)際工程的需要。LU分解法是一種改良的高斯消去法，它的具體思路是將系數(shù)矩陣分解成為兩個(gè)矩陣的乘積的形式，這兩個(gè)矩陣可以表示成一個(gè)下三角和一個(gè)上三角矩陣的乘積形式，這樣只需要求解兩個(gè)簡(jiǎn)單的線性方程組即可得到問(wèn)題的解，相比于高斯消去法，它在存儲(chǔ)空間上能大大較少，能夠縮短計(jì)算所需要的時(shí)間，同時(shí)，我們對(duì)選主元的LU分解法做了分析，它是與選主元的高斯消去法相對(duì)應(yīng)的一種計(jì)算方法，在計(jì)算一般線性方程組的問(wèn)題時(shí)，它不但節(jié)省了存儲(chǔ)空間，而且可以到達(dá)比擬好的計(jì)算精度。但是，只對(duì)傳統(tǒng)的一般線性方程組的研究是不夠的，特別是對(duì)于工程實(shí)際中碰到的大型稀釋矩陣和病態(tài)方程組的求解上，傳統(tǒng)方法的存儲(chǔ)空間大、計(jì)算效率不高等諸多問(wèn)題會(huì)困擾著問(wèn)題的求解。針對(duì)大型系數(shù)矩陣的特點(diǎn)，我們必須用不同的計(jì)算和存儲(chǔ)方法。此時(shí)，迭代算法表達(dá)了它的優(yōu)勢(shì)。迭代算法由于存儲(chǔ)簡(jiǎn)便，運(yùn)算高效等特點(diǎn)被工程實(shí)踐所廣泛采用。共軛梯度法法是一種加速線性方程組收斂的常用算法，特別在處理大型的稀疏矩陣時(shí)，共軛梯度的方法能夠明顯的加速收斂，減少處理的時(shí)間，它是一種預(yù)處理的方法，也是現(xiàn)在數(shù)值分析領(lǐng)域一個(gè)研究的重點(diǎn)。算法及算法分析2.1共軛梯度法理論依據(jù)及推導(dǎo)共軛梯度法法是一種預(yù)處理方法，用共軛梯度法求解高階的線性方程組問(wèn)題，由于它對(duì)矩陣元素結(jié)構(gòu)沒(méi)有特殊要求，通常用以求解一般大型稀疏矩陣的線性方程組。共軛梯度法是一種迭代算法，具體思路如下：設(shè)為Ax=b的精確解，為任一初始的近似向量，有，一般，如有，那么：，假設(shè)考慮函數(shù)，顯然，當(dāng)且僅當(dāng)時(shí)，，因此，假設(shè)能求得向量序列，使逐步減小，那么由，有，那么為Ax=b的解。假設(shè)產(chǎn)生的迭代向量序列的公式為：其中為n維方向向量，為常數(shù)。假設(shè)給定的向量，為了使為最小，那么于是，，此時(shí)，，顯然，，而且確定的方法不止一種，例如可取，此時(shí)得到最速下降法。在共軛梯度法中，是向量的線性組合，對(duì)于新的向量，使函數(shù)取盡可能小的值?？梢粤睿浩渲袨樘囟ǔ?shù)。為確定，不失一般性，假設(shè)由已經(jīng)求出，相應(yīng)的有。因?yàn)?，而從而有，選取使得極小，即使極小有從而有，令，即可以得到共軛梯度法的計(jì)算公式：任給，對(duì)于作：可以證明，在沒(méi)有舍入誤差的條件下，一定有，使得，即，因此至多迭代n步，可得到準(zhǔn)確解。但是由于舍入誤差的影響，一般作迭代使用，此時(shí)當(dāng)充分小時(shí)，終止迭代，此時(shí)可以近似看作是方程組的解。2.2共軛梯度法算法流程圖共軛梯度法解線性方程組用共軛梯度法解教材P469例1，結(jié)果如下列圖所示結(jié)果分析用本程序進(jìn)行3次迭代之后成功到方程組的實(shí)際解與教材結(jié)果完全一致，證明該算法的正確性。共軛梯度法在解中小型方程組時(shí)計(jì)算量比擬大，表達(dá)不出它的優(yōu)越性。就程序本身而言還有些缺乏之處，例如：它沒(méi)有提供輸入的接口，只是單純的解決教材上的一個(gè)實(shí)際例題，使該程序不具有實(shí)際的使用和推廣的價(jià)值。另外運(yùn)行后的界面外觀也不夠完美，這些都有待進(jìn)一步改良以使其發(fā)揮更大功能。附錄程序源代碼：#include"math.h"#include"iostream.h"voidgrad(intn,double*a,double*b,double*x,doubleeps=1e-10){inti,j,k;double*p,*r,*s,*q,alpha,beta,d,e;p=newdouble[n];r=newdouble[n];s=newdouble[n];q=newdouble[n];for(i=0;i<=n-1;i++){x[i]=0.0;p[i]=b[i];r[i]=b[i];}i=0;while(i<=n-1){for(k=0;k<=n-1;k++){s[k]=0.0;for(j=0;j<=n-1;j++)s[k]=s[k]+a[k*n+j]*p[j];}d=0.0;e=0.0;for(k=0;k<=n-1;k++){d=d+p[k]*b[k];e=e+p[k]*s[k];}alpha=d/e;for(k=0;k<=n-1;k++)x[k]=x[k]+alpha*p[k];for(k=0;k<=n-1;k++){q[k]=0.0;for(j=0;j<=n-1;j++)q[k]=q[k]+a[k*n+j]*x[j];}d=0.0;for(k=0;k<=n-1;k++){r[k]=b[k]-q[k];d=d+r[k]*s[k];}beta=d/e;d=0.0;for(k=0;k<=n-1;k++)d=d+r[k]*r[k];d=sqrt(d);if(d<eps){delete[]p;delete[]r;delete[]s;delete[]q;return;}for(k=0;k<=n-1;k++)p[k]=r[k]-beta*p[k];i=i+1;}delete[]p;delete[]r;delete[]s;delete[]q;return;}voidmain(){inti;doubleeps,x[4];staticdoublea[3][3]={{4.0,3.0,0.0},{3.0,4.0,-1.0},{0.0,-1.0,4.0},};staticdoubleb[3]={24.0,30.0,-24.0};eps=0.000001;grad(3,*a,b,x,eps);for(i=0;i<=2;i++)cout<<"x["<<i<<"]="<<x[i]<<endl;}