论文部分内容阅读
[摘 要]针对共轭梯度法求解线性方程组，提出一种预处理思想。基于次思想，首先给出预处理矩阵，然后求解预处理线性方程组，再使用共轭梯度法求解。最后通过几个数值试验，与直接使用共轭梯度法求解线性方程组相比较，本文的方法提高了收敛速度。
[关键词]线性方程组，预处理，共轭梯度法
中图分类号：E911 文献标识码：A 文章编号：1009-914X（2014）30-0020-01
1.引言
线性方程组是线性代数的核心内容之一，其解法研究是代数学中经典且重要的研究课题。线性方程组的直接解法有消元法，克拉默法则，直接三角形法，平方根法，追赶法等。线性方程组的直接解法是最早出现的求解方法，但是由于直接解法的存储量和计算量一般很大，所以迭代法在近年来越来越受到重视。迭代法[1]有Jacobi迭代法，Gauss-Seidel迭代法，JGS迭代法，SOR迭代法，参数迭代法等。而对于求解大型线性方程组以共轭梯度法和变形共轭梯度法为主，其具有存储量少，计算量少等优点。共轭梯度法是最基本的Krylov子空间方法。共轭梯度法的收敛速度与系数矩阵的条件数紧密相关，条件数愈小，收敛性愈好，该算法可以在很少的几步就会获得高精度的近似解。但当系数矩阵的条件数很大时，收敛速度就很慢。于是出现了预处理共轭梯度法[3]（简称PCG法），它是通过适当的预处理方法引入预处理矩阵，使矩阵的特征值分布更为集中，降低矩阵条件数，以达到提高收敛速度的目的。
本文针对对称正定系数矩阵的线性方程组提出了一种预处理解决方案，为了降低求解预条件矩阵方程的计算复杂度，选取特殊的预处理矩阵。预处理矩阵方程在求解过程中既更简洁，又能有效的改变了原矩阵方程的条件数。
2.预处理方法
若为预条件矩阵且是对称正定矩阵，线性方程组可转化为
（2.1）
只要使的条件数小于，则采用共轭梯度法求解矩阵方程（2.1）的速度将得到提高。这里选取预条件矩阵使尽量接近矩阵的等价标准形，采用迭代算法计算的近似矩阵，这里选取为对阵矩阵。本文采用Jacobi迭代算法求解，Jacobi迭代算法收敛的充分条件为系数矩阵为严格对角占优。设，，则（2.1）转化为
（2.2）
针对（2.2）进行共轭梯度算法如下：
1）任意给定初始量，置，计算
，
2） 若，或者而， 则停止；否则，计算
3） 计算
4） 置，转第2步。
3.数值算例与结果分析
下面给出两个算例，分别用共轭梯度法，预处理共轭梯度法求解线性方程组，最后得出两种算法的计算时间与迭代次数。
例1 用求解线性方程组，，，其中
，，
终止准则，计算结果比较见表1。
例2 用求解线性方程组，，，其中
，。终止准则，计算结果比较见表2。
结果分析
当系数矩阵是对称正定时，使用预处理共轭梯度法（CG）迭代次数比共轭梯度法（MCG）少，这说明本文迭代算法优于传统的迭代算法。
4 结束语
本文主要内容是共轭梯度法求解线性方程组。首先通过构造预处理矩阵，来降低求解线性方程组的复杂度，再通过本文的几个算例结果与直接使用共轭梯度法求解矩阵方程相比较，我们得出结论，当系数矩阵为对称正定时，在一般情况下，本文算法提高了运算效率。
参考文献
[1] 张凯院，徐仲.数值代数（第2版修订本）[M].北京：科学出版社，2010.
[2] 张永杰，孙秦.预处理矩阵及其构造方法[J].长春：长春理工大学学报，2006，29（04）：128-130.
[3] 胡家赣.解线性代数方程组的迭代解法[M].北京：科学出版社，1999：173-201.
通讯作者：任国霞
[关键词]线性方程组，预处理，共轭梯度法
中图分类号：E911 文献标识码：A 文章编号：1009-914X（2014）30-0020-01
1.引言
线性方程组是线性代数的核心内容之一，其解法研究是代数学中经典且重要的研究课题。线性方程组的直接解法有消元法，克拉默法则，直接三角形法，平方根法，追赶法等。线性方程组的直接解法是最早出现的求解方法，但是由于直接解法的存储量和计算量一般很大，所以迭代法在近年来越来越受到重视。迭代法[1]有Jacobi迭代法，Gauss-Seidel迭代法，JGS迭代法，SOR迭代法，参数迭代法等。而对于求解大型线性方程组以共轭梯度法和变形共轭梯度法为主，其具有存储量少，计算量少等优点。共轭梯度法是最基本的Krylov子空间方法。共轭梯度法的收敛速度与系数矩阵的条件数紧密相关，条件数愈小，收敛性愈好，该算法可以在很少的几步就会获得高精度的近似解。但当系数矩阵的条件数很大时，收敛速度就很慢。于是出现了预处理共轭梯度法[3]（简称PCG法），它是通过适当的预处理方法引入预处理矩阵，使矩阵的特征值分布更为集中，降低矩阵条件数，以达到提高收敛速度的目的。
本文针对对称正定系数矩阵的线性方程组提出了一种预处理解决方案，为了降低求解预条件矩阵方程的计算复杂度，选取特殊的预处理矩阵。预处理矩阵方程在求解过程中既更简洁，又能有效的改变了原矩阵方程的条件数。
2.预处理方法
若为预条件矩阵且是对称正定矩阵，线性方程组可转化为
（2.1）
只要使的条件数小于，则采用共轭梯度法求解矩阵方程（2.1）的速度将得到提高。这里选取预条件矩阵使尽量接近矩阵的等价标准形，采用迭代算法计算的近似矩阵，这里选取为对阵矩阵。本文采用Jacobi迭代算法求解，Jacobi迭代算法收敛的充分条件为系数矩阵为严格对角占优。设，，则（2.1）转化为
（2.2）
针对（2.2）进行共轭梯度算法如下：
1）任意给定初始量，置，计算
，
2） 若，或者而， 则停止；否则，计算
3） 计算
4） 置，转第2步。
3.数值算例与结果分析
下面给出两个算例，分别用共轭梯度法，预处理共轭梯度法求解线性方程组，最后得出两种算法的计算时间与迭代次数。
例1 用求解线性方程组，，，其中
，，
终止准则，计算结果比较见表1。
例2 用求解线性方程组，，，其中
，。终止准则，计算结果比较见表2。
结果分析
当系数矩阵是对称正定时，使用预处理共轭梯度法（CG）迭代次数比共轭梯度法（MCG）少，这说明本文迭代算法优于传统的迭代算法。
4 结束语
本文主要内容是共轭梯度法求解线性方程组。首先通过构造预处理矩阵，来降低求解线性方程组的复杂度，再通过本文的几个算例结果与直接使用共轭梯度法求解矩阵方程相比较，我们得出结论，当系数矩阵为对称正定时，在一般情况下，本文算法提高了运算效率。
参考文献
[1] 张凯院，徐仲.数值代数（第2版修订本）[M].北京：科学出版社，2010.
[2] 张永杰，孙秦.预处理矩阵及其构造方法[J].长春：长春理工大学学报，2006，29（04）：128-130.
[3] 胡家赣.解线性代数方程组的迭代解法[M].北京：科学出版社，1999：173-201.
通讯作者：任国霞