稀疏矩阵——算法及其程序实现

稀疏矩阵是数学和计算机科学领域中的一个重要概念，它广泛应用于各类科学与工程计算问题中，如线性代数方程组的求解、电子线路分析、线性规划以及非线性优化问题等。稀疏矩阵指的是在矩阵中大部分元素为零的矩阵，只有相对少数的元素是非零的。由于这些非零元素在矩阵中的分布通常比较稀疏，因此被称作稀疏矩阵。 在处理稀疏矩阵时，直接采用常规的矩阵运算算法，如高斯消去法等，效率是非常低的。因此，研究稀疏矩阵的高效算法以及程序实现就显得非常重要。稀疏矩阵的算法主要包括稀疏矩阵的存储、稀疏矩阵的运算、以及线性方程组的求解等。 书中提到的稀疏矩阵算法的研究动向，不仅包括了国内外在该领域取得的主要成果，也涵盖了数据结构算法及其程序实现。在介绍算法的同时，作者也详细讲解了各种算法的优缺点以及适用场景。书中分为十章，分别介绍了绪论、线性代数方程组的解法、矩阵分解、稀疏矩阵的存储、选择主元的策略、结构对称矩阵的解法、对称变带宽矩阵的解法、非对称时变稀疏矩阵的解法、以及稀疏矩阵算法在其他领域的应用。 对于稀疏矩阵的存储，书中提出了几种不同的数据结构，每种结构都有自己的优缺点。例如，双链表数据结构在稀疏矩阵的存储中不需要重选主元，但在必要时也可以进行主元的调整。又如闭性表数据结构，它可以根据需要进行时变主元的更换。 在求解线性方程组时，可以采用直接法和迭代法两种途径。直接法如高斯消去法、LU分解、高斯-约当消去法、全主元消去法等；迭代法则包括高斯-赛德尔迭代法、松驰法等。这些方法在处理不同稀疏矩阵问题时，选择合适的算法，可以显著提高求解效率。 矩阵的分解在稀疏矩阵算法中占有重要的地位。书中提到的分解方法包括LU分解、QR分解和全主元原位分解法。LU分解是将矩阵分解为两个三角矩阵的乘积形式，而QR分解则是将矩阵分解为一个正交矩阵和一个上三角矩阵的乘积形式。 在稀疏矩阵算法的实现上，书中也给出了算法的汇编代码，方便读者直接查阅和使用。此外，书中的每一章节后面都配有习题，帮助读者更好地理解和掌握所学的知识，并将其应用于实际问题中。 本书不仅适用于科学技术领域的师生和科研技术人员作为参考书籍，也可以作为电子工程、数学规划、结构分析、遗传学理论等专业的教学用书。作者在书中还特意强调了稀疏矩阵算法在非线性代数方程组、非线性微分方程组、非线性优化问题求解中的关键性，以及该算法在线性规划、电子线路分析和非线性优化问题中的应用。 作者通过大量实例和详尽的算法描述，旨在帮助读者深入理解稀疏矩阵的算法原理，并在实际问题中有效地应用这些算法。尽管作者也指出由于时间仓促和水平所限，书中难免会有误，请读者批评指正。这本书的完成得益于谈根林和杨绍祺两人的共同努力，谈根林负责编写第四到第七章以及第八章，而杨绍祺则完成了其余五章。谈根林还完成了书籍的文字整理工作。本书的出版意义重大，不仅丰富了稀疏矩阵算法的研究成果，也为其应用提供了一定的指导和参考。