数值分析1-3.ppt

3误差定性分析与避免误差危害 一 算法的数值稳定性概念 二 设计算法的若干原则 1 定义 算法 所谓算法 是指对一些数据按某种规定的顺序进行的运算序列 一 算法的数值稳定性概念 对同一问题 选用不同的算法 所得结果的精度往往大不相同 请看下例 例 用四位有效数字计算如下y的值 解 y的精确值是0 0158074374 算法1 直接计算 则 结果只有一位有效数字 其相对误差大于26 算法2 作适当变形后计算 结果具有四位有效数字 其相对误差不超过0 02 2 定义 数值稳定性 初始数据的误差或计算中的舍入误差在计算过程中的传播 因算法不同而异 一个算法 如果计算结果受误差的影响小 就称该算法具有较好的数值稳定性 二 设计算法的若干原则 一 要避免相近两数相减 例 a1 0 12345 a2 0 12346 各有5位有效数字 而a2 a1 0 00001 只剩下1位有效数字 很小 几种经验性避免方法 很小 二 要防止大数 吃掉 小数 注意保护重要数据 例 用单精度计算的根 精确解为 算法1 利用求根公式 在计算机内 109存为0 1 1010 1存为0 1 101 做加法时 两加数的指数先向大指数对齐 再将浮点部分相加 即1的指数部分须变为1010 则 1 0 0000000001 1010 取单精度时就成为 109 1 0 10000000 1010 0 00000000 1010 0 10000000 1010 大数吃小数 算法2 先解出再利用 注 求和时从小到大相加 可使和的误差减小 例 在5位浮点十进制计算机上 计算y 54321 0 4 0 3 0 4 解 若按从左到右的顺序进行计算 后三位在对阶过程变为 后三个数都在对阶过程中变为零 得出含有较大误差的结果y 54321 但若按从右到左的顺序进行计算 后三位在对阶过程变为 这种算法避免了大数 吃掉 小数 一般地 有如下原则若干数相加 采用绝对值较小者先加的算法 结果的相对误差限较小 三 注意简化计算步骤 减少运算次数 避免误差积累 例 计算多项式的值 解 如果先计算各项然后相加 则乘法次数 4 3 2 1 10 加法次数 4 但如改用下式计算 则只需做4次乘法和4次加法 计算量大大减少 秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算法 在西方被称作霍纳算法 Horneralgorithm或Hornerscheme 是以英国数学家威廉 乔治 霍纳命名的 秦九韶作于1240年的 数书九章 已经运用十进制和零 领先于英国数学家威廉 乔治 霍纳 WilliamGeorgeHorner 于1819年发表的解高次代数方程的方法 注 第二种方法称为 秦九韶算法 通常 计算如下n次多项式的值 如果先计算各项然后相加 则乘法次数 n n 1 2 1 n n 1 2加法次数 n 若采用 秦九韶算法 则乘法次数 n加法次数 n 两种算法的乘法运算次数随n的变化见下表 四 要避免绝对值小的数作除数 可知 当除数x2接近于零时 商的绝对误差就可能很大 因此要避免绝对值小的数作除数 由商的绝对误差限 例 当x接近于0时 的分子 分母都接近0 为避免绝对值小的数作除数 可将原式变形为 例 当x很大时 的分母接近0 为避免绝对值小的数作除数 可将原式变形为 五 设法控制误差的传播 许多算法具有递推性 递推法运算过程较规律 但多次递推必然导致误差的积累 例 计算积分 解 利用分部积分公式 有 从而有递推公式 又因为 这说明由初始值E1的误差在计算过程中绝对值会迅速扩大 因此这个算法不可靠 则误差传递规律是 但若将公式改为 则误差按规律 逐步缩小 从而 所以只要适当选择初值E9 再由公式依次计算E8 E7 E1 便可以得到比较精确的结果 因此这个算法是稳定的 本章作业 习题1 2 3 4 6 9 11 12 第一章复习 一 主要内容 省略 二 典型题解析 二 典型题解析 例1用最小刻度为毫米的卡尺测量直杆甲和直杆乙 分别读出长度a 312mm和b 24mm 问a b的绝对误差限 相对误差限各是多少 两直杆实际长度x和y在什么范围内 解 由于绝对误差限是测量工具最小单位的一半 故 故两直杆实际长度x和y的取值范围为 即 同理 注 本题x与y有相同的绝对误差限 但相对误差限不同 相对误差限越小越精确 例2设a 2 18和b 2 1200是分别由准确值x和y经过四舍五入而得到的近似值 问 各是多少 解 由于凡是由准确值经过四舍五入而得到的近似值 其绝对误差限等于该近似值末位的半个单位 故 因此相对误差限为 例3下列近似值的绝对误差限都是0 005 问 各个近似值有几位有效数字 分析按有效数字的定义 根据绝对误差限 并将其取为某位的半个单位 从中就可看出有效数字的个数 解 由题意 近似值的绝对误差限都是0 005 由于 故近似值精确到小数点后第二位 根据有效数字的定义 有三位有效数字1 3 8 有一位有效数字3 没有有效数字 例4按四舍五入原则写出下列各数具有5位有效数字的近似值 解 由于有效数字的计算是从第一位非零数字算起 故 具有5位有效数字的近似数是 例5设x 10 5 试求函数f x x1 n的相对误差限 分析这是标准的一元函数误差的传播问题 只需利用公式直接计算 解由x 10 5 知近似值x 10 绝对误差限 由于 故 因此当x 10时 即x 10相对误差限 注 从本例可以看出 对于函数x1 n 函数值的相对误差限约是自变量相对误差限的1 n倍 由 例6设x 1 30 0 005 y 0 871 0 0005 如果用作为f x y 的近似值 则能有几位有效数字 解 而 故 所以 将数据代入 得 这说明 精确到小数点后第二位 故能有两位有效数字4 9 例7请给一种算法计算2256要求乘法次数尽可能少 分析如果逐个相乘要用255次乘法 要尽可能减少运算量 一种思路是尽可能运用已经算出的