數(shù)值算法習(xí)題1

1、寫在前面的話各位同學(xué)：自計算方法開課以來，大家的學(xué)習(xí)熱情很高，但也有一部分同學(xué)反映做習(xí)題有些困難。我們計算方法教學(xué)組的老師們商量以后，覺得可以考慮借助于網(wǎng)絡(luò)，提供一部分輔導(dǎo)，通過演示和講解部分練習(xí)題，使大家加深對教材內(nèi)容的理解，學(xué)會如何用理論來解決有關(guān)題目和問題。這只是一個嘗試，效果如何還有待實踐來檢驗。有一點是肯定的，那就學(xué)數(shù)學(xué)不能照葫蘆畫瓢，只有理解了的才能有解題的思路，而成功地解了題，反過來也會加深對理論的理解和認(rèn)識，這是一個反復(fù)提高的過程。對嗎？在這里，我們還要感謝那些打印文稿的同學(xué)，正是由于他們的勞動，才使大家能看到這幾章的內(nèi)容。 數(shù)學(xué)系 計算方法教學(xué)組 2008.11.10習(xí)題一

2、數(shù)值分析引論提要：1、 了解數(shù)學(xué)問題與數(shù)值計算問題的聯(lián)系與區(qū)別。為什么要解數(shù)值計算問題？2、 知道有哪些基本的數(shù)值計算問題。i) 求值。ii) 方程求解iii) 數(shù)值逼近3、 了解數(shù)值計算的基本數(shù)學(xué)思想和方法基本思想： 1. 等價變換思想 2. 逐次迭代思想 3. 逐步迭代思想 4. 化整為零：數(shù)值積分，求微分方程數(shù)值解 5. 化曲為直：牛頓法 6. 轉(zhuǎn)變問題類型 7. 外推思想基本方法： 1. 直接方法 2. 間接方法：迭代，遞歸4、 誤差分析誤差來源絕對誤差，相對誤差，有效數(shù)字。5、 數(shù)值分析6. 算法性態(tài)分析誤差分析中的重要概念與公式1. 有效數(shù)字的位數(shù)n： 其中m為整數(shù)，為0-9中的一

3、個數(shù)字，如的絕對誤差不超過末位的半個單位，即，則稱具有n位有效數(shù)字。因此，如的絕對誤差界是某一位的半個單位，該位到的第一位非零數(shù)字共計有n位。則有n位有效數(shù)字。有效數(shù)字不僅給出了近似值的大小，還給出了它的絕對誤差界。2. 定理3.1 1）有效數(shù)字相對誤差界：有n位有效數(shù)字相對誤差界 2）相對誤差界有效數(shù)字：的相對誤差界滿足，則它有n位有效數(shù)字。3、 對 絕對誤差： 相對誤差： 對 絕對誤差：相對誤差： 思考題1.11. 設(shè)，（1）用左矩形公式，右矩形公式，梯形公式，simpson公式分別計算其近似值；（2）把原積分區(qū)間對分為，分別在兩子區(qū)間用上述公式近似計算，再求和，與（1）的計算結(jié)果進(jìn)行比較

4、，你有何看法？解：不能積分求出精確值。記，（1） 左矩形公式 右矩形公式 梯形公式 Simpson公式 其中，所以，（2） 把左矩形公式右矩形公式梯形公式Simpson公式2. 按定義計算行列式。一個N維行列式有項，每一項為數(shù)的乘積，總共要作次乘法和次加法，由公式stirling公式，計算一個25階行列式的值，計算量多大？（只計乘除法的次數(shù)），并假定計算機(jī)每秒可作次乘除法的計算，試求總共要計算多少時間？由此，計算解25階線性方程組的Gremer法則要作多少時間？解：。計算一個行列式的乘除法次數(shù) 。 需要時間： 即總共需要2.740億年。 解一個25階線性方程組：Gremer法則，要作26個行列

5、式計算，故需要3 用差分法離散化下列邊值問題 對照教科書上的例1.6，寫出離散后的線性方程組。解： ， 。把區(qū)間作9等分，得： 記 故在內(nèi)點處有 代入，得方程組：此為三對角方程組。思考題 1.21. 涉及一個計算的保證收斂的不動點迭代算法。解： 又 記 故有 迭代格式為 ，設(shè)，有：，2. 在外推法的介紹的算例中，我們采取了步長取半的方式，實際上只需要步長序列單調(diào)遞減就可實現(xiàn)外推。試推出這樣一般情況下的外推公式，并根據(jù)諸值，來計算圓周率的近似值 。解：設(shè)圓直徑為1，則其內(nèi)接正n邊形的周長為圓周長。記，（即把圓周n等分），把n理解為步長。 又設(shè)把原式Taylor展開： 故 其中，選擇當(dāng)取時， （*

6、） （*）這里 用圓內(nèi)接正邊形的周長近似的誤差，即用離散近似值 近似極限值的誤差稱為離散化誤差。記用（*）中的近似的誤差階為。用乘以（*），乘以（*），然后兩式相減得： 整理并記 ，將上式兩邊除以： （*）注意到上式中已經(jīng)沒有了，而的系數(shù)為，為步長的四次方！如果用來近似，其誤差階為！引入 （*）（*）式可以寫為：建立如下的外推表：在這里，再次表明，用外推表中的第一列元素來近似，其誤差也比第0列小，為類似地可得： 這些式子表明，外推表的i列值越大，即得m越大，所得到的誤差的階數(shù)越高。因此，Romberg外推法的計算過程，實質(zhì)就是逐列消去低次誤差項，逐列提高誤差階數(shù)的過程。從而逐步地使得到的近似值

7、越來越精確?，F(xiàn)在用：代入外推表：這里列到m=4。 而值精確到小數(shù)點后10位數(shù)字為：3.1415926535，它同3.141592648之差 恰好為，可見這里的誤差估計非常精確。從上面的推導(dǎo)看，如果把改為其他值，它為當(dāng)時的極限值。而具有形如：，那么，把Romberg外推法：應(yīng)用于離散化的近似值，同樣可以逐列消去誤差項 ，使近似值越來越精確。正是這個原因，Romberg外推法有著廣泛的應(yīng)用。4 試根據(jù)Newton迭代公式（2.5），推導(dǎo)計算的迭代式。請你試試，它對初值的選擇有什么要求？你的式子與（2.1）有什么關(guān)系？解：求，所以，迭代式為5 對本節(jié)例2.8，試從正反兩個方向證明問題解對稱正定矩陣方

8、程與問題在解相等的意義下等價。解：（1） 對任意的 （+） 如果滿足，則由公式可得： （-） 上式的最后一式是因為A正定，對任意的，有，顯然在（-）中，結(jié)果成立的充要條件為，（+）表明，如，則在處達(dá)到極小值。（2）設(shè)在處達(dá)到極小值，那么對任意的，必有，對（+）作具體的計算，對任意的：，故有，即，這就是說，正定二次函數(shù)在處達(dá)到極小值，則必有。6. 根據(jù)數(shù)學(xué)分析中“單調(diào)遞增有上界的數(shù)列存在極限”的結(jié)論，試研究數(shù)列的收斂性，并由此研究不動點迭代格式收斂于何值，其中迭代函數(shù)（含n個根號），取初始迭代值為，請你仔細(xì)體會不動點迭代格式的作用。解：記 顯然，所以數(shù)列單調(diào)遞增。 可見，有上界2。根據(jù)上面的過程

9、，可以知道，具有極限。設(shè)極限為A。故 解得 ，由于A不能為負(fù)數(shù)，所以，A =2。（3） 下面根據(jù)迭代，取，則：所以，6 下列極限中哪些是正確的？試用不動點迭代來加以說明：（1） ， （2）（3）， （4）你還能夠?qū)懗鲱愃频臉O限式嗎？這里有什么樣的規(guī)律？解：（1） ，所以不成立 （2） ，所以該式成立。 （3） ，所以該式成立。 （4） ，所以該式成立。 思考題1.3 1. 請把例3.2中的計算機(jī)的所有機(jī)器數(shù)畫在數(shù)軸上,你有什么認(rèn)識?用此計算機(jī)表示數(shù)1.80,0.80, ,，誤差各為多少？解：例3.2所示的計算機(jī)（t,L,U）=(3,-4,3) 表示的機(jī)器數(shù)尾數(shù)有8個：0.111，0.110，0

10、.101，0.100，0.011，0.010，0.001，0.000 越靠近0，機(jī)器數(shù)越稠密 y=1.80,只能用1.75=0.111×21表示 y=0.80,只能用0.75=0.011×21表示y=3.1415926535,只能用3.0=0.110×22表示y=1.414213526,只能用1.50=0.110×21表示。3.設(shè)的近似數(shù)的相對誤差界為0.0005，問至少有幾位有效數(shù)字？解：設(shè)有n位有效數(shù)字，記=故 相對誤差的上界可取為 現(xiàn)在的問題是不知n，故由上式不能求出n，所以就得從另一角度求。把縮小為由有效數(shù)字的定義知，至少有n位有效數(shù)字。現(xiàn)在回到

11、題中， =0.0005= 由 -2<1- n， 所以n<3。所以，至少有3位有效數(shù)字。5.設(shè)的近似數(shù)的相對誤差為0.0025，最壞情況是何數(shù)？解：這里“最壞情況”是至少有n位有效數(shù)字。解法同題3。8. 證明兩數(shù)四則運算的絕對誤差界公式：(1)(xy)= (x)+ (y);(2) (xy)=(y)+(x);(3) ，.證明：（1）(2) 【10.設(shè)計一個好的方法，使計算的計算量最小。解：死算： ，需要做21次乘法。好方法：所以 ，只要做6次乘法。15. 當(dāng)N充分大時，如何計算，以提高計算精度？解：由分部積分法當(dāng)N充分大時， 故 這樣，可以計算，整個計算也可以進(jìn)行了。補(bǔ)充題1.當(dāng)時，有

12、如下的Taylor展開式 試確定和的復(fù)雜度階數(shù)。解：計算復(fù)雜度階數(shù)T(n)是這樣定義的。如果對于算法A存在n的函數(shù)以及正常數(shù)c和，使得當(dāng)時，成立，則稱該算法的時間復(fù)雜度是階的，記做。 根據(jù)此定義，正數(shù)是的上界。例如下列復(fù)雜度階關(guān)系成立：除了大外， 還有小，如果 ，則記。(1) (2) = , , 補(bǔ)充題2. 研究開鎖題的平均開鎖次數(shù)。把這10把鎖排成一排，依次記為1號、2號、10號，按次序是計算試開1號鎖的平均次數(shù)，再計算試開2號鎖的平均次數(shù)記Tk為試開k把鎖時，試開排在首位的鎖的期望次數(shù)，那么，打開這10把鎖的總期望次數(shù)為T(10)= ，顯然，當(dāng)前9把鎖都成功打開了，那么最后一把不用試了。先

13、計算T10，即有10把鎖打開1號鎖的平均次數(shù)。由概率論知，其中j為打開1號鎖的次數(shù)，為對應(yīng)的概率。如果j=1，意味著1號鎖的鑰匙恰好排在鑰匙列的第1號位，由于每把鑰匙在這10個位置上都是可能的，故=1/10；如果j=2，意味著1號鎖的鑰匙恰好排在鑰匙列的第2號位，亦為1/10；如果j=9，意味著1號鎖的鑰匙恰好排在鑰匙列的第9號位，亦為1/10。對最后一把鑰匙，實際上不用去試開10次，因為如果前把鑰匙都打不開1號鎖，那么這第10把鑰匙必是1號鎖對應(yīng)的鑰匙，它排在這個位置的概率也是1/10。所以，T10的數(shù)學(xué)期望 ：T10= =同理，T9= T8= Tj=，T2=所以，打開這10把鎖的期望次數(shù)為

14、：T10=1/2(11+10+3)-(1/10+1/9+1/2)=31.5-1.92886829.571.請大家繼續(xù)研究下一個問題：如何計算開鎖次數(shù)的均方差？教科書習(xí)題一2. 某人在野外工作時，（手邊沒有計算工具和數(shù)學(xué)用表）需要計算的值。（1） 請你設(shè)計一種計算方法，能得到近似值；（2） 如要求達(dá)到絕對誤差界不大于10-6，你的方法能達(dá)到嗎？如達(dá)不到，你的方法需要作什么改進(jìn)？（3） 你算出的近似值有幾位有效數(shù)字？解：（1）函數(shù)的Taylor展開，是設(shè)計計算方法的常用計算工具。 是一個相距零很接近的消暑 ，故采用sinx的在點0處的Maclaurin公式，其中x= （手算）取的近似值為，則這樣近

15、似的截斷誤差為故 近似的絕對誤差界取為（2） 故用=0.017453292來近似，能滿足絕對誤差界的指標(biāo)。如果不符合要求，那么就要考慮用的Maclaurin公式的更多項來近似，比如用來近似，此時的絕對誤差為： 這樣，精度可以達(dá)到更高的要求。（3）要估計近似數(shù)0.01745329=0.1745329×10-2的有效數(shù)字，有2個方法。其一，由有效數(shù)字位數(shù)的定義，即近似值的絕對誤差不超過末位的半個單位，。但這里需要知道m(xù)與n，這里，這里缺少n的信息，故不能用此方法求出有效數(shù)字的位數(shù)。其二，由定理3.1，它給出了近似數(shù)的相對誤差與其有效數(shù)字位數(shù)的內(nèi)在關(guān)系取。現(xiàn)在已知近似值 ，所以。設(shè)有位有效

16、數(shù)字，其相對誤差界可縮小到由，故 。即0.1745329×10-2 至多只有4位有效數(shù)字，即0.1745×10-2，從小數(shù)點第5位起的數(shù)字，是不可靠的。3.證明：理論上下列6個表達(dá)式完全等價：，現(xiàn)在計算機(jī)上計算，因為只能取有限位長，這6個表達(dá)式不再相等，你認(rèn)為哪個最合理？為什么？解：上述6個表達(dá)式理論上定是等價的，用初等數(shù)學(xué)即可證明，這里不證。 記精確值，而的近似值為，當(dāng)用近似x時，這些表達(dá)式的實際值不再相等，根源在于不同正函數(shù)的計算放大倍數(shù)不一樣。設(shè) 故有又因 所以，第6個最合理。4已知是其真值經(jīng)過舍入后得到的,則其相對誤差限為(相對誤差限)=2.4560=0.24560

17、. 相對誤差 5. 為了計算次數(shù)，如何改寫？解： 令，則可改寫為6. 序列滿足迭推關(guān)系，如取 作初值，并計算到時，誤差為多少? 此迭代穩(wěn)定嗎？ 解/：初始誤差 計算到 ,被極大地放大，故計算過程不穩(wěn)定。 7. 已知 ln20.64314718，問欲精確到，近似值取多少?解: ln2=0.64314718.= m=0.而要精確到，或者，那么 ，故n至少為3，也即取ln2=0.643時，絕對誤差8. 如三函數(shù)值取4位有效數(shù)字，怎么樣計算才能保證 的精度?解： 因接近1，故直接計算必會損失有效數(shù)字，故采用下面兩種非直接計算這2種算法都優(yōu)于直接計算。（如直接計算）9測量長方形地的長110cm, .如果

18、,求其面積的絕對誤差和相對誤差。解: 面積 故面積的絕對誤差為也可以用二元函數(shù)近似值的絕對誤差界的估計公式相對誤界 10. 試用兩種方法計算,并比較結(jié)果方法一: 直接計算有 ，只有1位有效數(shù)字。原因為兩相近數(shù)直接相減，損失了有效數(shù)字。方法二：. 代入n=994. 故有 = 而精確值為0.10110916，可見方法2有4位有效數(shù)字11. 正方形邊長約100cm.問如何測量才能使其面積誤差?解: 設(shè)正方形邊長為 , 面積為 則設(shè)正方形邊長的近似值為，面積的近似值為，得誤差 現(xiàn)有=100, 故 即當(dāng)邊長的誤差不超過0.005cm時,才愛能使面積誤差12. N充分大時，求 解：=。，當(dāng)N充分大時，與很

19、接近，兩數(shù)相減需要避免，故要改造計算式。因 ，。 11. 設(shè)原始數(shù)據(jù)如下列近似值每位都是是有效數(shù)字. , , , 計算(1) (2) ； 并估計他們的相對誤差界.解: 因,的每一位均為有效數(shù)字,故它們的絕對誤差界. (1) . =1.1021+0.031+56.430=57.5631相對誤差界 ；(2) 。12.設(shè)有一個長方形水池,由測量知長為,寬為,深為,求該水池的容積,并分析所得近似值的絕對和相對誤差.給出絕對誤差界和相對誤差界.解: 設(shè)是水池邊長、寬和深分別為則容積為。由數(shù)據(jù)知，。絕對誤差估計位 =；相對誤差誤差估計。13. 已知,均具有4位有效數(shù)字,試估計的絕對誤差和相對誤差界. 解:

20、 絕對誤差兩數(shù)之差的絕對誤差限而其相對誤差限 14. 用遞推公式 n=1,2，如取問求有多大誤差。解： ， 故， n=1，2誤差取n=100，則此算法的誤差不斷擴(kuò)大，故數(shù)值不穩(wěn)定。15. 對函數(shù) 計算.(1).如何計算才能避免有效數(shù)字的損失.(2).開方和對數(shù)計算取6位有效數(shù)字，試計算和解：當(dāng)時，對函數(shù)計算，沒有有效數(shù)字的損失。當(dāng)時，存在有效數(shù)字的損失，故要做等價變換：(2) x=30, x=-30 16. 可由迭代公式計算 k=0,1,2.若是的具有n位有效數(shù)字的近似值,則是具有2n位有效數(shù)字的近似值.證: , k=0,1,2.又雖為的弱近似值,但是 故是的強(qiáng)近似值.故有下界， 且而.單調(diào)不

21、增.，因此存在極限。對兩邊取極限,得, 解得 =假設(shè)是的具有n位有效數(shù)字的近似值.則 可見，是具有2n位有效數(shù)字的近似值.17. 復(fù)數(shù)的平方根為.其中u,v可用公式， 來計算。分別就 ， 兩種情況討論計算結(jié)果，必要時可改變上述計算公式。解： 時，上述公式不會損失有效數(shù)字，因此計算結(jié)果是較精確的。 時，若則，屬于兩相近數(shù)相減，往往會造成有效數(shù)字的大量丟失，因而用上述公式計算就使結(jié)果失真。為此，要做等價變形： 18. 已知三角形面積 ,其中c為弧度, ,且測量a,b,c的誤差分別為,.證明:面積誤差 滿足 解: 由多元函數(shù)近似值的絕對誤差和相對誤差估計公式.則0<c<, .從而得 19. 當(dāng)=0.001時,求函數(shù)的近似值(要求6位有效數(shù)字)解: 有,又只此取近似值.故y的近似程度, 取決的近似程度.對可作Taylor展開. 取則當(dāng)=0.0