提问:数值分析是做什么用的? 输入复杂问题或运算 数值 Ax= b 分析 ∫(x)dx ∫(x), 近似解计算机 +×
• 提问：数值分析是做什么用的？ 数值 分析 输入复杂问题或运算 ( ) , ( ), ...... , , ln , , f x dx d f x dx x a x Ax b b a x = + − 近似解 计算机
第一章误差/Eror §1误差的背景介绍/ ntroduction 来源与分类/ Source& Classification 从实际问题中抽象出数学模型 模型误差 Modeling Error- 通过测量得到模型中参数的值 观测误差/ Measurement error 求近似解—方法误差(截断误差/ Truncation Error+) >机器字长有限—舍入误差/* Roundoff error
第一章 误差 /* Error */ §1 误差的背景介绍 /* Introduction */ 1. 来源与分类 /* Source & Classification */ ➢ 从实际问题中抽象出数学模型 —— 模型误差 /* Modeling Error */ ➢ 通过测量得到模型中参数的值 —— 观测误差 /* Measurement Error */ ➢ 求近似解 —— 方法误差 (截断误差 /* Truncation Error */ ) ➢ 机器字长有限 —— 舍入误差 /* Roundoff Error */
8 1 Introduction: Source Classification The 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 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 number 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. Therefore 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. That 's 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 tries to sum the infinite series wWhat do you mean, strange?asked Von Neumann Thats how i did it
§1 Introduction: Source & Classification The 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 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 number 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. Therefore 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. That's 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 tries to sum the infinite series." "What do you mean, strange?" asked Von Neumann. "That's how I did it!
1 Introduction: Source Classification 例:近似计算。e dx=0.747. 解法之一:将e作 Taylor展开后再积分 ed=(1-x2+ 十 2!3:4! 32!53!74!9 取Jd≈S4, 4 R/* Remainder *I 则R由留下部分截断误差/ Truncation Error r* included terms * 这里灬,引起 由截去部分 I excluded terms * S,=1 ≈1-0.333+0.1 1042 引起 舍入误差/ Roundoff error+|<00009×2=0001 计算∫”的总体误差000100
§1 Introduction: Source & Classification e dx x − 1 0 2 例:近似计算 大家一起猜？ − e dx 2 x 1 0 1 / e 1 解法之一：将 作Taylor展开后再积分 2 x e − = − + − + − = − + − + − − 9 1 4! 1 7 1 3! 1 5 1 2! 1 3 1 1 ) 2 ! 3! 4! (1 1 0 4 6 8 2 1 0 dx x x x e dx x 2 x S4 R4 , /* Remainder */ 1 0 4 − e dx S 2 x 取 则 = − + 11 1 5! 1 9 1 4! 1 R4 称为截断误差 /* Truncation Error */ 0 005 9 1 4! 1 4 这里 R . 1 0 333 0 1 0 024 0 743 42 1 10 1 3 1 S4 = 1− + − − . + . − . = . | 舍入误差 /* Roundoff Error */ | 0.0005 2 = 0.001 0 005 0 001 0 006 1 0 2 e dx . . . -x + = 计 算 的总体误差 = 0.747… … 由截去部分 /* excluded terms */ 引起 由留下部分 /* included terms */ 引起
1 Introduction: Spread accumulation 2.传播与积累/ Spread& Accumulation 例:蝴蝶效应——纽约的一只蝴蝶翘膀一拍,风和日丽的北京 就利起台风来了?! BJ 以上是一个病态问题/i- posed problem 关于本身是病态的问题,我们还是留给数学家去头痛吧
§1 Introduction: Spread & Accumulation 2. 传播与积累 /* Spread & Accumulation */ 例：蝴蝶效应 —— 纽约的一只蝴蝶翅膀一拍，风和日丽的北京 就刮起台风来了？！ NY BJ 以上是一个病态问题 /* ill-posed problem*/ 关于本身是病态的问题，我们还是留给数学家去头痛吧！
8 1 Introduction: Spread Accumulation 例:计算 x"ed,n=0,1,2 0 公式 =2,ch=1-1206212m为 e 注意此公式精确成 则初始误差|E0|=0-(2<0.5×103 立 xn·e"d<lI<-xn·edx <I< 0 e(+1 n+1 =1-1·l=0.36787944 What 10=1-10.,=0.08812800 happened 1=1-11·1o=0.03059200 I",=1-12·I,=0.63289600 13=1-13.I12=-7.2276480 1=1-1413=94.959424! I=1-15I,=-14233914!!
§1 Introduction: Spread & Accumulation 0 1 2 ...... 1 1 0 x e dx , n , , , e I n x n = = 例：计算 n = 1− n−1 公式一： I n I 注意此公式精确成 立 0 63212056 1 1 1 1 0 0 . e e dx e I x = = − 记为 * 0 I 8 0 0 0 0 5 10 − 则初始误差 E = I − I . 1 1 1 1 1 1 1 1 0 0 1 0 + + n I e(n ) x e dx e x e dx I e n n n n 1 1 5 14233914 1 1 4 9 4 959424 1 1 3 7 2276480 1 1 2 0 63289600 1 1 1 0 03059200 1 1 0 0 08812800 ............ 1 1 0 36787944 1 5 1 4 * 1 3 * 1 4 * 1 2 * 1 3 * 1 1 * 1 2 * 1 0 * 1 1 * 9 * 1 0 * 0 * 1 I I . I I . I I . I I . I I . I I . I I . = − = − = − = = − = − = − = = − = = − = = − = ? ?? ? ! ! ! What happened ?!
8 1 Introduction: Spread Accumulation 考察第步的误差En En|=|In-In|=|(1 )-(1-nIm1)|=nEn n!|E0 可见初始的小扰动|E|<0.5×1038迅速积累,误差呈递增走势。 造成这种情况的是不稳定的算法/ unstable algorithm 我们有责任改变。 a公式二:In=1-nln-1→In-1=-(1-Ln) 方法:先估计一个Ⅰ,再反推要求的n(n<<N) 注意此公式与公式 N+1 在理论上等价。 可取 2e(n+1)N+ 当N→+∞时,EN Ix|→0
§1 Introduction: Spread & Accumulation 考察第n步的误差 En | | | | |(1 ) (1 )| * 1 1 * n = n − n = − nIn− − − nIn− E I I !| | 1 n E0 n |E | = n− == 我们有责任改变。 造成这种情况的是不稳定的算法 /* unstable algorithm */ 可见初始的小扰动 | E0 | 0.510−8 迅速积累，误差呈递增走势。 (1 ) 1 n 1 n 1 n 1 n I n 公式二： I = − n I − I − = − 注意此公式与公式一 在理论上等价。 方法：先估计一个IN ,再反推要求的In ( n << N )。 1 1 ( 1) 1 + + N I e N N N N I e N N I + + + = 1 1 ( 1) 1 2 * 1 可取 0 当N → + 时, EN = I N − I N * →
8 1 Introduction: Spread& Accumulation 取 +|≈0.042746233 e·1616 We just got lucky? 15)≈0.063816918 15 (1-l14)≈0.066870220 14 12=(1-l3)≈0.071779214 1-12)≈0.077351732 12 (1-I1)≈0.083877115 I1=3(1-l2)≈036787944 In=(1-1) ≈0.63212056
§1 Introduction: Spread & Accumulation ( 1 ) 0 63212056 11 ( 1 ) 0 36787944 21 ( 1 ) 0 083877115 111 ( 1 ) 0 077351732 121 ( 1 ) 0 071779214 131 ( 1 ) 0 066870220 141 ( 1 ) 0 063816918 151 0 042746233 161 16 1 21 *1 *0 *2 *1 * 1 1 * 1 0 * 1 2 * 1 1 * 1 3 * 1 2 * 1 4 * 1 3 * 1 5 * 1 4 * 1 5I I . I I . I I . I I . I I . I I . I I .. e I = − = − = − = − = − = − = − + = 取 We just got lucky?
8 1 Introduction: Spread Accumulation 考察反推一步的误差: E E 以此类推,对n<N有: E E N(N-1)…(n+1) 误差逐步递减这样的算法称为稳定的算法/ stable algorithm 在我们今后的讨论中,误差将不可回避, 算法的稳定性会是一个非常重要的话题
§1 Introduction: Spread & Accumulation 考察反推一步的误差： | | 1 (1 ) 1 (1 ) 1 | | * N 1 N N EN N I N I N E − = − − − = 以此类推，对 n < N 有： | | ( 1) ...( 1) 1 | | n EN N N n E − + = 误差逐步递减, 这样的算法称为稳定的算法 /* stable algorithm */ 在我们今后的讨论中，误差将不可回避， 算法的稳定性会是一个非常重要的话题
§2误差与有效数字/ Error and Significant Digits >绝对误差/ absolute error e=x-x其中为精确值,x为x的近似值。 e^|的上限记为e,称为绝对误差限/ accuracy+, 工程上常记为5击21,留进 e-d=0.743±0006 注:e理论上讲是唯一确定的,可能取正,也可能取负。 E*>0不唯一,当然s*越小越具有参考价值。 Of course mine is more accurate! The accuracy ○ relates to not only the absolute error but also to the size of the exact value
§2 误差与有效数字 /* Error and Significant Digits */ ➢ 绝对误差 /* absolute error */ e = x − x * * 其中x为精确值，x *为x的近似值。 Hey isn’t it simple? Oh yeah? Then tell me the absolute error of 0.743 1 0 2 − e dx Oops! x | | * e * ε = − 1 0 0 743 0 006 2 e dx . . * * x 工程上常记为 x = x ε ，例如： 的上限记为 ，称为绝对误差限 /* accuracy */， 注：e* 理论上讲是唯一确定的，可能取正，也可能取负。 e > 0 不唯一，当然 e 越小越具有参考价值。 I can tell that this part’s diameter is 20cm1cm. I can tell that distance between two planets is 1 million light year ±1 light year. Of course mine is more accurate ! The accuracy relates to not only the absolute error, but also to the size of the exact value