常用算法程序集（C++语言描述）第四版 徐士良

本书是针对工程中常用且行之有效的算法而编写的，并且根据算法的分类以及使用特点作了精心的组织和安排。本书具有以下几个特点： (1) 书中除收集了传统的算法外，还根据作者工作的经验和近年来数值计算的发展，选取了一些新的、实用的算法。可以说，书中各章几乎都有一些新的算法。 (2) 书中所有的算法程序都经过认真的调试。 (3) 本书全部的算法程序均可从清华大学出版社网站上的本书页面中下载，读者可以从中方便地使用书中的每一个算法程序。 (4) 书中收集的算法都是行之有效的，基本可以满足解决工程中各种实际问题的需要。 书中程序是用C++描述的。根据问题的特点，采取了以下两种描述的方法： 第一种方法是为每一个算法定义一个类。在这种类中，数据成员包括算法所处理的数据以及一些重要参数（相当于面向过程程序设计中子程序的形参），有时也将这个类中的各函数成员所用到的公共数据也作为类的数据成员，以便于各函数成员间互相通信。算法所处理的数据以及一些重要参数一般事先由用户存放在一个文件中，各数据之间用若干个空格或回车换行进行分隔。在这种类中，主要函数成员包括以下4种： (1) 构造函数与析构函数。对于涉及到问题规模的数据（如矩阵阶数，多项式次数等）一般通过构造函数来提供，以便保证在创建该类对象的同时为数据分配存储空间，并且在析构函数中释放这些空间。有时对于个别数据也通过构造函数来提供。 (2) 文件读入函数。在这个函数中，读入算法所需要处理的数据以及一些重要参数。在执行这个函数过程中，程序会提示用户从键盘键入输入文件名。 (3) 实现算法的执行函数。有时还包括这个算法需要调用的其他一些函数。 (4) 输出函数。在这个函数中，将结果输出到一个文件中（文件名由用户提供）, 但一般也在屏幕上显示，对于输出到文件中的结果纯粹是数据，不加任何文字信息，各数据之间只用空格或回车换行作分隔，以便这些数据在以后再用程序处理，而在屏幕上显示的结果中还包含有一些文字说明或格式，以便用户阅读。在执行这个函数过程中，程序会提示用户从键盘键入输出文件名。 显然，用户使用这种算法是很方便的，只要事先准备好存放算法所处理的数据以及一些重要参数的输入文件；然后编写一个主函数，该主函数包括创建该类的对象以及由这个对象分别调用输入函数成员、执行算法的函数成员和输出函数成员语句；在执行程序的过程中，用户只要根据程序的提示，由键盘分别键入输入函数名和输出函数名即可。程序执行完成后，屏幕上即显示带有文字说明或格式的输出结果，在输出文件中同时被写进了输出的数据。 第二种方法是将若干同类算法封装在一个类中。例如，在本书的第10章中，将复数运算封装成一个类，将实系数多项式运算封装成一个类，将复系数多项式运算封装成一个类，以及将各种特殊函数的计算封装成一个类。 限于作者水平，书中难免有错误之处，恳请读者批评指正。 作者 2008年4月 第1章 矩阵运算1 1.1 实矩阵相乘1 1.2 复矩阵相乘4 1.3 一般实矩阵求逆8 1.4 一般复矩阵求逆13 1.5 对称正定矩阵的求逆18 1.6 托伯利兹矩阵求逆的特兰持方法21 1.7 求一般行列式的值25 1.8 求矩阵的秩29 1.9 对称正定矩阵的乔里斯基分解与行列式求值33 1.10 矩阵的三角分解36 1.11 一般实矩阵的QR分解41 1.12 一般实矩阵的奇异值分解46 1.13 求广义逆的奇异值分解法61 第2章 矩阵特征值与特征向量的计算75 2.1 求对称三对角阵的全部特征值与特征向量75 2.2 求实对称矩阵全部特征值与特征向量的 豪斯荷尔德变换法80 2.3 求赫申伯格矩阵全部特征值的QR方法88 2.4 求一般实矩阵的全部特征值95 2.5 求实对称矩阵特征值与特征向量的雅可比法102 2.6 求实对称矩阵特征值与特征向量的雅可比过关法109 第3章 线性代数方程组的求解115 3.1 求解实系数方程组的全选主元高斯消去法115 3.2 求解实系数方程组的全选主元高斯\|约当消去法119 3.3 求解复系数方程组的全选主元高斯消去法124 3.4 求解复系数方程组的全选主元高斯\|约当消去法129 3.5 求解三对角线方程组的追赶法135 3.6 求解一般带型方程组139 3.7 求解对称方程组的分解法146 3.8 求解对称正定方程组的平方根法151 3.9 求解托伯利兹方程组的列文逊方法155 3.10 高斯\|赛德尔迭代法161 3.11 求解对称正定方程组的共轭梯度法165 3.12 求解线性最小二乘问题的豪斯荷尔德变换法169 3.13 求解线性最小二乘问题的广义逆法175 3.14 求解病态方程组189 第4章 非线性方程与方程组的求解195 4.1 求非线性方程实根的对分法195 4.2 求非线性方程一个实根的牛顿法198 4.3 求非线性方程一个实根的埃特金迭代法201 4.4 求非线性方程一个实根的试位法204 4.5 求非线性方程一个实根的连分式法206 4.6 求实系数代数方程全部根的QR方法211 4.7 求实系数代数方程全部根的牛顿下山法216 4.8 求复系数代数方程全部根的牛顿下山法225 4.9 求非线性方程组一组实根的梯度法233 4.10 求非线性方程组一组实根的拟牛顿法238 4.11 求非线性方程组最小二乘解的广义逆法246 4.12 求非线性方程一个实根的蒙特卡洛法262 4.13 求实函数或复函数方程一个复根的蒙特卡洛法265 4.14 求非线性方程组一组实根的蒙特卡洛法269 第5章 插值与逼近274 5.1 Lagrange插值274 5.2 连分式插值277 5.3 埃尔米特插值281 5.4 埃特金逐步插值284 5.5 光滑插值288 5.6 第一种边界条件的三次样条函数插值、微商与积分294 5.7 第二种边界条件的三次样条函数插值、微商与积分301 5.8 第三种边界条件的三次样条函数插值、微商与积分307 5.9 二元Lagrange插值314 5.10 最小二乘曲线拟合319 5.11 切比雪夫曲线拟合326 5.12 最佳一致逼近的里米兹方法332 5.13 矩形域的最小二乘曲面拟合337 第6章 数值积分348 6.1 变步长梯形求积法348 6.2 变步长辛卜生求积法351 6.3 自适应梯形求积法353 6.4 龙贝格求积法356 6.5 计算一维积分的连分式法359 6.6 高振荡函数求积法363 6.7 勒让德-高斯求积法368 6.8 拉盖尔-高斯求积法371 6.9 埃尔米特-高斯求积法374 6.10 切比雪夫求积法376 6.11 计算一维积分的蒙特卡洛法379 6.12 变步长辛卜生二重积分法382 6.13 计算多重积分的高斯方法386 6.14 计算二重积分的连分式法391 6.15 计算多重积分的蒙特卡洛法395 第7章 常微分方程组的求解399 7.1 定步长欧拉方法399 7.2 变步长欧拉方法404 7.3 维梯方法409 7.4 定步长龙格-库塔方法414 7.5 变步长龙格-库塔方法419 7.6 变步长基尔方法424 7.7 变步长默森方法430 7.8 连分式法436 7.9 双边法444 7.10 阿当姆斯预报校正法450 7.11 哈明方法456 7.12 特雷纳方法463 7.13 积分刚性方程组的吉尔方法470 7.14 二阶微分方程边值问题的数值解法487 第8章 数据处理494 8.1 随机样本分析494 8.2 一元线性回归分析499 8.3 多元线性回归分析503 8.4 逐步回归分析510 8.5 半对数数据相关521 8.6 对数数据相关525第9章 极值问题的求解529 9.1 一维极值连分式法529 9.2 n维极值连分式法532 9.3 不等式约束线性规划问题538 9.4 求n维极值的单形调优法545 9.5 求约束条件下n维极值的复形调优法552 第10章 复数、多项式与特殊函数的计算562 10.1 复数运算562 10.2 实系数多项式的计算569 10.3 复系数多项式的计算574 10.4 特殊函数的计算581 第11章 查找与排序619 11.1 顺序表的查找与排序619 11.2 结构表的查找与排序629 11.3 磁盘文件结构表的查找与排序636 11.4 磁盘随机文本文件的字符串匹配642参考文献646