
虽然数值分析属于数学课程,但它与我们以往所熟悉的数学课程是完全不同的,从基本的思想方法和思维方式到课程的学习方式都有很大的差异。我们所熟悉的数学课程的共同特点是抽象和严格的演绎、严密和清晰的逻辑思维,但对于数值分析课程来说,除了上述特点之外,“归纳”将成为不容忽视的思维方法,这里讨论的核心问题是“误差”这个在数学上似乎根本不存在的东西。在以往的数学课程中,教师可能会强调阅读教科书和做习题,但在数值分析课程中,除了读书和做习题之外,用计算机计算也是同样重要的。
数值分析是培养学生算法意识和能力的基本课程,应从培养学生科学计算能力出发,但这一点绝不能靠单纯讲授来解决,必须在计算机环境下通过实验完成,从这一点上来说,数值分析方面的书籍应该更多地面向实际应用,或许是数值分析所涉及的范围太广,大多数数值分析教材特别是国内的教材都侧重于基本算法的推导和理论分析的细节,其目的在于给读者打下一个较为坚实的理论基础,在此基础上设计和编写自己的算法和程序,但实际上在过去的十几年中,数值分析的实践和教学已经发生了巨大的变化,人们不必再去书写那些繁杂的代码和程序,可以更多的依赖像MATLAB这样的软件包,同时人们所解决的问题的规模也越来越大,因而对计算机硬件的要求也越来越高。这种新的形势要求我们不仅要了解算法的基本思想及推导过程,还要进一步了解怎样才能更好地使用这些算法,其中包括如何使算法在合理的时间内收敛,如何选择适当的初值、如何对各种方法进行结合等等,从这一点上说科学计算更加重要。
Jeffery J. Leader教授的这本教材采用数值分析与科学计算并重的思想,很好地解决了大部分现有教材没有很好解决的问题。书中没有过多地进行枯燥的定理论述,也没有过多地分析算法的细节,重点介绍了方法基本思想以及在MATLAB平台上的使用,其目的在于通过数值实验提高学生对算法的“鉴赏”能力,使学生熟练使用标准的计算机软件,了解各种算法的优缺点,最终能“拥有”这些算法。
本书每小节后面的习题可以使读者加深理解本小节所介绍的基本问题,这些问题一般不需要其他的附加资源;MATLAB部分介绍了与本小节内容相关的MATLAB命令以及相应的数值实验,这部分的内容可以使读者逐渐认识这个软件并有机会通过数值实验获得对科学计算的直观认识,这些内容即使不在教学中讲授也可以作为自学MATLAB的参考书,在翻译此书的过程中译者就曾在数学建模培训中以这部分内容作为教材介绍过MATLAB软件,收到了很好的效果;附加问题特别是序号10以后的附加题可能完成起来要有一定的难度,可有选择的完成。
本书结构合理,可读性强,除了可以作为本科高年级或研究生的“数值分析”教材,对以科学计算为工具的科技人员也有很大的参考价值。
数值分析与科学计算翻译过程中我们力求忠实、准确地反映原著的内容和风格,但由于水平所限,难免会有疏漏及不妥之处,恳请读者批评指正。
数值分析是对连续数学问题的算法的研究。 Lloyd Trefethen (1992) 初等数值分析是一门非常具有吸引力的学科。只需花费很少的精力利用很少的代数知识就可以得出重要的算法、写出代码并执行。 G.W.Stewart (1998)
本书是在过去9年我所讲授的数值分析课程的基础上编写而成的,该课程最初是工科大学二年级的一门必修课,目前已成为数学、计算机科学、物理学和工科各年级学生的选修课。近年来我暑期在美国陆军研究实验室(Adelphi MD)、海军作战中心(Dahlgren VA)和空军研究实验室(Dayton OH)所做的计算咨询顾问工作以及其他咨询和研究工作的经历都对此书产生了很大影响,同时与其他同事的座谈以及所翻阅的其他教材也对本书有很大帮助。
我希望本书在以下方面与其他数值分析教材有所不同:
首先给出数值方法,将截断误差和计算机运算推迟到学生具有一定实际计算经验之后。
采用数值线性代数的最新方案。
用学生在实际中愿意使用的主要计算程序(包括MATLAB以及Maple和Netlib库)解释数值技术。
将数值分析理论和实际的科学计算原理有机地结合。
更注重最优化的分析。
通过数值实验提高学生的能力。
自然而有效地介绍MATLAB.
每节后面以附加内容的方式介绍了MATLAB的相关内容,如果希望学生在学习本教程的同时学会MATLAB,那么这部分的内容可以使他们逐渐认识这个软件并有机会通过数值实验获得对科学计算的直观认识。即使在教学中不使用MATLAB也应鼓励学生大致浏览一下这部分的内容以便将来使用。 当然使用本教材时也可以不使用包含MATLAB的部分。我曾利用上述方案在课堂上进行了MATLAB的教学,效果很好。
科学计算的实践告诉我们,从某种程度上说,几乎任何问题最终都可以化简为求根、非线性优化或数值线性代数问题。前两个问题中往往也涉及线性方程组的求解。本书从求根问题(第1章)开始,主要介绍一维求根,这是因为学生在微积分中已经了解了这个问题,然后介绍数值线性代数(第2、3章),因为这部分内容不仅本身重要,而且后面的章节中还要使用,第4章介绍作为推导其他方法的工具的多项式插值以及描绘由数据给出的曲线的工具的样条,第5章介绍数值求积的基本技术并重点介绍这些方法在MATLAB和Maple中的使用,第6章主要处理常微分方程组的求解,非线性优化的相关内容在第7章介绍,第8章讨论逼近理论的基本思想和方法。
本书试图避免落入那种先介绍一种完全新的数学思想,然后再给出关于这种思想的计算技术的套路中。如果学生还没有了解相关的数学问题,像求根、最大值和最小值、微积分中的微分和积分以及微积分或常微分方程课程中的一阶常微分方程,那么对于他们来说就很难理解为什么要了解关于这些问题的数值方法。例如对于富里叶变换,本书并没有先介绍富里叶变换,然后再介绍其离散形式,最后再给出快速傅里叶变换的计算方法,但是在介绍QR分解和奇异值时却违背了这个原则,因为这部分的内容在矩阵或线性代数教程中并没有标准化。
在课堂上,我经常让学生思考有关求根问题的具体方案或让学生对所学到的方法进行改进。为了模拟书中的方法,有些章节中还简要讨论了所介绍方法的替换和改进,即使在课堂上及教科书中没有详细的介绍,这样做是很有必要的。到本课程结束,学生们应该能够提出一些诸如用二次逼近代替线性逼近等等的问题,当然也可以跳过这些讨论。
为了强调方法背后的基本思想以及将各种方法进行融合,我总是鼓励学生使其感觉到他们“拥有”了这些方法。通常情况下,学生们总是感觉他们无法完全掌握现有的方法和软件,这时就需要多进行试探,以我的经验,随意地去“篡改”那些方法也许是大有好处的,这就是为什么人们总是使用而不是编写算法的主要原因,数值软件需要这样的过程。必须知道怎样才是好的初始值,怎样才能逼近导数,怎样才能选择正确的方法和参数。
数值分析与科学计算在过去的十几年中,数值分析的实践和教学已经发生了巨大的变化,几乎很少有人再去写那些繁杂的代码和程序,人们更多的是依赖像MATLAB以及类似像Octave、GAUSS那样的软件包,同时人们所解决问题的规模也越来越大,从这方面说,还要感谢那些高级的计算机硬件以及Netlib、NAG那些强有力的软件。但即使这样也还是要进一步了解算法背后的基本思想以及怎样使这些算法在合理的时间内收敛,其中包括选择适当的初值、各种方法的结合以及调整算法的参数,当然对如何详细地写出算法的代码则可以有很少的了解(事实上,书写代码的工作可以留给专业的团队去完成),与数值分析相比,科学计算更加重要。
从教学层面上看,许多学校都在课程中减少了微积分的理论并很大程度上引入了计算机代数,这样就产生了两方面的问题:首先,教师必须按学生的知识背景去考虑问题;其次,学生往往习惯于看到计算机代数系统所给出的答案是数值形式的,而不是符号的。今天学习数值分析的学生可能不像从前那样具有数值计算的经验,这一点要归功于计算机代数系统。本书的目的在于通过强调形象思维(如线性和二次逼近)以及列举一些计算机代数系统不能解决的例子说明学习数值方法的必要性。
书中也提到了几种方法的并行问题,但没有做详细介绍。虽然学生应该知道这方面内容的存在,但我认为数值分析的初等课程中并不应该过分强调这一点。即使学生能接触到这样的机器,但编程却可能超出了他们的能力。
本书不属于参考书,所以学生只有彻底读懂才能学会这门课程。书中尽量避免枯燥的定理论述,尽量通过严格的推导说明方法背后的思想。我认为学生在具有一定的数值计算经验之前不可能对那些枯燥的理论感兴趣,所以本书的目的在于让学生能够熟练地使用标准的计算机软件,其中包括选择完成任务的方法,同时也阐述了其他方法的主要优缺点。虽然我已经成功地做到了这一点,但还是希望你们也同样能够做到这一点。
书中的每个小节可以作为一讲,但也因人而异。习题部分包括用来加深理解内容的基本问题,除了前一小节刚刚讲过的内容之外,这些问题一般不需要其他的附加资源;MATLAB部分介绍MATLAB命令以及数值实验的问题,学生可以将这部分内容作为自学MATLAB的参考书。通常我要求学生输出并上交他们的命令日志以及对结果进行简单的评价;有些附加问题可能需要与MATLAB中所介绍的内容等价的其他计算工具,序号在10以后的附加题可能更具有挑战性,最后两三个附加题通常相当困难。
本书所包含的教学内容可能会超过一个季度或一个学期。前10周我通常讲授下面的部分:1.1~1.9;2.1~2.9;3.1~3.6;4.1~4.4;5.1~5.3以及5.6和5.7的基本思想;6.1~6.3以及6.5和6.6的基本思想;7.1~7.3(如果时间允许可以加上7.4和7.5). 我在讲授的过程中比较偏重于数值线性代数,因为许多其他的问题,像偏微分方程数值解等通常都需要这方面的知识,其他领域的许多问题也都需要进行线性代数方程组的求解。第5、6章中的许多内容都是以第2章的后半部分为基础的,由于存在这种依赖关系,所以1.1~1.4,1.7,2.1~2.3和4.1是必讲的。
本课程的先修课程包括一年的微积分、矩阵代数基础以及第6章所涉及的一阶常微分方程。第8章内容要求的条件可能更高一些,通常需要熟练地掌握一些其他数学知识。另外本课程还需要一些编程经验(如果使用MATLAB) .
我的岳父曾经在他撰写的一本书的序言中写道: “一本书的完成需要众人的力量。”对此我深信不疑。我要感谢出版这本书的Addison-Wesley出版社,特别还要感谢Addison-Wesley的Cindy Cody、Joe Vetere和RoseAnne Johnson; Cris Miller和她的团队;责任编辑Louise Gache; Michael Brown编写了本书的习题解答并对本书进行了详细的检查;其他还有许多人也为本书做了大量的工作。
在此还要提及许多评论家对本书的评论,他们对内容的顺序、各段落的繁简程度都给出了很好的建议,同时还指出了书中的一些错误和疏漏。Rose-Hulman工程学院的4届学生都曾使用过本书的手稿,他们对本书的进一步加工也有很大的帮助,在此也一并表示感谢,我希望在此提到他们中的所有人。书中所遗留的所有错误都归咎于我自己。
在完成本书的过程中,Rose-Hulman工程学院的同事们给了我很大的帮助,在此特别要感谢S.Allen Broughton、Ralph P.Grimaldi和Robert Lopez(目前在Maplesoft)对我的鼓励和建议。
多年来我有幸和众多数值分析学者共同进行研究和工作,这些经历使我在这个领域不断成长,我特别要感谢我的导师Brown大学的Philip J.Davis; Brown大学的Gottlieb以及Naval Postgraduate大学的Bill Gragg.
还要感谢的是在我职业生涯中对我帮助极大的两个人:Harvey Mudd学院的Robert L.Borrelli 和Courtney S.Coleman.
最后还要感谢我妻子Meg对我的帮助,感谢她和我们的两个孩子Derek和Corrinne 在我完成本书期间对我的耐心。
第1章 非线性方程1
1.1 对分法和反线性插值1
1.2 牛顿法10
1.3 固定点定理17
1.4 牛顿法的二次收敛性27
1.5 牛顿法的变形37
1.6 布伦特方法47
1.7 有限精度运算的效果53
1.8 方程组的牛顿法62
1.9 Broyden方法70第2章 线性方程组77
2.1 部分主元高斯消去法77
2.2 LU分解87
2.3 选主元的LU分解97
2.4 楚列斯基分解111
2.5 条件数121
2.6 QR分解132
2.7 豪斯霍尔德三角化和QR分解143
2.8 格拉姆-施密特正交化和QR分解154
2.9 奇异值分解165第3章 迭代法171
3.1 雅可比迭代和高斯-塞德尔迭代171
3.2 稀疏性181
3.3 迭代加工188
3.4 预处理192
3.5 克里洛夫空间方法198
3.6 数值特征值问题208第4章 多项式插值215
4.1 拉格朗日插值多项式215
4.2 分段线性插值227
4.3 三次样条237
4.4 三次样条系数的计算246第5章 数值积分258
5.1 闭牛顿-柯特斯公式258
5.2 开牛顿-柯特斯公式和待定系数法273
5.3 高斯求积285
5.4 高斯-切比雪夫求积295
5.5 Radau和洛巴托求积303
5.6 自适应性和自动求积311
5.7 龙贝格积分319数值分析与科学计算第6章 微分方程328
6.1 数值微分328
6.2 欧拉法337
6.3 改进欧拉法346
6.4 显式单步法分析353
6.5 泰勒和龙格-库塔方法360
6.6 自适应性和刚性368
6.7 多步法376第7章 非线性优化384
7.1 一维搜索384
7.2 最速下降法392
7.3 非线性优化的牛顿法402
7.4 多重随机启动方法410
7.5 直接搜索法417
7.6 Nelder-Mead方法425
7.7 共轭方向法431第8章 逼近方法438
8.1 线性和非线性最小二乘438
8.2 最佳逼近问题446
8.3 最佳一致逼近452
8.4 切比雪夫多项式的应用462后记468习题答案471参考