数值分析第1章数值分析与科学计算引论.ppt

2020 3 26 数值分析与科学计算引论 1 第1章数值分析与科学计算引论 数值分析的对象 作用与特点数值计算的误差数值计算的误差定性分析与避免误差危害数值计算中算法设计的技术 2020 3 26 数值分析与科学计算引论 2 1 1数值分析的对象 作用与特点 1 1 1研究对象与作用 计算数学根据实际问题的数学模型提出问题求解的数值计算方法 并对方法进行理论分析和软件实现 1 1 2特点 算法能在计算机上实现 并有好的计算复杂性 面向计算机 提供切实可行的有效算法 有可靠的理论分析 能达到精度要求 算法的收敛性与数值稳定性 算法的误差分析 通过数值实验证明算法行之有效 计算机上实现数值计算 解决实际问题 1 1 3实际应用 2020 3 26 数值分析与科学计算引论 3 1 2数值计算的误差 1 2 1误差的来源与分类 模型误差 在将实际问题归结为数学模型时 需要对问题作一定的简化和假设 观测误差 数学模型中需要用到的一些系数 初值等常数来自于测量仪器或统计资料 由于客观条件和仪器精度的限制不可避免有误差 方法误差 截断误差 模型的准确解与用数值方法求得的近似解之间的误差称为 截断误差 舍入误差 在上机实际计算时 由于计算机对所运算的对象按机器字长四舍五入而产生的最终计算解与模型的准确解之间的误差 实际算法 有限 四则运算化 理论计算误差 2020 3 26 数值分析与科学计算引论 4 误差的产生 实际问题 数学模型 建模 模型误差 观测误差 数值方法 数值解 离散 截断误差 计算 舍入误差 实例 2020 3 26 数值分析与科学计算引论 5 大家一起猜 1 1 e 将作Taylor展开后再积分 舍入误差 0 743 由截去部分引起 由留下部分引起 解 2020 3 26 数值分析与科学计算引论 6 1 2 2误差与有效数字 绝对误差 absoluteerror 其中 x 准确值 x x的近似值 例如 上常记为 误差绝对值不能超过某个正数 工程 注 e 理论上讲是唯一确定的 可能取正 也可能取负 e 0时 x 称为强近似值 e 0不唯一 当然越小越具有参考价值 通常是不知道的 根据具体情况 可事先估计出误差的范围 误差绝对值的 上界 或称 误差限 即有 2020 3 26 数值分析与科学计算引论 7 例2设 3 1415926 近似值 A 3 14 它的绝对误差是0 0015926 有 A 0 0015926 0 002 0 2 10 2 可见 绝对误差限 不是唯一的 但 越小越好 例3又近似值 A 3 1416 它的绝对误差是0 0000074 有 A 0 0000074 0 000008 0 8 10 5 例4又近似值 A 3 1415 它的绝对误差是0 0000926 有 A 0 0000926 0 0001 0 1 10 3 绝对误差限并不能很好地反映近似值的好坏 x 10 x 1 y 10000 y 5 虽然 y 是 x 的5倍 但在10000内差5显然比10内差1好 2020 3 26 数值分析与科学计算引论 8 相对误差 relativeerror x 的相对误差限 实际计算中 相对误差通常取为 2020 3 26 数值分析与科学计算引论 9 例5 解 结论 俗称 好坏 多少 是相对的 设 估计近似数的绝对误差与相对误差 但是的一个好的近似 不是的好的近似 2020 3 26 数值分析与科学计算引论 10 有效数字 4 3 若近似值x 的误差限是某一位的半个单位 该位到x 的第一位非零数字共有n位 就说x 有n位有效数字 证明 注 如果x 是由x四舍五入得到的近似值 则x 的每一位都是有效数字 当x已知时 可根据需要产生每位皆有效的近似值 有n位有效数字的x 可表示为 2020 3 26 数值分析与科学计算引论 11 有效数字与相对误差的关系 有效数字 相对误差限 已知x 有n位有效数字 则其相对误差为 相对误差限 有效数字 已知x 的相对误差满足 可见x 至少有n位有效数字 2020 3 26 数值分析与科学计算引论 12 假设 取到n位有效数字 则其相对误差上限满足 要保证其相对误差限小于0 001 只要保证其上限满足 已知a1 3 则从以上不等式可解得n 6 log6 即n 6 应取 3 14159 例7为使的相对误差小于0 001 至少应取几位有效数字 解 2020 3 26 数值分析与科学计算引论 13 问题 这些公式的形式有什么特点 使你想到什么 代数运算的误差估计 1 2 3数值运算的误差估计 2020 3 26 数值分析与科学计算引论 14 函数值的误差估计 问题 对于y f x 若用x 取代x 将对y产生什么影响 由函数的泰勒展开式 函数值的相对误差 限 有 2020 3 26 数值分析与科学计算引论 15 相对误差条件数 f的条件数在某一点是小 大 则称f在该点是好条件的 坏条件的 问题 则的近似值 于是函数值的误差 2020 3 26 数值分析与科学计算引论 16 1 3误差定性分析与避免误差危害 一个工程或科学计算问题往往要运算千万次 由于每步运算都有误差 如果每步都做误差分析是不可能的 也不科学 误差积累有正有负 绝对值有大有小 都按最坏情况估计误差限得到的结果比实际误差大得多 这种保守的误差估计不反映实际误差积累 概率分析法威尔金森 Wilkinson 的向后误差分析法穆尔 Moore 的区间分析法 1 3 1舍入误差的定量分析方法 2020 3 26 数值分析与科学计算引论 17 例8计算 公式一 注意此公式精确成立 发生了什麽 1 3 2数值稳定性与误差的传播 2020 3 26 数值分析与科学计算引论 18 考察第n步的误差 公式二 注意此公式与公式一在理论上等价 方法 先估计一个IN 再反推要求的In n N 可取 2020 3 26 数值分析与科学计算引论 19 取 2020 3 26 数值分析与科学计算引论 20 考察反推一步的误差 以此类推 对n N有 误差逐步递减 这样的算法称为稳定的算法 舍入误差的定性分析 一个算法如果输入数据有扰动 即误差 而计算过程中舍入误差不增长 则称此算法是数值稳定的 否则此算法就称为不稳定的 数值稳定性 NumericalStability 2020 3 26 数值分析与科学计算引论 21 病态问题输入数据的微小扰动 即误差 引起输出数据 即问题解 的相对误差很大的数学问题 3 3 称为计算函数值问题的条件数 计算函数值时 若有扰动 相对误差为 函数值的相对误差为 相对误差比值 1 3 2病态问题与条件数 病态问题举例 计算函数值问题的条件数 很大的问题 病态问题 2020 3 26 数值分析与科学计算引论 22 函数 它表示相对误差可能放大倍 如 有 自变量相对误差为 函数值相对误差为 一般情况下 条件数就认为是病态 越大 病态越严重 的条件数 若取 这时问题可以认为是病态的 计算函数值问题举例 2020 3 26 数值分析与科学计算引论 23 避免相近二数相减 举例 a1 0 12345 a2 0 12346 各有5位有效数字 而a2 a1 0 00001 只剩下1位有效数字 几种经验性避免方法 当 x 1时 避免小分母 分母小会造成舍入误差增大 选用稳定的算法 1 3 3避免误差危害的若干原则 2020 3 26 数值分析与科学计算引论 24 避免大数吃小数 举例 用单精度计算的根 精确解为 算法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 大数吃小数 2020 3 26 数值分析与科学计算引论 25 算法2 先取再利用 求和时从小到大相加 可使和的误差减小 举例 按从小到大 以及从大到小的顺序分别计算1 2 3 40 109 先化简再计算 减少步骤 避免误差积累 一般来说 计算机处理下列运算的速度为 如计算多项式的值用秦九韶法 P11 2020 3 26 数值分析与科学计算引论 26 算法设计的好坏影响计算结果的精度 好算法大量节省计算时间 1 4数值计算中算法设计的技术 算法设计的一个重要原则 减少运算次数 1 4 1多项式求值的秦九韶算法 设给定次多项式 求处的值 直接计算再相加 加法次数 减少计算量 减少误差 多项式求值 乘法次数 计算量 2020 3 26 数值分析与科学计算引论 27 记 4 1 则 求在点的值 其中 秦九韶算法 计算量 加法次数 乘法次数 优点 由 4 1 式 2020 3 26 数值分析与科学计算引论 28 对求导得 故 则 4 1 其中 计算的秦九韶算法 2020 3 26 数值分析与科学计算引论 29 此处 例8设 用秦九韶算法求和的值 用 4 1 和 4 2 式构造出计算表格 1 2 解 2020 3 26 数值分析与科学计算引论 30 迭代法举例 开方运算 迭代法 数值计算普遍使用的重要方法 1 4 2迭代法与开方求值 迭代法的构造 先给定一个初始近似 令 是一个校正量 称为增量 按同一公式重复计算逐次逼近真值的方法 即 舍去高阶项 则得 即 2020 3 26 数值分析与科学计算引论 31 4 4 这里不是的真值 但它是真值的进一步近似 重复以上过程进行迭代 它可逐次求得若 则 容易证明序列对任何均收敛 1次加法1次除法1次移位 例9用迭代法 4 4 求 取 若计算精确到 由 4 4 式可求得 迭代3次误差即小于 解 2020 3 26 数值分析与科学计算引论 32 1 4 3以直代曲与化整为 零 数值计算 将非线性问题线性化 圆周率的计算是古代数学的一个光辉成就 充分体现了以直代曲化整为 零 的思想 图1 1 几何 在局部范围内用直线近似曲线 2020 3 26 数值分析与科学计算引论 33 方程求根的牛顿迭代法 求函数方程的根 图1 2 以直代曲相当于用切线方程 的根近似 从而 4 5 牛顿迭代法 以直代曲举例 几何上表现为平面上的一条曲线 它与轴交点的横坐标即为方程的根 2020 3 26 数值分析与科学计算引论 34 4 6 定积分计算的梯形公式与复合梯形公式 梯形公式