数值分析与算法(第3版)

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

清华大学计算机系教授，中国科学院院士
数值分析与算法(第3版)第3版前言第3版前言
　　“数值分析”或“计算方法”是理工科大学各专业普遍开设的一门课程，其内容主要包括有关数值计算（numerical computing）的理论与方法。数值计算是计算数学、计算机科学与其他工程学科相结合的产物，随着计算技术的发展与普及，它正变得越来越重要。尤其是人工智能和机器学习正得到蓬勃发展与应用，作为它们基础的数值计算方法也受到更广泛的重视，其重要性不言而喻。
　　本书的主要内容与一般的“数值分析”教材基本一致，但还具有如下特点：
（1） 对数学理论的介绍简明扼要。尽量用形象的方式解释数学中的一些概念与理论，通过定理总结重要的结论。在不失严谨性的前提下，省略部分定理的证明，取而代之的是直观的解释、验证，并说明其意义与用途。
（2） 强调算法的实际应用与分析比较。对大多数算法，采用程序伪码的形式加以描述，同时分析其计算复杂度。说明算法应用中的细节问题，对几个较新的算法还给出了MATLAB源程序。通过“应用实例”和相关MATLAB命令，更详细地介绍算法的应用。
（3） 具有较强的可读性与实用性。尽量用图、表等形象的方式对概念、现象进行解释。每章都编写了“算法背后的历史”子栏目，以增强阅读的趣味性。书末附有算法、术语索引，便于查阅。为了便于读者动手实践，对MATLAB和Python软件的相关功能进行了简单介绍。
（4） 在内容编排上有利于教学。依据教学规律安排各章的顺序；每章的“评述”部分列出了主要知识点，除练习题外，还提供了上机实验题，附录中给出了部分习题的答案。
　　学习数值分析与算法，应重视通过计算机编程加深理解相关理论与算法。本书提倡使用MATLAB或Python语言进行编程实验，基于如下理由：①它们较易于学习、代码简洁，可节省编程实验时间。②MATLAB还具有功能强大的科学计算集成环境，便于程序调试和形象直观地展示程序运行结果。③它们包含丰富、先进的数值计算功能，已被广泛用于科学与工程实践。学习MATLAB与Python中使用的技术可作为课程学习的扩展与提高。
　　本书第1版于2012年年初出版、第2版于2015年年底出版，已作为“数值分析”课的教材使用多年，收到了较满意的效果。但通过教学实践也发现了书中的一些问题与错误，有必要进行更正与修订。本书第3版在保持全书结构不变的前提下对前7章做了全面细致的修订，主要修改的部分包括部分定理的表述和证明、数值计算网络资源信息的更新、增加与修订了一些插图、对一些扩展知识给出了更多的说明、删除了少量不实用的内容、增加了一节专门介绍矩阵的奇异值分解、增加了一个附录介绍Python中数值计算的功能。总之，在保持全书篇幅基本不变的情况下，对内容进行了增删，力求涵盖当下重要的数值计算内容，并呈现出更高的品质和阅读体验。
　　本书体现了作者十多年来的相关教学和科研积累，参考、借鉴了十余种较新的国内外优秀教材，力争在理论与实践相结合、反映学科发展前沿，以及适应时代发展对学生培养的新要求等方面取得好的效果。本书内容由误差分析、非线性方程求根、数值线性代数、函数插值、数值积分、常微分方程数值解法等部分组成，包括数值计算领域中经典、应用较广泛的内容，也为学习化方法、大数据分析、机器学习等新兴领域中的一些高级算法提供了基础。使用本教材时，可用48学时讲授主要内容，几乎每章都包含一些简介性质或与MATLAB软件有关的内容，供感兴趣的学生选学或课后阅读。
　　下图显示了各章主要内容的知识依赖关系。总体上，建议教师按照从第1～8章的顺序开展教学，只是第2.7节依赖于线性方程组的有关知识，需在第3章讲完后介绍。
白如冰、朱臻垚参加了本书第1版部分内容的编写，刘志强参加了本书第3版部分内容的编写，选修作者讲授的“数值分析”课的同学指出了第1版、第2版中的很多错误，提供了积极反馈，在此致以诚挚的谢意！此外，还要感谢清华大学王泽毅、殷人昆、边计年、蔡懿慈等教授给予的指导与帮助，以及清华大学出版社的编辑在出版本书过程中付出的辛勤劳动。
　　据不完全统计，本书已被40多所大学选作教材，使用的专业包括计算机专业、软件工程专业、电子信息专业、自动化专业等。在此，作者对广大读者的支持表示诚挚的感谢！也希望广大读者提出宝贵的意见与建议。

喻文健2019年9月

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

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

目录
第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通用求根算法zeroin49
应用实例： 城市水管应埋于地下多深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.3LU分解的用途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对称正定矩阵的Cholesky分解94
3.5.2带状线性方程组的解法97
应用实例: 稳态电路的求解100
3.6有关稀疏线性方程组的实用技术101
3.6.1稀疏矩阵的基本概念102
3.6.2MATLAB中的相关功能104
3.7有关数值软件107
评述109
算法背后的历史: 威尔金森与数值分析110
练习题111
上机题113
第4章线性方程组的迭代解法114
4.1迭代解法的基本理论114
4.1.1基本概念114
4.1.21阶定常迭代法的收敛性115
4.1.3收敛阶与收敛速度118
4.2经典迭代法120
4.2.1雅可比迭代法120
4.2.2高斯赛德尔迭代法121
4.2.3逐次超松弛迭代法123
4.2.43种迭代法的收敛条件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
应用实例： Google的PageRank算法162
5.3矩阵的正交三角化165
5.3.1Householder变换165
5.3.2Givens旋转变换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.Householder与矩阵分解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.3B样条函数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.3Romberg算法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.2Adams公式303
8.4.3更多讨论307
8.5常微分方程组与实用技术307
8.5.11阶常微分方程组308
8.5.2MATLAB中的实用ODE求解器311
应用实例: 洛伦兹吸引子314
评述316
算法背后的历史: “数学家之英雄”欧拉317
练习题318
上机题320
附录A有关数学记号的说明322
附录BMATLAB简介324
附录CPython数值计算简介344
附录D部分习题答案348
算法索引352
术语索引354
参考文献362

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

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