数值计算方法(第二版)

第1章 绪 论 1.1 数值计算方法的任务与基本方法 随着计算机科学与技术的不断发展及计算机应用的普及，继试验方法和理论方法之后，科学计算已成为科学实践的第三种重要手段。它主要在物理学、力学、化学、生命科学、天文学、环境科学、经济科学及社会科学等领域中得到了广泛的应用，成为不可缺少的重要工具。因此，适用于计算机的数值计算方法已成为理工科相关专业的硕士研究生及本科生的必修课程。 利用计算机进行数值计算，实质上就是对具有一定数位的数值进行加、减、乘、除等算术运算，以及一些逻辑运算。而研究怎样把各种数学问题的求解运算归结为有限数位的四则运算，以求得各种数学问题的数值解或近似数值解，是数值计算方法的根本课题。由四则运算及运算顺序的规定构成的完整解题步骤称为算法，数值计算方法的根本任务就是研究算法，包括算法构成与算法分析。事实上，数值计算方法与数学问题（或数学模型）密不可分，研究的各种与数值相关的数学问题*终可归结为各类数学模型，表1-1-1给出的是数值计算方法描述的客观现象、数学模型、数学工具及所属的数值逻辑范畴。 表1-1-1 数值计算方法描述的客观现象、数学模型、数学工具及所属的数值逻辑范畴 有关非确定性现象的数学模型的数值计算方法将由另外的课程介绍，如“正交试验与数据处理”等。本课程涉及的内容是介绍描述确定性现象的数学模型中的数值计算方法，因此本课程的基本任务就是研究描述确定性现象的各种数学问题的算法，包括算法构成及算法分析等。 算法构成的原则就是以计算机所能执行的运算为依据，尽可能节省机器内存和运算工作量。在构造算法时，常常采用近似替代，而在数值计算方法中，函数的近似替代称为函数逼近。在函数逼近中，被逼近的函数一般比较复杂，或只知在若干点的值，难以计算和分析；逼近的函数往往比较简单，如多项式、有理函数、分段多项式等。利用函数的近似替代可以计算函数的积分、导数、极值及零点等，利用积分和导数的近似公式可以把微分方程或积分方程化为代数方程组。微分方程或积分方程的解本来是连续变量，数值计算方法常常只计算它在某点处的值，这些值是连续变量的离散结果。把求解连续变量问题转化为求解离散变量问题称为离散化。离散化后得到的代数方程组往往用来获取数值间的递推关系，进而利用递推关系编写计算机程序去求解。这种通过使用递推公式求一系列的近似解，并使它们越来越接近真实解的算法称为迭代法或逐次逼近法，上述这一整套办法都是采用数值计算方法求解各种数学问题的基本方法。 算法分析就是分析算法的理论依据、应用范围、收敛性、稳定性、误差估计及计算的空间和时间复杂度等。 本书将在“数学分析”“空间解析几何”“高等代数”（或“高等数学”“线性代数”）的基础上，不仅介绍求各类数学问题近似解的*基本、常用的数值计算方法，而且注重阐明构造算法的基本思想和原理，既注重介绍算法的构造和使用，也注重算法的分析与研究。 1.2 误差及有关概念 1.2.1 误差的来源及分类 一个物理量和实际计算的值往往不同，两者之差就称为这个物理量的误差。产生误差的原因是多方面的，因此一个物理量的误差具有多种来源。 首先，通过对实际问题进行抽象与简化（即忽略了一些次要因素）得到数学模型，因而即使数学问题能准确求解，它与实际问题的解之间也有误差。一般地，通过数学模型对实际问题近似求解的过程见图 1-2-1，数学模型与实际问题之间出现的这种误差称为模型误差。同时，数学模型往往包含若干个由观测得到的参量，如温度、时间、电压等，这些观测得到的数据也有误差，这种由观测产生的误差称为观测误差。 图1-2-1 实际问题的近似求解过程图 其次，根据实际问题建立的数学模型在许多情况下很难得到精确解，需要选取适当的数值计算方法将其简化为较易求解的数值问题。这种由数学问题转化为数值问题产生的误差称为截断误差。 例如，用 的幂级数展开式 来计算 的值时，由于算法的有限性，只能截取其部分和 来近似替代，由此产生的误差为截断误差。由微积分可知（泰勒公式），该截断误差为 （ ）。 *后，当将计算机作为计算工具时，计算机的字位有限，只能用有限位进行取值和运算，因此，原始数据在计算机上表示时会产生误差，而计算过程中又可能产生新的误差。这种由计算机字位而产生的误差称为舍入误差。 例如，有一台计算机只能表示6位十进制数，圆周率 在计算机上表示为3.14159，从而产生误差 。又如，3.14159与9.21000在计算机上进行加法运算，可得 ，产生的误差 。 一般地，将模型误差和观测误差统称为系统误差，而将截断误差和舍入误差统称为方法误差，本课程涉及的误差分析仅指方法误差（即截断误差和舍入误差）。 1.2.2 误差的描述 1. 绝对误差与绝对误差限 设 是准确值（或精确值） 的一个近似值，则称 为近似值 的绝对误差，简称误差。 一般而言， 的准确值很难求出或不能准确知道，但可以根据测量工具或计算的具体情况估计出它的取值范围，即存在某个正数 ，使 （1.2.1） 这个 就称为近似值 的绝对误差限。显然，一个近似值的绝对误差限是不唯一的，且若已知近似值的一个绝对误差限 ，就可以知道精确值 的取值范围： 或（1.2.2） 对同一个准确值 而言， 或 越小，近似值 就越精确，但是对不同的数 和 而言，误差 或绝对误差限 的大小不能完全反映出近似值 和 中哪一个近似程度更好。例如，有两个测量值 和 ，其中， 和 的近似值分别为 = 15与 = 1000，其绝对误差限分别是2和5。单从绝对误差限来看，前者小，而后者大。但是，不能得出“前者的测量精度高于后者”的结论，这是为什么？因为绝对误差或绝对误差限仅考虑了误差本身的大小，没有考虑准确值（或度量）的大小。为了更好地反映近似值的精确程度，引入相对误差的概念。 2. 相对误差与相对误差限 设 是准确值 的一个近似值， 是它的绝对误差，则称 （1.2.3） 为近似值 的相对误差。在实际计算时，由于准确值 往往是不知道的，相对误差 也不能准确知道。特别地，当 较小时，通常取 （1.2.4） 作为 的相对误差。这是因为当 较小时，有 （1.2.5） 这是 的高阶无穷小量。 与绝对误差一样，相对误差也只能估计其上限。如果存在正数 ，使 （1.2.6） 则称 为近似值 的相对误差限。 尽管绝对误差（限）与相对误差（限）都用于误差的度量，但它们之间有着本质的差异，前者是有量纲的，后者是无量纲的。因此，在误差的度量比较上，相对误差（限）比绝对误差（限）有更广的适用范围，相对误差（限）不仅适用于相同量纲之间的比较，也适用于不同量纲之间的比较，而绝对误差（限）只能用于相同量纲之间的比较。 上面提到的近似值 = 15和 = 1000的相对误差限分别为 ， 。由此可见， 近似 的程度比 近似 的程度要高。 3. 精确位数与有效数字 有效数字是近似值的一种表示方法，它既能表示近似值的大小，又能表示其精确程度。一个数值的有效数字与精确位数密切相关。当精确值 为有限多位数时，常常按照四舍五入的原则取前 位数 作为 的近似值。 例如， ，若取前5位数，得 ，相应的误差为 ，绝对误差限为 ，此时称 准确到小数位后的第4位，并称前5位数字1.4142为 。下面给出有效数字的准确定义。 定义1.2.1 如果近似值 的误差绝对值不超过某一位数字所在数字位的半个单位，且该数字到 的第1位非零数字共有 位，则称用 近似 时具有 位有效数字，简称 有 位有效数字。 例如，圆周率 分别满足 ， ，则 的近似值3.1416具有5位有效数字，而3.14159具有6位有效数字。 对计算机中参加运算的数值通常进行标准化处理，即将数值表示成如下形式： （1.2.7） 其中， 为整数； 为0、1、 、9中的数字，且 。此种表示法也称为科学记数法。 例1.2.1 ， 。 在式（1.2.7）中，如果 （1.2.8） 是对 的第 位数字进行四舍五入后得到的近似值，则 具有 位有效数字，且其误差的绝对值不超过 ，即 （1.2.9） 其中， 是 的一个特殊误差限。它之所以为特殊误差限，是因为可以被用来判定近似值的有效数字的位数。因此，有效数字还可以有如下定义。 定义1.2.2 如果 的近似值 满足式（1.2.9），则 具有 位有效数字。 如果例1.2.1中的 和 都是四舍五入得到的有效数字，那么 和 分别具有2位和7 位有效数字。根据式（1.2.9）， 的误差绝对值满足 。由定义1.2.1可知，有效数字的位数与小数点的位置无关。因此，精确小数点后 位，不能反映有效数字位数的多少，只有经四舍五入得到的数字按式（1.2.7）的形式规格化后，小数点后的位数才能反映出有效数字位数的多少。 一般地，一个数字经四舍五入后得到的近似值的每位有效数字都是唯一确定的，但必须注意有效数字的定义中出现“等号”而带来的问题，即此时会出现有效数字不唯一的特殊情况。 例1.2.2 对准确值 的*后一位进行四舍五入后得到 ，但若将*后一位5舍掉就得到 ，它们的误差绝对值都不超过近似值*小数位的半个单位，即 由定义1.2.2知， 、 都具有2位有效数字。 例1.2.2说明了近似值中的有效数字不一定都是通过四舍五入得到的。通过对某个数四舍五入取近似值可得到它的有效数字，但是并不是所有的有效数字都通过四舍五入得到。 例1.2.3 设 ，它的两个近似值分别为 和 ，其误差绝对值均为 ，但 ，从而 ；而 ，可得 ，由定义1.2.2知， 具有3位有效数字，同理可知， 具有4位有效数字。 例1.2.3说明某个数的近似值如果不是通过四舍五入得到，那么它的数字并不都是有效数字，同时它的数字位数并不等于该数的有效数字的位数。定理1.2.1给出了相对误差限与有效数字的关系。 定理1.2.1 设 是 的近似值，它的表达式为式（1.2.8），则 的有效数字与 的相对误差有如下关系。 （1）若 具有 位有效数字， 的相对误差为 （1.2.10） （2）若 的相对误差限 （1.2.11） 则 至少具有 位有效数字。 证明 （1）由式（1.2.9）可得 ，从而有 即 是 的相对误差。 （2）若 ，则由 可得 由定义1.2.2知， 至少有 位有效数字。 定理1.2.1表明，近似值的有效数字位数越多（即 越大），相对误差（限）就越小；反之，相对误差（限）越小，则式（1.2.11）右端项中的 就有可能越大，有效数字位数就有可能越多。在今后的数值问题中，如果没有特别声明，都可认为所有的原始数据均是有效数字。计算数值具有多少位有效数字是数值计算方法的根本，也是评定算法好坏的主要标准之一。 1.3 数值计算中的误差传播 1.3.1 基本运算中的误差估计 本节讨论的基本运算是指四则运算与一些常用函数的计算。 由微积分知识可知，当自变量的改变量（误差）很小时，函数的微分作为函数改变量的主要线性部分可近似表示函数的改变量，因此，利用微分运算公式可导出误差运算公式。设数值计算中求得的解 与参量 的函数关系为 （1.3.1） 记 的近似值为 ，相应的解为 （1.3.2） 假设 在点 处可微，则当数据误差较小时，解的绝对误差为 从而有