数值分析_1ppt课件.ppt

数值分析 计算机学院软件部王贵珍Tel o 68914322 mmail gzwang Address 中心教学楼906 软件教研室 1 2 课程内容 第一章数值计算中的误差第二章方程 组 的迭代解法第三章解线性方程组的直接解法第四章解线性方程组的迭代法第五章插值法第六章数值积分与数值微分 3 第一章数值计算中的误差 4 本章内容 1计数与数值 2舍入方法与有效数字 3算术运算中的误差 4算法举例 5数值计算中的误差 6误差分配原则与处理方法 5 2舍入方法与有效数字 6 2舍入方法与有效数字2 1绝对误差与相对误差 近似数a的绝对误差 设a是精确值A的近似值 a A绝对误差限 a A 上界 由上式可推知a A a 也可表示为A a 简称误差 7 相对误差 绝对误差与精确值之比 A 实际计算 a 代替后误差 相对误差限 a a 上界 绝对误差是有量纲的量 相对误差没有量纲 有时亦用百分比 千分比表示 2舍入方法与有效数字2 1绝对误差与相对误差 8 例 计算绝对误差与相对误差 1 a 0 3100 101近似精确值A 0 3000 101 2 a 0 3100 10 3近似精确值A 0 3000 10 3 解 1 0 1 2 0 1 10 4 2舍入方法与有效数字2 1绝对误差与相对误差 0 033 3 3 0 033 3 3 9 例 用最小刻度为毫米的卡尺测量直杆甲和直杆乙 分别读出长度a 312mm和b 24mm 问 1 a b的绝对误差限 相对误差限各是多少 2 两直杆实际长度x和y在什么范围内 解 2舍入方法与有效数字2 1绝对误差与相对误差 10 舍入方法 将无限位字长的精确数处理成有限位字长近似数的处理方法 A a0a1 am am 1 am n 0 0 0am n 1 2舍入方法与有效数字2 2舍入方法 11 取a a0a1 am am 1 am n a A 0 0 0am n 1 0 0 0999 0 0 01 1 10 n 截断法产生的绝对误差限不超过近似数a最末位的1个单位 2舍入方法与有效数字2 2舍入方法2 2 1截断法 12 四舍情况 当am n 1 0 1 2 3 4时 取a a0a1 am am 1 am n a A 0 0 0am n 1 0 0 0499 0 0 05 0 5 10 n 0 1 2 3 4 2舍入方法与有效数字2 2舍入方法2 2 2四舍五入法 绝对误差限 0 5 10 n 13 五入情况当am n 1 5 6 7 8 9时 取a a0a1 am am 1 am n 1 a A 0 0 01 0 0 0am n 1 0 0 01 0 0 050 0 5 10 n 5 6 7 8 9 2舍入方法与有效数字2 2舍入方法2 2 2四舍五入法 绝对误差限 0 5 10 n 14 四舍五入到小数点后第n位的方法 0 5 10 n 0 5 10 n结论 凡是由准确值经过四舍五入而得到的近似值 其绝对误差限等于该近似值末位的半个单位 2舍入方法与有效数字2 2舍入方法2 2 2四舍五入法 15 例 设a 2 18和b 2 1200是分别由准确值x和y经过四舍五入而得到的近似值 问 a b的绝对误差限 相对误差限各是多少 解 2舍入方法与有效数字2 2舍入方法2 2 2四舍五入法 16 定义 如果近似数x的绝对误差不超过某一位数字的半个单位 则称x准确到这一位 从该位数字到第一位非零的所有数字均叫做有效数字 若共有n位数字 则称x具有n位有效数字 若近似数x的绝对误差不超过最末一位的半个单位 则称x为有效数 2舍入方法与有效数字2 3有效数字 推论1对于给出的有效数 其绝对误差限不大于其最末数字的半个单位 由准确值经过四舍五入得到的近似值是有效数 17 例 设x 2 40315是精确值x 2 40194的近似值 则x 有几位有效数字 2舍入方法与有效数字2 3有效数字 0 5 10 2 解 2 40315 2 40194 0 00121x 有3位有效数字 18 推论2有效数的相对误差限为 有效数位越多 相对误差就越小 2舍入方法与有效数字2 3有效数字 证明 令有效数A a0a1 am am 1 am n 19 例 计算sin1 2 问要取几位有效数字才能保证相对误差限不大于0 01 2舍入方法与有效数字2 3有效数字 解 Sin1 2 0 932039 设取n位有效数字则 5 10 n 9 0 01 10 n 1 4 10 4n 4取4位有效数字 20 注1 从有效数x的最末位数字向左到x的第一位非零数字均为有效数字 2舍入方法与有效数字2 3有效数字 由准确值经过四舍五入得到的近似值为有效数 从它的末位数字到第一位非零数字都是有效数字 例 x 1 315416876 如果取作1 32 则有三位有效数字 误差限0 005 如果取作1 3154 则有五位有效数字 误差限为0 00005 0 0035290 00352900 21 注2 浮点数的有效数字由其定点部分的有效数位确定 2舍入方法与有效数字2 3有效数字 例 有效数x 15 10 5 定点部分15有2位有效数字x有2位有效数字误差限 为0 5 10 5相对误差限 为有效数y 7 83 105y有3位有效数字 误差限 为0 005 105 0 5 103 22 例 下列近似值的绝对误差限都是0 005 a 1 38 b 0 0312 c 0 86 10 4 d 0 86 104问 各个近似值有几个有效数字 从小数点后第二位开始数起解 a n 3 1 3 8 b n 1 3 c n 0 没有有效数字 d n 6 8 6 0 0 0 0 2舍入方法与有效数字2 3有效数字 23 注3 若已知数x及其误差限 要求确定其有效数位并对x作舍入处理 2舍入方法与有效数字2 3有效数字 将 扩大成 0 5 10 k 对x舍入到小数点后k位 例 x 2 45648 其误差限 0 000789456 0 000789456 0 5 10 2x 2 45648 有3位有效数字 舍入处理为x 2 46 x 2 46不是有效数 其误差包含了舍入误差与原误差 24 注4 若要求近似数x的误差限小于 确定x取几位有效数字 2舍入方法与有效数字2 3有效数字 将 缩小成0 5 10 k 对x对应的精确数舍入到小数点后k位得到x 例 要求x的误差限小于 0 00045 0 5 10 4 0 00045x取至小数点后第4位 25 2 1绝对误差与相对误差设A是精确值 a是近似值 绝对误差 a A绝对误差限 a A 上界 相对误差 A相对误差限 A 上界 绝对误差和相对误差有关系 a 2舍入方法与有效数字小结 26 2 2舍入方法截断法 绝对误差限为最末位的1个单位四舍五入法 绝对误差限为末位的半个单位 2舍入方法与有效数字小结 27 我们希望所表示的数本身就能显示出它的准确程度 于是引入2 3有效数字 反映绝对误差限有效数的绝对误差限为最末数字的半个单位由准确值经过四舍五入得到的近似值 从它的末位数字到第一位非零数字都是有效数字在讲了有效数字之后 规定 所写出的数都应该是四舍五入到最后一位有效数字位 2舍入方法与有效数字小结 28 本章内容 1计数与数值 2舍入方法与有效数字 3算术运算中的误差 4算法举例 5数值计算中的误差 6误差分配原则与处理方法 29 3算术运算中的误差 30 x y 为准确值 x y为其近似值绝对误差为 x x x y y y 绝对误差限为 x x x y y yC x y C C C x y x y x x y y x y C x y x y 和差运算的绝对误差限为各数的绝对误差限之和 3算术运算中的误差3 1加减运算 C 31 例1 1 求有效数285 35 196 87 58 43 4 96的和 和545 61的绝对误差限为 4 0 5 10 2 0 02 545 61有4位有效数字 舍入处理为545 6 3算术运算中的误差3 1加减运算 0 05 32 例1 2 求有效数3 150950 15 426463 568 3758 7684 388的和 0 5 10 2 和 8271 34 误差限 3算术运算中的误差3 1加减运算 33 和的绝对误差限为3 0 5 10 4 0 5 10 3 0 00065 0 005和 8271 34 3算术运算中的误差3 1加减运算 34 3算术运算中的误差3 2乘积运算 若多元函数f在其定义域内的一点 x1 x2 xn 可微 则f在该点的增量可表示为 或 35 3算术运算中的误差3 2乘积运算 x y 为准确值 x y为其近似值绝对误差为 x x x y y y 绝对误差限为 x x x y y yC xydC近似 C dx x dy y C y x x y y x x y dC xdy ydx C y x x y 36 乘积运算的相对误差为各乘数的相对误差之和 乘积运算的相对误差限为各乘数相对误差限之和 3算术运算中的误差3 2乘积运算 C y x x y y x x y C x y C C x y x y x y 37 商运算的相对误差限等于除数与被除数的相对误差限之和 3算术运算中的误差3 3商运算 C x y 38 例1 4 求有效数25 7和3 6的商以及商的相对误差限和绝对误差限 解 C 0 05 25 7 0 05 3 6 0 016 C 25 7 3 6 7 13889 C 7 13889 0 016 0 11 0 5 3算术运算中的误差3 3商运算 25 7 3 6 7 39 3算术运算中的误差3 3幂运算 幂运算的相对误差等于底数相对误差的指数倍幂运算的相对误差限等于底数相对误差限的指数倍 c p x 40 1 误差与计算次数成正比 简化计算步骤 减少运算次数 例 计算多项式的值 如果改写为 运算次数 乘法 n n 1 1 n n 1 2加法 n 运算次数 乘法 n加法 n 3算术运算中的误差3 4运算时需要注意的地方 1 减少运算次数 41 2 防止大数吃小数的情况 数量级相同的先运算在计算机内 做加法时 两加数的指数先向大指数对齐 再将浮点部分相加 103 0 8961 10 3 0 4688 103 0 8961 103 0 0000 004688 可能结果 a b c a c b例 a 1012 b 10 c a 3算术运算中的误差3 4运算时需要注意的地方 2 防止大数吃小数 42 例如计算采用3位浮点数的截断方式进行运算 从左到右的次序计算得y 2 91 从右到左的次序计算得y 2 93 避免这种情况 按绝对值从小到大的次序相加 3算术运算中的误差3 4运算时需要注意的地方 2 防止大数吃小数 43 3 两个相近数相减 易失有效位两正数之差C x y的相对误差限是因为x和y的前几位有效数字必然相同 相减之后有效数字位会大大减少 使有效数字严重损失例如 cos20 0 9994 1 cos20 0 0006避免这种情况 可以使用转换公式 或者增加字长 维持一定有效位 保证精度 3算术运算中的误差3 4运算时需要注意的地方 3 禁止相近数相减 44 4 当商运算的分母很小时 c 可能很大 分子舍入误差 放大了106倍 3算术运算中的误差3 4运算时需要注意的地方 4 禁止除数过小 例 分母 0 000001 45 5 当分母为两个相近数相减时 会因有效数字丧失而出现 4 的情况 这里分子的误差被扩大104倍 3算术运算中的误差3 4运算时需要注意的地方 4 禁止除数过小 46 在各种数学模型中 它们的解与x1 x2 xn有关 可以记为y f x1 x2 xn 假定f在点 x1 x2 xn 可微 则当数据误差较小时 解的误差限可估计如下 3算术运算中的误差3 5数学问题解的误差估计 f 47 解的相对误差限如下 公式仅当 xi较小时才合宜 否则 f或 f按 xi为线性迭加进行估计 实际为非线性变化系数Ai Bi的大小可以衡量解对数据误差的敏感程度 3算术运算中的误差3 5数学问题解的误差估计 f 48 例已知球体的直径D 3 7cm 按v D3 6计算体积 求其绝对误差限与相对误差限 3算术运算中的误差3 5数学问题解的误差估计 解 取 3 14 0 0016 D 0 05 取 3 10 V 8 44 0 0016 21 5 0 05 1 088 5 49 例设f x y cosy x x 1 30 0 005 y 0 871 0 0005 如果用u f 1 30 0 871 作为f x y 的近似值 则u 有几位有效数字 3算术运算中的误差3 5数学问题解的误差估计 解 u cos0 871 1 30 0 49543 有2位有效数字 0 0022 0 005 50 本章内容 1计数与数值 2舍入方法与有效数字 3算术运算中的误差 4算法举例 5数值计算中的误差 6误差分配原则与处理方法 51 4算法举例 52 例1 8计算 解 1 算法1 分子分母分别计算后相除 取9位小数 A 0 0005 0 0143 0 0012 0 00000715 0 0012 0 000000009 有舍入 B 0 0003 0 0125 0 0135 0 00000375 0 0135 0 000000051 有舍入 A B 0 5 10 9 取D 0 2 4算法举例 D A B 0 17647 下页 53 2 算法2 分成三组因子 每组只取六位小数计算a 0 0005 0 0003 1 666667 有舍入 b 0 0143 0 0125 1 144000c 0 0012 0 0135 0 088889 有舍入 D 1 666667 1 144000 0 088889 0 169482 4算法举例 D 0 0000003 0 0000056 0 0000059 D 0 169482 D 1 0 10 6 0 5 10 5 上页 取D 0 16948 真值为0 16948148 54 例1 9 试用5位有效数字及Taylor公式计算e 5 5的值 n 8 0 5 10 3 0 004 0 5 10 2 4算法举例 55 改变算法计算例1 9先计算x 5 5的部分级数 再求倒数 n n 15 5000106 980912 692215 125820 768327 730730 208438 13 n 170 010842160 033511150 097486140 26587130 6767601 0000121 5997113 4902 4算法举例 638 45541 94 0 0108420 0443530 141840 407711 08452 08453 68427 1744 12 67419 65432 34647 47168 23995 969126 18164 30 202 74244 70 3 0 5 10 6 2 0 5 10 5 2 0 5 10 4 6 0 5 10 3 2 0 5 10 2 0 024 商1 244 70的值0 0040866367具有相对误差限 0 1 0 024 244 70 0 000098 0 0040866367 0 000098 0 4 10 6 0 5 10 6所以0 0040866367可以取为0 004087 56 解决方法 1 增加有效数位增加数值的有效数位至11位进行计算 结果为x1 99999 999990 正确 x2 0 000010 正确 例1 10 求二次方程x2 105x 1 0的根解 按二次方程求根公式及8位有效数字计算 得 4算法举例 57 解决方法 2 选择求根公式根据ax2 bx c 0中b的符号选择求根公式 105 4算法举例 例1 10 求二次方程x2 105x 1 0的根 58 例1 11 计算In 01xnex 1dx n 0 7解 算法1 用分部积分法可以推知In满足以下递推公式In 1 nIn 1取I0 01ex 1dx ex 1 01 1 e 1 0 6321逐次递推得I1 I2 I9 算法2 按照公式In 1 1 In n取I9 0 0684 反向计算得I8 I7 I0 4算法举例 59 算法1的误差 I0与I1的误差是 I2的误差是2 I3的误差是6 I9的误差是9 算法2的误差 I9的误差是 I8的误差是 9I7的误差是 9 8 I0与I1的误差 9 舍入误差对计算结果影响小的算法称为稳定的算法 否则称为不稳定的算法 4算法举例 In 1 nIn 1 In 1 1 In n 在大量计算中 舍入误差的积累和传播 与算法有关 舍入误差能控制在一定范围内就是稳定的 60 结论 计算中出现的舍入误差是不可避免的它直接影响到算法的数值稳定性 所以在数值方法的选择和设计中必须慎重考虑大量数值运算中 有效数位流失是难免的由于舍入误差估计的困难性 粗略的做法是按照预定精度用多取若干位的数值计算 4算法举例 61 本章内容 1计数与数值 2舍入方法与有效数字 3算术运算中的误差 4算法举例 5数值计算中的误差 6误差分配原则与处理方法 62 5数值计算中的误差 63 数值方法解题的一般过程 1 对于要解决的问题建立数学模型2 研究用于求解该数学问题近似解的算法和过程3 按照2进行计算 得到计算结果 5数值计算中的误差5 1数值计算中的误差种类 64 数值计算中的误差种类 1 模型误差2 观测误差3 截断误差4 舍入误差 5数值计算中的误差5 1数值计算中的误差种类 65 数学模型是指那些利用数学语言模拟现实而建立起来的有关量的描述 例用s t gt2 2 g 9 81米 秒2来描述自由落体下落时距离和时间的关系 设自由落体在时间t的实际下落距离为S t 则把S t s t 叫做模型误差模型误差 描述误差 实际问题的真解与数学模型的真解之间的误差 5数值计算中的误差5 1数值计算中的误差种类5 1 1模型误差 66 数学模型中的参数和原始数据 是由观测和试验得到的由于测量工具的精度 观测方法或客观条件的限制 使数据含有测量误差 这类误差叫做观测误差或数据误差 5数值计算中的误差5 1数值计算中的误差种类5 1 2观测误差 67 求解数学模型所用的数值计算方法如果是一种近似的方法 那么得到的是数学模型的近似解 由此产生的误差称为截断误差精确公式用近似公式代替时 所产生的误差截断误差是数值计算中必须考虑的一类误差例一个无穷级数实际计算的时候 我们只能取前面有限项 如n项 5数值计算中的误差5 1数值计算中的误差种类5 1 3截断误差 68 由于计算机的字长有限 参加运算的数据以及运算结果在计算机上存放会产生误差 这种误差称舍入误差 例 3 1415926 5数值计算中的误差5 1数值计算中的误差种类5 1 4舍入误差 69 1 数学模型的精确解使用数学模型 精确数据 精确计算2 参数模型的精确解使用数学模型 观测数据 精确计算3 计算模型的精确解不能求解数学模型的精确解时 就采用数值的方法建立该数学模型的求解模型 称为计算模型使用计算模型 观测数据 精确计算所获得的解4 计算模型的近似解用计算模型 有舍入的观测数据 近似计算获得的解 方法误差 截断误差 舍入误差 5数值计算中的误差5 2模型与解 70 前面的舍入误差估计方法不足 只对运算量很少的情形适用大规模的无有效的方法做出定量估计 5数值计算中的误差5 3数学问题的适定性 确保数值计算结果的正确性 对数值计算问题进行定性分析保证其舍入误差不会影响计算的精度 71 数学问题的适定性定义设D为X x1 x2 xn 的值域 简记数学问题的解Y与参量 原始数据 X的关系为Y f X 若1 对X D 数学问题的解存在且唯一 2 满足连续性条件 即当 X 0时 有 Y 0成立 则称该数学问题是适定的 反之 若数学问题的解多于一个 或者解不连续依赖于原始数据 则称为不适定的 5数值计算中的误差5 3数学问题的适定性 72 良态 问题和 病态 问题在适定的情况下 若对于原始数据很小的变化 数学模型解的变化也很小 则称该数学问题是良态问题 若原始数据很小的变化 数学模型解的变化很大 则称为病态问题舍入误差对计算结果影响小的算法称为稳定的算法 否则称为不稳定的算法 数学问题的性态是针对数学问题的 数值稳定性是针对数值方法的 5数值计算中的误差5 3数学问题的适定性 73 稳定算法和不稳定算法 5数值计算中的误差5 3数学问题的适定性 74 参数模型是病态的曲线图 5数值计算中的误差5 3数学问题的适定性 75 小结数值计算中除了尽量避免误差危害外 还应要分清问题是否病态和算法的数值稳定性误差的定性分析中首先要分清问题是否病态 如果问题计算结果相对误差很大就是病态问题 对病态问题计算结果就可能不可靠 对良态问题主要考虑算法的稳定性 对不稳定的算法计算结果也不可靠计算中还要根据以前给出的原则尽量避免舍入误差增长 5数值计算中的误差5 3数学问题的适定性 76 本章内容 1计数与数值 2舍入方法与有效数字 3算术运算中的误差 4算法举例 5数值计算中的误差 6误差分配原则与处理方法 77 6误差分配原则与处理方法 78 1 误差配置原理计算模型的近似解相对于参数模型精确解的总误差 截断误差R 舍入误差 1 R 即舍入误差小于截断误差时 总误差的主部取决于截断误差的主部 此时过多位字长部分的计算工作量无意义 3 R 此时 不会出现过多位字长和过多项部分计算量上的浪费现象 6误差分配原则与处理方法6 1误差分配原则 79 1 给定运算误差 确定参与运算的数值字长若计算公式表示为u f x1 x2 xn 设xi的舍入误差为 xi 则计算结果的舍入误差可按下式近似计算 6误差分配原则与处理方法6 2误差配置的处理方法 假设所有的运算量的舍入误差相同均为 则 80 例 长方形面积s ab 其中a 5m b 200m 计算S的运算误差要求为 s 1m2 试确定两直角边的允许误差 解 因为 s a b 1 5 200 0 0048 可见数值a b的字长应取至小数后3位 6误差分配原则与处理方法6 2误差配置的处理方法 0 5 10 3 81 2