预处理共轭梯度法求解线性方程组

  [摘 要]针对共轭梯度法求解线性方程组,提出一种预处理思想。基于次思想,首先给出预处理矩阵,然后求解预处理线性方程组,再使用共轭梯度法求解。最后通过几个数值试验,与直接使用共轭梯度法求解线性方程组相比较,本文的方法提高了收敛速度。   [关键词]线性方程组,预处理,共轭梯度法   中图分类号: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.   通讯作者:任国霞


相关内容

  • ch17-有约束最优化问题
  • 第17章 有约束最优化问题 17.1 线性规划 线性规划是处理线性目标函数和线性约束的一种较为成熟的方法,目前已经广泛应用于军事.经济.工业.农业.教育.商业和社会科学等许多方面. 线性规划的求解方法主要是单纯形法(Simple Method).该法由Dantzig 于1947年提出,以后经过多次改 ...

  • 有限元的弱形式
  • PDE 弱形式介绍 GJ :看到一个介绍COMSOL 解决物理问题弱形式的文档,感觉很牛啊,通过COMSOL Multiphysics 的弱形式用户界面来求解更多更复杂的问题,这绝对是物理研究的利器啊!而且貌似COMSOL 是唯一可以直接使用弱形式来求解问题的软件. 为什么要理解PDE 方程的弱形式 ...

  • COMSOL Multiphysics弱形式入门
  • COMSOL Multiphysics弱形式入门 物理问题的描述方式有三种: 1. 偏微分方程 2. 能量最小化形式 3. 弱形式 本文希望通过比较浅显的方式来讲解弱形式,使用户更有信心通过COMSOL Multiphysics 的弱形式用户界面来求解更多更复杂的问题.COMSOL Multiphy ...

  • 数值分析中牛顿迭代法的引入方法探讨
  • 第25卷第5期2010年lO月 天中学刊 JournalofTianzhong .,01.25No.5 oct.20lO 数值分析中牛顿迭代法的引入方法探讨 王霞,张启虎 (郑州轻工业学院数学与信息科学系,河南郑州450002) 摘要:数值分析中牛顿迭代法是求解非线性方程的基本方法.与一般教材上牛顿 ...

  • 叠前地震全波形反演实际应用的关键影响因素
  • ㊀ 第40卷第5期㊀ 2016年10月 GEOPHYSICAL&GEOCHEMICALEXPLORATION 物㊀ 探㊀ 与㊀ 化㊀ 探 Vol.40,No.5㊀Oct.,2016㊀ doi:10.11720/wtyht.2016.5.17 苗永康.叠前地震全波形反演实际应用的关键影响因素[ ...

  • 傅里叶变换在图像处理中的作用
  • 傅立叶变换在图像处理中的作用 (2011-05-21 20:01:34) 转载▼ 标签: 分类: 学习历程 杂谈 从现代数学的眼光来看,傅里叶变换是一种特殊的积分变换.它能将满足一定条件的某个函数表示成正弦基函数的线性组合或者积分.在不同的研究领域,傅里叶变换具有多种不同的变体形式,如连续傅里叶变换 ...

  • 中科大_盲信号处理_第5章2
  • 第五章 盲源抽取 第三.四章讨论的方法是通过批处理算法或自适应算法"一次性"地将所有的源信号分离出来,这种方式可以称为是"并行式的盲源分离". 本章要讨论的盲源抽取是将源信号一个一个地逐次提取出来,即一次只分离出一个源信号,而且每提取出的源信号都不同,或者每提 ...

  • 最优化基础理论与方法
  • 目录 1.最优化的概念与分类 ................................................................................................................. 2 2. 最优化问题的求解方法 ..... ...

  • 材料成型计算机模拟(纯手工打造)
  • 一.名词解释 1计算机模拟的概念:根据实际体系在计算机上进行模拟实验,通过将模拟结果与实际体系的实验数据进行比较,可以检验模型的准确性,也可以检验由模型导出的解析理论作为所作的简化近似是否成功.1 2材料设计是指(主要包含三个方面的含义):理论计算→预报→组分.结构和性能:理论设计→订做→新材料:按 ...