计算方法第一章r.ppt

计算方法 吴开谡wuks 教材 西安交通大学出版社 计算方法 作者 邓建中 第一章计算方法的一般概念 1计算方法的意义 内容与方法 实际问题 数学模型 数值计算方法 程序设计 计算机计算出结果 应用数学 计算数学 计算数学的根本任务是研究怎样通过计算机所能执行的基本运算 加 减 乘 除等 求出所研究的问题的数值解或近似数值解 由基本运算和运算顺序的规定所构成的完整的解题步骤 称为算法 1 构造计算机能用的算法 例1 计算sinx x 0 4 例2 求解函数方程f x 0 例3 求解常微分方程 一个具体的例子 迭代格式为 精确解 2 怎样才能算的又快又省 算法要既要节省内存又要运算速度快 例 计算多项式 需10次乘法4次加法 4次乘法4次加法 这是多项式计算的秦九韶算法 3次乘法5次加法 下面给出秦九韶算法的一般计算格式 对于多项式计算x a的值p a 记第k个内括号的值为bk 记b0 a0 bn p a 则秦九韶算法计算公式为 对于复杂大型的计算 计算速度与内存节省具有决定意义 例 解代数方程 用Cramer法则解 3 计算结果可靠计算机在计算过程中对数有要求与限制 不符合要求的作近似处理 用近似数计算 有时会对计算带来较大影响 例 解为 x1 x2 x3 1 如近似为 则解为 例 求方程根 如z10系数 210略有误差 为 210 000000119 则根20变为20 847 19和18变为19 502 1 94i 例 求解微分方程 某些问题的计算中 由于数据的微小变化引起解的剧烈变化 称这类问题为病态问题和坏条件问题 对于这类问题的计算 一定要采用高精度计算 但对于非病态的良态问题 如算法不当 由于计算机的近似性 有时也可能得到不可靠的结果 例 如在尾数为4位的计算机上计算其真正值为0 05572809 但计算结果为 0 0560 但如果先进行有理化在计算 结果为 0 05574 显然 后一种计算精度高 例 如在尾数为4位的计算机上计算精确值为34 5612 计算时如先加前两项 再加后一项 结果为34 57 如先加后两项 再加前一项 结果为34 56 显然 后一种算法更好 例 如在尾数为4位的计算机上计算按两种不同递推计算 结果为 由此可见 舍入误差对计算有影响 影响小的算法称为数值稳定的算法 有些算法具有递推性 称之为迭代法或逐次逼近法 再计算一些复杂的函数的值 有时我们用一些简单的函数 如多项式 有理函数等 来近似之 这称为函数逼近 有时要求逼近函数与被逼近函数之间在某些点函数值及若干阶导数值相等 这种逼近称为插值 有时要求在逼近区间上的最大误差取极小 这称为最佳一致逼近 或在某些点的误差值平方和取极小 这称为最佳平方逼近 2误差及有关概念2 1误差的来源真实值与我们所获得的值之间的差异就是误差 对实际问题的研究需要建立数学模型 这带来模型误差 求解数学问题时需要若干参量和初始值 这些数据往往通过对实际问题的观测得到 由于观测引起的误差称为观测误差 数据误差 模型参量误差 求解数学问题时 由于算法而引起的误差称为方法误差 截断误差 计算机计算时只能对有限位数进行计算 超过的进行舍入 由此引起的误差称为舍入误差 计算误差 实际问题 数学问题 可计算问题 数学建模 构造算法 计算求解 计算结果 模型误差 方法误差 舍入误差 输入数据误差 2 2绝对误差与相对误差设x为真正值 为近似值 称 为近似值的绝对误差 简称误差 通常我们要求绝对误差不能超过某个值 称为绝对误差限或误差限 设x为真正值 为近似值 称 为的相对误差 如果存在 r 使得 称之为相对误差限 在实际计算中 相对误差限很小时 也取 2 3有效位数与有效数字如果的误差限为0 5 10 n 即则称其准确到小数后第n位 并称的第一个非零数字到第n位的全部数字为的有效数字 例如 若x 3 1415926535 则 准确到小数后4位 具有5位有效数字 显然 近似值的绝对误差越小 其准确到小数后的位数越多 注意 若x 0 200001 则 作为x的近似只有1位有效数字 而 作为x的近似具有4位有效数字 具有k位有效数字 则易知 若 这说明近似值的相对误差越小 其有效数字越多 2 4数据误差的影响2 4数据误差的影响对两个数x1和x2 简单计算可得 可见 当x1和x2同号时 反之 当x1和x2异号时 尤其 这表明 大小接近的异号数相加或大小接近的同号数相减 会严重损失有效数字 乘数绝对值很大 或除数接近零时 可能会严重扩大绝对误差 减少精度 开方会减少相对误差 提高精度 一般地 设数学问题的解为 近似解为 则绝对误差为 相对误差为 和起对误差的放大和缩小作用 其绝对值分别称为所求解的数学问题的绝对误差下的条件数和相对误差下的条件数 条件数很大时称该问题为病态问题或坏条件问题 它是问题固有的属性 与算法无关 但由于这类问题数据的微小变化会引起解的剧烈变化 对于这类问题的计算 一般要采用高精度计算 或改变问题的提法 降低条件数 2 5舍入误差的影响 在计算机中 用浮点法表示的数 称为浮点数 的尾数 位数是固定的 称为字长 设计算机字长为t 任意数x十进制是按舍入原则表为浮点数则相对误差的绝对值 记称 为计算机的相对精度 我们有 则对于多数相加相对误差 类似地有在大体相同情况下 如则于是可得 多数相加时 一般先加绝对值较小的数 相对误差较小 通常称舍入误差对计算结果影响不大的算法为稳定的算法 反之为不稳定的算法 计算数学的特点 1 面向计算机 构造计算机能用的算法 2 要有可靠的理论分析 指误差 算法的收敛性 稳定性等 3 要有好的计算复杂性 指算法省时 节省内存 4 要有数值试验 检验算法及程序的正