《数值计算方法及其程序实现》力图探索数值计算方法教学的一种新尝试, 立足于数学思维而面向科学计算, 适应应用型人才的培养需要, 内容处理上突出数值计算方法的基本设计和内涵理解. 《数值计算方法及其程序实现》旨在介绍科学计算中常用的数值计算方法及其理论, 包括数值计算方法的意义、插值方法、数值积分与数值微分、非线性方程求根、线性方程组的迭代法和直接法、微分方程的数值解法. 在每章的结构安排上,先有导读、问题分析、基础知识和具体算法分析, 然后是数值实验讨论, 在每章小结中除了本章基本内容总结外, 还介绍算法的最新研究现状和应用成果.同时, 为了便于读者学习之用, 每章都配有相应的习题和数值实验题, 以及部分习题答案、计算程序.

第 1 章 引 论 
导 读 
数值计算方法[1.14] 的历史源远流长， 自有数学以来就有关于数值计算方面的 研究. 公元前 2000 年古巴比伦就有对开方运算的研究， 公元 13 世纪我国南宋数学 家秦九韶提出了多项式的计算方法， 以及公元 3 世纪我国数学家刘徽提出的 \割圆 术" 都是数值计算方面的杰出成就. 数值计算的理论和方法是在解决数值问题的长 期实践过程中逐步形成和发展起来的， 由于受到计算工具的限制， 它的理论和方法 发展十分缓慢. 随着计算机和科学技术的发展， 数值计算方法也得到了空前的发展， 已经成为与计算机密切结合的科学计算， 并广泛应用于机电产品的设计、建筑工程 项目的设计、气象和新型尖端武器的研制、火箭的发射等国防尖端技术， 这些技术 都有大量复杂的数值计算问题亟待解决， 它们的复杂程度已达到远非人工手算 (包括使用计算器等简单的计算工具) 所能解决的地步. 
数值计算方法主要是讨论借助于计算机研究求解各种数学问题的数值计算方 法及其理论与软件实现， 其目的是用简单的算术运算求解复杂的数值问题， 并设计 和评价由给出数据计算数值结果的方法， 这些方法即为算法， 因此， 数值计算方法 也可以称为计算方法. 数值计算方法虽然也主要是以数学问题为研究对象，但它不 像纯数学那样只研究数学本身的理论， 而是把理论与计算机紧密结合， 着重研究数学问题的数值方法及其理论， 也深刻地体现了数学的应用性和应用数学的特点. 因此， 数值计算方法既有纯数学高度抽象性与严密科学性的特点， 又有应用数学的广泛性与试验的高度技术性的特点， 是一门与计算机使用密切结合的实用性很强的数学课程. 
用数值计算的方法来解决工程实际和科学技术中的具体问题时， 首先必须将具体问题抽象为数学问题， 即建立能描述实际问题的数学模型， 例如， 各种微分方程、积分方程、代数方程等；然后选择合适的计算方法 (算法)、计算机语言 (MAT- LAB、C++ 等)， 编写出计算程序， 最后上机调试进行计算， 得出所求解的结果 (数值结果). 因此， 用计算机解决工程实际问题的步骤可以归纳如下:
数值计算方法中的算法就是数学中的计算公式吗？对于同一个计算问题能够给出多种求解的算法吗？用什么样的标准去衡量一个算法的合理性和有效性? 
1.1 数值计算方法 
问题 1.1 (算法的含义) 所谓算法 (数值计算方法)， 是由基本运算及规定的运算顺序所构成的完整的解题步骤. 算法的内涵是构造性的数值方法， 即不但要论证问题的可解性， 而且解的结构是通过数值演算过程来完成的. 下面通过例子来进一步说明算法的内涵， 帮助读者理解. 
例 1.1 证明：一元二次方程 x2 + bx + c = 0 至多有两个不同的实根， 其中b; c 均为实数. 
证明 下面给出三种解法. 
(1) 图解法 将方程 x2 + bx + c = 0 配方后得到上式左端为抛物线 y = μx + b， 如果抛物线与 x 轴有交点， 其横坐标即为所求的实根， 而且交点至多只有两个. 
(2) 反证法 假设方程 x2 + bx + c = 0 有三个互异的实根 x1， x2 和 x3， 则有 
式 (1.1)、(1.2) 分别减去式 (1.3) 得
x1 + x2 + b = 0; 
x1 + x3 + b = 0; 
从而有 x2 = x3， 这与假设矛盾. 
(3) 公式法 根据一元二次方程的求根公式有 
上述三种方法中， 图解法是构造性的， 但不是数值的；反证法不是构造性的. 这里所说的算法"， 不只是单纯的数学公式， 而且是指由基本运算及规定的运算顺序所构成的完整的解题步骤. 一般可以通过框图 (流程图) 来较直观地描述算法的全过程， 图 1-1 为求解一元二次方程 x2 + bx + c = 0 的流程图. 
图 1-1 流程图 
问题 1.2 (研究算法的意义) 同一个数学问题可能有多种数值计算方法， 但不一定都是有效、可用的. 评价一个算法的好坏主要有两条标准：计算结果的精度以及所付出的代价. 一个好的算法当然应该要满足精度要求且代价小， 这里的代价往往包括时间复杂性和空间复杂性. 时间复杂性好是指节省时间， 运算速度快， 主要由运算次数来决定；空间复杂性好是指节省储存量， 主要由使用的数据量决定. 
下面将通过两个实例来说明合理地选择算法可以使时间复杂性更好.
例如， 线性方程组的行列式求解方法 (Gramer 法则) 在理论上可以求解任意阶线性方程组. 用 Gramer 法则求解一个 n 阶方程组， 要计算 n + 1 个 n 阶行列式的 ， 为此总共需要做 n!(n . 1)(n + 1) 次乘法. 当 n 充分大时， 这个计算量是相当大 的， 手工算法是完全不切实际的， 那么是不是现代超级计算机就很容易计算呢？可 以简单来验证一下. 例如， 一个 20 阶不算太大的线性方程组， 大约要做 1021 次乘 法， 用运算速度为 5.49 亿亿次每秒的天河-2 号计算机计算， 大约花费的时间为
从计算结果来看， 即使选择运算如此神速的计算机计算也需要连续工作 5 小 时才能完成， 事实上， 求解线性方程组有许多实用的算法：直接法和迭代法 (第 5 章 和第 6 章) 等， 用普通的计算机也能很快地求解 20 阶的线性方程组. 
又例如， 当计算多项式 
的值时， 若直接计算 an.ixi(i = 1; 2; ￠ ￠ ￠ ; n)， 再逐项相加， 共需做 
次乘法和 n 次加法. 如当 n = 10 时， 需要 55 次乘法和 10 次加法. 
若将多项式 p(x) 改写成 
即从里往外一层一层地计算. 
设用 vk 表示第 k 层 (从里面数起) 的值 
那么， 第 k 层的结果 vk 显然等于第 k . 1 层的结果 vk.1 层乘以 x 再加上系数 ak， 
即 
显然， 上述求解多项式的算法只需做 n 次乘法和 n 次加法， 如当 n = 20 时， 只要 做 20 次乘法和 20 次加法， 与前面进行对比， 可见算法的优势直接影响计算的速度 和效率. 上述计算多项式的方法是我国南宋大数学家秦九韶提出的秦九韶算法， 其计算量远比前述逐项生成算法的计算量小， 说明秦九韶算法是一种优秀算法. 国外 文献常称这一算法为 Horner 算法， 而 Horner 的工作比秦九韶晚了五六百年. 
因此， 即便对于计算机如此发达的今天， 选定合适的算法仍然是整个数值计算方法研究中非常重要的一个问题. 值得说明的是， 对于小型问题， 计算的速度和占用 计算机内存的多寡似乎意义不大， 但对于复杂的大型问题， 却起着决定性作用. 数 值计算方法除了构造算法， 还涉及许多理论问题， 包括算法的收敛性、稳定性及其 误差分析. 除了理论分析外， 一个数值算法是否有效， 最终还要通过大量的数值试 验来检验. 数值计算方法具有理论性、实用性和实践性都很强的特点， 可以归纳为 以下四点： 
(i) 面向计算机， 能根据计算机特点提供切实可行的有效算法； 
(ii) 有可靠的理论分析， 可以任意逼近并达到精度要求， 对近似算法要保证收 敛性和数值稳定性， 还要对误差进行必要分析； 
(iii) 要有好的计算复杂性， 即时间复杂性和空间复杂性； 
(iv) 通过大量数值试验验证其算法的有效性. 
问题 1.3 (算法设计中的基本要求与技术) 在问题 1.2 中已经了解， 即使计算 机的运算速度如此神速， 也并不意味着计算机的算法可以随意地选择， 能否合理地 选择算法是科学计算成败及其结果有用性的关键. 算法重在设计思想， 设计思想重 在追求简单与统一. 简单是重视基础的算法， 是用最简单的算法去解释最复杂的问 题. 统一是强调算法的共性， 是用一类算法去解决所有复杂的问题. 在算法的设计 中始终要围绕 \计算复杂性" 和 \计算精度" 两个问题进行设计， 因此， 可以将常用 的算法设计技巧分为 \减模" 和 \提精" 两类. 
1. 减模技术 
一个数值计算问题一般可以用某个实数即问题的规模来刻画其空间和时间计 算的 \大小"， 而问题的解则是其规模为足够小 (规模为 0 或 1 的退化情形). 这类 问题的求解是通过某种简单的运算方法逐步缩减问题的规模， 直到加工得出所求的 解. 算法设计的这种技巧就是减模技术， 它适用于直接法， 所谓直接法即是通过有 限步计算可以直接得出问题的精确解 (如果不考虑舍入误差). 
考虑数列求和的累加算法
式 (1.10) 有两个简单的特例， 即 
当 n = 0 时， 所给计算模型就是它的解， 不需要做任何计算. 这表明对于数列求和 
问题， 它的解是计算模型退化的情形. 又当 n = 1 时， 计算过程是平凡的， 这时不存 在算法设计问题. 
现在基于这两种简单情形考察所给和式 (1.10) 的累加求和算法. 设 bk 表示前k + 1 项的部分和 a0 + a1 + ￠ ￠ ￠ + ak， 则有 
计算结果 bn 即为所求的和值 
上述数列求和的累加算法， 其设计思想是将多项求和 (式 (1.10)) 化归为两项求 和 (式 (1.11)) 的重复. 按照式 (1.11) 重复加工若干次， 最终即可将所给和式 (1.10) 加工成 1 项和式 (1.12) 的退化情形， 从而得出和值 S. 按式 (1.11) 每加工一次， 所 给和式 (1.10) 便减少 1 项， 而所生成的计算模型依然是数列求和. 反复施行这种加 工运算， 计算模型不断变形为 
n + 1项和式 
(计算模型) ) n项和式 ) n . 1项和式 ) ￠ ￠ ￠ ) 1项和式 
(所求结果)
这里， 符号 \)" 表示重复施行两项求和的加工运算. 
这样， 如果定义和式的项数为数列求和问题的规模， 则所求和值可以视作规模 为 1 的退化情形. 因此， 只要令和式的规模 (项数) 逐次减 1， 最终当规模为 1 时即 可直接得出所求的和值. 这样设计出的算法称为模减 1 技术. 再考虑式 (1.10)， 若将前后对应项两两合并， 即 
这样数列求和问题的规模就减半了， 这样设计出的算法称为模减半技术， 也称二分技术. 二分技术是缩减技术的延伸， 针对规模 N = 2n(n 为正整数) 的大规模计算问 题， 如果运用每作一步规模减 1 的缩减技术实在太慢了， 因此， 二分技术是缩减技 术的优化， 它也是将计算问题加工成同类问题， 不同的是二分技术的每一步使问题 的规模减半， 即其规模按等比级数 (公比为 1/2) 递减， 直到规模变为 1 时终止计算. 这样， 对于规模为 N = 2n(n 为正整数) 的大规模计算问题， 只要二分 n = log2 N 次即可使其规模变为 1， 从而得出所求解.

写给读者的话 
写给教师的教学建议 
前言 
第 1 章 引论 1 
导读 1 
1.1 数值计算方法 2 
1.2 误差的种类及其来源 10 
1.3 绝对误差和相对误差 12 
1.3.1 绝对误差和绝对误差限.12 
1.3.2 相对误差和相对误差限.13 
1.4 有效数字及其与误差的关系.14 
1.4.1 有效数字 14 
1.4.2 有效数字与相对误差的关系 15 
1.5 误差的传播与估计 16 
1.5.1 误差估计的一般公式17 
1.5.2 误差在算术运算中的传播.18 
1.6 算法的数值稳定性及其注意事项 21 
1.6.1 算法的数值稳定性 21 
1.6.2 数值计算中应该注意的问题 23 
1.7 数值实验 24 
小结27 
习题 1 27 
实验 1 28 
秦九韶简介.28 
主要参考文献 29 
第 2 章 插值方法 31 
导读31 
2.1 插值概念 32 
2.1.1 代数插值问题 32
2.1.2 插值多项式的存在唯一性.33 
2.2 拉格朗日插值公式 34 
2.2.1 两点插值 34 
2.2.2 三点插值 36 
2.2.3 多点插值 38 
2.2.4 插值余项 39 
2.3 埃特金算法 41 
2.4 埃尔米特插值公式 44 
2.4.1 泰勒插值 44 
2.4.2 埃尔米特插值 45 
2.5 分段插值 48 
2.5.1 高次插值的龙格现象48 
2.5.2 分段插值的概念 49 
2.5.3 分段线性插值 50 
2.5.4 分段三次埃尔米特插值.51 
2.6 样条插值 52 
2.6.1 样条函数的概念 52 
2.6.2 三次样条插值 53 
2.6.3 三次样条插值函数的导出.55 
2.7 曲线拟合的最小二乘法 58 
2.7.1 直线拟合 59 
2.7.2 多项式拟合 60 
2.7.3 其他拟合类型 62 
2.8 数值实验 63 
小结68 
习题 2 69 
实验 2 70 
拉格朗日简介 72 
主要参考文献 73 
第 3 章 数值积分与数值微分 74 
导读74 
3.1 数值积分基本概念 75 
3.1.1 数值积分法 75 
3.1.2 代数精度 76 
3.2 插值型数值积分公式 78
3.2.1 低阶插值型数值积分公式.78 
3.2.2 牛顿{柯特斯公式 80 
3.3 复合数值积分公式 82 
3.3.1 复合梯形公式 82 
3.3.2 复合辛普森公式 82 
3.3.3 变步长梯形公式 83 
3.3.4 龙贝格算法 86 
3.4 高斯型数值积分公式 90 
3.4.1 定义及其特征 90 
3.4.2 高斯公式的一般构造法.93 
3.5 数值微分 94 
3.5.1 差商与微商 94 
3.5.2 插值函数与数值微分95 
3.5.3 数值积分与数值微分96 
3.6 数值实验 97 
小结.102 
习题 3103 
实验 3103 
勒让德简介 104 
主要参考文献 104 
第 4 章 非线性方程求根 106 
导读.106 
4.1 根的搜索.107 
4.1.1 逐步搜索法 (扫描法) 107 
4.1.2 区间二分法 107 
4.2 迭代法 109 
4.2.1 迭代法的设计思想109 
4.2.2 线性迭代的启示 111 
4.2.3 压缩映像原理 112 
4.2.4 迭代法的局部收敛性.115 
4.2.5 迭代法的收敛速度116 
4.3 牛顿法 116 
4.3.1 牛顿公式及误差分析.117 
4.3.2 牛顿法的局部收敛性.119
4.3.3 牛顿法的应用及算法.119 
4.4 牛顿法的改进与变形121 
4.4.1 牛顿下山法 121 
4.4.2 弦截法 123 
4.4.3 快速弦截法 123 
4.5 数值实验.124 
小结.134 
习题 4134 
实验 4135 
牛顿简介 135 
主要参考文献 136 
第 5 章 线性方程组的迭代法 138 
导读.138 
5.1 雅可比迭代法和高斯{赛德尔迭代法 139 
5.1.1 雅可比迭代法 139 
5.1.2 高斯{赛德尔迭代法.142 
5.2 迭代法的收敛性.145 
5.2.1 迭代收敛的概念 146 
5.2.2 严格对角占优阵的概念.146 
5.2.3 迭代收敛的一个充分条件 147 
5.3 超松弛迭代 148 
5.4 数值实验.150 
小结.154 
习题 5155 
实验 5156 
雅可比简介 156 
主要参考文献 157 
第 6 章 线性方程组的直接法 158 
导读.158 
6.1 追赶法 159 
6.1.1 二对角方程组的回代过程 159 
6.1.2 追赶法 160 
6.2 消去法 163 
6.2.1 高斯消去法 163 
6.2.2 高斯{若尔当消去法.166
6.2.3 高斯主元素消去法167 
6.3 收敛性 170 
6.3.1 病态方程组 170 
6.3.2 精度分析 173 
6.4 数值实验.173 
小结.180 
习题 6181 
实验 6182 
高斯简介 182 
主要参考文献 183 
第 7 章 微分方程的数值解法 185 
导读.185 
7.1 欧拉方法.186 
7.1.1 欧拉格式 186 
7.1.2 单步法的局部截断误差和阶 189 
7.1.3 梯形方法 190 
7.1.4 改进的欧拉格式 191 
7.2 龙格{库塔方法192 
7.2.1 龙格{库塔方法的设计思想 192 
7.2.2 龙格{库塔方法的推导.194 
7.3 亚当姆斯方法 196 
7.3.1 亚当姆斯格式 196 
7.3.2 亚当姆斯预报-校正系统 198 
7.4 收敛性和稳定性.198 
7.4.1 收敛性 198 
7.4.2 稳定性 199 
7.5 方程组和高阶方程的情形 200 
7.5.1 一阶方程组 200 
7.5.2 高阶方程 201 
7.6 数值实验.201 
小结.206 
习题 7207 
实验 7208 
欧拉简介 208 
主要参考文献 209 
部分习题参考答案 211