數值算法習題1

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

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

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

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

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

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

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

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

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

10、.101，0.100，0.011，0.010，0.001，0.000 越靠近0，機器數越稠密 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.設的近似數的相對誤差界為0.0005，問至少有幾位有效數字？解：設有n位有效數字，記=故 相對誤差的上界可取為 現在的問題是不知n，故由上式不能求出n，所以就得從另一角度求。把縮小為由有效數字的定義知，至少有n位有效數字。現在回到

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

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

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

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

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

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

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

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

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

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

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