數(shù)值計算(或計算方法)試驗教學講義28886

1、第一章 實驗的目的和要求1.1實驗目的為了掌握計算方法的基本思想、原理和方法，要注意計算方法的處理技巧與計算機實現(xiàn) 的結(jié)合，需將各種數(shù)值方法設(shè)計成算法，并編制好程序，拿到計算機上實現(xiàn)，最示得到可行 性的驗證。12實驗要求（1）用c或c+、java. fortran matlab等計算機程序設(shè)計語言編寫程序。（2）上機前充分準備，復習相關(guān)知識，選用合適的數(shù)據(jù)結(jié)構(gòu)并詳細設(shè)計算法，盡量寫出 具有通用性的程序，反復檢查程序。（3）上機時快速輸入程序；首先排除語法錯謀；然后采用多組數(shù)據(jù)，詳細測試，排除邏 輯錯誤；最后將程序調(diào)試成功，運行程序得到準確結(jié)果。（4）完成計算后，反復體會和分析，試著改善計算復雜

2、性，使程序或算法更加完美。1.3實驗環(huán)境1. 3. 1硬件環(huán)境cpu : pentium 4以上內(nèi)存：256mb以上1. 3. 2軟件環(huán)境（1）操作系統(tǒng):microsoft windows xp 和 2000（2）編譯器：c或c+、java、fortran> mat lab1.4本實驗課程與其它課程的關(guān)系本課程的前導課程冇高等數(shù)學、線性代數(shù)（或高等代數(shù)）、c語言或fortran語言等，最 好事先開設(shè)數(shù)據(jù)結(jié)構(gòu)；后續(xù)課程有計算機圖形學、圖像處理、模式識別等。第二章實驗的計劃和內(nèi)容2. 1實驗計劃計算方法實驗課共安排20學時。計算方法實驗計劃如下(l)lagrango插值多項式newton插值

3、多項式(3) iiennite插值多項式最小二乘法復化求積公式(6) romberg求積公式數(shù)值微分的外推算法gauss消元法肓接三角分解法(10)解方程組的迭代法2.2實驗內(nèi)容共十個實驗題目，每次課(2學時)一個題目。2. 2. 1實驗一實驗題冃：lagrange插值多項式相關(guān)知識：通過ni 1個節(jié)點的次數(shù)不超過n的lagrange插值多項式為：厶心)=£兒人(兀)k=()齊 % 兀.其中,lagrange插值基函數(shù)lk(x)= ft, k=0, 1, , n0>« 忑-xj沖k另外，補充c語言繪制圖形方面的內(nèi)容如下1. 屏幕坐標系 坐標原點在屏幕的左上介，x軸水平

4、向右，y軸垂直向下。2. 常用的繪圖兩數(shù)(繪圖庫函數(shù)所在的頭文件graphics, h)初始化圖形系統(tǒng)的函數(shù) void initgraph(int * graphdriver, int graphmode,畫點函數(shù) void putpixel (int x, int y, int pixelcolor);移"畫筆”函數(shù) void moveto(int x, int y);畫直線函數(shù)voidline(int xl,int yl, int x2, inty2);voidlineto(int x, int y);設(shè)置詢景顏色函數(shù)void setcolor(int color);設(shè)置巧景顏色

5、函數(shù)void setbkcolor(int color);設(shè)置畫線寬度和類型函數(shù)void setlinestyle(int 1 inestyle,unsigned upattern, int thickness);關(guān)閉圖形系統(tǒng)函數(shù)void closegraph (void);3. 繪圖程序的設(shè)計模式include "graphics, h"mai n ()int graphdriver二detect, graphmode;initgraph(&graphdtivcr, &graphniode,"”)； 調(diào)用繪圖兩數(shù)進行繪圖 closegraph (

6、);數(shù)據(jù)結(jié)構(gòu)：兩個一維數(shù)組或一個二維數(shù)組算法設(shè)計：(略)編寫代碼：(略)實驗用例：已知函數(shù)y=f(x)的一張表：x0102030405060708090100110120y517. 534.5& 815. 56. 5_5-10-24. 57試驗要求：利用lagrange插值多項式厶”(兀)求被插值函數(shù)f(x)在點x=65處的近似值。建議：畫出lagrange插值多項式厶“(x)的曲線。2. 2.2實驗二實驗題目：newton插值多項式相關(guān)知識：通過n+1個節(jié)點的次數(shù)不超過n的newton插值多項式為:rt(x) = /(x0) + /x0,x1(x-x0) + yx0,x1,x2(x-

7、x0)(x-x1) + -+ /1兀0，兀1，£(兀一兀0)(兀一兀1)(兀一?！?1)數(shù)據(jù)結(jié)構(gòu)：兩個一維數(shù)組或一個二維數(shù)組算法設(shè)計：（略）編寫代碼：（略）實驗用例：已知函數(shù)y=f（x）的一張表（同上一個試驗）試驗要求：利用newton插值多項式n” （兀）求被插值函數(shù)f（x）在點x=65處的近似值。建議:irlljncwton插值多項式nn （x）的|11|線。2. 2.3實驗三實驗題目：hcnni tc插值多項式相關(guān)知識：通過n+1個節(jié)點的次數(shù)不超過2n+l的hormitc插值多項式為:h2卄 =工兒勺(x) + mjf3i (x)；=o其中，hermite插值基函數(shù)a)(x)

8、= 1 - 2(x 一 xj )1 j (勺)(x)0/ (x) = (x-x)；(兀)(x-x。) (x-x：i) (x-x打)打1k=0 x i k$j數(shù)據(jù)結(jié)構(gòu)：三個一維數(shù)組或一個二維數(shù)組算法設(shè)計：（略）編寫代碼：（略）實驗用例：已知函數(shù)y=f（x）的一張表（其中m = /'（%）：x0. 100. 200. 300. 400. 50y0.9048370.8187310. 7408180. 6703200.606531m-0.904837-0.818731-0.740818-0.670320-0.606531x0. 600. 700. 800. 901.00y0. 5488120.

9、4965850. 4493290. 4065700. 367879m-0.548812-0.496585-0. 449329-0.406570-0.367879實驗用例：jwhermite插值多項式比曲求被插值函數(shù)f(x)在點x=0.55處的近似值。建議：畫出hermite插值多項式w2/t+l (x)的曲線。2. 2. 4實驗四實驗題目：111!線擬侖的最小二乘法相關(guān)知識：已知ca, b中函數(shù)f (x)的一組實驗數(shù)據(jù)(x“ y：)(1=0, 1,),其中yk(x)。 設(shè)(pj (x)( j = 0,1, , 71； /? < 777)是 ca, b上 線性 無關(guān)函 數(shù)族。 在 0 =

10、¥期0(),0(兀),，久0)中找函數(shù)f(x)曲線擬合的最小二乘解禺，其法方程(組)為:7=0工（洙 ,禺）勺=dk （k =0,1,«）加其中，（禺，久）=工 ®g（pj g（pk a）r=0m（/,%） = s）/a）洙 a）三 dkk=o,l,n?=0特別是，求函數(shù)f（x） 111線擬合的線性最小二乘解sx = ax + b的計算公式為:（£ x；）（£ x） -（£ xf）（£ xj x）b i=0心0匸0匸0（加+ i）£f-/=0 /=0曲mm伽+ 1）工i -（工兀）（工x）c _/ = 0/ = 0

11、/=0a _匸（加+1）£彳-（£忑）2i=0i=0數(shù)據(jù)結(jié)構(gòu)：兩個一維數(shù)組或一個二維數(shù)組算法設(shè)計：(略)編寫代碼：(略)實驗用例：已知函數(shù)y二f(x)的一張表：x0102030405060708090y6867. 166. 465.664.661.861.060.860.460試驗要求：利用曲線擬合的線性最小二乘法求被逼近函數(shù)f(x)在點x=55處的近似值，并 曲出實驗數(shù)據(jù)和直線。2. 2. 5實驗五實驗題目：復化求積公式b cl相關(guān)知識：將積分區(qū)間a, bn等分，節(jié)點xk=a+kh, k=0, 1, , n,步長力=。復化n梯形公式為：hn-l人二亍/(d)+ 2工/a

12、+ 肋)+/(b)2k=再將每個小區(qū)間二等分，即整個積分區(qū)間a,b2n等分，此時復化梯形公式為“。復化梯形公式的遞推關(guān)系為乙專+施)u. . tt , a(2/-1)a. b-a具中，h,嚴迄f(a+'丿),h =oz=i2n數(shù)據(jù)結(jié)構(gòu)：(略)算法設(shè)計：復化梯形公式的算法如卞第一步:n=1, h=b-a；h第二步：tn=-f(a) + f(b)；第三步：計算hj第四步：計算卩2“；第五步:n=2n, h=h/2；第六步：若t.-t%(事先給定的誤差精度)，則轉(zhuǎn)第三步；第七步：輸出tn和等分數(shù)n/2,結(jié)束算法。編寫代碼：（略）實驗用例：/ = t ex cos xdx試驗要求：利用復化梯形

13、求積公式求/ = f vcosxjx的近似值（積分的粕確值i=-12. 0703463164, 7t = 3.14159265358979323846.),誤差精度£ = 10"。2. 2. 6實驗六實驗題目：romberg求積公式相關(guān)知識：用兩個相鄰的近似公式（其中后一個公式是由前一個公式的分半得到的）的線性組合而得到更好的近似公式的方法，就是近代電子計算機上常用的romberg求積方法，也叫逐次分半加速（收斂）法。設(shè)以加）表示二分k次后求得的梯形值，且以羅t）表示序列/）的j次加速值。romberg求積公式的t表如.卜kh7伙）11t）t/1 0b-ar0<0)

14、1b-a2t（o） 上1 2b-a4a/(i)11吋0） 3b-a8at 上1tf為(0) 4b-a16y(4)1 0y11t2(2)tv町0) romberg求積公式（逐次分半加速公式）女ii卜2k硏=*礦"+穿+-1）#）心1，24）丁伙-j+1）_丁伙一門t嚴二,j",2,k數(shù)據(jù)結(jié)構(gòu)：一個二維數(shù)組算法設(shè)計：romberg求積公式的算法如卜h第一步:取k=0, h=b-a,求70) =-/(a)+ /(/?)2第二步：令1-k (k記區(qū)間a,b的二分次數(shù))求梯形值丁()，按梯形的遞推公式； 求加速值，按公式逐個求出t表的笫k行其余各元素町s)(j=l,2,k)； 若怦&

15、#176;)-礎(chǔ)卜£ (預先給定的誤差精度)，k+17,則轉(zhuǎn)(1)；第三步：輸出7；和等分數(shù)2* (或二分次數(shù)k),結(jié)束算法。編寫代碼：(略)實驗用例:2試驗耍求：利用romberg求積公式求上述定積分(z =-« 0.636619772 ),誤差和度71£ = 10"6 o2. 2. 7實驗七實驗題m數(shù)值微分相關(guān)知識：數(shù)值微分的中點公式為f (%) u g(h)=2h應用理查森(richardson)外推對h逐次分半，計算過程如下農(nóng)(g()(ho二g(h)g°(/i) 喝)g(h) 時)囲)gm) g*)g噲)g2(f)gw) 計算公式為數(shù)據(jù)

16、結(jié)構(gòu)：一個二維數(shù)組算法設(shè)計：（略）編寫代碼：（略）實驗用例：/（x） =試驗要求：利用數(shù)值微分的外推算法求.廠（1）的近似值2. 2. 8實驗八實驗題r :用gauss消元法求解線性代數(shù)方程組相關(guān)知識：在做除法運算吋，分母的絕對值越小，舍入誤差就越大。因此，消元的每一 步都先選取絕對值比較大的元素（稱作主元），用它作分母再消元。這就是主元素消去法的 基木思想。數(shù)據(jù)結(jié)構(gòu)：用一個二維數(shù)組存儲線性代數(shù)方程組的增廣炬陣；線性代數(shù)方程組的解最后 存儲在增廣矩陣的最后一列上。算法設(shè)計：用列主元gauss消元法求解線性代數(shù)方程組（同時求出系數(shù)行列式的值dot） 的算法為第一步：dett;第二步：對于k二1,

17、2,，nt按列選取主元,找匚w+1,使 = maxlaikk<i<n如果& = 0 （最好是r < £ , £為預先給定的一個非常小的數(shù)），則det=o, 計算停止如果l >k （或l ）,則換行 o+1,，斤+1det - det(4)消元計算,對于i=k+l, k+2, : n v亠% 對于j=k+l, k+2,，n+1aij aij aik x akj（5） det < detx akk第三步:如果仇“ =0（最好是£為預先給定的一個非常小的數(shù)），則det=0,計算停止，否則，回代求解（1）snn對于i=n-l, n-2

18、,，1 對于j=i+l, i+2,，n%+i一切 xd”+第四步:det < detx ann編寫代碼：（略）實驗川例：線性代數(shù)方程組為10-701 _ 8-32.09999962兀25.9000015-15-152102_1試驗要求：利用列主元的gauss消元法求解上述線性代數(shù)方程組（精確解為（o -1 11）?。⑼瑓记蟪鱿禂?shù)行列式的值2. 2. 9實驗九實驗題目：肓接三角分解法相關(guān)知識：有矩陣a的三角lu分解，則求解線性代數(shù)方程組ax二b的問題就等價于求解兩 個三角方程組ly二b和ux二y。而利用矩陣相等則對應元素相等的事實，可逐一求出系數(shù)矩陣a 的三角分解屮l和u的各元素。a2

19、 %12a22 an2«】u2%u22u2n 1 11“nn分解過程的計算公式如kr-uri =ciri - 工-mi，i =廠,廠+ 1,；廠= 1,2,hk=lir = （a” 一工/汕好）=r,r + l,-,n;r = 1,2,，/? 一1 k=/數(shù)據(jù)結(jié)構(gòu)：一個一維數(shù)組先后存儲b、y和x； 個二維數(shù)組先存儲兒后被l和u覆蓋（二者中的零元素不用存，i的對角元1亦不川存）算法設(shè)計：利用肓接三介分解法求解線性代數(shù)方程組的算法第一步:分解 對于r=l, 2, , n-1求l的r歹i對于i=t+l, r+2, , nairk=/求u的r+1行 1r+1 對于i=l, 1+1,，n/-iaii j aii -伙 k=第二步：求解ly二b （解存儲在b中）對