数值计算方法-预篇2014精讲.ppt

但实际问题往往可以估计出 不超过某个正数?. 定义 2 若已知? *0，使 （1.3） 则称? * 为绝对误差限，简称为误差限。 就可以知道x范围为 有时也表示为 2．相对误差和相对误差限 （1.4） 定义3：设x是准确值，x*是近似值，称 为近似值x的相对误差，记作 类似定义2，有 定义4 相对误差的上界，称为相对误差限，即 （1.5） 3．有效数字 定义5：如果 （1.6） 则说x*近似表示x 准确到小数后第n位，并从这第n位起 直到最左边的非零数字之间的一切数字都称为有效数字， 并把有效数字的位数称为有效位数。 由上述定义 有效数位为3位 有效数位为5位 有效数位为4位 定义6： 若将准确值x 的近似值x*表示成标准形式 （1.7） 而其误差限 （1.8） 则说近似值x*具有n 位有效数字。 这里n 为正整数，m 为整数，每个 均为0,1，…，9中的一个数字，。 定理1.1：若 x* 具有n位有效数字，则其相对误差满足 （1.9） 反之，若x*的相对误差 满足 （1.10） 则近似值x* 至少具有n位有效数字。 误差的传播与积累 例5：蝴蝶效应 —— 墨西哥的一只蝴蝶翅膀一拍，就引起了大西洋的风暴？！ 以上是一个病态问题 M A 1.4. 数值计算中应该注意的一些原则 1．算法的稳定性 例6：求 （n = 0, 1, 2, …, 8）的值。 解：由于 初值 递推公式 （1.11） 注意此公式精确成立 按 (1.8) 式就可以逐步算出 What happened?! 不稳定的算法 ！ 由递推公式（1.8）可看出，In-1的误差扩大了5倍后传给In， 因而初值I0的误差对以后各步计算结果的影响，随着n的增大 愈来愈严重。这就造成I4的计算结果严重失真。 这就是误差传播所引起的危害 ! 改变公式： 将公式 变为 不妨设I9 ? I10，于是由 可求得I9 ? 0.017，按公式（1.12）可逐次求得 （1.12） I8 ? 0.019 I7 ? 0.021 I6 ? 0.024 I8 ? 0.028 I4 ? 0.034 I3 ? 0.043 I2 ? 0.058 I1 ? 0.088 I0 ? 0.182 稳定的算法 ！ 在我们今后的讨论中，误差将不可回避， 算法的稳定性会是一个非常重要的话题。 2．要避免两个相似数相减 在数值计算中，两个相近的数作减法时有效数字会损失。 （1.13） 的值。当x = 1000，y 的准确值为0.01580 1、直接相减 2、将（1.13）改写为 则 y = 0.01581 例7: 求 类似地 3. 绝对值太小的数不宜作除数 例8： 如分母变为0.0011，也即分母只有0.0001的变化时 4. 避免大数吃小数 例9：用单精度计算 的根。 精确解为 ? 算法1：利用求根公式 在计算机内，109存为0.1?1010，1存为0.1?101。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1 的指数部分须变为1010，则：1 = 0.0000000001 ? 1010，取单精度时就成为： 109+1=01010+0?1010=0?1010 算法2：先解出 注：求和时从小到大相加，可使和的误差减小。 例10：按从小到大、以及从大到小的顺序分别计算 5. 先化简再计算，减少步骤，避免误差积累。 一般来说，计算机处理下列运算的速度为 1 + 2 + 3 + … + 40 + 109 再利用 1.5 中国古代数学中的算法案例 秦九韶算法—递推方法 计算机上使用的算法常采用递推化的形式，递推 化的基本思想是把一个复杂的计算过程归结为简单过程 的多次重复。这种重复在程序上表现为循环。递推化的 优点是简化结构和节省计算量。 多项式求值：给定的x 求下列n 次多项式 的值。 解：1. 用一般算法，即直接求和法: 2. 逐项求和法: 乘法的次数为: 加法次数为：n 令 则 记 可以看出前K + 1项部分和uk等于前K 项部分和uk-1再加上 第K + 1项，因此有 k = 1, 2, …, n 初值应取为 所用乘法的次数为2n，加法次数为n。 3. 秦九韶方法: 将多项式改写为 令 递推公式为： k= 1,