本书是针对“数值分析”“计算方法”“数值分析与算法”等课程编写的教材,主要面向理工科大学信息 科学与技术各专业,以及信息与计算科学专业的本科生。本书内容包括数值计算基础、非线性方程的数值 解法、线性方程组的直接解法与迭代解法、矩阵特征值与特征向量的计算、数值逼近与插值、数值积分方 法、常微分方程初值问题的解法,以及数值算法与应用的知识。本书涵盖数值分析、矩阵计算领域最基本、 最常用的一些知识与方法,而且在算法及应用方面增加了一些较新的内容。在叙述上既注重理论的严谨 性,又强调方法的应用背景、算法设计,以及不同方法的对比。为了增加实用性与可扩展性,每章都配备了 应用实例、算法背后的历史、评述等子栏目,书末附有算法、术语索引。附录中包括 MATLAB软件和 Py t hon软件的简介,便于读者快速掌握并进行编程实验。 

本书适合作为高年级本科生或研究生的教材,也可供从事科学与工程计算的科研人员参考。

序

“清华大学计算机系列教材”已经出版发行了三十余种,包括计算机科学与技术专业的 基础数学、专业技术基础和专业等课程的教材,覆盖计算机科学与技术专业本科生和研究生 的主要教学内容。这是一批至今发行数量很大并赢得广大读者赞誉的书籍,是近年来出版 的大学计算机专业教材中影响比较大的一批精品。 本系列教材的作者都是我熟悉的教授与同事,他们长期在第一线担任相关课程的教学 工作,是一批很受本科生和研究生欢迎的任课教师。编写高质量的计算机专业本科生(和研 究生)教材,不仅需要作者具备丰富的教学经验和科研实践,还需要对相关领域科技发展前 沿的正确把握和了解。正因为本系列教材的作者具备了这些条件,才有了这批高质量优秀 教材的产生。可以说,教材是他们长期辛勤工作的结晶。本系列教材出版发行以来,从其发 行的数量、读者的反映、已经获得的国家级与省部级的奖励,以及在各个高等院校教学中所 发挥的作用上,都可以看出本系列教材所产生的社会影响与效益。 计算机学科发展异常迅速,内容更新很快。作为教材,一方面要反映本领域基础性、普 遍性的知识,保持内容的相对稳定性;另一方面又需要紧跟科技的发展,及时调整和更新内 容。本系列教材都能按照自身的需要及时地做到这一点。如王爱英教授等编著的《计算机 组成与结构》、戴梅萼教授等编著的《微型计算机技术及应用》都已经出版了4版,严蔚敏教 授的《数据结构》也出版了3版,使教材既保持了稳定性,又达到了先进性的要求。 本系列教材内容丰富,体系结构严谨,概念清晰,易学易懂,符合学生的认知规律,适合 教学与自学,深受广大读者的欢迎。系列教材中多数都配有丰富的习题集、习题解答、上机 及实验指导和电子教案,便于学生理论联系实际地学习相关课程。 随着我国进一步的开放,我们需要扩大国际交流,加强学习国外的先进经验。在大学教 材建设上,我们也应该注意学习和引进国外的先进教材。但是,“清华大学计算机系列教材” 的出版发行实践以及它所取得的效果告诉我们,在当前形势下,编写符合国情的具有自主版 权的高质量教材仍具有重大意义和价值。它与国外原版教材不仅不矛盾,而且是相辅相成 的。本系列教材的出版还表明,针对某一学科培养的要求,在教育部等上级部门的指导下, 有计划地组织任课教师编写系列教材,还能促进对该学科科学、合理的教学体系和内容的 研究。 我希望今后有更多、更好的我国优秀教材出版。

清华大学计算机系教授,中国科学院院士

第3版

“数值分析”或“计算方法”是理工科大学各专业普遍开设的一门课程,其内容主要包括 有关数值计算( nume r i c a lcompu t i ng)的理论与方法。数值计算是计算数学、计算机科学与 其他工程学科相结合的产物,随着计算技术的发展与普及,它正变得越来越重要。尤其是人 工智能和机器学习正得到蓬勃发展与应用,作为它们基础的数值计算方法也受到更广泛的 重视,其重要性不言而喻。 本书的主要内容与一般的“数值分析”教材基本一致,但还具有如下特点: ( 1)对数学理论的介绍简明扼要。尽量用形象的方式解释数学中的一些概念与理论, 通过定理总结重要的结论。在不失严谨性的前提下,省略部分定理的证明,取而代之的是直 观的解释、验证,并说明其意义与用途。 ( 2)强调算法的实际应用与分析比较。对大多数算法,采用程序伪码的形式加以描述, 同时分析其计算复杂度。说明算法应用中的细节问题,对几个较新的算法还给出了 MATLAB源程序。通过“应用实例”和相关MATLAB命令,更详细地介绍算法的应用。 ( 3)具有较强的可读性与实用性。尽量用图、表等形象的方式对概念、现象进行解释。 每章都编写了“算法背后的历史”子栏目,以增强阅读的趣味性。书末附有算法、术语索引, 便于查阅。为了便于读者动手实践,对 MATLAB和Py t hon软件的相关功能进行了简单 介绍。 ( 4)在内容编排上有利于教学。依据教学规律安排各章的顺序;每章的“评述”部分列 出了主要知识点,除练习题外,还提供了上机实验题,附录中给出了部分习题的答案。 学习数值分析与算法,应重视通过计算机编程加深理解相关理论与算法。本书提倡使 用MATLAB或Py t hon语言进行编程实验,基于如下理由:①它们较易于学习、代码简洁, 可节省编程实验时间。②MATLAB还具有功能强大的科学计算集成环境,便于程序调试 和形象直观地展示程序运行结果。③它们包含丰富、先进的数值计算功能,已被广泛用于科 学与工程实践。学习MATLAB与Py t hon中使用的技术可作为课程学习的扩展与提高。 本书第1版于2012年年初出版、第2版于2015年年底出版,已作为“数值分析”课的教 材使用多年,收到了较满意的效果。但通过教学实践也发现了书中的一些问题与错误,有必 要进行更正与修订。本书第3版在保持全书结构不变的前提下对前7章做了全面细致的修 订,主要修改的部分包括部分定理的表述和证明、数值计算网络资源信息的更新、增加与修 订了一些插图、对一些扩展知识给出了更多的说明、删除了少量不实用的内容、增加了一节 专门介绍矩阵的奇异值分解、增加了一个附录介绍Py t hon中数值计算的功能。总之,在保 持全书篇幅基本不变的情况下,对内容进行了增删,力求涵盖当下最重要的数值计算内容, 并呈现出更高的品质和阅读体验。 本书体现了作者十多年来的相关教学和科研积累,参考、借鉴了十余种较新的国内外优 秀教材,力争在理论与实践相结合、反映学科发展前沿,以及适应时代发展对学生培养的新 要求等方面取得好的效果。本书内容由误差分析、非线性方程求根、数值线性代数、函数插

值、数值积分、常微分方程数值解法等部分组成,包括数值计算领域中经典、应用较广泛的内 容,也为学习最优化方法、大数据分析、机器学习等新兴领域中的一些高级算法提供了基础。 使用本教材时,可用48学时讲授主要内容,几乎每章都包含一些简介性质或与 MATLAB 软件有关的内容,供感兴趣的学生选学或课后阅读。 下图显示了各章主要内容的知识依赖关系。总体上,建议教师按照从第1~8章的顺序 开展教学,只是第2. 7节依赖于线性方程组的有关知识,需在第3章讲完后介绍。

白如冰、朱臻垚参加了本书第1版部分内容的编写,刘志强参加了本书第3版部分内容 的编写,选修作者讲授的“数值分析”课的同学指出了第1版、第2版中的很多错误,提供了 积极反馈,在此致以诚挚的谢意! 此外,还要感谢清华大学王泽毅、殷人昆、边计年、蔡懿慈 等教授给予的指导与帮助,以及清华大学出版社的编辑在出版本书过程中付出的辛勤劳动。 据不完全统计,本书已被40多所大学选作教材,使用的专业包括计算机专业、软件工程 专业、电子信息专业、自动化专业等。在此,作者对广大读者的支持表示诚挚的感谢! 也希 望广大读者提出宝贵的意见与建议。

喻文健 2019年9月

目  录 

第1章 数值计算

导论 1 

1. 1 概述 1 

1. 1. 1 数值计算与数值算法 1 

1. 1. 2 数值计算的问题与策略 2 

1. 1. 3 数值计算软件 4  

1. 2 误差分析基础 6  

1. 2. 1 数值计算的近似 6  

1. 2. 2 误差及其分类 7  

1. 2. 3 问题的敏感性与数据传递误差估算 11  

1. 2. 4 算法的稳定性 14 

1. 3 计算机浮点数系统与舍入误差 16  

1. 3. 1 计算机浮点数系统 16  

1. 3. 2 舍入与机器精度 18  

1. 3. 3 浮点运算的舍入误差 20  

1. 3. 4 抵消现象 21  

1. 4 保证数值计算的准确性 22  

1. 4. 1 减少舍入误差的几条建议 22  

1. 4. 2 影响结果准确性的主要因素 25  

评述 26  

算法背后的历史:浮点运算的先驱———威廉·卡亨 27  

练习题 28  

上机题 29  

第2章 非线性方程求根 31

2. 1 引言 31  

2. 1. 1 非线性方程的解 31  

2. 1. 2 问题的敏感性 32

2. 2 二分法 32  2. 2. 1 方法原理 32  

2. 2. 2 算法稳定性和结果准确度 34  

2. 3 不动点迭代法 36  

2. 3. 1 基本原理 36  

2. 3. 2 全局收敛的充分条件 37  

2. 3. 3 局部收敛性 39  

2. 3. 4 稳定性与收敛阶 40 

2. 4 牛顿迭代法 41 

2. 4. 1 方法原理 42  

2. 4. 2 重根的情况 44  

2. 4. 3 判停准则 44  

2. 4. 4 牛顿法的问题 45  

2. 5 割线法与抛物线法 45  

2. 5. 1 割线法 46  

2. 5. 2 抛物线法 47  

2. 6 实用的方程求根技术 48  

2. 6. 1 阻尼牛顿法 48  

2. 6. 2 多项式方程求根 48  

2. 6. 3 通用求根算法z e r o i n 49  

应用实例:城市水管应埋于地下多深 52  

2. 7 非线性方程组和有关数值软件 53  

2. 7. 1 非线性方程组 53  

2. 7. 2 非线性方程求根的相关软件 55  

评述 56  

算法背后的历史:牛顿与牛顿法 57  

练习题 58  

上机题 59  

第3章 线性方程组的直接解法 61  

3. 1 基本概念与问题的敏感性 61  

3. 1. 1 线性代数中的有关概念 61  

3. 1. 2 向量范数与矩阵范数 64 

3. 1. 3 问题的敏感性与矩阵条件数 68  

3. 2 高斯消去法 71  

3. 2. 1 基本的高斯消去法 71 

3. 2. 2 高斯-约当消去法 74  

3. 3 矩阵的LU分解 78  

3. 3. 1 高斯消去过程的矩阵形式 78  

3. 3. 2 矩阵的直接LU分解算法 81  

3. 3. 3 LU分解的用途 84  

3. 4 选主元技术与算法稳定性 86  

3. 4. 1 为什么要选主元 86 

3. 4. 2 使用部分主元技术的LU分解 88  

3. 4. 3 其他选主元技术 92  

3. 4. 4 算法的稳定性 93  

3. 5 对称正定矩阵与带状矩阵的解法 94  

3. 5. 1 对称正定矩阵的Cho l e sky分解 94  

3. 5. 2 带状线性方程组的解法 97  

应用实例:稳态电路的求解 100  

3. 6 有关稀疏线性方程组的实用技术 101  

3. 6. 1 稀疏矩阵的基本概念 102  

3. 6. 2 MATLAB中的相关功能 104  

3. 7 有关数值软件 107  

评述 109  

算法背后的历史:威尔金森与数值分析 110  

练习题 111  

上机题 113  

第4章 线性方程组的迭代解法 114  

4. 1 迭代解法的基本理论 114  

4. 1. 1 基本概念 114  

4. 1. 2 1阶定常迭代法的收敛性 115  

4. 1. 3 收敛阶与收敛速度 118  

4. 2 经典迭代法 120  

4. 2. 1 雅可比迭代法 120  

4. 2. 2 高斯-赛德尔迭代法 121  

4. 2. 3 逐次超松弛迭代法 123  

4. 2. 4 3种迭代法的收敛条件 125  

应用实例:桁架结构的应力分析 128  

4. 3 共轭梯度法简介 130  

4. 3. 1 最速下降法 130  

4. 3. 2 共轭梯度法 133  

4. 4 各种方法的比较 137  

4. 4. 1 迭代法之间的比较 137  

4. 4. 2 直接法与迭代法的对比 140  

4. 5 有关数值软件 141  

评述 142  

算法背后的历史:雅可比 144  

练习题 145  

上机题 146  

第5章 矩阵特征值计算 148  

5. 1 基本概念与特征值分布 148  

5. 1. 1 基本概念与性质 148  

5. 1. 2 特征值分布范围的估计 152  

5. 2 幂法与反幂法 154  

5. 2. 1 幂法 154  

5. 2. 2 加速收敛的方法 158  

5. 2. 3 反幂法 160  

应用实例:Goog l e的PageRank算法 162  

5. 3 矩阵的正交三角化 165  

5. 3. 1 Hous eho l de r变换 165  

5. 3. 2 Gi vens旋转变换 167  

5. 3. 3 矩阵的QR分解 168  

5. 4 所有特征值的计算与QR算法 172  

5. 4. 1 收缩技术 172  

5. 4. 2 基本QR算法 173  

5. 4. 3 实用QR算法的有关技术 176  

5. 5 奇异值分解简介 179  

5. 5. 1 基本概念与奇异值分解定理 179  

5. 5. 2 有关性质与计算方法 182  

5. 6 有关数值软件 184  

评述 186  

算法背后的历史:A. Hous eho l de r与矩阵分解 187  

练习题 188  

上机题 191  

第6章 函数逼近与函数插值 193  

6. 1 函数逼近的基本概念 193  

6. 1. 1 函数空间 193  

6. 1. 2 函数逼近的不同类型 196  

6. 2 连续函数的最佳平方逼近 198  

6. 2. 1 一般的法方程方法 198  

6. 2. 2 用正交函数族进行逼近 202  

6. 3 曲线拟合与最小二乘法 206  

6. 3. 1 问题的矩阵形式与法方程法 206  

6. 3. 2 用正交化方法求解最小二乘问题 209  

应用实例:原子弹爆炸的能量估计 213  

6. 4 函数插值与拉格朗日插值法 214  

6. 4. 1 插值的基本概念 214  

6. 4. 2 拉格朗日插值法 215  

6. 4. 3 多项式插值的误差估计 218  

6. 5 牛顿插值法 220  

6. 5. 1 基本思想 220  

6. 5. 2 差商与牛顿插值公式 221  

6. 6 分段多项式插值 226  

6. 6. 1 高次多项式插值的病态性质 226  

6. 6. 2 分段线性插值 227  

6. 6. 3 分段埃尔米特插值 228  

6. 6. 4 保形分段插值 231 

6. 7 样条插值函数 233  

6. 7. 1 三次样条插值 233  

6. 7. 2 三次样条插值函数的构造 234  

6. 7. 3 B -样条函数 236  

评述 239  

算法背后的历史:拉格朗日与插值法 240  

练习题 242  

上机题 244  

第7章 数值积分与数值微分 246  

7. 1 数值积分概论 246  

7. 1. 1 基本思想 246  

7. 1. 2 求积公式的积分余项与代数精度 248  

7. 1. 3 求积公式的收敛性与稳定性 249  

7. 2 牛顿-柯特斯公式 250  

7. 2. 1 柯特斯系数与几个低阶公式 250  

7. 2. 2 牛顿-柯特斯公式的代数精度 252  

7. 2. 3 几个低阶公式的余项 253  

7. 3 复合求积公式 254  

7. 3. 1 复合梯形公式 254  

7. 3. 2 复合辛普森公式 255  

7. 3. 3 步长折半的复合求积公式计算 257  

7. 4 龙贝格积分算法与理查森外推 258  

7. 4. 1 复合梯形公式的余项展开式 258  

7. 4. 2 理查森外推法 259  

7. 4. 3 Rombe r g算法 260  

7. 5 自适应积分算法 262  

7. 5. 1 自适应积分的原理 262  

7. 5. 2 一个具体的自适应积分算法 263  

7. 6 高斯求积公式 265  

7. 6. 1 一般理论 266  

7. 6. 2 高斯-勒让德积分公式及其他 269  

应用实例:探月卫星轨道长度计算 270  

7. 7 数值微分 272  

7. 7. 1 基本的有限差分公式 272  

7. 7. 2 插值型求导公式 274  

7. 7. 3 数值微分的外推算法 276  

评述 277  

算法背后的历史:“数学王子”高斯 279  

练习题 280  

上机题 281  

第8章 常微分方程初值问题的解法 283  

8. 1 引言 283  

8. 1. 1 问题分类与可解性 283  

8. 1. 2 问题的敏感性 284  

8. 2 简单的数值解法与有关概念 286  

8. 2. 1 欧拉法 286  

8. 2. 2 数值解法的稳定性与准确度 288  

8. 2. 3 向后欧拉法与梯形法 290  

8. 3 龙格-库塔方法 292  

8. 3. 1 基本思想 292  

8. 3. 2 几种显式R-K公式 293  

8. 3. 3 显式R-K公式的稳定性与收敛性 297  

8. 3. 4 自动变步长的R-K方法 298  

8. 4 多步法 300  

8. 4. 1 多步法公式的推导 300  

8. 4. 2 Adams公式 303  

8. 4. 3 更多讨论 307  

8. 5 常微分方程组与实用技术 307  

8. 5. 1 1阶常微分方程组 308  

8. 5. 2 MATLAB中的实用ODE求解器 311  

应用实例:洛伦兹吸引子 314  

评述 316  

算法背后的历史:“数学家之英雄”欧拉 317  

练习题 318  

上机题 320  

附录A 有关数学记号的说明 322  

附录B MATLAB简介 324  

附录C Py t hon数值计算简介 344  

附录D 部分习题答案 348  

算法索引 352  

术语索引 354  

参考文献 362

《数值分析与算法（第3版）》是清华大学计算机系“数值分析”课程的教材，是基于作者在清华大学多年科研、教学经验，并参考国内外最新相关教材与部分科研成果编写而成的。

喻文健，清华大学计算机系副教授。自1999年开始，我一直从事超大规模集成电路互连寄生参数提取的算法研究与软件开发。2004年至2007年，面向硅基数模混合电路和射频电路的设计，我着重研究了基于边界元法的衬底耦合参数提取和高频阻抗提取算法。2005年至2008年，我多次访问美国加州大学圣地亚哥分校（UCSD），在互连分析与电路仿真方面开展了合作研究。