数值计算方法与程序设计

1、 提问：数值分析是做什么用的？提问：数值分析是做什么用的？数值数值分析分析输入复杂问题或运算输入复杂问题或运算.),(,)(,ln,xfdxddxxfbxAxaxbax 计算机计算机近似解近似解第一章第一章 误差误差 /* Error */1 误差的背景介绍误差的背景介绍 /* Introduction */1. 来源与分类来源与分类 /* Source & Classification */ 从实际问题中抽象出数学模型从实际问题中抽象出数学模型 模型误差模型误差 /* Modeling Error */ 通过测量得到模型中参数的值通过测量得到模型中参数的值 观测误差观测误差 /* Measu

2、rement Error */ 求近似解求近似解 方法误差方法误差 (截断误差截断误差 /* Truncation Error */ ) 机器字长有限机器字长有限 舍入误差舍入误差 /* Roundoff Error */1 Introduction: Source & ClassificationThe following problem can be solved either the easy way or the hard way.Two trains 200 miles apart are moving toward each other; each one is going at

3、a speed of 50 miles per hour. A fly starting on the front of one of them flies back and forth between them at a rate of 75 miles per hour. It does this until the trains collide and crush the fly to death. What is the total distance the fly has flown?The fly actually hits each train an infinite numbe

4、r of times before it gets crushed, and one could solve the problem the hard way with pencil and paper by summing an infinite series of distances. The easy way is as follows: Since the trains are 200 miles apart and each train is going 50 miles an hour, it takes 2 hours for the trains to collide. The

5、refore the fly was flying for two hours. Since the fly was flying at a rate of 75 miles per hour, the fly must have flown 150 miles. Thats all there is to it.When this problem was posed to John von Neumann, he immediately replied, 150 miles.It is very strange, said the poser, but nearly everyone tri

6、es to sum the infinite series.What do you mean, strange? asked Von Neumann. Thats how I did it!1 Introduction: Source & Classification大家一起猜？大家一起猜？ dxe2x1011 / e解法之一解法之一：将将 作作Taylor展开后再积分展开后再积分2xe.91!4171!3151!21311).!4!3!21(10864210 dxxxxxdxe2xS4R4 /* Remainder */7430024010333014211013114.S 00102000

7、50. | 舍入误差舍入误差 /* Roundoff Error */ |006000100050102.dxe-x 的的总总体体误误差差计计算算= 0.747 由截去部分由截去部分/* excluded terms */引起引起,104 Sdxe2x取取则则.111!5191!414 R称为称为截断误差截断误差 /* Truncation Error */005091!414.R 这这里里由留下部分由留下部分/* included terms */引起引起dxex 102例：例：近似计算近似计算据说，美军据说，美军 1910 1910 年的一次部队的命令传递是这样的年的一次部队的命令传递是这

8、样的: : 营长对值班军官营长对值班军官: : 明晚大约明晚大约 8 8点钟左右，哈雷彗星将可能在这个地区点钟左右，哈雷彗星将可能在这个地区看到，这种彗星每隔看到，这种彗星每隔 7676年才能看见一次。命令所有士兵着野战服在操年才能看见一次。命令所有士兵着野战服在操场上集合，我将向他们解释这一罕见的现象。如果下雨的话，就在礼场上集合，我将向他们解释这一罕见的现象。如果下雨的话，就在礼堂集合，我为他们放一部有关彗星的影片。堂集合，我为他们放一部有关彗星的影片。值班军官对连长值班军官对连长: : 根据营长的命令，明晚根据营长的命令，明晚8 8点哈雷彗星将在操场上空出点哈雷彗星将在操场上空出现。如果

9、下雨的话，就让士兵穿着野战服列队前往礼堂，这一罕见的现。如果下雨的话，就让士兵穿着野战服列队前往礼堂，这一罕见的现象将在那里出现。现象将在那里出现。连长对排长连长对排长: : 根据营长的命令，明晚根据营长的命令，明晚8 8点，非凡的哈雷彗星将身穿野战点，非凡的哈雷彗星将身穿野战服在礼堂中出现。如果操场上下雨，营长将下达另一个命令，这种命服在礼堂中出现。如果操场上下雨，营长将下达另一个命令，这种命令每隔令每隔7676年才会出现一次。年才会出现一次。排长对班长排长对班长: : 明晚明晚8 8点，营长将带着哈雷彗星在礼堂中出现，这是每隔点，营长将带着哈雷彗星在礼堂中出现，这是每隔 7676年才有的事

10、。如果下雨的话，营长将命令彗星穿上野战服到操场上年才有的事。如果下雨的话，营长将命令彗星穿上野战服到操场上去。去。班长对士兵班长对士兵: : 在明晚在明晚8 8点下雨的时候，著名的点下雨的时候，著名的7676岁哈雷将军将在营长的岁哈雷将军将在营长的陪同下身着野战服，开着他那陪同下身着野战服，开着他那“彗星彗星”牌汽车，经过操场前往礼堂。牌汽车，经过操场前往礼堂。1 Introduction: Spread & Accumulation2. 传播与积累传播与积累 /* Spread & Accumulation */例：例：蝴蝶效应蝴蝶效应 纽约的一只蝴蝶翅膀一拍，风和日丽的北京纽约的一只蝴蝶翅

11、膀一拍，风和日丽的北京就刮起台风来了？！就刮起台风来了？！NYBJ以上是一个以上是一个病态问题病态问题 /* ill-posed problem*/关于本身是病态的问题，我们还是留给数学家去头痛吧！关于本身是病态的问题，我们还是留给数学家去头痛吧！1 Introduction: Spread & Accumulation.210110,n,dxexeIxnn 例：例：计算计算11 nnInI 公式一：公式一：注意此公式注意此公式精确精确成成立立632120560111100.edxeeIx 记为记为*0I80001050 .IIE则初始误差则初始误差111111110010 nI)e(ndxe

12、xeIdxexennnn391414231519594249414122764807131632896000121030592000111088128000101.367879440111415*13*14*12*13*11*12*10*11*9*10*0*1.II.II.II.II.II.II.II ? ! !What happened?!1 Introduction: Spread & Accumulation考察第考察第n步的误差步的误差nE| )1()1( |*11* nnnnnnInIIIE| !.01En|Enn 我们有责任改变。我们有责任改变。造成这种情况的是造成这种情况的是不稳

13、定的算法不稳定的算法 /* unstable algorithm */迅速积累，误差呈递增走势。迅速积累，误差呈递增走势。可见初始的小扰动可见初始的小扰动801050| .E)1(1111nnnnInIInI 公式二：公式二：注意此公式与公式一注意此公式与公式一在理论上在理论上等价等价。方法：先估计一个方法：先估计一个IN , ,再反推要求的再反推要求的In ( n N )。11)1(1 NINeNNNINNeI 11)1(121*可取可取0* NNNIIEN, ,时时当当1 Introduction: Spread & Accumulation632120560)1(11367879440)

14、1(21.0838771150)1(1110773517320)1(1210717792140)1(1310668702200)1(1410638169180)1(151042746233016116121*1*0*2*1*11*10*12*11*13*12*14*13*15*14*15.II.II.II.II.II.II.II.eI 取取 We just got lucky?1 Introduction: Spread & Accumulation考察反推一步的误差：考察反推一步的误差：|1)1 (1)1 (1|*1NNNNENININE 以此类推，对以此类推，对 n 6 log6，即，即

15、n 6，应取，应取 * = 3.14159。3 函数的误差估计函数的误差估计 /*Error Estimation for Functions*/问题问题：对于：对于 y = f (x)，若用，若用 x* 取代取代 x，将对，将对y 产生什么影响？产生什么影响？分析分析：e*(y) = f (x*) f (x) e*(x) = x* xMean Value Theorem= f ( )(x* x)x* 与与 x 非常接近时，可认为非常接近时，可认为 f ( ) f (x*) ，则有：，则有：|e*(y)| | f (x*)|e*(x)|即：即：x*产生的误差经过产生的误差经过 f 作用后被放大

16、作用后被放大/缩小了缩小了| f (x*)|倍。故称倍。故称| f (x*)|为为放大因子放大因子 /* amplification factor */ 或或 绝对条件数绝对条件数 /* absolute condition number */.3 Error Estimation for Functions*)()(*| )(|xfyey*er *)(*| )(|xxex*er )(*)(*)(*)(*)(*)(xexfxfxxxxxfxxxxfxfr 相对误差条件数相对误差条件数 /* relative condition number*/ f 的条件数在某一点是的条件数在某一点是小小大大

17、，则称，则称 f 在该点是在该点是好条件的好条件的 /* well-conditioned */ 坏条件的坏条件的 /* ill-conditioned */。注：关于多元函数注：关于多元函数 的讨论，请参阅教的讨论，请参阅教材第材第5、6页。页。).,(21nx,x,xfy 3 Error Estimation for Functions例例:计算计算 y = ln x。若。若 x 20，则取，则取 x 的几位有效数字可保证的几位有效数字可保证 y 的相对误差的相对误差 0.1% ?*ln| )(*| )(*|*)(*)(*| )(|xxexexyxyxy*errr 解：解：设截取设截取 n

18、 位有效数字后得位有效数字后得 x* x，则，则估计估计 x 和和 y 的相对误差上限满足近似关系的相对误差上限满足近似关系)(*ln)(*yxxrr %1 . 0*ln102111 xan不知道怎么办啊？不知道怎么办啊？x 可能是可能是20.#，也可能，也可能是是19.#，取最坏情况，取最坏情况，即即a1 = 1。 n 4例：例：计算计算 ，取，取 4 位有效，即位有效，即 , 则相对误差则相对误差 9820ln)8920ln(. %.1010029820ln9820ln8920ln5 4 几点注意事项几点注意事项 /* Remarks */1. 避免相近二数相减避免相近二数相减 (详细分析

19、请参阅教材详细分析请参阅教材p.6 - p.7)例：例：a1 = 0.12345，a2 = 0.12346，各有，各有5位有效数字。位有效数字。 而而 a2 a1 = 0.00001，只剩下，只剩下1位有效数字。位有效数字。 几种经验性避免方法：几种经验性避免方法：;xxxx ;1lnlnln xxx当当 | x | 1 时：时：;2sin2cos12xx .6121112xxxex更多技巧请见教材第更多技巧请见教材第8页习题页习题6。4 Remarks2. 避免小分母避免小分母 : 分母小会造成浮点溢出分母小会造成浮点溢出 /* over flow */3. 避免大数避免大数吃吃小数小数例：

20、例：用单精度计算用单精度计算 的根。的根。010)110(992 xx精确解为精确解为110291 x,x 算法算法1 1：利用求根公式利用求根公式aacbbx242 在计算机内，在计算机内，109存为存为0.1 1010，1存为存为0.1 101。做加法时，做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即两加数的指数先向大指数对齐，再将浮点部分相加。即1 的指数部分须变为的指数部分须变为1010，则：，则：1 = 0.0000000001 1010，取，取单精度时就成为：单精度时就成为： 109+1=0.10000000 1010+0.00000000 1010=0.1000000

21、0 1010大数大数吃吃小数小数024,102422921 aacbbxaacbbx4 Remarks算法算法2：先解出先解出 再利用再利用9211024)( aacbbsignbx11010991221 xacxacxx求和时求和时从小到大从小到大相加，可使和的误差减小。相加，可使和的误差减小。例：例：按从小到大、以及从大到小的顺序分别计算按从小到大、以及从大到小的顺序分别计算1 + 2 + 3 + + 40 + 1094. 先化简再计算，减少步骤，避免误差积累。先化简再计算，减少步骤，避免误差积累。一般来说，计算机处理下列运算的速度为一般来说，计算机处理下列运算的速度为 exp ,5. 选

22、用稳定的算法。选用稳定的算法。HW: p.8-9 #1, #7Self-study Ch.2-1 Excuses for not doing homeworkI accidentally divided by zeroand my paper burst into flames. Lab 01. Numerical Summation of a Series Produce a table of the values of the series (1)for the 3001 values of x, x = 0.0, 0.1, 0.2, , 300.00. All entries of th

23、e table must have an absolute error less than 1.0e-10. This problem is based on a problem from Hamming (1962), when mainframes were very slow by todays microcomputer standards. InputThere is no input.Output The output is to be formatted as two columns with the values of x and (x) printed as in the C fprintf: fprintf(outfile,%6.2f%16.12fn,x,psix); /* hererepresents a space */ 1)(1)(kxkkx As an example, the sample output below shows 4 acceptable lines out of 3001, which might appear in the output file. The values of