數(shù)值計(jì)算(或計(jì)算方法)試驗(yàn)教學(xué)講義28886

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

2、性，使程序或算法更加完美。1.3實(shí)驗(yàn)環(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本實(shí)驗(yàn)課程與其它課程的關(guān)系本課程的前導(dǎo)課程冇高等數(shù)學(xué)、線性代數(shù)（或高等代數(shù)）、c語(yǔ)言或fortran語(yǔ)言等，最 好事先開(kāi)設(shè)數(shù)據(jù)結(jié)構(gòu)；后續(xù)課程有計(jì)算機(jī)圖形學(xué)、圖像處理、模式識(shí)別等。第二章實(shí)驗(yàn)的計(jì)劃和內(nèi)容2. 1實(shí)驗(yàn)計(jì)劃計(jì)算方法實(shí)驗(yàn)課共安排20學(xué)時(shí)。計(jì)算方法實(shí)驗(yàn)計(jì)劃如下(l)lagrango插值多項(xiàng)式newton插值

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

4、向右，y軸垂直向下。2. 常用的繪圖兩數(shù)(繪圖庫(kù)函數(shù)所在的頭文件graphics, h)初始化圖形系統(tǒng)的函數(shù) void initgraph(int * graphdriver, int graphmode,畫點(diǎn)函數(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è)計(jì)模式include "graphics, h"mai n ()int graphdriver二detect, graphmode;initgraph(&graphdtivcr, &graphniode,"”)； 調(diào)用繪圖兩數(shù)進(jìn)行繪圖 closegraph (

6、);數(shù)據(jù)結(jié)構(gòu)：兩個(gè)一維數(shù)組或一個(gè)二維數(shù)組算法設(shè)計(jì)：(略)編寫代碼：(略)實(shí)驗(yàn)用例：已知函數(shù)y=f(x)的一張表：x0102030405060708090100110120y517. 534.5& 815. 56. 5_5-10-24. 57試驗(yàn)要求：利用lagrange插值多項(xiàng)式厶”(兀)求被插值函數(shù)f(x)在點(diǎn)x=65處的近似值。建議：畫出lagrange插值多項(xiàng)式厶“(x)的曲線。2. 2.2實(shí)驗(yàn)二實(shí)驗(yàn)題目：newton插值多項(xiàng)式相關(guān)知識(shí)：通過(guò)n+1個(gè)節(jié)點(diǎn)的次數(shù)不超過(guò)n的newton插值多項(xiàng)式為: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)：兩個(gè)一維數(shù)組或一個(gè)二維數(shù)組算法設(shè)計(jì)：（略）編寫代碼：（略）實(shí)驗(yàn)用例：已知函數(shù)y=f（x）的一張表（同上一個(gè)試驗(yàn)）試驗(yàn)要求：利用newton插值多項(xiàng)式n” （兀）求被插值函數(shù)f（x）在點(diǎn)x=65處的近似值。建議:irlljncwton插值多項(xiàng)式nn （x）的|11|線。2. 2.3實(shí)驗(yàn)三實(shí)驗(yàn)題目：hcnni tc插值多項(xiàng)式相關(guān)知識(shí)：通過(guò)n+1個(gè)節(jié)點(diǎn)的次數(shù)不超過(guò)2n+l的hormitc插值多項(xiàng)式為: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)：三個(gè)一維數(shù)組或一個(gè)二維數(shù)組算法設(shè)計(jì)：（略）編寫代碼：（略）實(shí)驗(yàn)用例：已知函數(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實(shí)驗(yàn)用例：jwhermite插值多項(xiàng)式比曲求被插值函數(shù)f(x)在點(diǎn)x=0.55處的近似值。建議：畫出hermite插值多項(xiàng)式w2/t+l (x)的曲線。2. 2. 4實(shí)驗(yàn)四實(shí)驗(yàn)題目：111!線擬侖的最小二乘法相關(guān)知識(shí)：已知ca, b中函數(shù)f (x)的一組實(shí)驗(yàn)數(shù)據(jù)(x“ y：)(1=0, 1,),其中yk(x)。 設(shè)(pj (x)( j = 0,1, , 71； /? < 777)是 ca, b上 線性 無(wú)關(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的計(jì)算公式為:（£ 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)：兩個(gè)一維數(shù)組或一個(gè)二維數(shù)組算法設(shè)計(jì)：(略)編寫代碼：(略)實(shí)驗(yàn)用例：已知函數(shù)y二f(x)的一張表：x0102030405060708090y6867. 166. 465.664.661.861.060.860.460試驗(yàn)要求：利用曲線擬合的線性最小二乘法求被逼近函數(shù)f(x)在點(diǎn)x=55處的近似值，并 曲出實(shí)驗(yàn)數(shù)據(jù)和直線。2. 2. 5實(shí)驗(yàn)五實(shí)驗(yàn)題目：復(fù)化求積公式b cl相關(guān)知識(shí)：將積分區(qū)間a, bn等分，節(jié)點(diǎn)xk=a+kh, k=0, 1, , n,步長(zhǎng)力=。復(fù)化n梯形公式為：hn-l人二亍/(d)+ 2工/a

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

13、求積公式求/ = f vcosxjx的近似值（積分的粕確值i=-12. 0703463164, 7t = 3.14159265358979323846.),誤差精度£ = 10"。2. 2. 6實(shí)驗(yàn)六實(shí)驗(yàn)題目：romberg求積公式相關(guān)知識(shí)：用兩個(gè)相鄰的近似公式（其中后一個(gè)公式是由前一個(gè)公式的分半得到的）的線性組合而得到更好的近似公式的方法，就是近代電子計(jì)算機(jī)上常用的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嚴(yán)二,j",2,k數(shù)據(jù)結(jié)構(gòu)：一個(gè)二維數(shù)組算法設(shè)計(jì)：romberg求積公式的算法如卜h第一步:取k=0, h=b-a,求70) =-/(a)+ /(/?)2第二步：令1-k (k記區(qū)間a,b的二分次數(shù))求梯形值丁()，按梯形的遞推公式； 求加速值，按公式逐個(gè)求出t表的笫k行其余各元素町s)(j=l,2,k)； 若怦&

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

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

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

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

19、 %12a22 an2«】u2%u22u2n 1 11“nn分解過(guò)程的計(jì)算公式如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)：一個(gè)一維數(shù)組先后存儲(chǔ)b、y和x； 個(gè)二維數(shù)組先存儲(chǔ)兒后被l和u覆蓋（二者中的零元素不用存，i的對(duì)角元1亦不川存）算法設(shè)計(jì)：利用肓接三介分解法求解線性代數(shù)方程組的算法第一步:分解 對(duì)于r=l, 2, , n-1求l的r歹i對(duì)于i=t+l, r+2, , nairk=/求u的r+1行 1r+1 對(duì)于i=l, 1+1,，n/-iaii j aii -伙 k=第二步：求解ly二b （解存儲(chǔ)在b中）對(duì)