文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
第一章 绪 论
本章以误差为主线，介绍了计算方法课程的特点，并概略描述了与算法相关的基本概
念，如收敛性、稳定性，其次给出了误差的度量方法以及误差的传播规律，最后，结合数值实验指出了算法设计时应注意的问题．
§1.1 引 言
计算方法以科学与工程等领域所建立的数学模型为求解对象，目的是在有限的时间段内
利用有限的计算工具计算出模型的有效解答。
由于科学与工程问题的多样性和复杂性，所建立的数学模型也是各种各样的、复杂的. 复杂性表现在如下几个方面：求解系统的规模很大，多种因素之间的非线性耦合，海量的数据处理等等，这样就使得在其它课程中学到的分析求解方法因计算量庞大而不能得到计算结果，且更多的复杂数学模型没有分析求解方法． 这门课程则是针对从各种各样的数学模型中抽象出或转化出的典型问题，介绍有效的串行求解算法，它们包括
(1) 非线性方程的近似求解方法； (2) 线性代数方程组的求解方法；
(3) 函数的插值近似和数据的拟合近似； (4) 积分和微分的近似计算方法； (5) 常微分方程初值问题的数值解法； (6) 优化问题的近似解法；等等
从如上内容可以看出，计算方法的显著特点之一是“近似”． 之所以要进行近似计算，这与我们使用的工具、追求的目标、以及参与计算的数据来源等因素有关．
计算机只能处理有限数据，只能区分、存储有限信息，而实数包含有无穷多个数据，这样，当把原始数据、中间数据、以及最终计算结果用机器数表示时就不可避免的引入了误差，称之为舍入误差．
我们需要在有限的时间段内得到运算结果，就需要将无穷的计算过程截断，从而产生截
11111???的计算是无穷过程，当用en?1?????作为e的1!2!1!2!n!近似时，则需要进行有限过程的计算，但产生了截断误差en?e．
断误差． 如e?1? 当用计算机计算en时，因为舍入误差的存在，我们也只能得到en的近似值e，也就是说最终用e近似e，该近似值既包含有舍入误差，也包含有截断误差．
当参与计算的原始数据是从仪器中观测得来时，也不可避免得有观测误差．
由于这些误差的大量存在，我们得到的只能是近似结果，进而对这些结果的“可靠性”进行分析就是必须的，它成为计算方法的第二个显著特点． 可靠性分析包括原问题的适定性和算法的收敛性、稳定性．
所谓适定性问题是指解存在、惟一，且解对原始数据具有连续依赖性的问题． 对于非适定问题的求解，通常需要作特殊的预处理，然后才能做数值计算． 在这里，如无特殊说明，都是对适定的问题进行求解．
对于给定的算法，若有限步内得不到精确解，则需研究其收敛性． 收敛性是研究当允许计算时间越来越长时，是否能够得到越来越可靠的结果，也就是研究截断误差是否能够趋于零．
**1文档收集于互联网，如有不妥请联系删除.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
对于给定的算法，稳定性分析是指随着计算过程的逐步向前推进，研究观测误差、舍入误差对计算结果的影响是否很大．
对于同一类模型问题的求解算法可能不止一种，常希望从中选出高效可靠的求解算法． 如我国南宋时期著名的数学家秦九韶就提出求n次多项式
anxn?an?1xn?1???a1x?a0值的如下快速算法
s?an；
t?an?k；s?sx?t (k?1,2,?,n)
它通过n次乘法和n次加法就计算出了任意n次多项式的值． 再如幂函数x可以通过如下快速算法计算出其值
s?x；
s?s?s；循环6次
如上算法仅用了6次乘法运算，就得到运算结果．
算法最终需要在计算机上运行相应程序，才能得到结果，这样就要关注算法的时间复杂度(计算机运行程序所需时间的度量)、空间复杂度(程序、数据对存储空间需求的度量)和逻辑复杂度(关联程序的开发周期、可维护性以及可扩展性)． 事实上，每一种算法都有自己的局限性和优点，仅仅理论分析是很不够的，大量的实际计算也非常重要，结合理论分析以及相当的数值算例结果才有可能选择出适合自己关心问题的有效求解算法． 也正因如此，只有理论分析结合实际计算才能真正把握准算法．
64§1.2 误差的度量与传播
一、误差的度量
误差的度量方式有绝对误差、相对误差和有效数字．
定义1.1 用x作为量x的近似，则称x?x?:e(x)为近似值x的绝对误差．
由于量x的真值通常未知，所以绝对误差不能依据定义求得，但根据测量工具或计算情况，可以估计出绝对误差绝对值的一个较小上界?，即有 e(x*)?x*?x??
称正数?为近似值x的绝对误差限，简称误差． 这样得到不等式 工程中常用
表示近似值x的精度或真值x所在的范围．
误差是有量纲的，所以仅误差数值的大小不足以刻划近似的准确程度． 如量 s?123?0.5cm?1.23?0.005m?1230000?5000?m (1.2) 为此，我们需要引入相对误差
******(1.1)
x*?x?:er(x*)为近似值x*的相对误差． 当 定义1.2 用x?0作为量x的近似，称x*x是x的较好近似时，也可以用如下公式计算相对误差
x*?x* er(x)? (1.3)
x** 显然，相对误差是一个无量纲量，它不随使用单位变化． 如式(1.2)中的量s的近似，无论使用何种单位，它的相对误差都是同一个值．
2文档收集于互联网，如有不妥请联系删除.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
* 同样地，因为量x的真值未知，我们需要引入近似值x的相对误差限?r(x)，它是相
*对误差绝对值的较小上界． 结合式(1.1)和(1.3)，x相对误差限可通过绝对误差限除以近似值的绝对值得到，即
?r(x)?**?(x*)x* (1.4)
为给出近似数的一种表示法，使之既能表示其大小，又能体现其精确程度，需引入有效数字以及有效数的概念．
定义1.3 设量x的近似值x有如下标准形式
* ＝?a1?10m?1?a2?10m?2???an?10m?n???ap?10m?p
p其中{ai}i?1?{0,1,?,9}且a1?0，m为近似值的量级． 如果使不等式
??(1.5)
x?x?**1?10m?n 2(1.6)
成立的最大整数为n，则称近似值x具有n位有效数字，它们分别是a1、a2、… 和
an． 特别地，如果有n?p，即最后一位数字也是有效数字，则称x*是有效数．
从定义可以看出，近似数是有效数的充分必要条件是末位数字所在位置的单位一半是绝对误差限． 利用该定义也可以证明，对真值进行“四舍五入”得到的是有效数． 对于有效数，有效数字的位数等于从第一位非零数字开始算起，该近似数具有的位数． 注意，不能给有效数的末位之后随意添加零，否则就改变了它的精度．
*** 例1.1 设量x??，其近似值x1?3.141，x2?3.142，x3?22． 试回答这三个近7似值分别有几位有效数字，它们是有效数吗？ 解 这三个近似值的量级m?1，因为有
所以x1和x3都有3位有效数字，但不是有效数． x2具有4位有效数字，是有效数．
***二、误差的传播
这里仅介绍初值误差传播，即假设自变量带有误差，函数值的计算不引入新的误
****差． 对于函数y?f(x1,x2,?,xn)有近似值y?f(x1,x2,?,xn)，利用在点***(x1,x2,?,xn)处的泰勒公式(Taylor Formula)，可以得到
?其中fi:??f(xii?1n*1**,x2,?,xn)e(xi*)
(1.7)
?f***，xi是xi的近似值，e(xi)是xi的绝对误差(i?1,2,?,n)． 式(1.7)表明函?xi数值的绝对误差近似等于自变量绝对误差的线性组合，组合系数为相应的偏导数值． 从式(1.7)也可以推得如下函数值的相对误差传播近似计算公式
xi* er(y)??fi(x,x,?,x)*er(xi*) (1.8)
yi?1 对于一元函数y?f(x)，从式(1.7)和(1.8)可得到如下初值误差传播近似计算公式
*** e(y)?f?(x)e(x) (1.9)
*n*1*2*n3文档收集于互联网，如有不妥请联系删除.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
x* er(y)?f?(x)*er(x*)
y**(1.10)
式(1.9)表明，当导数值的绝对值很大时，即使自变量的绝对误差比较小，函数值的绝对误差也可能很大．
例1.2 试建立函数y?f(x1,x2,?,xn)?x1?x2???xn的绝对误差(限)、相对误差的近似传播公式，以及xi*?0 e(y)?**??ni?1时的相对误差限传播公式．
*n*in 解 由公式(1.7)和(1.8)可分别推得和的绝对误差、相对误差传播公式如下
?f(xii?1n*1,x,?,x)e(x)＝?e(xi*)
*2i?1(1.11) (1.12)
nxi*xi** er(y)??fi(x,x,?,x)*er(xi)＝?*er(xi*)
yi?1i?1yn*1*2*n进而有
于是有和的绝对误差限近似传播公式 当xi*?0??ni?1时，由式(1.3)推得相对误差限的近似传播公式
** 例1.3 使用足够长且最小刻度为1mm的尺子，量得某桌面长的近似值a?1304.3 mm，宽的近似值b?704.8mm (数据的最后一位均为估计值)． 试求桌子面积近似值的绝对误差限和相对误差限．
解 长和宽的近似值的最后一位都是估计位，尺子的最小刻度是毫米，故有误差限 ?(a)?0.5mm，?(b)?0.5mm 面积S?ab，由式(1.7)得到近似值S?ab的绝对误差近似为 进而有绝对误差限
?(S*)?b*?(a*)?a*?(b*)?704.8?0.5?1304.3?0.5?1004.55 mm2 相对误差限
*****§1.3 数值实验与算法性能比较
本节通过几个简单算例说明解决同一个问题可以有不同的算法，但算法的性能并不完全
相同，他们各自有自己的适用范围，并进而指出算法设计时应该注意的事项． 算例1.1 表达式
111??，在计算过程中保留7位有效数字，研究对不同的xx?1x(x?1)x，两种计算公式的计算精度的差异．
说明1：Matlab软件采用IEEE规定的双精度浮点系统，即64位浮点系统，其中尾数占52位，阶码占10位，尾数以及阶码的符号各占1位． 机器数的相对误差限(机器精度)eps=2－52－－
≈2.220446×1016，能够表示的数的绝对值在区间(2.2250739×10308，1.797693×10308)内，该区间内的数能够近似表达，但有舍入误差，能够保留至少15位有效数字． 其原理可参阅参考文献[2, 4]．
111?和算法2： y2(x)?的误差时，精确解用双精
x(x?1)xx?1i30度的计算结果代替． 我们选取点集{?}i?1中的点作为x，比较两种方法误差的差异．
分析算法1： y1(x)?4文档收集于互联网，如有不妥请联系删除.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
从图1.1可以看出，当x不是很大时，两种算法的精度相当，但当x很大时算法2的精度明显高于算法1． 这是因为，当x很大时，
11和是相近数，用算法1进行计算时出xx?1现相近数相减，相同的有效数字相减后变成零，于是有效数字位数急剧减少，自然相对误差增大． 这一事实也可以从误差传播公式(1.12)分析出． 鉴于此，算法设计时，应该避免相近数相减．
在图1.2中我们给出了当x接近?1时，两种算法的精度比较，其中变量x依次取为
???i?1i?1． 从图中可以看出两种方法的相对误差基本上都为10?7，因而二者的精度相当．
图1.1 算例1.1中两种算法的相对误差图（x???） 图1.2 算例1.1中两种算法的精度比较(x??1)
?30 算例1.2 试用不同位数的浮点数系统求解如下线性方程组
说明2：浮点数系统中的加减法在运算时，首先按较大的阶对齐，其次对尾数实施相应的加减法运算，最后规范化存入计算机．
算法1 首先用第一个方程乘以适当的系数加至第二个方程，使得第二个方程的x1的系数为零，这时可解出x2；其次将x2带入第一个方程，进而求得x1(在第三章中称该方法为高斯消元法)． 当用4位和7位尾数的浮点运算实现该算法，分别记之为算法1a和算法1b． 算法 2 首先交换两个方程的位置，其次按算法1计算未知数 (第三章中称其为选主元的高斯消元法)． 当用4位和7位尾数的浮点运算实现该算法，分别记之为算法2a和算法2b． 方程组的精确解为x1?0.25000187...，x2?0.49999874... ，用不同的算法计算出的结果见表1.1．
表1.1 对算例1.2用不同算法的计算结果比较 算例1.2 －0.0000 0.5000 算法1a 0.10×101 0.25×107 －－0.2500 0.5000 算法2a 0.75×107 0.25×107 －－0.2600000 0.4999987 算法1b 0.40×101 0.10×106 －－0.2500020 0.5000000 算法2b 0.50×108 0.25×107 对于算例1.2，表中的数据表明，当用4位尾数计算时，算法1给出错误的结果，算法2则给出解很好的近似． 这是因为在实现算法1时，需要给第一个方程乘以－2/0.00001加至第二个方程，从而削去第二个方程中x1的系数，但在计算x2的系数时需做如下运算
－2(1.13) ?2?3?－0.4?106＋0.3?101＝－0.4?106＋0.000003?106
0.000016对上式用4位尾数进行计算，其结果为－0.4?10． 因为舍入误差，给相对较大的数加以
相对较小的数时，出现大数“吃掉”小数的现象． 计算右端项时，需做如下运算
－2?1?2?－0.2?106＋0.2?101＝－0.2?106＋0.000002?106
0.000016同样出现了大数吃小数现象，其结果为－0.2?10． 这样，得到的变形方程组
(1.14)
中没有原方程组中第二个方程的信息，因而其解远偏离于原方程组的解． 该算法中之所以出现较大数的原因是因为运算－2/0.00001，因而算法设计中尽可能避免用绝对值较大的数除以绝对值较小的数． 其实当分子的量级远远大于分母的量级时，除法运算还会导致溢出，计算机终止运行．
5文档收集于互联网，如有不妥请联系删除.
数值分析原理课件第一章
