提问：计算方法是做什么用的？ 输入复杂问题或运算 数值 分析     计算机 近似解.

Presentation on theme: "提问：计算方法是做什么用的？ 输入复杂问题或运算 数值 分析     计算机 近似解."— Presentation transcript:

1 提问：计算方法是做什么用的？ 输入复杂问题或运算 数值 分析     计算机 近似解

2 §1 数值计算方法的意义、内容与方法 20 世纪最伟大的科学技术发明---计算机 ， 计算机是对人脑的模拟，它强化了人的思 维智能；
§1 数值计算方法的意义、内容与方法 20 世纪最伟大的科学技术发明---计算机 ， 计算机是对人脑的模拟，它强化了人的思 维智能； 计算机的发展和应用，已不仅仅 是一种科学技术现象，而且成了一 种政治、军事、经济和社会现象；

3 算法的研究和应用正是本课程的主题 ！ 没有软件的支持，超级计算机只是一堆 废铁而已； 软件的核心就是算法。算法犹 如乐谱，软件犹如CD盘片，而硬 件如同CD唱机。

4 现代科学研究的三大支柱 理论研究 科学实验 科学计算 计算数学

5 21世纪信息社会的两个主要特征： “计算机无处不在” “数学无处不在” 21世纪信息社会对科技人才的要求： --会“用数学”解决实际问题 --会用计算机进行科学计算

6 科学计算解题过程 选取计算方法 建立数学模型 编写上机程序 计算得出结果

7 一、计算数学的产生和早期发展 计算数学是数学的一个古老的分支，虽然数学不仅仅 是计算，但推动数学产生和发展的最直接原因还是 计算问题。 二、二十世纪计算数学的发展 数值代数 概率统计计算 最优化计算 蒙特卡罗方法 数值逼近 微分方程的数值解法 计算几何 微分方程的反演问题

8 数值计算的主要内容 数值代数：方程求根、线性方程组求解、 特征值和特征向量的计算、非线性方程 组的求解； 数值逼近：插值、数值微分和积分、
最小二乘法； 微分方程数值解：常微分方程 数值解； 偏微分方程数值解： 差分法 有限元法、有限体积法

9 §2 算 法 一、算法的概念 定义：由基本运算及运算顺序的规定所构成的完 整的解题步骤，称为算法。
§2 算 法 一、算法的概念 定义：由基本运算及运算顺序的规定所构成的完 整的解题步骤，称为算法。 描述算法可以有不同的方式。例如，可以用日常语言和数学语言加以叙述，也可以借助形式语言（算法语言）给出精确的说明，也可以用框图直观地显示算法的全貌。

10 例1：一群小兔一群鸡，两群合到一群里，要数腿共48， 要数脑袋整17，多少小兔多少鸡？
算术方法 ： 代数方法 ： 若没有小兔，则鸡应是17只 设有x只小鸡，y只小兔 ， 总腿数 ：2＊17＝34 一只小兔增加 2条腿， 应该有 (-2)*(i) +(ii) , 得 高斯消去法 只小兔 只小兔 10只小鸡

11 二、算法的优劣  计算量小 例：用行列式解法求解线性方程组: n阶方程组，要计算n + 1个n阶行列式的值，
 存贮量少  逻辑结构简单

12 §3 误差的背景介绍 3.1. 来源与分类 从实际问题中抽象出数学模型 —— 模型误差 通过测量得到模型中参数的值 —— 观测误差
§3 误差的背景介绍 3.1. 来源与分类 从实际问题中抽象出数学模型 —— 模型误差 通过测量得到模型中参数的值 —— 观测误差 求近似解 —— 方法误差 (截断误差） 机器字长有限 —— 舍入误差

13 称为截断误差 /* Truncation Error */ 由留下部分 引起 由截去部分 引起
例：近似计算 = 0.747… … 解法之一：将 作Taylor展开后再积分 大家一起猜？ 1 / e 1 S4 R4 /* Remainder */ 取 则 称为截断误差 /* Truncation Error */ 由留下部分 /* included terms */ 引起 由截去部分 /* excluded terms */ 引起 | 舍入误差 /* Roundoff Error */ |

14 据说，美军 1910 年的一次部队的命令传递是这样的:
营长对值班军官: 明晚大约 8点钟左右，哈雷彗星将可能在这个地区看到，这种彗星每隔 76年才能看见一次。命令所有士兵着野战服在操场上集合，我将向他们解释这一罕见的现象。如果下雨的话，就在礼堂集合，我为他们放一部有关彗星的影片。 值班军官对连长: 根据营长的命令，明晚8点哈雷彗星将在操场上空出现。如果下雨的话，就让士兵穿着野战服列队前往礼堂，这一罕见的现象将在那里出现。 连长对排长: 根据营长的命令，明晚8点，非凡的哈雷彗星将身穿野战服在礼堂中出现。如果操场上下雨，营长将下达另一个命令，这种命令每隔76年才会出现一次。 排长对班长: 明晚8点，营长将带着哈雷彗星在礼堂中出现，这是每隔 76年才有的事。如果下雨的话，营长将命令彗星穿上野战服到操场上去。 班长对士兵: 在明晚8点下雨的时候，著名的76岁哈雷将军将在营长的陪同下身着野战服，开着他那“彗星”牌汽车，经过操场前往礼堂。

15 3.2. 传播与积累 例：蝴蝶效应 —— 纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！ 以上是一个病态问题 关于本身是病态的
NY BJ 以上是一个病态问题 关于本身是病态的 问题，我们还是留给数学家去头痛吧！

16 例：计算  公式一： 记为 则初始误差 注意此公式精确成立 What happened?! ? ?? ? ! ! !

17  公式二： 考察第n步的误差 迅速积累，误差呈递增走势。 可见初始的小扰动 我们有责任改变。
造成这种情况的是不稳定的算法 /* unstable algorithm */  公式二： 方法：先估计一个IN ,再反推要求的In ( n << N )。 注意此公式与公式一 在理论上等价。 可取

18 取 We just got lucky?

19 算法的稳定性会是一个非常重要的话题。 考察反推一步的误差： 以此类推，对 n < N 有：
误差逐步递减, 这样的算法称为稳定的算法 /* stable algorithm */ 在我们今后的讨论中，误差将不可回避， 算法的稳定性会是一个非常重要的话题。

20 3.3 误差与有效数字  绝对误差 其中x为精确值，x*为x的近似值。 ，例如： 工程上常记为 ，称为绝对误差限 的上限记为
3.3 误差与有效数字  绝对误差 其中x为精确值，x*为x的近似值。 ，例如： 工程上常记为 ，称为绝对误差限 的上限记为 注： e* 理论上讲是唯一确定的，可能 取正，也可能取负。e* > 0 不唯 一，当然 e* 越小越具有参考价值。

21  相对误差 /* relative error */
x 的相对误差上限 /* relative accuracy */ 定义为 A mathematician, a physicist, and an engineer were traveling through Scotland when they saw a black sheep through the window of the train. "Aha," says the engineer, "I see that Scottish sheep are black." "Hmm," says the physicist, "You mean that some Scottish sheep are black." "No," says the mathematician, "All we know is that there is at least one sheep in Scotland, and that at least one side of that one sheep is black!" Now I wouldn’t call it simple. Say … what is the relative error of 20cm±1cm? But what kind of information does that 5% give us anyway? Don’t tell me it’s 5% because… 注：从 的定义可见， 实际上被偷换成了 ，而后才考察其上限。那么这样的偷换是否合法？ 严格的说法是， 与 是否反映了同一数量级的误差？

22 有效数字 /* significant digits */
用科学计数法，记 （其中 ）。若 （即 的截取按四舍五入规则），则称 为有n 位有效数字，精确到 。 例： 问： 有几位有效数字？请证明你的结论。 证明： 有 位有效数字，精确到小数点后第 位。 4 3 注：0.2300有4位有效数字，而00023只有2位有效。12300如果写成0.123105，则表示只有3位有效数字。 数字末尾的0不可随意省去！

23 有效数字与相对误差的关系  有效数字  相对误差限 已知 x* 有 n 位有效数字，则其相对误差限为  相对误差限  有效数字 已知 x* 的相对误差限可写为 则 可见 x* 至少有 n 位有效数字。

24 例：为使 的相对误差小于0.001%,至少应取几位有效数字？
解：假设 * 取到 n 位有效数字，则其相对误差上限为 要保证其相对误差小于0.001%，只要保证其上限满足 已知 a1 = 3，则从以上不等式可解得 n > 6  log6，即 n  6，应取 * = 。

25 3.4 函数的误差估计 问题：对于 y = f (x)，若用 x* 取代 x，将对y 产生 什么影响？
3.4 函数的误差估计 问题：对于 y = f (x)，若用 x* 取代 x，将对y 产生 什么影响？ 分析：e*(y) = f (x*)  f (x) = f ’( )(x*  x) e*(x) = x*  x x* 与 x 非常接近时，可认为 f ’( )  f ’(x*) ，则有：|e*(y)|  | f ’(x*)|·|e*(x)| 即：x*产生的误差经过 f 作用后被放大/缩小了| f ’(x*)|倍。故称| f ’(x*)|为放大因子或 绝对条件数

26 /* relative condition number*/
相对误差条件数 /* relative condition number*/ f 的条件数在某一点是小\大，则称 f 在该点是好条件的 /* well-conditioned */ \坏条件的 /* ill-conditioned */。

27 x 可能是20.#，也可能是19.#，取最坏情况，即a1 = 1。
例:计算 y = ln x。若 x  20，则取 x 的几位有效数字可保证 y 的相对误差 < 0.1% ? 解：设截取 n 位有效数字后得 x*  x，则 估计 x 和 y 的相对误差上限满足近似关系 不知道怎么办啊？ x 可能是20.#，也可能是19.#，取最坏情况，即a1 = 1。  n  4 例：计算 ，取 4 位有效，即 , 则相对误差

28 3.5 几点注意事项 1. 避免相近二数相减  例：a1 = 0.12345，a2 = 0.12346，各有5位有效数字。
3.5 几点注意事项 1. 避免相近二数相减 例：a1 = ，a2 = ，各有5位有效数字。 而 a2  a1 = ，只剩下1位有效数字。  几种经验性避免方法： 当 | x | << 1 时： 

29 2. 避免小分母 : 分母小会造成浮点溢出 3. 避免大数吃小数 例：用单精度计算 的根。 精确解为  算法1：利用求根公式
2. 避免小分母 : 分母小会造成浮点溢出 3. 避免大数吃小数 例：用单精度计算 的根。 精确解为  算法1：利用求根公式 在计算机内，109存为0.11010，1存为 0.1101。做加法时，两加数的指数先向 大指数对齐，再将浮点部分相加。即1 的 指数部分须变为1010，

30 则：1 = 0.0000000001  1010，取单精度时就成为：109+1=0.100000001010+0.00000000 1010=0.10000000 1010=109
大数吃小数

31 算法2：先解出 再利用

32 4. 先化简再计算，减少步骤，避免误差积累。 5. 选用稳定的算法。 注：求和时从小到大相加，可使和的误差减小。
例：按从小到大、以及从大到小的顺序分别计算 … 4. 先化简再计算，减少步骤，避免误差积累。 一般来说，计算机处理下列运算的速度 为： 5. 选用稳定的算法。