数值计算方法 第1章讲解

《数值计算方法 第1章讲解》由会员分享，可在线阅读，更多相关《数值计算方法 第1章讲解（64页珍藏版）》请在金锄头文库上搜索。

1、现代数值计算方法 中国科学技术大学 工程科学学院近代力学系 授课教师：刘难生 联系电话：13955196890(HP) 63603345(O) Email: lns 办公室：力学一楼522 课程内容 2016/9/26数值计算方法 引 言 2 21世纪信息社会的两个主要特征： “计算机无处不在” “数学无处不在” 21世纪信息社会对科技人才的要求： -会用数学解决实际问题 -会用计算机进行科学计算 课程内容 2016/9/26数值计算方法 引 言 3 科学方法论的巨大变革： 如果说伽 利略和牛顿在科学发展史上奠定了实验 和理论这两大科学方法的支柱，那么由 冯.诺依曼研制的现代电子计算机把计 算

2、推上了人类科学活动的前沿，使计算 成为第三种方法。 课程内容 2016/9/26数值计算方法 引 言 4 理论研究 科学实验 科学计算 计算数学 诺贝尔奖得主,计算物理学家 Wilson提出 现代科学研究的三大支柱 课程内容 2016/9/26数值计算方法 引 言 5 数值计算方法是计算数学的一个主要组成部分， 定义：“什么是数值计算方法？” 它主要研究使用计算机求解各种科学与工程计算 问题的数值方法（近似方法）;对求得的解的精 度进行评估以及在计算机上实现求解等。 数值计算方法已经成为计算机处理实际问题 的一个重要手段，从宏观天体运动学到微观分子 细胞学，从工程系统到社会经济系统，无一能离

3、开数值计算方法。因此，数值计算与计算机模拟 被称为“第三种研究科学方法”。 课程内容 2016/9/26数值计算方法 引 言 6 数值计算方法的主要任务 借助计算机提供切实可行的数学算法. 想的精确度;收敛且稳定;误差可以分析或估计. 所提出的算法必须具有：可靠的理论分析;理 时间复杂性好_指节省时间； 空间复杂性好_指节省存储量。 计算复杂性好 通过数值实验证明算法行之有效. 课程内容 2016/9/26数值计算方法 引 言 7 实际物理问题 简化数学问题 编写计算程序计算得出结果 科学计算解题过程 建立数学模型 选取计算方法 课程内容 2016/9/26数值计算方法 课程内容 8 涉及的数

4、学问题： 1）求解线性方程组，即AnnXn1=Bn1 很多数值方法最后都归结为 （或最后一步）线性方程组 求根，如FEM、FDM、FVM 和优化方法等。 2）非线性方程（组）求根 代数方程和超越方程求根，如： h(x) Pn(x) 课程内容 2016/9/26数值计算方法 课程内容 9 涉及的数学问题： 3）矩阵特征值问题的计算 4）函数插值和数据拟合 使得 插值函数 : xiyi x1y1 x2y2 xn-1yn-1 xnyn 已知列表函数： 拟合函数 : 整体最贴近 ， 给定矩阵 ，求 和 ， 课程内容 2016/9/26数值计算方法 课程内容 10 涉及的数学问题： 5）数值积分定积分的

5、数值近似 f(x)=e-x/4cos(x) f(x) x 数值解：求函数y=y(x)在一系列离散点上y( xi )的函数近似值yi 定解条件 一维面积分、二维体积分 y( xi ) yi 6）常微分方程的数值求解初值问题 课程内容 2016/9/26数值计算方法 第一章 数值计算中的误差分析 11 本章内容： 1 误差与数值计算的误差分析 2 选用和设计算法应遵循的原则 课程内容 2016/9/26数值计算方法 1 误差与数值计算的误差分析 12 一、误差的来源与分类 模型误差对实际问题进行抽象和简化得到数学模型 例1: 质量为m的物体，在重力作用下自由下落， 其下落距离s 与时间t 的关系是

6、： 其中 g 为重力加速度。 抽象简化： 1）质点简化假设；2）忽略空气阻力；等等。 课程内容 2016/9/26数值计算方法 一、误差的来源与分类 13 例2: 均质、粘性可压缩流体运动方程的普遍形式为 1) 不可压缩流动假设 惯性力 = 体积力 + 压力 设 其中 为整数, 为正整数, 。 若 至多有 位有效数字,即 是有效数字, 而 不是有效数字, 课程内容 二、误差与有效数字 证明：不是有效数字 反之, 若 则 因为 即 至多有 位有效数字. 不是有效数字， 所以 课程内容 1 误差与数值计算的误差分析 三、数值计算的误差估计 单元函数的误差传播 变量近似 2016/9/26 相关性？

7、 Taylor展开 近似 函数值近似 结果误差测量误差 y = f (x) 课程内容 三、数值计算的误差估计 2016/9/26 所以，绝对误差限 类似地，相对误差 相对误差限 x y x* y* 真实 误差 估计 误差 f (x) 课程内容 三、数值计算的误差估计 多元函数的误差估计 由Taylor展开估计, 可微函数 ,如果 的近似值为 ,则 的近似为 于是函数值 的绝对误差 增长因子 课程内容 三、数值计算的误差估计 另外，相对误差估计式为 绝对误差限为 增长因子 相对误差限为 课程内容 三、数值计算的误差估计 四则运算的误差估计 1）和、差的误差 a) 当 和 同号， b) 当 和 异

8、号（相当于减法），且 则有 相对误差放大，尽量 避免相近的数相减! 讨论： 课程内容 三、数值计算的误差估计 2）积的误差 乘以大数，放大 绝对误差 3）商的误差 除以小数，放大 绝对误差 相对误差不变 相对误差不变 课程内容 三、数值计算的误差估计 例: 已测得某场地长 的值为 ,宽 的值为 , 已知 , . 试求 面积 的绝对误差限与相对误差限. 解: 因 其中 由积的误差估计式得 课程内容 三、数值计算的误差估计 而 于是绝对误差限为 相对误差限为 课程内容 2016/9/26数值计算方法 2 选用和设计算法时应遵循的原则 38 主要遵循的原则： 算法有效性 结果精度好 计算效率高 计算

9、代价小 算法是否稳定？ 算法逻辑简单？ 计算次数 和存储量少？ 课程内容 2016/9/26数值计算方法 2 选用和设计算法时应遵循的原则 39 一、选用数值稳定的计算公式 数值计算在设计算法时首先关心的是由它 产生的计算结果的稳定性，而算法的稳定性与 舍入误差是否增长密切相关。一个算法如果输 入数据有微小扰动（即误差），而在计算过程 中舍入误差不增长，则称此算法是数值稳定的 ，否则称其为数值不稳定。 算法的数值稳定性 课程内容 2016/9/26数值计算方法 一、选用数值稳定的计算公式 40 例：求定积分 的值. 解：直接积分可产生递推公式 若取初值 课程内容 2016/9/26数值计算方法

10、 一、选用数值稳定的计算公式 41 可得递推公式 按公式就可以逐步算出 What happened ?! 不稳定的算法 ！ 这就是误差传播所引起的危害这就是误差传播所引起的危害 ! ! 注意此公式精确成 立，且 课程内容 2016/9/26数值计算方法 一、选用数值稳定的计算公式 42 NYBJ 蝴蝶效应 这是一个病态问题，根源在于 误差的传播、积累和放大。 纽约的一只蝴蝶翅膀一拍，风和日 丽的北京就刮起台风来了？！ 课程内容 2016/9/26数值计算方法 一、选用数值稳定的计算公式 43 递推公式的稳定性分析 原式为 近似式为原始数据读入的计算机数 于是： 舍入误差进一步 误差传播公式 不

11、稳定！ 误差指数 放大！ 课程内容 2016/9/26数值计算方法 一、选用数值稳定的计算公式 44 由误差传播公式可看出， 的误差放大了 5倍后传给 ，因而初值 的误差对以后各步 这就造成 的计算结果严重失真。 计算结果的影响，随着 的增大愈来愈严重。 要怎么做才能解决这个问 题呢? 课程内容 2016/9/26数值计算方法 一、选用数值稳定的计算公式 45 可求得I9 0.017，按改写后的公式可逐次求得 不妨设I9 I10，于是由 逆递推公式 将公式 变为 课程内容 2016/9/26数值计算方法 一、选用数值稳定的计算公式 46 I8 0.019 I7 0.021 I6 0.024 I

12、8 0.028 I4 0.034 I3 0.043 I2 0.058 I1 0.088 I0 0.182 稳定的算法 ！ 在我们今后的讨论中，误差将不可回避， 算法的稳定性会是一个非常重要的话题。 误差指数 减小！ 课程内容 2016/9/26数值计算方法 一、选用数值稳定的计算公式 47 注：递推公式的舍入误差以5的幂次增长进行 传播，因此是数值不稳定的，而逆递推公式 的舍入误差在一定范围内以0.2的幂次进行传 播，随着n的增大，误差逐步减少，因此该算 法是数值稳定的。 因此，可以看出数值不稳定的算法是不能使用 的，实际计算中对任何输入数据都是数值稳定的算 法，称为无条件稳定。而对某些数据数

13、值稳定，对 其它数据数值不稳定的算法，称为条件稳定。 课程内容 2016/9/26数值计算方法 二、注意选择适当的算法 48 如果算法效率低，则计算量大，精度一般也降低， 这是由于计算过程中的误差积累。 例： Cramer法则 线代理论 计算速度百万亿次(10 14flops)， 计算量为：乘法(n+1)(n-1)n!次，加法(n+1)n!次。 n=20时，乘法次数为211920! 9.71020， 需要106秒 100天。 课程内容 2016/9/26数值计算方法 二、注意选择适当的算法 49 适当的算法能极大的减小计算量 解法 乘法 加法 年代 耗时 Gauss-Jordan n3/2 次

14、 n3/2 次 Gauss n3/3 次 n3/3 次 1950s 90天 Gauss-Seidel Iteration O(n2) 1960s 1秒 Wave Front Method(FEM) O(n ln n) 1970s 10-5秒 Incomplete Facterization O(n ln n) 1980s 10-5秒 Multigrid Method O(n) 1980s 10-6秒 例：3D FEM，n=102102102=106(百万节点)， 10 12flops 课程内容 2016/9/26数值计算方法 三、简化计算步骤避免误差积累 50 一般来说，算法的计算量（次数）愈

15、小 例1：多项式求值：给定的x 求下列n 次多项式的值。 解：1. 用一般算法，即直接求和法； 舍入误差积累机会愈小 计算耗费机时愈小 乘法： 1 2 n = n(n+1)/2次 加法： 1 1 1 = n次 运算速度： 课程内容 2016/9/26数值计算方法 三、简化计算步骤避免误差积累 51 算法的递推性 计算机上使用的算法常采用递推化的形式， 递推化的基本思想是把一个复杂的计算过程 归结为简单过程的多次重复。这种重复在程序 上表现为循环。递推化的优点是简化结构和节 省计算量。 课程内容 2016/9/26数值计算方法 三、简化计算步骤避免误差积累 52 解：2.秦九韶方法(即Hornor算法）: 乘法： 1 1 1 = n次 加法： 1 1 1 = n次 n-1个 例2：三角函数逼近 直接计算 利用三角函数的周期性延拓得到 否者正负交错级数不易收敛，易导致计 算次数过多，有效位数丢失而降低精度 课程内容 2016/9/26数值计