一类按行稀疏存储结构的稀疏线性代数方程组的快速求解.doc

一类按行稀疏存储结构的稀疏线性代数方程组的快速求解 目录摘要.1abstract.21 引言和预备知识.31.1 引言.31.2 稀疏线性代数方程组的定义.41.3 稀疏存储的概念.41.4 行稀疏存储格式.42 稀疏线性代数方程组的共轭梯度（cg）法.62.1 共轭梯度法原理.6    2.2  算法描述.63 稀疏线性代数方程组的预条件共轭梯度(pcg)法.93.1预条件共轭梯度法的算法简介.93.2 共轭梯度法的几个重要问题.12  3.2.1 等价问题123.2.2 最速下降法12    3.2.3 共轭梯度法143.3 小结.174 例题分析.185 总结20参考文献.21致谢22附录.23摘要本毕业论文主要包含两部分内容。第1部分针对1类稀疏线性代数方程组，利用目前国际上使用比较频繁的处理稀疏矩阵的按行稀疏存储结构，设计了求解稀疏线性代数方程组的共轭梯度（cg）法，并分析计算复杂度。第2部分为这类线性代数方程组设计了1种基于不完全lu分解的预条件共轭梯度（pcg）法，并给出了计算实例，验证程序设计的正确性。在本次设计最后还附上了详细的程序代码。关键词 稀疏存储结构; 不完全lu分解; 共轭梯度法(cg); 预条件共轭梯度法（pcg）; 行存储 abstractthis thesis mainly contains two parts. one points at a sequence of one sparse linear algebra system of equation ,utilizing frequent treatment sparse matrix data structure at present that is according to the competent store structure, design the law of conjugation gradient method (cg) which solves the equation group of the sparse linear algebra of asking analyses the complexity of calculating. the other designs the law of the preconditioned conjugate gradient method (pcg) that is based upon the incomplete analysis of lu for this kind of linear algebraic equation, testing the correctness of this procedure design.  keywords   store the structure sparsely; incomplete analysis of lu; conjugation gradient method (cg); preconditioned conjugate gradient method (pcg);  storage by row1 引言和预备知识1.1 引言自从计算机出现以来，人们的生活越来越依赖于计算机。计算机拥有人类无法比拟的计算速度，比如在气象预报上，没有计算机的帮助是几乎不可能做到及时准确的预报气象信息。但是计算机并非拥有类似人类的思维，它所能做的只是按照预先设置好的方法计算。计算机的计算速度受硬件限制，但其所用的计算方法却是人设计的。目前电子计算机运算的速度已经接近极限，而计算机的计算效率除了计算速度以外还受计算方法的制约，好的计算方法可以快速而有效的计算出需要的结果来，从某种意义上来说。设计1个好的计算方法相当于变相的提高了计算机的计算速度，效率也得到了相应的提高。所以目前寻找好的计算方法已经为越来越多的人所重视。计算机需要计算的大部分都是方程组，本文只讨论线性代数方程组。而解方程组主要有直接法和迭代法2种， 到目前为止，直接法由于其很好的健壮性和可估计性而得到广泛应用，在很多情况下往往优于迭代法。所谓直接法，它是1类精确方法，即若不考虑计算过程中的舍入误差，通过有限步计算就可以获得方程组的精确解。所谓迭代方法，就是构造某种极限过程去逐步逼近方程组的解。20世纪60年代到70年代，大型线性代数方程组的求解取得了两个重要的革命性的进步。首先是认识到如能利用系数矩阵的稀疏性设计1些特殊的直接法，效率将大大提高；其次是预处理技术的产生，将预处理技术与krylov子空间迭代法结合可以给出许多高效的1般化的程序。近年来，产生了各种好的迭代法，如适用于系数矩阵对称正定情形的共轭梯度法（cg法），用来解非对称正定问题的gmres方法，它们都是基于krylov子空间得到的迭代法，将预处理技术与上述方法结合又