数值算法习题1

1、写在前面的话各位同学：自计算方法开课以来，大家的学习热情很高，但也有一部分同学反映做习题有些困难。我们计算方法教学组的老师们商量以后，觉得可以考虑借助于网络，提供一部分辅导，通过演示和讲解部分练习题，使大家加深对教材内容的理解，学会如何用理论来解决有关题目和问题。这只是一个尝试，效果如何还有待实践来检验。有一点是肯定的，那就学数学不能照葫芦画瓢，只有理解了的才能有解题的思路，而成功地解了题，反过来也会加深对理论的理解和认识，这是一个反复提高的过程。对吗？在这里，我们还要感谢那些打印文稿的同学，正是由于他们的劳动，才使大家能看到这几章的内容。 数学系 计算方法教学组 2008.11.10习题一

2、数值分析引论提要：1、 了解数学问题与数值计算问题的联系与区别。为什么要解数值计算问题？2、 知道有哪些基本的数值计算问题。i) 求值。ii) 方程求解iii) 数值逼近3、 了解数值计算的基本数学思想和方法基本思想： 1. 等价变换思想 2. 逐次迭代思想 3. 逐步迭代思想 4. 化整为零：数值积分，求微分方程数值解 5. 化曲为直：牛顿法 6. 转变问题类型 7. 外推思想基本方法： 1. 直接方法 2. 间接方法：迭代，递归4、 误差分析误差来源绝对误差，相对误差，有效数字。5、 数值分析6. 算法性态分析误差分析中的重要概念与公式1. 有效数字的位数n： 其中m为整数，为0-9中的一

3、个数字，如的绝对误差不超过末位的半个单位，即，则称具有n位有效数字。因此，如的绝对误差界是某一位的半个单位，该位到的第一位非零数字共计有n位。则有n位有效数字。有效数字不仅给出了近似值的大小，还给出了它的绝对误差界。2. 定理3.1 1）有效数字相对误差界：有n位有效数字相对误差界 2）相对误差界有效数字：的相对误差界满足，则它有n位有效数字。3、 对 绝对误差： 相对误差： 对 绝对误差：相对误差： 思考题1.11. 设，（1）用左矩形公式，右矩形公式，梯形公式，simpson公式分别计算其近似值；（2）把原积分区间对分为，分别在两子区间用上述公式近似计算，再求和，与（1）的计算结果进行比较

4、，你有何看法？解：不能积分求出精确值。记，（1） 左矩形公式 右矩形公式 梯形公式 Simpson公式 其中，所以，（2） 把左矩形公式右矩形公式梯形公式Simpson公式2. 按定义计算行列式。一个N维行列式有项，每一项为数的乘积，总共要作次乘法和次加法，由公式stirling公式，计算一个25阶行列式的值，计算量多大？（只计乘除法的次数），并假定计算机每秒可作次乘除法的计算，试求总共要计算多少时间？由此，计算解25阶线性方程组的Gremer法则要作多少时间？解：。计算一个行列式的乘除法次数 。 需要时间： 即总共需要2.740亿年。 解一个25阶线性方程组：Gremer法则，要作26个行列

5、式计算，故需要3 用差分法离散化下列边值问题 对照教科书上的例1.6，写出离散后的线性方程组。解： ， 。把区间作9等分，得： 记 故在内点处有 代入，得方程组：此为三对角方程组。思考题 1.21. 涉及一个计算的保证收敛的不动点迭代算法。解： 又 记 故有 迭代格式为 ，设，有：，2. 在外推法的介绍的算例中，我们采取了步长取半的方式，实际上只需要步长序列单调递减就可实现外推。试推出这样一般情况下的外推公式，并根据诸值，来计算圆周率的近似值 。解：设圆直径为1，则其内接正n边形的周长为圆周长。记，（即把圆周n等分），把n理解为步长。 又设把原式Taylor展开： 故 其中，选择当取时， （*

6、） （*）这里 用圆内接正边形的周长近似的误差，即用离散近似值 近似极限值的误差称为离散化误差。记用（*）中的近似的误差阶为。用乘以（*），乘以（*），然后两式相减得： 整理并记 ，将上式两边除以： （*）注意到上式中已经没有了，而的系数为，为步长的四次方！如果用来近似，其误差阶为！引入 （*）（*）式可以写为：建立如下的外推表：在这里，再次表明，用外推表中的第一列元素来近似，其误差也比第0列小，为类似地可得： 这些式子表明，外推表的i列值越大，即得m越大，所得到的误差的阶数越高。因此，Romberg外推法的计算过程，实质就是逐列消去低次误差项，逐列提高误差阶数的过程。从而逐步地使得到的近似值

7、越来越精确。现在用：代入外推表：这里列到m=4。 而值精确到小数点后10位数字为：3.1415926535，它同3.141592648之差 恰好为，可见这里的误差估计非常精确。从上面的推导看，如果把改为其他值，它为当时的极限值。而具有形如：，那么，把Romberg外推法：应用于离散化的近似值，同样可以逐列消去误差项 ，使近似值越来越精确。正是这个原因，Romberg外推法有着广泛的应用。4 试根据Newton迭代公式（2.5），推导计算的迭代式。请你试试，它对初值的选择有什么要求？你的式子与（2.1）有什么关系？解：求，所以，迭代式为5 对本节例2.8，试从正反两个方向证明问题解对称正定矩阵方

8、程与问题在解相等的意义下等价。解：（1） 对任意的 （+） 如果满足，则由公式可得： （-） 上式的最后一式是因为A正定，对任意的，有，显然在（-）中，结果成立的充要条件为，（+）表明，如，则在处达到极小值。（2）设在处达到极小值，那么对任意的，必有，对（+）作具体的计算，对任意的：，故有，即，这就是说，正定二次函数在处达到极小值，则必有。6. 根据数学分析中“单调递增有上界的数列存在极限”的结论，试研究数列的收敛性，并由此研究不动点迭代格式收敛于何值，其中迭代函数（含n个根号），取初始迭代值为，请你仔细体会不动点迭代格式的作用。解：记 显然，所以数列单调递增。 可见，有上界2。根据上面的过程

9、，可以知道，具有极限。设极限为A。故 解得 ，由于A不能为负数，所以，A =2。（3） 下面根据迭代，取，则：所以，6 下列极限中哪些是正确的？试用不动点迭代来加以说明：（1） ， （2）（3）， （4）你还能够写出类似的极限式吗？这里有什么样的规律？解：（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.请大家继续研究下一个问题：如何计算开锁次数的均方差？教科书习题一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与n，这里，这里缺少n的信息，故不能用此方法求出有效数字的位数。其二，由定理3.1，它给出了近似数的相对误差与其有效数字位数的内在关系取。现在已知近似值 ，所以。设有位有效

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. 序列满足迭推关系，如取 作初值，并计算到时，误差为多少? 此迭代稳定吗？ 解/：初始误差 计算到 ,被极大地放大，故计算过程不稳定。 7. 已知 ln20.64314718，问欲精确到，近似值取多少?解: ln2=0.64314718.= m=0.而要精确到，或者，那么 ，故n至少为3，也即取ln2=0.643时，绝对误差8. 如三函数值取4位有效数字，怎么样计算才能保证 的精度?解： 因接近1，故直接计算必会损失有效数字，故采用下面两种非直接计算这2种算法都优于直接计算。（如直接计算）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，则此算法的误差不断扩大，故数值不稳定。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