西北工业大学计算方法课件第一章绪论nwpu.ppt

计算方法讲义 教材 计算方法 计算方法课程组 作业 计算方法作业集 A B 参考书 1 封建湖 车刚明 计算方法典型题分析解集 第二版 西北工业大学出版社 2001 2 封建湖 聂玉峰 王振海 数值分析导教导学导考 西北工业大学出版社 2003 课时数 32 第一章绪论 内容提要 1 1引言 1 2误差的度量与传播 1 3数值试验与算法性能比较 1 1引言 提出实际问题辨析其中的主要矛盾和次要矛盾 并在合理假设的条件下 运用各种数学理论 工具和方法 建立起问题中不同量之间的联系 即得到数学模型 建立数学模型模型的适定性 数学模型解的存在性 模型内部没有蕴含矛盾 惟一性 模型是完备的 以及对原始数据具有的连续依赖性统称为模型的适定性 科学与工程计算过程 提出数值问题数值问题是指有限个输入数据 问题的自变量 原始数据 与有限个输出数据 待求解数据 之间函数关系的一个明确无歧义的描述 这正是数值分析所研究的对象 数值问题举例 是用一阶常微分方程初值问题表示的数学模型 要求无穷多个输出 因而它不是数值问题 但当我们要求出有限个点处函数值的近似值时 便成为一数值问题 设计高效可靠的算法计算方法的任务之一就是提供求得数值问题近似解的方法 算法 算法 指把对数学问题的解法归结为只有加 减 乘 除等基本运算 并确定运算次序的完整而准确的描述 算法分类 分类方法1 若算法包含有一个进程则称其为串行算法 否则为并行算法 分类方法2 从算法执行所花费的时间角度来讲 若算术运算占绝大多数时间则称其为数值型算法 否则为非数值型算法 本课程介绍数值型串行算法 其它类型算法参阅数据结构 并行算法等课程 算法的可靠性 算法的可靠性包括算法的收敛性 稳定性 误差估计等几个方面 这些是数值分析研究的第二个任务 一个算法在保证可靠的大前提下再评价其优劣才是有价值的 算法的优劣评价 可靠算法的优劣 应该考虑其时间复杂度 计算机运行时间 空间复杂度 占据计算机存储空间的多少 以及逻辑复杂度 影响程序开发的周期以及维护 这是数值分析研究的第三个任务 例1 例2秦九韶算法 算法应用状态 计算方法研究对象以及解决问题方法的广泛适用性 著名流行软件如Maple Matlab Mathematica等已将其绝大多数内容设计成函数 简单调用之后便可以得到运行结果 但由于实际问题的具体特征 复杂性 以及算法自身的适用范围决定了应用中必须选择 设计适合于自己特定问题的算法 因而掌握数值方法的思想和内容是至关重要的 科学与工程计算过程小结 提出实际问题建立数学模型提出数值问题设计可靠 高效的算法程序设计 上机实践计算结果计算结果的可视化在具体问题的求解过程中 上述步骤形成一个循环 科学计算 数值模拟 已经被公认为与理论分析 实验分析并列的科学研究三大基本手段之一 鉴于实际问题的复杂性 通常将其具体地分解为一系列子问题进行研究 本课程主要涉及如下几个方面问题的求解算法 函数的插值和曲线拟合数值积分和数值微分线性方程组求解 非线性方程 组 求解代数特征值问题常微分方程数值解法 本课程主要内容 本课程的学习方法 尽管我们所学算法有限 但许多仍有学多学生会觉得公式多 理论分析复杂 我们提出如下的几点学习方法 仅供初学者参考 1 以算法的理论分析为基础 理解记忆公式 2 搞清各章问题的基本提法 算法提出的背景 3 理解每个算法建立的数学背景 数学原理和基本线索 熟练掌握最基本的算法 4 从各种算法的理论分析中学习推理证明方法 提高推理证明能力 5 认真进行数值计算的训练 1 2误差的度量与传播 内容提要 一 误差的来源二 误差的度量三 误差的传播 一 误差来源及其分类 1 模型误差 描述误差 反映实际问题有关量之间的计算公式 数学模型 通常是近似的 2 观测误差数学模型中包含的某些参数是通过观测得到的 在计算方法中不研究这两类误差 总是假定数学模型是正确合理的反映了客观实际问题 3 截断误差 方法误差 数值方法精确解与待求解模型的理论分析解之间的差异 这是由于我们需要将无穷过程截断为有限过程 而使得算法必须在有限步内执行结束而导致的 例如 4 舍入误差在实现数值方法的过程中 由于计算机表示浮点数采用的是有限字长 因而仅能够区分有限个信息 准确表示某些数 不能准确表示所有实数 这样在计算机中表示的原始输入数据 中间计算数据 以及最终输出结果必然产生误差 称此类误差为舍入误差 如利用计算机计算e的近似值en时 实际上得不到en的精确值 只能得到en的近似e 这样e 作为e的近似包含有舍入误差和截断误差两部分 二 误差的度量 绝对误差相对误差有效数字各种度量之间的关系 1 绝对误差 绝对误差定义 准确值减近似值 绝对误差限 2 相对误差 Remark 绝对误差限虽然能够刻划对同一真值不同近似的好坏 但它不能刻划对不同真值近似程度的好坏 3 有效数字 为了规定一种近似数的表示法 使得用它表示的近似数自身就直接指示出其误差的大小 为此需要引出有效数字和有效数的概念 有效数 当x 准确到末位 即n p 则称x 为有效数 举例 x x1 3 141 x2 3 142 3位有效数字 非有效数 4位有效数字 有效数 Remark1 有效数的误差限是末位数单位的一半 可见有效数本身就体现了误差界 Remark2 对真值进行四舍五入得到有效数 Remark3 准确数字有无穷多位有效数字 Remark4 从实验仪器所读的近似数 最后一为是估计位 不是有效数 估计最后一位是为了确保对最后一位进行四舍五入得到有效数 例从最小刻度为厘米的标尺读得的数据123 4cm是为了得到有效数123 cm 读得数据156 7cm是为了得到有效数157 cm 4 误差度量间的联系 绝对误差与相对误差 绝对误差与有效数字 相对误差与有效数字 定理证明 证毕 Remark1 该定理实质上给出了一种求相对误差限的方法 2 仅从并不能保证x 一定具有n位有效数字 如设其近似值a 0 484 其相对误差为 我们并不能由此断定a有两位有效数字 因为 例题 解 三 误差的传播 概念 近似数参加运算后所得之值一般也是近似值 含有误差 将这一现象称为误差传播 误差传播的表现 算法本身可能有截断误差 初始数据在计算机内的浮点表示一般有舍入误差 每次运算一般又会产生新的舍入误差 并传播以前各步已经引入的误差 误差有正有负 误差积累的过程一般包含有误差增长和误差相消的过程 并非简单的单调增长 运算次数非常之多 不可能人为地跟踪每一步运算 初值误差传播 假设每一步都是准确计算 即不考虑截断误差和由运算进一步引入的舍入误差 仅介绍初始数据的误差传播规律 研究方法 泰勒 Taylor 方法n元函数 复习泰勒公式 泰勒公式分析初值误差传播 相对误差 进而得到如下绝对误差限和相对误差限传播关系 对于一元函数 有如下初值误差传播近似计算公式 二元函数算术运算误差传播规律 绝对误差限 相对误差限 尽量避免相近的数相减例x 52 127x 52 129四位有效数字y 52 123y 52 121四位有效数字A x y 0 004A x y 0 008零位有效数字结论 避免相近数相减 1 3数值试验与算法性能比较 一些避免相近数相减示例当 x 1时 当 x 1时 两种算法的相对误差图比较 尽可能避免绝对值很小的数做分母 防止出现溢出 当a b中有近似值时 由 若 则可能很大 当a b都是准确值时 由于很大 会使其它较小的数加不到中而引起严重误差 或者会发生计算机 溢出 导致计算无法进行下去 算例用不同位数的浮点数系统求解如下线性方程组 算法1 顺序消去法 分别保留4位和7位小数进行计算 算法2 将第1个和第2个方程交换次序后 使用消去法分别保留4位和7位小数进行计算 准确解 计算结果 选用数值稳定性好的算法 定义 一个算法 如果在运算过程中舍入误差在一定条件下能够得到控制 或者舍入误差的增长不影响产生可靠的结果 则称该算法是数值稳定的 否则称其为数值不稳定 例 计算如下积分近似值的两种方案比较 方法1 方法1计算结果 方法一结果分析 方法一分析 计算结果表明 舍入误差的传播近似依5的幂次进行增长 因而是一种不稳定的方法 方法二 由此分析知 该方法是稳定的 关于初值的近似可由下面式子得到 方法2计算结果 总之 除了算法的正确性之外 在算法设计中至少还应 1尽量避免两个相近的近似数相减 2合理安排量级相差很大的数之间的运算次序 防止大数 吃掉 小数 3尽可能避免绝对值很小的数做分母 4防止出现溢出 5简化计算步骤以减少运算次数 6选用数值稳定性好的算法 本章知识结构图 本章典型例题 例1 指出如下有效数的有效数字位数并计算绝对误差限和相对误差限 解 1 x 有2位有效数字 绝对误差限为 相对误差限为 2 y 有3位有效数字 绝对误差限为 相对误差限为 3 z 有5位有效数字 绝对误差限为 相对误差限为 解 由题意知 近似数x 的绝对误差限 相对误差限 例2 已知试求的相对误差限 注意 此处正好有 解 例3 已知桌子长宽近似值 并且已知 求近似面积的绝对误差限和相对误差限 例4 下列公式如何变形才能使数值计算得到比较精确的结果