大型稀疏矩阵的求解演示教学.ppt

L/O/G/O 大型稀疏矩阵的求解 学生：袁涛 学号Contents 1. 快速、有效求解线性方程组意义 2. 大型稀疏矩阵的概念及其特点 3. 稀疏矩阵的求解方法及优缺点 4. 用VB实现解线性方程组雅克比法 5. 结论 快速、有效求解线性方程组意义 如何利用计算机来快速、有效地求解线性方程组的问题是数值线性代数研究的核心问题，而且也是目前仍在继续研究的重大课题之一。这是因为各种各样的科学与工程问题往往最终都要归结为一个求解线性方程组的问题。例如，结构分析、网络分析、数据分析、最优化及非线性方程组和微分方程数值解等，都常遇到线性方程组的求解问题。求解线性方程组的数值方法可分为直接法和迭代法两大类。直接法是指在没有舍入误差的情况下经过有限次运算可求得方程组的精确解的方法；迭代法则是采取逐次逼近的方法，从一个初始向量出发，按照一定的计算格式，构造一个向量的无穷序列，其极限是方程组的精确 解，只经过有限次运算得不到精确解。 大型稀疏矩阵的概念及其特点 稀疏矩阵的概念：所谓稀疏矩阵，是指矩阵中大多数元 素为零元素。而大型稀疏矩阵，顾名思义是指矩阵的阶数 很大的稀疏矩阵，比如阶数大于1O万甚至100万或更大。 大型稀疏矩阵的特点有： 1、如何存储，减少内存的占用量 2、如何根据矩阵本身特点选择可靠的解法，缩短计算 时间，同时使解具有一定的精度和稳定性。 稀疏矩阵的求解方法及优缺点 线性方程组的直接解法：高斯消去法，直接三角分解法 线性方程组的迭代解法：Jacobi迭代法，Gauss-Seidel迭代法，SOR 迭代法 高斯消去法：Gauss消去法是计算机上常用的解线性方程组的有效算法。此方法为消元过程和回代过程。消元过程是把原方程组化为上三角形方程组的过程，而回代过程是求解上三角形方程组的过程。 直接三角分解法：可以直接从矩阵A出发，利用矩阵的乘法实现A的LU分解。最后的解也是回求迭代求出。 稀疏矩阵的求解方法及优缺点 Jacobi迭代法：将n阶线性方程组： （其中，系数矩阵为n阶非奇异阵，且 ，i=1，2， ，n。） 建立迭代格式： 稀疏矩阵的求解方法及优缺点 给出一组初值 后，由迭代式反复迭代得到一个向量序 列 。如果 ，则 就是原线性方程组的真解。 Gauss-Seidel迭代法：是Jacobi的进一步优化的方法，当计算 时，总是 起用前面必威体育精装版计算出的 ，它们一般比 （j=1， 2，…. ，i-1）要精确。 SOR迭代法：它是GS迭代格式的一种加速方法，是解大型系数方程组的有效算 法之一。它引入了松弛因子w，使得改进后的迭代方案收敛速度得到加快。 当w1时称为超松弛迭代法，w1时称为低松弛迭代法，w=1时即为GS迭代法。 稀疏矩阵的求解方法及优缺点 各方法的优缺点： 高斯消去法与直接三角分解法：计算量大致相同，约为 乘除法运 算。三角分解的优越性在于：如果实现了A的三角分解A=LU，则解方程组Ax=b等 价于解方程组LUx=b。令Ux=y，则解Ax=b等价于解Ly=b，Ux=b。这是两个三角形 方程组，很容易求解。直接法精确性较高，对矩阵本身性质要求较低，所以适用 性比较广，但要防止舍入误差过大地影响结果，导致解的失真。 Jacobi迭代法，Gauss-Seidel迭代法，SOR迭代法：迭代法对矩阵的本身性质要 求比较高，但对于大型矩阵，由于计算机有效位数的限制，直接法中的误差，消 元中有效位数的损失等将会影响方程求解精度，所以这时迭代法比较适用。 2、软件的应用 本次使用的软件是我们组员共同用VB语言自己编写的程序，我负责的部分是Jacobi法，具体操作界面如下： 具体实例 主要针对100*100，200*200这两种实际矩阵进行五种算 法程序的运行，计算时间大体是： 100阶的，计算时间在1秒以内； 200阶的，计算时间在3秒左右。 对于阶数较高的矩阵，尤其是万阶以上的矩阵，本课题没有进行实际试算，主要原因