计算方法 by 张世禄 何洪英.pdf

高等学校教材 计 算 方 法 张世禄 何洪英 编著 Publishing House of Electronics Industry 北京BEIJING 内 容 简 介 本书比较全面地介绍了科学与工程计算中常用的计算方法，具体介绍了这些计算方法的基本理论与实际应用，同时对这些数值计算方法的计算效果、稳定性、收敛效果、适用范围以及优劣性与特点也做了简要分析。全书共11章，主要介绍数值代数和数值逼近中常用的实用算法，书中的所有算法都用带计算过程和计算条件的数学语言描述。凡可以手算的算法都附有带计算过程的算例。书中较为详细地介绍了变带宽压缩存储平方根法和压缩存储Seidel迭代法，并附有C程序。书中所有算例的结果都用程序验证过，保证无错，书中有些内容是作者的科研成果。本书可作为高等院校数学与应用数学、信息与计算科学、应用物理学、计算机科学等专业的高年级本科生和工科硕士研究生使用，也可供从事科学与工程计算的科技工作者参考。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目（CIP）数据 计算方法/张世禄，何洪英编著北京：电子工业出版社，2010.8（高等学校教材）ISBN 978-7-121-11426-7.计 .张 何 .计算方法高等学校教材 .O241 中国版本图书馆 CIP 数据核字（2010）第 140804 号 策划编辑：王赫男 责任编辑：谭海平 印 刷：装 订：出版发行：电子工业出版社 北京市海淀区万寿路 173 信箱 邮编 100036 开 本：787980 1/16 印张：15 字数：324 千字 印 次：2010 年 8 月第 1 次印刷 印 数：4 000 册 定价：27.00 元 凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（010）88254888。质量投诉请发邮件至 ，盗版侵权举报请发邮件至 。服务热线：（010）88258888。前 言 计算方法是数学中的一个古老分支，自计算机问世之后，计算方法得到了飞速发展计算方法是计算（computing）学科各专业、数学各专业学生的必修课，也是不少理工专业学生的必修课和选修课考虑到传统关系，主要考虑到课时关系，计算方法不包含有限单元法、快速 Fourier 变换等算法，也不包含最优逼近、最优化算法，仍只由数值代数和数值逼近组成 本书的特点如下 1全书所有算法都用带计算过程和计算条件的数学语言描述 计算方法主要是计算机使用的算法，计算机只能直接或间接识别人们用计算机语言编写的程序程序也是算法，是计算机使用的算法程序设计就是将非计算机使用的算法翻译成计算机使用的算法带计算过程和计算条件的数学公式和计算机语言有一对一的映射关系，很容易翻译成计算机语言 现有计算方法教材中，有少数算法是用自然语言描述的，例如，解()0=f x的对分法，求三角矩阵特征值所用的对分法；还有些算法是用表格加算例表述的，例如，牛顿插值多项式系数计算，不少书中仅给出了一个具体算例的差商表一般的计算方法书中，绝大多数算法虽然都是用数学公式表示的，但是未明确给出计算过程和计算条件，不能直接翻译成计算机语言 将算法用带计算过程和计算条件的数学公式表示，不仅方便于程序设计，也便于手算 2纠正了一般计算方法中不当的提法和结论 现行教材中有些提法和结论是有问题的，有些提法不准确，不能体现实质例如，在解方程组=Axb的直接法的稳定性分析中，一般教材的结论是条件数 condp(A)愈大，稳定性愈差，未能体现算法本书的结论是：直接法的稳定性与算法有关，与方程组系数矩阵本身的特性有关，还与右端扰动大小有关，但与系数矩阵的条件数没有直接关系这样既弄清了高斯列主元消元法、全主元法为什么能求解高斯消元法中所不能求解的问题或者误差很大的问题，又弄清了为什么平方根法、改进平方根法要求方程组=Axb中A的本身性能必须较好才能使用的原因，这样提法才和算法有关又如在求解()0=f x的牛顿法收敛性定理中，一般认为定理()()0f a f b 理论性强，用处大，而定理在根的邻域内牛顿法收敛且是二阶收敛实用性差我们的结论正好相反，原因是牛顿法并不麻烦，但要鉴别一个二阶导数不变号尚未见可行的数值算法恰恰相反，后一定理的可操作性好，因为对任何求根区间，我们总可以将之划分成等距的n等份，只要n充分大，任何子区间或者有一个根，或者无根，只要有根，该子区间就是根的邻域，而且前一个定理只能在,a b 上有一个根才管用，而后者可求所有根（单根）再如在讲逆幂法的功能时，不少书讲逆幂法的功能是求A按模最小特征值及对应特征向量，实际上应强调是求1A的按模最大特征值及特征向量为好因为数学上只关心按模最大特征值工程物理问题只关心固有频 率（基频），或许还关心次频、第三频，所对应特征值为最大特征值、次大特征值等实际上逆幂法并不单独使用，它总是和对称矩阵三对角化（镜面反射变换）对分法求指定特征值、原点平移配合使用的，它所求的特征值是A经过原点平移后的最小特征值，而不是A的最小特征值，一般教材中过分强调原点平移后会降低按模最大特征值和按模次大特征值之比，实际上原点平移可能改变特征值序号，还可能增大二者的比，在数值计算中也只和对分法和逆幂法配合使用才有意义 3强调实用和应用 一般教材都讲迭代法可解大、中型代数方程组，但不介绍压缩存储实际上若不压缩存储，无论是在算法复杂性上和内存开销上，迭代法都不及直接法，更不及变带宽平方根法或改进平方根法（一般书不介绍），只是对于高阶线性代数方程组计算误差小一些本书增加了压缩存储算法，压缩存储算法的计算公式与对应的非压缩存储算法的计算公式相比并不复杂，其程序复杂程度比非压缩存储的还要小 4对绝大多数（除压缩存储迭代法外）算法都给出了手算算例，其计算结论都用程序做了验证 书中除了压缩存储赛得尔迭代法和变带宽平方根法外，都给出了手算算例，并在算例中给出了算法计算过程，对压缩存储赛得尔迭代法及程序设计难度较大的算法，例如高斯全主元消元法、镜面反射变换等才附了程序 计算方法是数学的分支，学生不做习题很难掌握算法，不给出算例也不方便学生做题，不易提高学生的抽象归纳能力，计算方法虽和程序设计相关，但两者不相等，所以不必每个算法都附程序程序中的算例也不能代替手算算例冯康先生所著书中在计算每个算法时都附了程序，但冯康先生的计算方法实质上是用文字书写的软件包，不主要作为教学用本书给出的所有算例都经过了计算机程序的验证，确保无误 5增加了一些新算法 本书增加了幂级数型插值多项式及泰勒级数数值算法，在推导 Adams 线性多步法时，直接使用了幂级数插值多项式，给出了公式推导过程，而其他教材只是讲可使用牛顿插值多项式推导线性多项式，却未给出推导过程（原因在于太麻烦）此外，本书给出了一般牛顿积分代数精确度的证明，给出了高斯积分代数精确度的简洁证明，对牛顿插值多项式的计算也做了改进（仿秦九韶计算）?本书由张世禄和何洪英编写，编写书稿时得到了数学与信息学院领导的大力支持，得到了我的学生陈豫眉、熊华、谭代伦的帮助，这里特以致谢！张世禄 何洪英 2010 年 6 月于四川南充 V 目 录 第 1 章 误差和算法选择1 1.1 误差概念1 1.1.1 误差分类1 1.1.2 误差表示法和误差限3 1.1.3 误差运算4 1.1.4 有效数字4 1.2 算法选择5 1.2.1 正确性5 1.2.2 选择低复杂性算法8 1.2.3 减少误差的一些简单办法9 1.2.4 一种新的算法模式9 习题 110 第 2 章 解线性方程组方法之直接法11 2.1 Gauss 消元法11 2.1.1 Gauss 消元法 11 2.1.2 Gauss 消元法的计算过程和计算算例13 2.1.3 Gauss 消元法计算量 15 2.1.4 Gauss 列主元素消元法 16 2.1.5 Gauss 全主元素消元法 18 2.1.6 Gauss 列主元法和 Gauss 全主元法计算量 20 2.1.7 Gauss 全主元素消元法计算程序20 2.1.8 消元法适用范围22 2.2 矩阵三角分解法23 2.2.1 LU 分解法23 2.2.2 LU 分解算例24 2.2.3 利用 LU 分解法解方程组25 2.2.4 LU 分解法解方程组算例25 2.2.5 平方根法和改进平方根法27 2.2.6 改进平方根法29 VI 2.2.7 LU 分解法、平方根法和改进平方根法计算量31 2.2.8 变带宽压缩存储平方根法33 2.2.9 追赶法36 2.3 范数简介38 2.3.1 向量范数定义38 2.3.2 常用向量范数38 2.3.3 向量范数性质38 2.3.4 矩阵范数定义39 2.3.5 矩阵范数基本性质40 2.4 直接法的稳定性分析43 2.4.1 常见稳定性分析43 2.4.2 消元法稳定性分析46 2.4.3 三角分解法稳定性分析47 2.4.4 直接法稳定性分析结论48 习题 248 第 3 章 解方程 f(x)=0 的迭代法50 3.1 逐次迭代法50 3.1.1 逐次迭代法50 3.1.2 收敛阶52 3.1.3 逐次迭代法的几何意义53 3.1.4 计算实例54 3.2 Newton 法55 3.2.1 Newton 法算式推导56 3.2.2 Newton 法的几何意义 56 3.2.3 Newton 法的收敛条件 56 3.2.4 Newton 法的计算过程和计算实例 58 3.3 割线法59 3.3.1 单点割线法59 3.3.2 单点割线法的收敛条件60 3.3.3 单点割线法的计算过程和计算实例60 3.3.4 双点割线法61 3.3.5 双点割线法的收敛条件61 3.3.6 双点割线法的计算过程和计算实例61 3.4 对分法62 VII 3.4.1 对分法算式推导62 3.4.2 对分法的计算过程和计算实例63 3.5 分离根方法及求所有根算法63 3.5.1 分离根方法64 3.5.2 求所有根算法64 3.5.3 特殊处理64 3.5.4 计算实例65 习题 365 第 4 章 解线性代数方程组的迭代法66 4.1 向量序列和矩阵序列的极限66 4.2 Jacobi 迭代法67 4.2.1 Jacobi 迭代法推导67 4.2.2 Jacobi 迭代法的矩阵形式68 4.2.3 Jacobi 迭代法的计算过程和计算实例69 4.3 Seidel 迭代法70 4.3.1 Seidel 迭代算法推导70 4.3.2 Seidel 迭代法的矩阵表示70 4.3.3 Seidel 迭代法的计算过程和计算实例71 4.4 松弛法72 4.4.1 松弛法计算公式72 4.4.2 松弛法的矩阵形式72 4.4.3 松弛法的计算过程和计算实例73 4.5 迭代法收敛条件74 4.5.1 对角占优矩阵和不可约矩阵74 4.5.2 迭代法的收敛条件和误差估计75 4.6 压缩存储迭代法84 4.6.1 压缩存储 Seidel 迭代法84 4.6.2 压缩存储 Seidel 迭代法计算公式85 4.6.3 压缩存储 Seidel 迭代法计算步骤85 4.6.4 计算实例86 习题 488 第 5 章 特征值数值算法90 5.1 幂法90 VIII 5.1.1 幂法计算公式90 5.1.2 实用幂法91 5.1.3 实用幂法的计算过程和计算实例92 5.2 原点平移和逆幂法93 5.2.1 原点平移算式93 5.2.2 原点平移加幂法的计算特征值过程和计算实例93 5.2.3 逆幂法94 5.2.4 逆幂法计算实例95 5.3 实对称矩阵特征值数值算法对分法96 5.3.1 镜面反射矩阵及其性质97 5.3.2 实对称矩阵三对角化98 5.3.3 实对称矩阵三对角化算法99 5.3.4 实对称矩阵三对角化程序100 5.3.5 求实对称矩阵特征值的对分法102 习题 5108 第 6 章 代数插值多项式109 6.1 Lagrange 插值多项式109 6.1.1 Lagra