科学计算导论

Scientific Computing: An Introductory Survey by Micheal T. Heath序言PREFACE本书概述了数值方法,对象为计算领域内需要解决数学问题的学生和专业人士.本书与传统的数值分析教材不同,主要侧重于介绍隐藏在算法后的基本原理和思想,而不是分析算法的细节.在求解每一大类问题时,无论是关于问题的正确表示,还是结果的合理解释,本书都采取一种通俗易懂的方式来阐述.另外,本书提倡在求解时尽可能地使用专业数学软件.本书的目标是倾向于数学软件的“使用者”,而不是这些软件的创造者".我希望读者在选择合适的方法和软件时能够对相关的问题有所了解,并正确地使用这些方法和软件在伊利诺伊大学,本书作为数值方法的教材使用,时间为一学期,主要用途有三个·作为计算机科学、数学和工程等学科高年级本科生的教材作为计算机科学系非数值分析专业研究生的参考教材.·作为在研究工作中需要使用数值方法和软件的理工科研究生的培训教材.为适应各种不同学生的需要,学习本教材的前提条件是非常基本的,只要基本熟悉线性代数、多元微积分,并对微分方程知识有少量的了解即可.对所使用的数值方法不必事先了解.但是,本书采用的观点是有一定深度的,所以,对学生(或读者)来讲还是要具备一定的知识水平.除了用于高等院校外,我还希望本书能对需要概括了解给定的计算问题及解决该问题的方法和软件的科技人员有所帮助虽然本书强调了数学软件的应用,但与其他的软件教科书不同,它既不提供任何软件;也不致力于任何特定的软件包、库或环境,而是对每类问题指出其特定的程序在公用资源和主要商用程序库或程序包中的位置许多高等院校和工程计算环境中都安装了这类软件,许多情形中我们还给出了通过互联网免费得到这类软件的网站,书中的上机练习并不依赖于任剩学计算导论何具体的软件或编程语言本书的主要组成部分如下章:本书的每一章都涵盖了一个主要的计算领域.书的前半部分主要处理代数问题,而后半部分主要处理涉及导数和积分的分析问题.前两章是本书的基础,后面的各章可以根据不同的需要重新排序.各章节间的具体关系如下表所示章所依赖的章章所依赖的章章所依赖的章1、2、3、5101、2、5、7、92l、2111、2、7、9、1041、2、31、2、7122、72、5、713这样,可以将第7、8、12和13章的内容提前,而将第3、4和6章放在后面.例如,第3、7和12章都涉及某类数据拟合,所以应该把它们作为一个整体来讲述.又例如,由于线性方程组的迭代法主要应用在偏微分方程的求解中,所以本书将这一部分内容放在了关于偏微分方程的第11章,实际上其中的大部分内容都可以在第2章线性方程组的直接法之后立刻给出.注意到在本书的后半部分广泛地使用了特征值,所以这也是将其早早地放在第4章的原因,但如果学生已对这个问题非常了解则例外在一个学期内完成本书的内容有些困难,可以根据需要作适当删减例如,关于随机数和随机模拟的第13章与本书的其他内容关系不大,因此可以略去(但本书中的许多习题都用到了随机数发生器).本书的全部内容可用1.5或2个学期完成例题:书中的每个概念和方法几乎都用一个或多个例子加以说明.这些例子对所讨论的内容作了相对简要的补充,是本书必不可少的部分.我们尽量使用简单的例子(有时甚至过于简单),目的是为了使读者容易接受.依我本人的经验,彻底弄明白一个简单的例子往往比那些虽然更为实际但却不易接受的例子更有帮助软件:针对每类问题,本书都列出了大量的软件.然而对每个给定的问题,我们并不特别指出哪个软件是“最好的”,因为没有哪个软件包在所有方面都是优秀的.而且,我们也要考虑读者所能获得的软件及使用的编程语言.本书所列出的所有软件至少都是令人满意的,甚至其中有些是极为优秀的练习:本书包含了丰富的习题,它们分为三类复习题:是只需简要回答的问题,用来测试对基本概念的理解练习题:需要一定的思考并作较长的解答,有的要进行手工计算上机问题:需要进行程序设计,也可以使用现成的软件复习题可作为读者的自我测试题,通过仔细考虑找出解答的关键点,并建立掌握这些知识的信心练习题可作为课后作业,有些需要结合简单的例子进行手工计算,有些是对正文中省略的证明和推导的细节的补充.如果以本书作为理论性较强的课程的教材,则这些证明和推导细节是必不可少的.上机问题可以使读者在利用所推荐的软件解决各类典型问题方面积累一定的经验有些上机问题是一般的,还有一些是与科学和工程的某些具体应用直接相关的第2版的变化:每一章都从问题的来源开始讨论,并用一个或多个例子加以说明,然后讨论给定问题的解的存在性、惟一性和病态性.目的是让学生理解问题的重要性,并在考虑解决问题的算法之前识别问题的“好”与“坏”的表示方式.主要的算法都给以规范的说明,并加以编号.更新了参考文献,并对有关历史的注记及参考文献进行了定的扩充.对第1章中讨论的向前和向后误差以及它们间的关系进行了进一步的扩充和澄清.关于奇异值分解的许多内容从第4章移到了第3章,这样更为适当第4章对特征值算法的收敛性作了扩充,包括了更多的原理和细节,特别是关于QR迭代及其他的方法.第6章对约束优化的处理作了相当大的扩充.关于微分方程的章节稍作整理,增加了谱方法的收敛性.重新编写了关于快速傅里叶变换的第12章,删掉了某些无关的内容(致谢部分略)M.T. HEATH符号说明7A八本书采用标准符号,无需更多解释.书中大量地使用了向量和矩阵符号,一般用大写黑体形式表示矩阵,用小写黑体表示向量,常规形式表示标量.迭代和分量的序号用下标表示,一般从i到n.例如向量x和矩阵A的元素分别为x;和an,如果既要使用迭代序号又要使用分量序号,一般用加括号的上标表示迭代,如x{表示序列中第k个向量的第讠个分量否则,x,表示x的第i个分量,xk表示序列的第k个向量虽然所讨论的大多数理论和算法都可以不加或稍加变化推广到复数域,但为了简化,这里只讨论实向量和实矩阵.用R表示实数集合,R"表示n维实欧几里得空间,Rmx表示实m×n矩阵的集合.复空间中对应的表示分别为C、C”和Cmx向量或矩阵的转置用上标T表示,用上标H表示共轭转置( Hermite转置).除非有其他说明,否则所有向量都是列向量,行向量用列向量的转置表示.为方便排版,列向量的分量有时用相应行向量的转置表示,如x=[x1x2].两个n维向量x和y的内积(也称点积或标量积)是矩阵乘积的特殊情形,用xy(复数域时用xHy)表示.类似地,两个n维向量x和y的外积,用xy表示,它是一个n×n的矩阵.n阶单位矩阵记为In(如果不会发生维数混淆,用I表示),用e,表示单位矩阵的第列零矩阵和零向量都用0表示,标量零用0表示,对角元为d1,d2,…,d,的对角阵记为diag(a1,d2,…,dn),向量或矩阵间的不等关系按元素间的关系表示,由m×n矩阵A的列所张成的子空间R”,即{Ax:x∈R"},用span(A)表示单变量函数f(t)的导数用dfdt或∫'(t)表示.多变量函数如u(x,y)的偏导数用aw/3x或u,表示.梯度向量、雅可比( Jacobi)矩阵和黑塞( Hessian)矩阵将根据需要引入,如果不做特别说明,所有对数都是自然Ⅵ科学计算旨论对数(底数e≈2.718).一般情况下,用≈表示近似相等,用全表示最小二乘近似数值方法的计算成本或复杂性一般是用所需的代数运算次数来衡量的.数值分析中通常只计乘法(及必要的除法和开方),这是由于乘法通常比加法和减法费时,以及在大多数算法中,乘法的次数往往与加法的次数相近(例如,计算两个向量的内积).但近年来,加法和乘法的耗时已相差甚微(事实上,时下许多微处理器都可用单指令multiply-add完成一对乘法和加法).计算机销售商和用户一般都要对计算机最高性能作大肆宣扬,所以现在普遍的说法是计算所有的运算次数.但由于某些操作的计算次数已经广为人知,所以本书一般只计算乘法次数.为了区别起见,一般加上“相同数量的加法”一词,或同时计算乘法和加法时,直接加以说明在确定操作次数或近似值的精确度时,经常使用大O符号表示函数值的阶或主项对于操作次数,主要关心的是当问题的规模也可以说n变大时的性态.如果存在正常数C,使对充分大的n有f(n)|≤C|g(n)则称(读作“f是g的大O”或“f∫是g阶的”).例如2n23+3n2+n=O(n3)这是因为随着n的增大,阶数小于n3的项相对来说就是无关紧要的.对于精度估计,主要关心的是当某个量h,如步长或划分间隔变小时的性态,如果存在正常数C,对充分小的h有f(h)|≤C|g(h)|,则称f(h)=og(h)).例如,1+h+h2+h3+1+h+O(h2),这是因为随着h的变小,所忽略的那些阶数超过h2的项相对来说是无关紧要的.需要注意的是,如果h=1/n,则两个定义是等价的目录CONTENTS序言符号说明V第1章科学计算1.1引1.2科学计算中的近似1.3计算机运算131.4数学软件…261.5有关历史的注记及参考文献……………………31第2章线性方程组2.1线性方程组2.2解的存在性和惟一性…∴422.3问题的敏感性和病态性昏鲁自昏…………………432.4线性方程组的求解2.5特殊类型的线性方程组…………722.6线性方程组的迭代法…………D··……762.7有关线性方程组的软件…762.8有关历史的注记及参考文献第3章线性最小二乘···:····.·····:···············:······:·:.·903.1线性最小二乘问题…………………………………903.2解的存在性和惟一性……………933.3问题的敏感性和病态性自鲁鲁血鲁·973.4问题的变形………100Ⅶ》科学计镎号论3.5正交化方法…·鲁非1043.6奇异值分解…1193.7方法间的比较自·番●卡鲁·。鲁1243.8有关线性最小二乘的软件·····……1259有关历史的注记及参考文献126第4章特征值问题1364.1特征值和特征向量1364.2解的存在性和惟一性1384.3问题的敏感性和条件数…1444.4问题的变形…1464.5特征值和特征向量的计算1504.6广义特征值问题1744.7奇异值分解的计算1754.8有关特征值问题的软件………………17549有关历史的注记及参考文献鲁带鲁……………177第5章非线性方程1875.1非线性方程∴1875.2解的存在性和惟一性1885.3问题的敏感性和病态性5.4收敛速度和判停准则1925.5一维非线性方程…1935.6非线性方程组……………2055.7有关非线性方程组的软件∴∴…2108有关历史的注记及参考文献212第6章优化问题····由自···由·;·····v··b2216.1优化问题·鲁2216.2最优解的存在性和惟一性·鲁垂·2236.3问题的敏感性和病态性……2324一维优化………………2336.5无约束优化2396.6非线性最小二乘…………………………247求6.7约束优化2506.8有关优化的软件∴2566.9有关历史的注记及参考文献258第7章插值2697.1插值2697.2插值的存在性、惟一性和病态性2717.3多项式插值………2727.4分段多项式插值…287.5有关插值的软件…垂●垂·垂D幽专·章看······“············‘.··········2877.6有关历史的注记及参考文献289第8章数值积分和数值微分2948.1积分…咖鲁2948.2积分解的存在性、惟一性和问题的病态性2958.3数值求积…2968.4其他积分问题3108.5积分方程8.6数值微分…8.7理查森外推法3188.8有关积分和微分的软件3218.9有关历史的注记及参考文献………322第9章常微分方程的初值问题………3309.1常微分方程者鲁着即带·.··。●3309.2解的存在性惟一性和问题的病态性·····.······:·a·“·3349.3常微分方程数值解香着鲁·看·鲁鲁鲁·。·鲁·.·垂…3369.4有关常微分方程初值问题的软件3549.5有关历史的注记及参考文献355第10章常微分方程边值问题36310.1边值问题……36310.2解的存在性、惟一性和问题的病态性36410.3打靶法鲁鲁自36710.4有限差分法370