数值分析庆课件群共享第一章

1、Introduction to Numerical AnalysisChapter 1: Introduction庆本人所有2015 年 9 月 7 日庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日1 / 65及作业：数值分析（第三版），2012年3月印刷（有部分修订）。参考书：数值分析全真试题（2007-2012）。无责任: 在校本部上课的学生，可让他们去校礼堂东楼北20米的书库去买书；九龙湖上课的学生还请您让班长统计一下人数然后和我，我直接送过去。书售价定为：单买数值分析，35元（80折）；单买数值分析全真试题

2、解析，25元（74 折）；数值分析+数值分析全真试题解析，55元（71折）。比重：期末80，课堂作业10，上机作业10（至少交5次，程序+数值结果+心得+纸质版）。信箱：liyq.庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日2 / 65Q1：什么是数值分析？（1）传统称谓：数值分析（Numerical Analysis）；最新叫法：科学计算（Scientific Computing）；主要目的：很多领域（尤其是科学研究和工程领域）中所提出的数学问题进行数值算法的设计与分析。：Modern scientific c

3、omputing using electronic computershas its origin in research and developments during the secondworld war （20世纪40年代末50年代初，数值分析作为的数学分现，这是现代科学计算的真正）。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日3 / 65Q1：什么是数值分析？（2）功用：The new capabilities（能力）of performing millions of operations led to

4、 new classes of algorithms, which needed a careful analysis to ensure their accuracy and stability（计算能力的提高-¿问题规模的扩大-¿新的算法-¿必须分析这些算法的 精确性和稳定性）。：As a rule, applications lead to mathematical problemswhich in their complete form cannot be conveniently solved with exact formulas, unless on

5、e restricts oneself to specialcases or simplified ms.（实际应用导出了很多的数学问题，通常而言，这些问题很难找到一个确定的公式解，除非把问题做很多的限制或者简化模型）！庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日4 / 65Q1：什么是数值分析？（3）策略：In many cases, one thereby reduces the problem to a linear problemfor example, a linear system of differ

6、ential equations. Such an approach can quite often lead to concepts andpoints of view which, at least qualitatively, can be used even in the unreduced problems.先将复杂问题简单化，构造相应的数值算法，再应用在一般问题上（需要一定程度的变化），对很多问题来说，都是一条值得尝试的解决方案。地位：计算机硬件的发展（速度更快、了数值方法的应用范围，但这不是全部更大）大大的刺激。Gains in problemsolving capabiliti

7、es through better mathematical algorithmshave in many cases played an equally important role!庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日5 / 65Q1：什么是数值分析？（4）现状：Today one can treat much more complex and less simplified problems through massive amounts of numericalcalculations. Adva

8、nced mathematical ms and methods arenow used more and more also in areas like medicine, economics and social sciences. It is fair to say that today experiment and theory, the two classical elements of scientific method, in many fields of science and engineering are supplemented bycomputations as an

9、equally important component. （数值模拟已经同实验、理论研究一起成为科学研究的三大）。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日6 / 65Q1：什么是数值分析？（5）数值分析具有的主要特点：特点1：同一般计算机科学不同，它处理的是连续量。特点2：同一般的论科学不同，它强调近似效果。通常而言，数值算法和数值计算本身都是近似的，因此数值计算的基本要求就是：准确(Accurate) 、快速(Fast)、可靠(Reliable)。换句话说：这是一座桥梁？庆 (本人所有)Introducti

10、on to Numerical Analysis Chapte2015 年 9 月 7 日7 / 65Q2：为什么我们需要科学计算？理由1：很多连续的数学问题没有办法精确求解。例如：Z1ex2 dx0无法精确计算，但它非常重要，同概率中的正态分布有关。理由2：理论求解往往通过一个无限的过程来完成，因此理论 解可能不具有实际操作性！例如：分析迭代序列xk+1 = (xk )极限是否存在时，我们通常会取极限。理由3：随着科技的发展，问题的规模越来越大，理论求解往往 为力，通常会借助计算机完成某些研究。此时，The errorcan not be avoided！（记住这句话？）理由n：庆 (本人所

11、有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日8 / 65计算模拟计算模拟就是利用计算机来实现或者模拟或过程。基本工具：computer！（了解计算机如何“想”是一个前提？）研究的传统方法：理论研究，观察，实验等。Q3：现在，我们为什么需要计算模拟？传统方法可能很难或者不可能完成研究，如两个黑洞的碰撞。1数值模拟能够比传统方法更快、更、更安全的解决“常规问2题”，比如在计算机上进行汽车的碰撞实验要比实际碰撞要更便宜、更安全，也更容易得到精确的设计参数。3庆 (本人所有)Introduction to Numerical Ana

12、lysis Chapte2015 年 9 月 7 日9 / 65Q4：如何进行计算模拟？数学建模（非常关键的一步）；设计数值算法（我们课程主要关注的部分）；实现算法（一个“好”的实现更重要，什么是好？）；实际模拟；表示结果；解释并确认计算结果，如果需要，重复某些或者全部步骤!123456庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日10 / 65Q5：以上步骤具有什么样的关系？Each aspect affects and is affected by the others！特别是第一步：数学建模！物理规律通常有其

13、适用的范围，超出这个范围，物理规律就会 发生变化，进而物理模型也会随之发生变化。正确的理解问题，然后再去建模（建模需要简化，但不能想当然？）。物理问题到数学模型需要简化，简化的原则是什么？（问题的主要部分，“站位”要正确？）。总而言之，the problems affect the computational process.只有正确理解问题，正确的描述问题，才能构建合理的算法！7庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日11 / 65Q6：拿到一个问题，“好”问题还是“坏问题？一个“好”问题（well-pos

14、ed ）的要求：解存在、唯一、并连续依赖于数据。（传统意义？）Q7：什么是连续依赖性？粗略地，输入数据的轻微扰动没有引起输出的大幅度变化。一个“坏”（ ill-posed）问题则不具备上述性质。特别注意：一个“坏”问题是不能奢望通过算法改变其内在性质的！只能通过转化，将 ill-posed 问题转化成 well-posed 问题再解决（出身很重要。？）。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日12 / 65ffffff ”好坏”问题举ff 例微分是非常敏感的，数据的微小扰动会使结果产生很大变化。ffff是一个

15、相对平滑的过程，具有很强的稳定性！对比图：Two functions whose integrals equal but derivatives notffff. . . . . . . . . . . . . . . . . . . . . . . . . . 2015 年 9 月 7 日13 / 65 ff庆 (本人所有)Introduction to Numerical Analysis ChapteQ8：我们对数值算法的期望是什么？基本期望：accurate（精确）; quick（快速）; robust（稳健）;the programming is not too hard（实现不太复

16、杂）; transplantable（可移植性）.12345这些要求，是设计算法时必须关注的内容，除此之外：It is natural to look forward to those discrete systems which preserve as much as possible intrinsic properties of the continuous system.By K. Feng (1985)庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日14 / 65Q9：计算模拟中的基本策略是什么？词汇：Re

17、placing！具体则是：无限-有限1无限的过程-有限的过程微分方程-代数方程非线性问题-线性问题高维问题-低维问题复杂函数-简单函数一般矩阵问题-特殊矩阵问题2345678总而言之，“解决不了的”变成“能解决的”？庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日15 / 65Q10：如何使用这些基本策略呢？例如：非线性微分方程 非线性代数方程 线性代数方程 特殊形式的线性系统。（不唯一？）基本原则：Solutions unchanged, or at least within some required toler

18、ance of the true solution.You need:An alternative problem, or class of problems, that is easier solve.A transformation of the given problem into a problem of thisalternative type that preserves the solution in some sense.1to2具体问题具体分析！庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日16

19、/ 65Q11：误差的来源有哪些呢？（1）Before a computation begins:Ming.1Empirical measurements.Previous computations.23During computation:Truncation or discretization.（截断误差） Rounding（舍入误差）.12一个故事：The first American Venus probe was lost due to a program fault caused by the inadvertent substitution of a statement in a

20、 Fortran program of the form DO 3 I = 1.3 for one of the form DO 3 I = 1,3. The erroneous replaced comma“,”with adot“.”converts the intended loop statement into an assignment statement!（循环变成了赋值!） 庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日17 / 65Q11：误差的来源有哪些呢？(2)最终误差：combination

21、all or part of them.误差可能会被放大，可能源自于问题本身，也可能是算法的问题。必须做简单的误差分析，了解误差的大致。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日18 / 65Q12：如何衡量误差的大小？误差的意义与其度量或者计算的量的大小有关系！比如人口普查时的误差 1 的意义要远远小于一个房间里人数的误差 1 的意义（点名？）。设 x 是的某个近似值，则：x 绝对误差 Absolute error e = x x（真实值减去近似值）.相对误差 Relative error er = e .x

22、 误差可正可负。真实值通常是未知的，这时候我们需要考虑误差限。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日19 / 65Q13：什么是误差界（限）？如果 |e| ，则 称为绝对误差 e 的一个绝对误差限。找到其误差限或者估计其大小比精确计算更有意义。同样有相对误差限：|er | r .需要指出的是，我们总是期望误差限越小越好，但这通常很难做到。基本上所有的误差估计都是“悲观”估计。e通常会用 e = e ，这是“合理（都有前提？）”的：¯rrxx x(x x )2e2x xre¯r er =x

23、x = 1 erxx 庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日20 / 65Q14：Precision 和 Accuracy 有什么区别？在进一步讨论误差之前，先区分这两个概念：精度（Precision）与所表示的数的数字个数有关。准确度（精确度）（Accuracy）与近似某个量时的有效数字的个数有关，同相对误差有关！例如：3.25603764689720 是一个精度很高的数字，但是将其作为 的近似值，显然是很确的。精度更可以看做是系统提供的，如计算机里的单、双精度。当用给定的精度去计算一个量时，绝对不能说明

24、结果可以达到那个精确度！庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日21 / 65Q15：什么是有效数字（significant digits）？significant digits（源自Wiki）：Those digits that carry meaning contributing to its accuracy, this includes all digits except:leading and trailing zeros (unless a decimal point is present) wh

25、ere they serve merely as placeholders to indicate the scale of the number;spurious digits introduced, for example, by calculations carried outto greater accuracy than that of the original data, or measurements reported to a greater precision than the equipment supports.12因此，在分析有效数字之前，必须要明了其来源。关于有效数字

26、，有更为详细的定义方式，随后介绍。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日22 / 65Q16：数据误差和计算误差有何不同？有些误差是由初始数据（测量、预处理等）引起的，有些误差是在随后的计算过程（截断、舍入）中引入的。一般情况下，我们暂不分析舍入误差（见第三节）。以计算函数值 f (x ),f : R R 为例：如果 x x,f f ，那么：f (x ) f (x ) = f (x ) f (x ) + f (x ) f (x ).f (x ) f (x ) 称为计算误差（computational err

27、or）。f (x ) f (x ) 称为遗传误差（propagated error）。要减少误差，必须从这两方面入手，减少两部分误差。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日23 / 65Q17：计算误差主要指什么？分析计算误差时主要考虑截断误差（Truncation error）：真实结果与给定算法经精确计算得到的结果之间的差。一般由无穷级数的截断、有限差分代替导数、迭代收敛序列终 止迭代等产生！例 6 ：有限差分格式：f 0(x ) f (x + h) f (x ) .h根据Taylor展开：f (x +

28、 h) = f (x ) + f 0(x )h + f 00( )h2/2.截断误差界为：Mh/2，其中 M 是导数在 x附近的界。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日24 / 65Q18：如何分析误差？首先强调一点：如果输入数据只精确到4位有效数字，那么无 论随后的计算多么精确，结果的有效数字也超过4位！ 所谓的“废料进，废料出”（Garbage In，Garbage Out）！以计算函数值 f (x ) 为例，实际计算中得到 y，则：y = y y 称为向前误差 forward error；1如果 f

29、 (x) = y，则 x = x x 称为误差 backward error。2一般来说，误差是一个更为有用的工具。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日25 / 65向前误差误差图示fx . .f (x).|forward error.f.backward error.|.|.f. .xf (x) = f (x). 庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日26 / 65 Q19：如何图示向前误差误差？Q20：什么是浮点数

30、？例如：2347 和 0.0007396 可以写成 2.347 × 103, 7.396 × 104等。这种格式下，小数点随着通常来说，一个浮点10 的幂次的变化而移动或浮动。具有如下的几个量： Base or radix;p Precision;L, U Exponent range.123ddp11Ex =(d + · · · +) , 0 d 1, E integer±0ip1L E U.括号中的部分用 进制数值 d0d1 · · · dp1 表示，称为尾数或则称为指数。者有效数字（！），E庆 (本

31、人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日27 / 65Q21：何谓标准化（Normalization）？通常取 = 2。Normalization：d0 非 0，除非表示的数字为 0。优点：The representation of each number is then unique. No digits are wasted on leading zeros, thereby precision.izingThe leading bit is always 1 and thus need not be store

32、d.基于以上优点，一般的浮点系统都是要正规化的。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日28 / 65能精确表示的浮点数的总个数为：2( 1)p1(U L + 1) + 1.浮点是一个有限离散系统。上溢 overflow: OFL = U+1(1 p)，最大数。下溢 underflow: UFL = L，最小正数。在浮点数范围内，浮点数并不均匀分布，但在 的相同幂次间均匀分布。如图：.Floating system 举例. . . . . . . . .432101234ff庆 (本人所有)Introduct

33、ion to Numerical Analysis Chapte2015 年 9 月 7 日29 / 65Q22：浮点具有什么样的性质呢？Q23：舍入误差是怎么来的？数指的是能被浮点系统准确表示的数，只有有限个！x 不是数，由其附近的某个浮点数近似表示，为 fl(x )。Q24：近似规则有哪些呢？截断（chop）：将 x 的 基底展开的第 p 1 位以后的又称round toward zero。四舍五入法（Round to nearest）：fl(x ) is the nearest floating-point number to x ;In case of a tie, we use th

34、e floating-point number whose last stored digit is even, round to even.，庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日30 / 65Q25：有效数字能否有其他的定义方式？标准化浮点中，尾数又称为有效数字。注意末尾的0!一个经常的问题：x 是的近似值，x 具有几位精度？x 有效数字的其他定义：如果近似值x的绝对误差限是其某一位的半个，且该位直到x的第一位非零数字之间共有n位，则称x具有n位有效数字, 用这n位有效数字表示的近似数称为有效数。庆 (

35、本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日31 / 65关于有效数字的进一步的例子（1）例：如 的近似值取 x1 = 3.14，则：| 3.14| = 0.0012926 · · · < 1/2 × 102 = 0.005所以如取x1 有 3 位有效数字！x2 = 3.1416，则14| x | < 000005 =× 10 ,.22所以如取x2 有 5 位有效数字;x3 = 3.1415，则13 x | = 000009 · · &#

36、183;< 00005 =× 10 ,|.32所以x3 只有 4 位有效数字.庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日32 / 65关于有效数字的进一步的例子（2）例：x = 0.045113, x = 0.04518，问具有几位有效数字？方法：x 0.5 × 104 < |x x | = 0.000067 < 0.5 × 103,因此具有 2 位有效数字 -0.045。庆 (本人所有)Introduction to Numerical Analysis Cha

37、pte2015 年 9 月 7 日33 / 65Q26：什么是precision）(1)？精度（Machine精度：满足 fl(1 + ) > 1 最小的正 。精度说明了一个非 0 实数最大可能的相对误差，即：fl(x ) x .mach x这句话可理解为如果两个数的相对误差比计算机而言，它们是一个数。精度还小，则对精度还有其他定义，可能略微不同，但其根本都是对浮点颗粒性的度量。通常有关系式：0 < UFL < mach < OFL。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日34 / 6

38、5Q26：什么是precision）？(2)精度（Machine中的eps函数:eps Spacing of floating point numbers. D = eps(X), is the positive distance from ABS(X) to the next larger in magnitude floating point number of the same precision as X. X may be either double precision or single precision. For all X, eps(X) is equal to eps(AB

39、S(X).eps, with no arguments, is the distance from 1.0 to the next largerdouble precision number, that is eps with no arguments returns 252.庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日35 / 65Q27：浮点运算同普通的代数运算和不同？+, , ×, ÷ 都不再精确！一些熟知的结理论不再成立，如加法的结合律不再成立！两个浮点数的运算也不一定产生另一个浮点数

40、！比如 + 法，先对指数，然后再操作尾数，有可能大数吃小数！浮点运算都是 fl(x op y ) = (x op y )(1 + ) 的形式。浮点运算是一个复杂的运算过程，应尽可能的主动去避免一些糟糕情形的发生！庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日36 / 65Q28：如何分析数据误差的影响？（1）设 x1, x2 为准确值，y = f (x1, x2)，x1, x2 为对应的近似值，y = f (x1, x2)，分析二元函数的误差：e(y )。Taylor 展开得到：由二元函数e(y )= y y =

41、f (x1, x2) f (x1, x2)f (x , x )f (x , x )1 2x11 2(x x ) +(x x ),1212x2即是：f (x , x )f (x , x )1 2x11 2x2e(y ) e(x ) +e(x ).12庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日37 / 65Q28：如何分析数据误差的影响？（2）相对误差：f er (y ) = e(y )(x , x )x1 21e (x )r1x1f (x1, x2)yf (x1, x2)x2x2f (x1, x2) er (x2

42、).+利用上述两个关系式，可以分析和差积商的关系式。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日38 / 65Q28：如何分析数据误差的影响？（3）具体结果为：e(x1 + x2) = e(x1) + e(x2),e(x1 x2) = e(x1) e(x2),e(x1x2) x2e(x1) + x1e(x2), x 1x11ee(x ) e(x ),12x2x2x 22 x x12e (x + x ) e (x ) +e (x ),r12r1r2x1 + x2x1 + x2 x1x2er (x1 x2) er (

43、x1) er (x2),x1 x2x1 x2er (x1x2) er (x1) + er (x2), x1e e (x ) e (x ).rr1r2x2庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日39 / 65数据误差分析举例（1）例：设 x1 = 2001，x2 = 1999，x1 = 44.7325，x2 = 44.7102，已知 x1, x2 分别是 x1, x2 的具有 6 位有效数字的近似值。计算 2001 1999，现有下面两种算法：方法 1：1x1 x2 x1 x2 = 44.7325 44.710

44、2 = 0.0223.方法 2：x1 x2=2 2 2x1 + x2 244.7325 + 44.7102=x1 + x2= 0.0223606845 · · · .试分析上述两种算法所得结果的有效数字。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日40 / 65数据误差分析举例（2）由条件得11|e(x1)| 2 × 104,|e(x2)| 2 × 104.|e(x1 x2)| = |e(x1) e(x2)| |e(x1)| + |e(x2)|1114443 2

45、× 10+ 2 × 10= 10< 2 × 10.因此方法 1 所得结果至少具有 2 位有效数字。输入数据有 6 位有效数字，输出结果只具有 2 位有效数字。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日41 / 65数据误差分析举例（3）22|e( x1 + x2 )| (x1 + x2)2 e(x1 + x2)|=2| (x1 + x2)2 e(x1) + e(x2)|2(x1 + x2)2 |e(x1)| + |e(x2)| 21144× 10 +× 1

46、0(44.7325 + 44.7102)22217725 × 10 <× 100.2按方法 2显然方法得到的结果至少具有 6 位有效数字。2 优于方法 1，为什么会如此？庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日42 / 65Q29：什么导致了不精确的解？一个不精确解的出现并不一定是源自一个不好的算法，也很有可能源自问题本身！重述：问题条件性的概念：A problem is said to be insensitive, or well-conditioned, if a given

47、relative change in the input data causes a reasonably commensurate relative change in the solution. A problem is said to be sensitive, or ill-conditioned, if the relative change in the solution can be much larger than that in the input data.ill-conditioned 的问题和不稳定的数值算法都可能导致不精确解的出现。要避免不精确解，必须两个方面都要考虑

48、。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日43 / 65Q30：如何去衡量一个问题的好坏呢？工具：条件数（Condition number），误差的放大因子！例如：对函数求值问题 y = f (x )，Condition number = |(f (x ) f (x)/f (x )| = |y/y | .|(x x)/x |x/x |上述称为相对条件数，当 x = 0 or y = 0，用绝对条件数|y |。|x |条件数的具体表和计算方法因问题而异。庆 (本人所有)Introduction to Numer

49、ical Analysis Chapte2015 年 9 月 7 日44 / 65Q31：能否举一个简单的 ill-posed 的例子？寻找多项式的实根的数目就是一个坏问题。比如多项式p(x ) = x 4 x 2(2a 1) + a(a 1),当 a 连续变化时，根的个数则是不连续变化的。具体结果是：4 a 1;2 0 a < 1;0 a < 0.number of real roots =庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日45 / 65Q31：什么是算法的稳定性（Stability）？简

50、单地说，算法稳定性的概念同问题的条件性概念是类似的， 也与扰动的影响有关。粗略地讲，一个算法称为是 stable 的， 指的是它的结果对计算过程中所产生的近似扰动相对不敏感。对于某一种算法，如果初始数据很小的误差仅使最终结果产生 较小的误差，则称该算法是数值稳定的, 否则称为不稳定的。insensitive problem + stable algorithm accurate result!设计稳定性好的算法是算法设计的目标之一。庆 (本人所有)Introduction to Numerical Analysis Chapte2015 年 9 月 7 日46 / 65Q32：能否给出一个算法不稳定的例子？（1）例：建立计算Z1xnex 1dxI(n = 0 1 2 · · ·。, , , 20n =)0的递推公式，并研究其误差利用分部得到：In = 1 nIn1.则可以得到算法：I0= 1 e1In= 1 nIn