天津理工大学数值计算第一章 戴敏.ppt

数值计算方法 第一章数值计算引论 2 1 1数值计算方法 数值计算方法是应用数学的一个分支 又称为数值分析或计算方法 它是研究用数字计算机求解各种数学问题的数值方法及其理论的一门学科 是程序设计和对数值结果进行分析的依据和基础 3 1 1数值计算方法 利用电子计算机解题的一般步骤 提出实际问题构造数学模型 将实际问题归纳为明确的数学问题选择计算方法 对数学问题 选择运算简单 工作量节省 并能保证精确度要求的计算方法 确定计算步骤计算过程的程序设计 用一定的程序设计语言将计算过程编成程序将计算程序和原始数据输入 上机计算 最后计算机输出计算结果 4 1 1数值计算方法 数值计算方法 数值算法 把对数学问题的解法归结为有加 减 乘 除等基本运算 并对运算顺序有完整而准确的描述的算法数值算法具有的特点面向计算机有可靠的理论分析要有好的计算复杂性 5 1 1数值计算方法 总之 对于给定的数学模型所提出的可行 有效的算法应该是符合计算机的要求 在理论上收敛 稳定 在实际计算中精度高 计算复杂性小 能通过实验验证的数值方法 6 1 2算法 算法的概念人工手算过程计算机运算过程 先将所制定的解题方案告诉计算机 令计算机按照人们所规定的计算顺序去自动执行程序设计 用机器所能接受的 语言 来描述解题步骤算法 指解题方案的准确而完整的描述算法的描述 日常语言 数学语言 算法语言 算法框图 7 1 2算法 举例 求解二元一次方程组首先判断是否为0 8 1 2算法 算法框图 9 1 2算法 算法的优劣计算量的大小是衡量算法优劣的一个重要标准例如 行列式解法的克莱姆法则 解一个n阶方程组 要算n 1个n阶行列式的值 总共需要n n 1 n 1 次乘法 如果求解一个20阶左右的方程组 需要工作很多年才能完成尽量节约存储量 也是设计算法时需要考虑的一个因素尽量利用原有的工作单元进行累算 算式采用 动态 形式 如将y x2表示为 即将单元x的内容自乘 结果仍存放在单元x中 10 1 2算法 设计算法所要考虑的另一个因素就是逻辑结构的复杂性问题算法的递推性算法的递推化 将一个复杂的计算过程归结为简单过程的多次重复例如 给定x的n次多项式 11 1 2算法 令上式可以表示为递推的公式 初值为 12 1 2算法 多项式的秦九韶计算方法将多项式按降幂的次序排列为 将多项式表示为嵌套形式 设用表示第k层的值 那么第k层的结果显然等于第k 1层的结果乘上x再加上系数 13 1 2算法 初值为 14 1 2算法 15 1 2算法 例 用秦九韶方法求多项式在x 0 2的值 16 1 2算法 17 1 3误差的来源 数可以分为两类 精确数 准确数 真值 精确的反映实际情况的数 如教室里面有42名学生近似数 某准确数的近似值 只能近似的反映实际情况 如测量得到桌子的长度为950mm 这个测量值是不能精确的反映桌子实际长度的近似值误差 将一个数的准确值与其近似值之差称为误差 18 1 3误差的来源 误差产生的原因模型误差 描述误差 观测误差 测量误差 截断误差 方法误差 无穷过程用有限过程近似引起的误差例如 指数函数可展开成下列幂级数形式但在实际计算中 只能截取有限项求出 19 1 3误差的来源 根据泰勒余项定理 关于的截断误差是例 假定 x 1 用泰勒多项式计算的值 设要求截断误差不超过0 005 问公式该取多少项 舍入误差 计算误差 无论用计算机 计算器计算还是笔算 都只能用有限位小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数 产生舍入误差例如 3 1415926 20 1 4近似数的误差表示法 绝对误差设x 是准确值x的一个近似值 则称为近似值x 的绝对误差 简称误差 定义如果那么叫做近似数x 的绝对误差限 用它反映近似数的精度 21 1 4近似数的误差表示法 通常我们用x x 来表示近似数x 的精确度或准确值所在的范围 应该取得尽可能小例x 4 3762816 取近似数x 4 376 则x x 0 0002816 有 x x 0 0002816 0 0003 0 3 10 3同样 x x 0 0002816 0 00029 0 29 10 3例 用一把有毫米刻度的尺子 测量桌子的长度 读出来的值x 1235mm 这是桌子实际长度x的一个近似值 由尺子的精度可以知道 这个近似值的误差不会超过1 2mm 22 1 4近似数的误差表示法 按四舍五入原则取近似值是使用最广泛的取近似值的方法四舍五入的误差限在计算机中通常采用的是二进制实数系统 表示形式为 的数称为机器数 其中整数m称为阶码 小数为尾数 23 1 4近似数的误差表示法 设x为一个实数 其十进制的标准形式为 x 0 x1x2 10m其中m是整数 x1 x2 是0 1 9中的任一数 但x1 0 经过四舍五入保留n位数字 得到近似值 24 1 4近似数的误差表示法 四舍时的误差限为 x x 0 x1x2 xnxn 1 0 x1x2 xn 10m 0 x1x2 xn499 0 x1x2 xn 10m 10m 0 0 0499 1 2 10m n五入时的误差限 x x 0 x1x2 xn 1 xn 1 0 x1x2 xn 10m 0 0 01 0 0 0 xn 1 10m 10m n 1 0 xn 1 由于xn 1 5 所以1 0 xn 1 1 2 因此有 x x 1 2 10m n 25 1 4近似数的误差表示法 例 圆周率 3 14159 用四舍五入取小数点后4位时 近似值为3 1416 此时m 1 n 5 m n 1 5 4 因此绝对误差 1 2 10 4 同样取小数点后2位时 近似值为3 14 其绝对误差 1 2 10 2线性运算对误差的影响设xk 是xk的近似值 对任意系数 k 取作为的近似值 这时有不等式 26 1 4近似数的误差表示法 如果每个近似值xk 的误差限全为 则和式x 的误差限为 例 用近似公式求ex在x 0 2的值 并估计误差令 0 81873利用余项公式可估计出截断误差限 1 0 3 10 6 系数的舍入误差都不超过1 2 10 5 和式的舍入误差限为 2 0 5 10 7 误差限为 1 2 0 35 10 6 27 1 4近似数的误差表示法 有效数字定义设数x的近似值x 0 x1x2 xn 10m 其中xi是0到9之间的任一个数 但x1 0 i 1 2 3 n正整数 m整数 如果 x x 1 2 10m n则称x 为x的具有n位有效数字的近似值 x 准确到第n位 x1x2 xn是x 的有效数字 28 1 4近似数的误差表示法 由上述定义例 3 141592 当取3 142和3 141作为其近似值时 有效数字分别为多少位 有效数位为3位 有效数位为5位 有效数位为4位 29 1 4近似数的误差表示法 有效数字的确定用四舍五入取准确值的前n位x 作为近似值 则x 必有n个有效数字例如 3 1415926 取3 14作为近似值 则有3位有效数字 取3 142作为近似值 则有4位有效数字有效数字位数相同的两个近似数 绝对误差不一定相同例如 设x1 12345 x2 12 345 二者均有5位有效数字 前者的绝对误差为1 2 后者的绝对误差为1 2 10 3把任何数乘以10p等于移动该数的小数点 这样并不影响其有效数字的位数 30 1 4近似数的误差表示法 准确值被认为具有无穷多位有效数字例如 真值0 5 不表示只有1位有效数字 具有无穷多位有效数字相对误差定义x的近似值x 的相对误差相对误差限可由绝对误差限求出 反之 绝对误差限也可由相对误差限求出 31 1 4近似数的误差表示法 例 取3 14作为 的四舍五入的近似值 试求其相对误差 32 1 4近似数的误差表示法 有效数字与相对误差定理1如果近似数具有n位有效数字 则其相对误差证因 有又 有n位有效数字 即 因此 33 1 4近似数的误差表示法 例 取3 14作为 的四舍五入的近似值 试求其相对误差解 四舍五入的近似值3 14 各位都是有效数字 因此n 3 所以 34 1 4近似数的误差表示法 定理2如果近似数的相对误差则该近似数至少具有n位有效数字证因为 35 1 4近似数的误差表示法 根据有效数字定义可知 x 具有n位有效数字例 已知近似数的相对误差为0 25 问可能有几位有效数字解 根据定理2x1未给出 取按最不利的情况取 x 至少应该有2位有效数字 36 1 4近似数的误差表示法 有效数字的位数表征了近似数的精度 绝对误差与小数点后的位数有关 相对误差与有效数字的位数有关 37 1 5数值运算误差分析 函数运算误差设一元函数f x 的自变量x的近似值为x f x 的近似值为f x 其误差记为 对f x 在近似值x 附近泰勒展开式为两边取绝对值得 38 1 5数值运算误差分析 设与相差不大 可以忽略 的高次项 于是可以得出函数运算的误差和相对误差 39 1 5数值运算误差分析 例 正方形的边长约为100cm 怎样测量才能使其面积误差不超过1cm2 解 设正方形的边长为xcm 测量值为x cm 面积为Y f x x2因此要使正方形面积误差不超过1cm2 测量边长时绝对误差应不超过0 005cm 40 1 6减少运算误差的若干原则 两个相近的数相减 会严重损失有效数字设y x A其中A和x均为准确值 假设A运算时不发生误差 而x有误差 其近似值为x 由此可估计出当用x 近似代替x时 y的相对误差由上可以看出 在x的绝对误差 x 不变时 如果x 越接近A 那么y的相对误差 r y 会变得越大 而相对误差的增大必然会导致有效数字位数的减少 41 1 6减少运算误差的若干原则 例 当x 10003时 计算的近似值解 如果使用6位十进制浮点运算 运算时取6位有效数字 结果为只有一位有效数字 损失了5位有效数字如果改用则其结果有6位有效数字 与精确值0 00499912523117984 非常接近 42 1 6减少运算误差的若干原则 例 x1 1 99999 x2 1 99998 求lgx1 lgx2 如果使用6位十进制浮点运算 运算时取6位有效数字 则lgx1 lgx2 0 301028 0 301026 0 000002只有一位有效数字 损失了5位有效数字 如果改用lgx1 lgx2 2 17149 10 6 则其结果有6位有效数字 与精确值2 171488695634 10 6非常接近 43 1 6减少运算误差的若干原则 当x接近0时当x充分大时 44 1 6减少运算误差的若干原则 防止大数 吃掉 小数计算机的位数有限 在进行加减法运算时 要对阶和规格化例如在四位浮点机上作运算0 7315 103 0 4506 10 5对阶是0 7315 103 0 0000 103 计算结果为0 7315 103 结果是大数 吃掉 了小数当参加运算的两个数的数量级相差很大时 如果不注意运算次序 就有可能把数量级小的数 吃掉 45 1 6减少运算误差的若干原则 例如 已知A 105 B 5 C 105如果按照 A B C进行运算 则结果接近于零 结果失真 如果按照 A C B进行计算 则结果接近于正确的结果5 46 1 6减少运算误差的若干原则 在除法运算中要避免出现除数的绝对值远远小于被除数绝对值的情形例 在4位浮点十进制数下 用消去法解线性方程组解 仿计算机实际计算 将上述方程组写成 47 1 6减少运算误差的若干原则 1 0 3000 10 4 2 得到下述方程组解得x1 0 x2 0 2如果反过来用第二个方程消去第一个方程中含x1的项 那么就可以避免很小的数作除数的情形 即 2 0 3000 10 4 1 得解得x1 1 4 x2 0 2 48 1 6减少运算误差的若干原则 简化计算步骤 减少运算次数例如 计算x255 如果逐个相乘 要做254次乘法 但若改成x255 xx2x4x8x16x32x64x128只要14次乘法运算即可例 计算和式的值 如果直接逐项求和 运算次数多且误差积累 但是可以进行化简 那么整个计算只要一个求倒数和一次减法就可以 49 1 6减少运算误差的若干原则 选用数值稳定性好的计算公式定义一个算法如果输入数据有误差 而在计算过程中舍入误差不增长 那么称此算法是数