第一章数值计算方法与误差分析

第一章数值计算引论 数值计算方法就是要解决如何让计算机计算数值 如解方程 解方程组 求积分等 不仅算得快 用的机时少 而且也要算得准 与真实值的误差小 的问题 如果光算得快 算得不准 超过了误差范围 计算出来的结果不能用 计算也就没有什么意义 如何才能让计算机既算得快又算得准 误差达到最小 呢 这就需要掌握一些误差知识 本章介绍的内容 数值计算方法的含义及其特点 误差的来源 误差的有关概念 绝对误差 相对误差 有效数字 误差的传播过程 算法的数值稳定性概念 选用数值算法的若干原则 第一节数值计算方法 数值计算方法是应用数学的一个分支 又称数值分析或计算方法 它是研究用计算机求解各种数学问题的数值方法及其理论的一门学科 是程序设计和对数值结果进行分析的依据和基础 我们知道 用计算机解决科学计算问题需要经过以下几个过程 提出具体问题 建立数学模型 选用数值计算方法 程序设计 上机调试直至得出最终数值结果 可见 选用数值计算方法是应用计算机进行科学计算全过程的一个重要环节 数值计算方法特点 1 面向计算机 根据计算机特点提供实际可行的有效算法 即算法只能包括加 减 乘 除和逻辑运算 是计算机所能直接处理的 2 有可靠的理论分析 能任意逼近并达到精度要求 对近似算法要保证收敛性和数值稳定性 还要对误差进行分析 有相应的数学理论做基础 3 有好的计算复杂性 包括空间复杂度和时间复杂度 算法需占用的存储空间要小 运算次数要少 这也是建立算法要研究的问题 它关系到算法能否在计算机上实现 第二节科学计算中误差的来源 用计算机解决科学计算问题通常经历以下过程 据此误差的来源主要有以下四类 实际问题 数学模型 数值计算方法 程序设计 上机计算结果 一 模型误差 在将实际问题转化为数学模型的过程中 为了使数学模型尽量简单 以便于分析或计算 往往要忽略一些次要的因素 进行合理的简化 这样 实际问题与数学模型之间就产生了误差 这种误差称为模型误差 由于这类误差难于作定量分析 所以在计算方法中 总是假定所研究的数学模型是合理的 对模型误差不作深入的讨论 二 观测误差 在数学模型中 一般都含有从观测 或实验 得到的数据 如温度 时间 速度 距离 电流 电压等等 但由于仪器本身的精度有限或某些偶然的客观因素 会引入一定的误差 这类误差叫做观测误差 通常根据测量工具或仪器本身的精度 可以知道这类误差的上限值 所以无需在数值分析中作过多的研究 当数学模型得不到精确解时 要用数值计算方法求它的近似解 由此产生的误差称为截断误差或方法误差 譬如在数值计算中 常用收敛的无穷级数的前几项来代替无穷级数进行计算 即抛弃了无穷级数的后段 这样就产生了截断误差 三 截断误差 方法误差 截断误差举例 例如sinx x x3 3 x5 5 x7 7 x 当 x 很小时 常用x代替sinx 其截断误差大约为x3 6 截断误差的大小 直接影响数值计算的精度 所以它是数值计算中必须十分重视的一类误差 四 舍入误差 由于计算机字长有限 原始数据的输入及浮点运算过程中都可能产生误差 而事实上 无论用电子计算器计算还是笔算 都只能用有限位小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数 这样产生的误差叫做舍入误差 在数值计算中 往往要进行成千上万次四则运算 因而就会有成千上万个舍入误差产生 这些误差一经叠加或传递 对精度可能有较大的影响 所以 作数值计算时 对舍入误差应予以足够的重视 小结 上述四类误差都会影响计算结果的准确性 但模型误差和观测误差往往需要会同各有关学科的科学工作者共同研究 因此在计算方法课程中 主要研究截断误差和舍入误差 包括初始数据的误差 对计算结果的影响 第三节误差的有关概念 一 绝对误差和绝对误差限 定义1假设某一量的准确值为x 近似值为x 则x与x 之差叫做近似值x 的绝对误差 简称误差 记为 x 即 x x x x 的大小标志着x 的精确度 一般地 在同一量的不同近似值中 x 越小 x 的精确度越高 当 x 较小时 由微分和增量的关系知x 的绝对误差 x dx 故我们可以利用微分估计误差 绝对误差限的概念 由于准确值x一般不能得到 于是误差的准确值也无法求得 但在实际测量计算时 可根据具体情况估计出它的大小范围 也就是指定一个适当小的正数 使 x x x 我们称 为近似值x 的绝对误差限 有时也用x x 表示近似值的精度或准确值的所在范围 在实际问题中 绝对误差一般是有量纲的 例如 测得某一物体的长度为5m 其误差限为0 01m 通常将准确长度 记为 5 0 01即准确值在5m左右 其误差限为0 01m的误差限 二 相对误差和相对误差限 绝对误差的大小并不能确定近似程度的好坏 例如 有两个温度计 其一测量1000 时的绝对误差限为5 而另一测量100 时的绝对误差限为1 虽然后者绝对误差限的数值较小 但第一种温度计更为精确 可见 决定一个量的近似值的精确度除了要看绝对误差的大小外 还要考虑到该量本身的大小 据此 我们引进相对误差的概念 相对误差的概念 定义2我们把绝对误差与准确值之比 r x x x x x x x 0称为x 的相对误差 由于准确值x往往是不知道的 因此在实际问题中 当 r x 较小时 常取 r x x x 一般地 在同一量或不同量的几个近似值中 r x 小者精确度高 相对误差是一个无量纲量 相对误差限的概念 在实际计算中 由于 x 与x都不能准确地求得 因此相对误差 r x 也不可能准确地得到 我们只能估计它的大小范围 即指定一个适当小的正数 使 r x x x 称 为近似值x 的相对误差限 当 r x 较小时 可以用下式来计算 x 相对误差限概念举例 显然 上例第一种温度计的相对误差限为5 1000 而第二种的相对误差限为1 100 它是前者的两倍 三 有效数字 为了既能表示近似数的大小 又能表示近似数的精确程度 我们下面介绍有效数字的概念 注意 有效数字既能表示近似数的大小 又能表示近似数的精确程度 半个单位的概念 为了理解有效数字的概念 首先要弄清什么是半个单位 我们知道 当x有很多位数字时 常常按照 四舍五入 原则取前几位数字作为x的近似值x 例1设x 3 1415926 取x1 3作为 的近似值 则 1 x 0 1415 0 5 100 取x2 3 14 则 2 x 0 00159 0 5 10 2 取x3 3 1416 则 3 x 0 0000074 0 5 10 4 它们的误差都不超过末位数字的半个单位 有效数字的概念 定义3若近似值x 的绝对误差限是某一位上的半个单位 该位到x 的第一位非零数字一共有n位 则称近似值x 有n位有效数字 或说x 精确到该位 准确数本身有无穷多位有效数字 即从第一位非零数字以后的所有数字都是有效数字 有效数字举例 如例1中的x 1 x 2 x 3 分别有1 3 5位有效数字 实际上 用四舍五入法取准确值x的前n位 不包括第一位非零数字前面的零 作为它的近似值x 时 x 有n位有效数字 例2设x 4 26972 则按四舍五入法 取2位 x1 4 3有效数字为2位 取3位 x2 4 27 有效数字为3位 取4位 x3 4 270 有效数字为4位 特别注意 近似值后面的零不能随便省去 如例2中4 27和4 270 前者精确到4 27 有效数字为3位 取4位 x3 4 270 有效数字为4位 可见 它们的近似程度完全不同 与准确值的最大误差也完全不同 有效数字和绝对误差的关系 定义3换一种说法就是 设x的近似值x 0 a1a2 an 10p若其绝对误差 x x x 0 5 10p n则称近似数x 具有n位有效数字 这里p为整数 a1 a2 an是0到9中的一个数字且a1 0 例如 若x 0 23156 10 2是x的具有五位有效数字的近似值 则绝对误差是 x x 0 5 10 2 5 0 5 10 7定义3或式 x x x 0 5 10p n建立了绝对误差 限 和有效数字之间的关系 由于n越大 10p n的值越小 所以有效数字位越多 则绝对误差 限 越小 有效数字与相对误差的关系 定理1若近似数x 具有n位有效数字 则其相对误差为 r x 1 2 a1 10 n 1 其中a1 0是x 的第一位有效数字 定理1说明有效数字位越多 相对误差 限 越小 定理2形式如x 0 a1a2 an 10p的近似数x 若其相对误差满足 r x 1 2 a1 1 10 n 1 则x 至少有n位有效数字 由此可知 有效数字位数可刻画近似数的精确度 相对误差 限 与有效数字的位数有关 有效数字与相对误差关系举例 注意从并不能保证x 一定具有n位有效数字 如x sin29020 0 4900设其近似值x 0 484 其相对误差为我们不能由此推出x 有两位有效数字 这是因为x x 0 4900 0 484 0 0060 0 005即可知近似值x 并不具有两位有效数字 实际上 x 只有一位有效数字 r x 1 2 a1 10 n 1 第四节数值运算中误差的传播 要分析数值运算中误差的传播 首先就要估计数值运算中的误差 数值运算的误差估计情况较复杂 通常利用微分来估计误差 一 利用微分估计误差 1 一元函数设y f x 为一元函数 则计算函数值的误差为 y y y f x f x dy f x dx f x x 解的相对误差 r y dy y 一元函数的误差估计举例 例正方形的边长约为100cm 怎样测量才能使其面积误差不超过1cm2 解设正方形的边长为xcm 测量值为x cm 面积y f x x2f x 2x y y y dy f x dx f x x f x x 2x x 200 x 由于 y 1即 200 x 1所以 x 0 005cm 2 二元函数设数学问题的解y与变量x1 x2有关 y f x1 x2 若x1 x2的近似值为x1 x2 相应解为y 则当数据误差较小时解的绝对误差 y y y f x1 x2 f x1 x2 dy f x1 x2 x1 x1 f x1 x2 x2 x2 解的相对误差 r y dy y f x1 x2 xi xi f x1 x2 r xi i 1 2 利用这两式可得到两数和 差 积 商的误差估计 二 和差误差估计 设y f x1 x2 x1 x2 利用式 y y y f x1 x2 f x1 x2 dy f x1 x2 x1 x1 f x1 x2 x2 x2 可得 x1 x2 x1 x2 x1 x2 x1 x2 x1 x2 因此 任何两个数之和的绝对误差等于两个数的绝对误差之和 任何两个数之和的绝对误差限为这两个数的绝对误差限之和 且可推广到有限多个数相加的情形 所以作大量加减运算后的绝对误差是绝不可以忽视的 由于加法和减法是互为逆运算关系 所以减法可以化为加法情形讨论 两数之和的相对误差 利用式 r y dy y f x1 x2 xi xi f x1 x2 r xi i 1 2 可得两个数之和的相对误差为 r x1 x2 x1 x1 x2 r x1 x2 x1 x2 r x2 当x1和 x2相当接近时x1 x2 0 x1 x1 x2 和 x2 x1 x2 都将很大 所以相近两数之差的相对误差将很大 即原始数据的误差会对计算结果产生很大的影响 和差误差估计举例 例1用四位有效数字计算y 的值 解如果直接计算 则y 31 64 31 62 0 02由于y的准确值是0 0158074374 可见直接计算所得的近似值仅有一位有效数字 其相对误差大于26 若作适当变形后计算 可以避免相近两数相减的计算 如y 1 63 26 0 01581所得结果与准确值比较可知具有四位有效数字 其相对误差不超过0 02 所以在数值计算中 必须避免相近两数相减 以免损失有效数字的位数 三 积商误差估计 利用微分可得两数积的绝对误差为 x1x2 d x1x2 x2 x1 x1 x2 相对误差为 r x1x2 x1x2 x1x2 r x1 r x2 两数商的绝对误差为 x1 x2 d x1 x2 x2 x1 x1 x2 x22 x2 0 相对误差为 r x1 x2 x1 x2 x2 x1 r x1 r x2 x2 0 从而得出 两数乘积的相对误差 可看作是各乘数的相对误差之和 两数商的相对误差 可看作是被除数与除数的相对误差之差 上述误差积累规律 对多个近似数的运算也是成立的 通常 任意多次连乘连除所得结果的相对误差限 可看作是各乘数和除数的相对误差限之和 第五节算法的数值稳定性 一 算法的数值稳定性概念 所谓算法 是指对一些数据按某种规定的顺序进行的运算序列 在实际计算中 对于同一问题我们选用不同的算法 所得结果的精度往往大不相同 这是因为初始数据的误差或计算中的舍入误差在计算过程中的传播 因算法不同而异 于是就产生了算法的数值稳定性问题 一个算法 如果计算结果受误差的影响小 就称这个算法具有较好的数值稳定性 否则 就称这个算法的数值稳定性不好 例如在第四节的例1中 第一种算法就是不稳定的 而第二种算法是数值稳定的 算法的数值稳定性概念举例 例1一元二次方程X2 2pX q 0的两个根分别是 x1 p p2 q 0 5 x2 p p2 q 0 5当p 0 5 105 q 1时 方程的两个根取11位有效数字为 x1 99999 999990 x2 0 000010000000001在高精度的计算机 进制 10 字长t 8 浮点阶码下限L 50 浮点阶码上限U 50 上直接用上述公式计算的结果为 x1 100000 00 x2 0可见 结果x1很好 而x2很不理想 这说明直接用上述公式计算第二个根是不稳定的 其原因在于在计算x2时造成相近两数相减 从而使有效数字严重损失 请看下面的求解方法 一元二次方程X2 2pX q 0的求解方法 根据根与系数的关系可知x1x2 q 1所以x2 1 x1因此 如果仍用上述方法算出x1 然后用x2 1 x1计算x2 可得x1 100000 00 x2 0 00001000该结果是非常好的 这就说明这种算法有较好的数值稳定性 一般说来 当 p q 时 用公式x1 p sign p p2 q 0 5 x2 q x1来求解方程X2 2pX q 0是数值稳定的 从而可知 算法数值稳定性的讨论甚为重要 二 设计算法的若干原则 为防止误差使计算结果失真 失常 现象发生 要选用数值稳定的计算公式 以保证算法的数值稳定性 下面我们给出设计算法的若干原则 并给出改善算法的例子 这些原则有助于鉴别算法的可靠性并防止误差危害的现象产生 一 要避免相近两数相减 在第四节例1和本节例1中 我们已看到这一原则实际应用的效果 下面再举几个例说明改善算法的方法 例 x充分大时1 x 1 x 1 1 x x 1 1 x 1 2 x1 2 1 1 x 1 2 x1 2 例 对于小的正数 sin x sinx 2cos x 2 sin 2 注 sin x sin y 2cos x y 2 sin x y 2 例 对于绝对值小的x 可利用泰勒级数ex 1 x x2 2 x3 6 取前n项来计算 二 要防止大数 吃掉 小数 注意保护重要数据 在数值运算中 参加运算的数有时数量级相差很大 而计算机位数有限 如不注意运算次序就可能出现大数 吃掉 小数的现象 影响计算结果的可靠性 例5在五位浮点十进制计算机上 计算y 54321 0 4 0 3 0 4如果按从左到右的顺序进行加法运算 后三个数都在对阶过程中被当作零 得出含有较大绝对误差的结果y 54321 要避免这种大数 吃掉 小数的现象 可以调整计算顺序 采用先小数后大数的计算次序 即先将0 4 0 3 0 4加起来 然后再加上54321 结果等于54322 一般情况下 若干数相加 采用绝对值较小者先加的算法 结果的相对误差限较小 三 注意简化计算步骤 减少运算次数 避免误差积累 同一个计算问题 如果能减少运算次数 不但可以提高计算速度 而且能减少误差的积累 简化计算步骤 减少运算次数 避免误差积累的例子 例6计算多项式P4 x 0 0625x4 0 425x3 1 215x2 1 912x 2 1296的值 如果先计算各项然后相加 需做十次乘法和四次加法 如改用下式计算 0 0625x 0 425 x 1 215 x 1 912 x 2 1296则只需做四次乘法和四次加法 秦九韶算法 通常 计算多项式Pn x anxn an 1xn 1 a1x a0的值 若直接计算再逐项相加 一共需做n n 1 2次乘法和n次加法 若采用Pn x anx an 1 x an 2 x a1 x a0即 秦九韶算法 则只需n次乘法和n次加法就可以算出Pn x 的值 秦九韶算法 的优点是不仅运算量小 而且数值稳定 秦九韶算法的计算机实现 Pn x anx an 1 x an 2 x a1 x a0为计算多项式Pn x anxn an 1xn 1 a1x a0的秦九韶算法 计算机实现可按下面的步骤进行 y an for i n 1 i 0 i y y x ai 只需n次乘法和n次加法 简化计算步骤 减少运算次数 避免误差积累的例子 又如计算1 1 2 1 2 3 1 1000 1001 的值 若一项一项进行计算 不仅计算次数多 而且误差积累也很大 若简化成1 1 1001进行计算 则整个计算只要一次求倒数和一次减法 四 要避免绝对值小的数作除数 由式 x1 x2 d x1 x2 x2 x1 x1 x2 x22 x2 0 可知 当除数x2接近于零时 商的绝对误差就可能很大 因此 在数值计算中要尽量避免绝对值小的数作除数 避免的方法是把算式变形或改变计算顺序 例8当x接近于0时 1 cosx sinx的分子 分母都接近0 为避免绝对值小的数作除数 可将原式化为 1 cosx sinx sinx 1 cosx 例9当x很大时 可化x x 1 0 5 x0 5 x x 1 0 5 x0 5 五 设法控制误差的传播 许多算法常常具有递推性 如计算多项式值的秦九韶算法 求方程根的牛顿迭代法等 利用递推关系进行计算时 运算过程比较规律 相当方便 但多次递推 必须注意误差的积累 如果递推过程中误差增大 多次递推会得到错误的结果 如果递推过程中误差减小 则得出的结果比较准确 控制误差传播的例子 例10计算积分In 01xnex 1dx n 0 1 2 9利用分部积分法 可得In xnex 1 01 01ex 1dxn 1 n 01xn 1ex 1dx 1 nIn 1从而有递推公式I0 01ex 1dx ex 1 01 1 e 1 0 6321In 1 nIn 1 n 0 1 2 9 计算积分In 01xnex 1dx的过程 如果直接应用递推公式I0 01ex 1dx ex 1 01 1 e 1 0 6321In 1 nIn 1 n 1 2 9 用四位小数计算依次得到 0 6321 0 3679 0 2642 0 2074 0 17040 1480 0 1120 0 2160 0 7280 7 5520由此看到I8为负值 I9 1 显然与一切0 In 1 由于e 1 n 1 min ex 1 01xndx In 0 x 1 max ex 1 01xndx 1 n 1 矛盾 事实上 从I7开始已经连一位有效数字也没有了 I7 1 8 0 125 而上面算得I7 0 2160 是什么原因造成这种结果呢 计算积分In 01xnex 1dx的误差分析 根据I0 01ex 1dx ex 1 01 1 e 1 0 6321In 1 nIn 1 n 1