計算方法試驗指導書

1、計算方法實驗指導書彭彬計算機技術實驗中心2012年3月實驗環(huán)境：VC+ 6.0實驗要求：在機房做實驗只是對準備好的實驗方案進行驗證，因此上機前要檢查實驗準備情況，通過 檢查后方可上機。沒有認真準備的學生不能上機，本次實驗沒有分數(shù)。實驗中要注意考察 和體會數(shù)值計算中出現(xiàn)的一些問題和現(xiàn)象：誤差的估計，算法的穩(wěn)定性、收斂性、收斂速度以及迭代初值對收斂的影響等。關于計算精度：如果沒有特別說明，在計算的過程中，小數(shù)點后保留5位數(shù)字，最后四舍五入到小數(shù)1點后四位數(shù)子。迭代運算的結(jié)束條件統(tǒng)一為一M105。在VC+ 6.0中，可使用2setprecision在流的輸出中控制浮點數(shù)的顯示(缺省顯示6位)。演示如

2、下：includeincludeinclude/輸出6位精度，輸出左對齊coutsetprecision(6)setiosflags(ios:left);/設置輸出寬度為12 (不夠?qū)⒀a充0) coutsetw(12)Cr patePen( PS_SDL ID J % “凱瓦 % 助 pal )Pi?niBpDC=S elec tObect(pneuPeo);療畫原始由要冼將動到第一個點pbt-ioro(2aF3SD);F口r(int h;K咻i*)原始坐標坐樹H x IM II; y -p Mil;F艱化為整型Int xi=(int)TextOut(250,10,龍格現(xiàn)象);/ 文本輸出/設

3、置畫筆，將影響畫線的樣式CPen *pnewPen,*poldPen;pnewPen=new CPen();pnewPen-CreatePen(PS_SOLID,10,RGB(0,0,0);poldPen=pDC-SelectObject(pnewPen);/畫坐標系pDC-MoveTo(0,380);pDC-LineTo(640,380);pDC-MoveTo(320,0);pDC-LineTo(320,480);/ 畫曲線，先移動到本曲線的第一個點pDC-MoveTo(20,380);for(int i=0;iLineTo(x1,y1); /重置畫筆void:dr auQldLin?(un

4、t % ttC 邛時)H一點數(shù)(B 3 01 classes+. *.jCAbaiJlDIgE CMainrrami: CfeslApp+ i； CTe$O-tCTesMewt AssertVaiijQ獅 CTestViewOdrgwOHUnM血機1口C*pDC.DumpCDu(npCon|efx| dcfGdD口cumcn班Lagrsnge|flDatx,iiii m lloatxlllo % OnBcginPrintingtCDC*pDC, CRinlli 0nDf3w|CDCxpDC)而 OnEndninlinylCDC *pD尊 CPrintlufi“ OnPrep arePtinti

5、ng|CPriiitlnh xplnlo PrtCftalcWlndHCREATESJRUCTIGI血怕pDC-SelectObject(poldPen);1圖2自定義函數(shù)回函數(shù)f(x)=的圖形1 4x2圖3是一個根據(jù)Lagrange插值多項式求函數(shù)值的自定義函數(shù)Lagrange(float x, int n, floatx1, float y1),其中n是插值節(jié)點的個數(shù)，數(shù)組 X1,y1存放插值節(jié)點的坐標，x是待求點的x坐標，函數(shù)根據(jù)插值多項式返回對應的y坐標。float CTestView:Lagrange(float x, int n, float x1, float y1) float

6、 y=0;存放函數(shù)值int k=0;/控制變量，求lagrange 基函數(shù)的值for( k=0;kn;k+) float t=1;for (int j=0;jUiieTQ(iMrSlD;醞沛我口儂0網(wǎng)；pDC-lineTD3?ai4e6);健置雄pDC- Selet tObj e Dt(poIdPen);floatint虛微1,求la|ra呼基函數(shù)的值For( K=0；ki;k圖4 OnDraw()函數(shù)的內(nèi)容/N-N 等分for(int N=2;N=10;N=N+2)/求插值節(jié)點for(int i=0;iMoveTo(20,380);/設置畫筆CPen *pnewPen,*poldPen;pn

7、ewPen=new CPen();pnewPen-CreatePen(PS_DASHDOT,1+N/2,RGB(255-20*N,0+10*N,20*N);poldPen=pDC-SelectObject(pnewPen);/按照插值節(jié)點求插值多項式的值，并描點for(int k=0;k=2000;k+)float x=-1+2.0/2000*k;float y=Lagrange(x,N+1,px,py);注意N+1個節(jié)點/坐標變換x=x*300;/Y坐標放大，并且反號，因為Y坐標軸是向下的y=-y*300;)Float 1=1;for (iflt j=6;jpoid ClestUiew; 7

8、flin&i aiw(C.BC* pDC) ch/ IUDUzdrjw cade for native data here/互原始圖形drawUldLin?(2lSUQl,pDC：3; float pxllbpyllj；“畫插值圖形“nif分For(int“,中插值節(jié)卓For(int MnuTa(2ia73Bfl); 門設置苗筆CPem 叩口(*9n產(chǎn)psldPen;唧(岬電“皿川CPH()；pififLHPen.- CrwtPfriit PS_OASH&IT ,1 *W2 ,RC 8(255-2 *H a&NP2C*H);poldFvn-|3OC-Select Qb jet tfpmewee

9、n);，或照插值節(jié).點求插值多項式的值并指點for(int k=0;kTextOut(x1,y1, 二等分);if (N=4 & x1=50)pDC-TextOut(x1,y1, 四等分);if (N=6 & x1=60)pDC-TextOut(x1,y1, 六等分);if (N=8 & x1=580)pDC-TextOut(x1,y1, 八等分);if (N=10 & x1=600)pDC-TextOut(x1,y1, 十等分);pDC-LineTo(x1,y1);/重置畫筆pDC-SelectObject(poldPen);實驗項目一覽表實驗學時12應開實驗項目個數(shù)6序號實驗項目名稱實驗要

10、求學時分配實驗類型備注1一元非線性方程求根的算法必做2綜合性2解線性方程組的直接方法必做2驗證性3解線性方程組的間接方法必做2驗證性4插值多項式的求法必做2驗證性5數(shù)值積分必做2驗證性6常微分方程的數(shù)值解必做2驗證性姓名班級學號日期元非線性方程求根的算法【實驗性質(zhì)】綜合性實驗?！緦嶒災康摹苛私夥蔷€性方程求根的基本方法；掌握二分法和牛頓法。3f(x) = x sin x 4x+1 的全部實根,【實驗內(nèi)容】選擇合適的初值，用二分法和牛頓迭代法求出一元非線性方程8=10?！纠碚摶A】數(shù)值法求非線性方程的跟一般分三步：判定根的存在性；確定根的分布范圍根的精確化常用的數(shù)值方法有二分法和迭代法。二分法的基

11、本思想是：先確定有根區(qū)間，然后通過逐步縮小(二分區(qū)間)有根區(qū)間的長度，以求根 的近似值。二分法只能求實根，不能求復根及重根。迭代法通過建立一個迭代序列來逼近根。迭代效果與迭代初值、迭代公式的收斂性有關。迭代初始值一般根據(jù)高等數(shù)學的知識或作圖的方法來確定；迭代公式通過對已知方程的某種變換得 到。迭代的收斂性以及收斂速度不僅與迭代公式有關，可能還與迭代初值有關。牛頓迭代是常用的迭代方法。把f (x)在xk處按泰勒公式展開為：f ( )2f (x) = f (%) + f (%)(x %) +-(x -xk) +，2!忽略高次項，得到 f (x)罔f (xk) +f (xk)(x -xk)。如果x*

12、是方程的根,則有：f(x ) : f (xk) f (xk)(x -凡)：0由此得：f(xk)f (xk)從而建立起牛頓迭代公式：f(xk)xk i = xk當相鄰兩次迭代結(jié)果滿足f (xk)xk + xk W w時停止計算。如果非線性方程為一元多項式方程，則其牛頓解法的關鍵在于求f(xk)與f(xk),這時可以用如下的快速算法(秦九韶算法)設n次多項式f(x)為： f(x) /xn *n -1次多項式Q(x)為：Q(x)= b0 xn bixn如果f(x)、Q(x)滿足bnqx bnf(x) =(x -Xk)Q(x) bn(1)則有f(x。=4于是求f (xk)就轉(zhuǎn)換為求系數(shù)bn。將式(1)

13、展開，有如下遞推關系：b0 二a0b =abZ a,（i =1,2，川，n）,如果是就開始計算，否則就輸出“不能保證主元非零，計算結(jié)束”。j熱 j七在線性代數(shù)中，只要系數(shù)行列式det（A）=|A #0,線性方程組就可求解，但 Gauss方法當主元為0時就不能繼續(xù)進行，因此順序高斯消元法有缺陷。另一方面，即使順序高斯消元法可行，但主元a（k/）很kk小，運算中用它作為除法的分母（aj =aj -阪a/sk）,也會導致其它元素數(shù)量級的嚴重增長和舍入誤差的擴散。這是Gauss法的另一缺陷。主元素消去法是 對上述算法的改進,其中列主元消去法較為常用：在第 i步，從第i列的第i行至 最后一行中選取絕對值

14、最大的元素（注意，不是該列的所有元素，而是部分元素），通過行互換，將其 調(diào)到主元位置，然后再做消元。用列選主元方法可以克服高斯消元法的額外限制，只要方程組有解，列 選主元消元法就能暢通無阻地順利求解，同時提高了解的精確度。2、追趕法在實踐中，常遇到 m（如m =3,5）對角方程組的求解問題。這類方程組的系數(shù)矩陣一般非奇異，可分解為特殊的矩陣，基于相關矩陣可得到求解的快速算法。第14頁姓名班級學號日期【實驗過程】.畫出選列主元的算法框圖。.分別用高斯消元法和列主元消去法求解，用表格比較兩種算法的結(jié)果與精度，分析實驗出現(xiàn)的問 題，并總結(jié)解決辦法。第15頁姓名班級學號日期第16頁姓名班級學號日期3.

15、用追趕法求解，分別給出兩個方程組Ly = f和Ux = y ,分析實驗出現(xiàn)的問題，并總結(jié)解決辦法。第17頁姓名班級學號日期4.從使用條件、運算量比較列主元消去法和追趕法?！緦嶒炐牡谩康?8頁姓名班級學號日期實驗三解線性方程組的間接方法【實驗性質(zhì)】驗證性實驗?！緦嶒災康摹空莆盏ㄇ蠼饩€性方程組?！緦嶒瀮?nèi)容】應用雅可比迭代法和Gauss-Sediel迭代法求解下方程組:12X2一01-2X3.02？4 一一6 一【理論基礎】線性方程組的數(shù)值解法分直接算法和迭代算法。迭代法將方程組的求解轉(zhuǎn)化為構(gòu)造一個向量序列， 其極限就是方程組的解。迭代法程序簡單，但有時工作量較大，在有限步內(nèi)，得不到精確解，適宜

16、某些 系數(shù)矩陣階數(shù)較高的問題。迭代的基本思想是構(gòu)造一個關于解向量的迭代序列X(K),使得這個序列隨k的增大而逐漸逼近準一乙一一*確解X ,常見的有Jacobi一0迭代算法和Gauss-Seidelan加速迭代算法。一。a12IIIa1na210IIIan,n 1a22annIIIa 2n=L+D+UJacobi迭代公式:(k)Xn一(k二(- ajXj b)/aiij 土：生(i =1,2，n)Gauss-Seidel 迭代公式為：x(k)naijX(k)+ 項乂)/a (i =1,2,., n)j 士 1迭代收斂的充分條件是：系數(shù)矩陣A嚴格對角占優(yōu)，或者迭代矩陣G滿足|g1或者|g|Lmi本

17、題的參考答案:【實驗過程】0.2857、-0.3265 、0.0408、2.97961.取三個不同初值，分別用雅可比法和高斯-塞得爾法求解，用表格記載求解過程。第19頁姓名班級學號日期第20頁姓名班級學號日期2.根據(jù)程序運行結(jié)果填寫下表，分析迭代初值、迭代公式對迭代的影響雅可比法高斯-塞得爾法初值近似根迭代次數(shù)近似根迭代次數(shù)123【實驗心得】第21頁姓名班級學號日期實驗四插值多項式的求法【實驗性質(zhì)】驗證性實驗?！緦嶒災康摹空莆誏agrange插值算法、Newton插值算法；理解 Newton插值算法相對于 Lagrange插值算法的優(yōu)點?！緦嶒瀮?nèi)容】TE T TE先用C語言自帶的系統(tǒng)函數(shù) si

18、n x求出sin x在x=0二二二二 的值，然后分別用 Lagrange、6 4 3 2Newton方法求出sin(土)的值，并與用 C語言sin x函數(shù)計算出的sin(E)作比較。 55【理論基礎】.Lagrange插值公式經(jīng)過n+1個插值節(jié)點(x0,y0),(x1,y1),|(xn,yn)的n次Lagrange插值多項式為：nn n x _ xPn(x)yJk(x)(=-j)ykk ak a j 衛(wèi) xk -Xjj k. NewTon插值公式經(jīng)過n十1個插值節(jié)點(x0,y0),( x1,y1),|(xn, yn)的n次Newton插值多項式為:Pn(x) =f (x。)f x0,x1(x-

19、x0) III fx0,x)|ILxn(x-x0)(x-x1)H|(x-xlA)上式中插商f x0, xi,III,xn 的計算常用到如下的Newton差商表:xf(x)一階插商二階插商三階插商四階插商x0f (x0)x1f(x)f 4，x2f(x2)f 為岡他？/x3f(x3)f區(qū)2f 為區(qū)區(qū)可飛,為243x4f(x,)f區(qū)fx2，x3，x4flXEEMf x0,x1，x2, x3，x4 . -其中差商是一個遞推的定義:fx0,xi，川，人fx0,x,川，王一 f xi,x2,|l|,xnx -xn由上表可知：每增加一個插值節(jié)點，都需從一階插商算起。但在具體應用時，有兩種方案：(一)當節(jié)點數(shù)

20、n+1固定時，使用兩個數(shù)組 xn+1,yn+1來存放插值計算的中間結(jié)果。其中xn+1存放插值節(jié)點的X坐標；y n+1開始存放插值節(jié)點的 丫坐標，計算過程中存放差商值。計算差商時，一次計算差商表的一列。計算fx0,x1時用到y(tǒng)1和y0,計算fx1,x2時用到y(tǒng)2和y1,不必再用到y(tǒng)0,由此可把fx0,x放到y(tǒng)0,把Hxe放到y(tǒng)1,。計算二階差商時, 把二階差商放到 y0、y1、。這樣牛頓插值公式中用到的fx0、fx0,x1 、fx0,x1,x2、依次均存放在丫0算法實現(xiàn)參考：丫= y0 , t=1for (int j=1;j=n;j+) /計算 J 階插商(t=t*(x-xj-1);for(in

21、t i=0;in-j;i+)yi=yi 1卜刎xi j -xi;/計算j階插商的各種結(jié)果第22頁姓名班級學號日期)Y=Y+y0*t;)NewTon差商表一階二階三階四階五階y。fx, x1f4,X,x2f x0,x1,x2,x3f x, X ,x2,x3,x4f x0, x, x2,x3,x4,x5y1fx1,x2f xi,x2,x3f x1,x2, x3,x，f 為2右34,%f x,x2,x3,x4,x5,x6y2fx2, x3f區(qū)區(qū)f 區(qū)區(qū),x，, 2f x2,x3, x4,xs,x6f 區(qū),x3,x4,x5, %y3fx3,xjf KE,%f區(qū)44, *5冬f 區(qū),4。5, %y，fx

22、4, x5f MW, %f MW, *6Vsfx5,%fl4%y6y6（二）考慮動態(tài)增加插值結(jié)點，比如已有x0, x1 ,再增加x2時，依次計算fx1,x2,fx0,x1,x2。當增加第n+1個節(jié)點時，用xn+1存放該點X坐標，用yn+10存放點的Y坐標，用 yn+1i 存放本行的i階差商（1Wi 1 1t * * * *【實驗過程】1.分別用Lagrange插值和Newton插值求解。第23頁姓名班級學號日期第24頁姓名班級學號日期2.用表格Lagrange法、Newton法以及C語言自帶函數(shù)對 sin（5）的求值結(jié)果。3.分析實驗出現(xiàn)的問題，總結(jié)解決辦法。【實驗心得】第25頁姓名班級學號日

23、期實驗五數(shù)值積分【實驗性質(zhì)】驗證性實驗?！緦嶒災康摹坷斫獠逯敌头e分法；掌握復化積分法算法。【實驗內(nèi)容】1對I =dx ,用復化梯形積分和變步長梯形積分求值(截斷誤差不超過 0 1 x1-5 X-X10-)。2【理論基礎】積分在工程中有重要的應用，數(shù)值積分的基本思想是用被積函數(shù)xi(i =0,1J|, n)處的值f(xj的線性組合作為積分的近似值：nba f (x)dx :打A f (xi)f (x)在區(qū)間a,b上的一些點i 實際應用中f(x)是未知的，一般用 f(x)的次數(shù)不超過 法)：n的插值多項式 Pn(x)來代替(插值型求積方bf (x)dx :I Pn(x)dx之i b(f li(x)

24、dx)f(Xi)o a如果考慮等距節(jié)點，即h = (b a) / n ,Xi= a + ih(i =0,1,| ,n),作變換 x = a + th ,有:nf f (x)dx &(b-a)Z Ckf (xk), a上式稱為Newton-Cotes求積公式，其中Ckk -0(-1產(chǎn)nk!(n -k)!n n f 口 (t - j)dt 稱為 Cotes 系數(shù):j 3Mk1 1n =1: Cotes系數(shù)為 一,一2 21 4n = 2: Cotes系數(shù)為一，一，6 6 613 3 1n =3: Cotes系數(shù)為一，一，一，一8 8 8 8n =4: Cotes系數(shù)為7 32 12 32.Newt

25、on-Cotes 求積公式Newton-Cotes求積公式中,Newton-Cotes求積公式中,Newton-Cotes求積公式中,b - a=1有梯形求積公式：T = f (a) + f (b)；2=2有拋物線公式(Simpson公式)：b-aa - bS=f(a) +4f()+f(b);62=4有Cotest公式：b aC =7 f (Xo) 32f (Xi) 12f(x2) 32f (x3) , 7f (x4)。90上述公式的余項分別為： TOC o 1-5 h z 357(b -a). _ ，. _(b -a)，.,(b -a) _-f (n),na,b Tf (),“ua,b和1y f (/a,b12180 2945 2.復化求積公式：Simpson 公式、為提高精度，常把區(qū)間 a,b等分成n個小區(qū)間，在每個小區(qū)間上使用梯形公式、Cotes公式，就得到復化積分公式：第26頁姓名班級學號日期Tn = f(a) f(b) 2% f (a - kh)復化梯形公式（h=） nb - a一復化 Simpson 公式(h =)nn ,Jf(Xk.3/4) 14%- f(Xk)k-1 TOC o 1-5 h z hn 1n 1Sn 葭f(a) f(b)平 f (Xki/2) 2- f(X