第1章 数值计算方法概论
1.1 数值计算方法的研究内容
1.1.1 科学计算的重要组成部分：数值计算方法
实验、科学计算和理论分析是现代科学研究的三种基本手段.随着计算机技术的发展，科学计算在科学研究与工程实际中起着越来越重要的作用，某些实验或理论证明往往通过科学计算实现.科学计算的过程如图1-1所示，数值计算方法是其重要组成部分.
图1-1 科学计算的过程
数值计算方法也称为数值分析或计算方法，狭义上也称为科学计算，是一门与计算机应用紧密结合的、理论性与适用性很强的数学课程，是近代数学的一个重要分支.数值计算能解决一些传统的解析方法不可能求解的问题.例如，求解超越方程在[0，1]上的根.原方程可化为，根据连续函数介值(零点)定理，方程在[0，1]上的根存在，但无法求得根的解析形式(精确解)，只能想办法求近似解(此例涉及本书非线性方程的数值解法内容).再如，计算，用高等数学的Newton-Leibniz公式计算失效，因为被积函数的原函数不是初等函数(被积函数“积不出”)，可以考虑近似求解方法(此例涉及本书的数值积分内容).又如，用线性代数中线性方程组求解的Cramer法则求解一个阶线性方程组需计算个行列式的值，共需次乘法，当较大时，由于计算量太大而没有实际使用价值，如当时，大约需次乘法，即使用每秒运算百亿次的计算机去计算，也需连续工作数千年才能完成，而采用Gauss消元法求解(此例涉及本书的线性方程组求解内容)，可在数秒内求出答案.上述例子告诉我们，工程实际中遇到的许多数学问题由于没有解析方法或由于计算量太大，需要设计求解算法，通过编程借助计算机来求解.通过有限次的四则运算和逻辑运算在计算机上求解数学问题的方法称为数值方法(numerical method)，求得的近似解(approximate solution)称为数值解(numerical solution).
1.1.2 数值计算方法处理问题的基本模式
数值计算方法研究求解各种数学问题数值解的数值算法及其相关理论，如数值算法的收敛性、稳定性和数值解的误差分析.可行、有效的数值算法是计算机能直接处理(只包含加减乘除及逻辑运算)，在理论上收敛、稳定，在实际计算中精确度高，计算复杂性(时间与空间复杂性)小，能通过实验验证的数值算法.数值计算方法处理问题的基本模式包括：近似代替，即把一个无限过程的计算问题转化为满足精度需求的有限的计算过程；迭代，即通过递推将计算问题转化为简单计算的不断重复，便于计算机实现；离散化，即将一个连续变量的计算问题转化为离散变量的计算问题；“化粗为精”，即将几个不同的近似结果通过引入不同权重组合成精度更高的数值结果.数值计算方法处理问题的基本手段是近似，核心是研究近似对问题真实结果的影响.
数值计算方法将数学高度抽象的理论化为基本的算术运算与逻辑运算，能增强我们对数学的理解，提高我们运用数学与计算机解决实际问题的能力.本书讨论常用的、基本的数值算法，读者在学习过程中应将重点放在各种数值算法的思想方法上，而不是死记硬背公式，不仅要学会使用计算软件进行计算，而且要学会自己编程计算.鉴于本书的特点，对读者的基本要求如下：具有微积分、线性代数、常微分方程、高级语言程序设计的基础知识；理解数值算法的基本原理；利用MATLAB等语言编程，认真完成数值实验，能处理一些工程实际计算问题，具备一定的分析问题及解决问题的能力.
1.2 误差及有效数字
数值解的误差有两类：固有误差和计算误差.固有误差来自模型误差与观测误差；计算误差来自截断误差与舍入误差.重视误差分析并控制误差扩散是十分重要的，没有误差分析的数值解是不可信的.误差就像矛盾一样无处不在，无时不有.实际中，得到精确解往往是一个理想情况，有时并不需要有精确解，多数情况是得到满足精度要求的数值解即可，过分追求精确结果有时并无必要，甚至是不现实的.
1.2.1 误差的来源
1.模型误差
数学模型与实际问题之间的误差称为模型误差(model error).一般来说，实际问题是比较复杂的，用数学模型来描述实际问题需要进行必要的简化，就会产生模型误差.
2.观测误差
实验或观测得到的数据与实际数据之间的误差称为观测误差(observation error).
3.截断误差及收敛性
计算机求解数学问题的数值解时用有限过程代替无限过程时产生的误差称为截断误差(truncation error)，也称方法误差(method error).例如，由Taylor公式得 ，用近似，截断误差为，其中介于0与之间.对于固定的，当时，余项，即，此时称近似代替这一算法是收敛(convergent)的.算法收敛表明该算法总可以通过提高计算量使得截断误差任意小.
4.舍入误差
计算机浮点数是一个有限集合，绝大部分实数在计算机上不能精确表示，总要经过舍或入由一个与之相近的浮点数代替，由此引起的误差称为舍入误差(round-off error)，即计算机字长为有限位导致的原始数据在计算机上表示及进行四则运算时可能产生的误差.如果在一个数值算法中，舍入误差在计算过程中不断增大，那么该算法数值不稳定，否则数值是稳定的.
科学计算各环节产生的误差如图1-2所示.数值计算方法中总假定数学模型是准确的，因而不考虑模型误差和观测误差，本书中所涉及的误差，一般是指截断误差和舍入误差，且总误差就是截断误差与舍入误差的和.
图1-2 科学计算各环节产生的误差
1.2.2 误差的度量
度量近似值“好坏”即误差大小有三种方法：绝对误差和绝对误差限、相对误差和相对误差限、有效数字.
1.绝对误差和绝对误差限、相对误差和相对误差限
定义1-1 设为准确值，是的近似值，称
(1-1)
为近似值的绝对误差(absolute error)，简称误差(error).
显然，误差既可为正，又可为负.一般来说，准确值是不知道的，因此误差的准确值无法求出.但是在实际工作中，可根据相关领域的知识、经验事先估计出误差绝对值不超过某个正数，即
(1-2)
则称为近似值的绝对误差限(absolute error bound)，简称误差限或精度(precision).有时，将准确值写成，或者表示为.
绝对误差的大小还不能完全表示近似值的好坏.例如，算得一个数据为100时有1的绝对误差与算得一个数据为1000时有1的绝对误差，绝对误差都是1，但后者的计算结果显然比前者要准确得多.这说明决定一个量的近似值的好坏，除了要考虑绝对误差的大小，还要考虑准确值本身的大小，这就需要引入相对误差的概念.
定义1-2 设为准确值，是的近似值，称
(1-3)
为近似值的相对误差(relative error).
在实际计算中，由于准确值总是未知的，也把
(1-4)
称为近似值的相对误差.
一般来说，相对误差越小，表明近似程度越好.称相对误差绝对值的上界为近似值的相对误差限(relative error bound)，即
(1-5)
绝对误差和绝对误差限有量纲，而相对误差和相对误差限没有量纲，而且误差限更具有实际意义.
2.有效数字
实际计算中，往往用四舍五入的方法取一个有许多位数的精确数据的前有限位数据作为近似值，此时近似值的绝对误差不会超过其末位数的半个单位.例如，按照四舍五入的方法，若取，则绝对误差；若取，则.
定义1-3 设是的近似值，写成规范化形式：
(1-6)
其中，是0和9之间的自然数，为整数，且使
(1-7)
成立的整数的*大值为，那么称近似值具有位有效数字(significant figures)；分别是近似的第1位，第2位， ，第位有效数字.若，则称准确到小数点后第位.
由定义1-3可知，数值计算中表达一个数值的有效数字是几位就意味着表达出了它的绝对误差限.
例1-1 设，它的近似值，分别具有几位有效数字？
解因为，所以具有4位有效数字(从的小数点后第3位数字0起直到左边第一个非零数字3为止的4个数字都是有效数字，而*后一位数字1不是有效数字).进一步可以看出，的误差不超过的小数点后第3位的半个单位，即我们说近似值准确到小数点后第3位.
类似地，故具有5位有效数字(从的小数点后第4位数字2起直到左边第一个非零数字3为止的5个数字都是有效数字).进一步可以看出，的误差不超过的小数点后第4位即末位的半个单位，即，我们说近似值准确到小数点后第4位.
故具有4位有效数字(从的小数点后第3位数字0起直到左边第一个非零数字3为止的4个数字都是有效数字).进一步可以看出，的误差不超过的小数点后第3位即末位的半个单位，即，我们说近似值准确到小数点后第3位.
特别要指出的是，在例1-1中，有4位有效数字，而只有2位有效数字.近似值末位也是有效数字的近似值称为有效数(significant figure)，都是有效数.若四舍五入后的数是有效数，则四舍五入后的数的数字全部是有效数字.
3.病态问题
在求解实际问题的数值解时，实际问题本身有“好”和“坏”之别.坏问题是问题的数值解对数据的初始误差非常敏感，反之属于好问题.坏问题在数值计算中称为病态问题(ill-posed problem).数据的初始误差对于好问题的解的影响是在允许、可控范围内的，而对于病态问题的解的影响是非常大的.例如，线性方程组的唯一精确解为.如果把方程组系数保留4位有效数字，用同样的算法求解方程组解为，与原方程组的解相比变化非常大，原因在于原方程组是一个病态方程组，虽然系数只是做了微小变化，但解产生了很大的变化.
1.3 数值计算中应注意的问题
用计算机实现算法时，输入计算机的数据一般是有误差的(如观测误差等)，计算机运算过程的每一步又会产生舍入误差，这些误差在计算过程中还会逐步传播和积累，因此必须研究这些误差对计算结果的影响.一个实际问题往往需要亿万次以上的计算，且每一步都可能产生误差，因此不可能对每一步的误差进行分析和研究，只能根据具体问题的特点进行研究，提出相应的误差估计.特别地，如果在构造算法的过程中注意一些原则，那么将有效地减少误差的危害，控制误差的传播和积累.
1.3.1 避免两个相近的数相减
在数值计算中，两个相近的数相减会造成有效数字的严重损失，从而导致误差增大，影响计算结果的精度.
例1-2 当时，计算的近似值(准确值为0.00499912523117984 ).
解若取6位有效数字，计算结果只有1位有效数字.若改用公式：
则其结果有6位有效数字，与准确值0.00499912523117984 非常接近.
例1-2表明利用恒等式或等价关系对计算公式进行变形可以避免或减少有效数字的损失.
1.3.2 防止重要的小数被大数“吃掉”
在数值计算中，参加运算的数的数量级有时相差很大，而计算机的字长又是有限的，如果不注意运算次序，那么就可能出现小数被大数“吃掉”的现象.这种现象在有些情况下是允许的，但在有些情况下这些小数很重要，若它们被“吃掉”，会影响计算结果的可靠性.
例如，如果在5位浮点十进制数下计算(仿机器实际运算)，首先要对阶(统一成大的阶码)，而计算机上只能达到5位，故计算机上不起作用，即视为0，于是.
展开
