《2022年2022年关于线性方程组的迭代法求解》由会员分享,可在线阅读,更多相关《2022年2022年关于线性方程组的迭代法求解(7页珍藏版)》请在金锄头文库上搜索。
1、关于线性方程组的迭代法求解摘要线性方程组的数值求解常见于许多科学与工程计算领域。介绍了求解大型线性方程组的主要迭代算法,对一些经典迭代法(Jacobi法、GaussSeidel法、SOR法、SSOR法和CG法等)进行了详细的讨论,并从理论上对收敛性进行分析。关键词迭代法线性方程组共轭梯度法Iterative Methods for Solving the Linear Systems Zhu Jun (Department of Mathematics Chaohu Colledge, Anhui Chaohu) Abstract Numerical methods for linear sy
2、stems are very important in many areas.Several iterative methods for solving the large linear systems are presented. Same classical iterative methods such as Jacobi,Gauss-Seidel, SOR,SSOR,and CG iterative method are discussed from the iterative formulas and convergence. key words iterative methods l
3、inear systems conjugate gradien talgorithm 在科学研究和大型工程设计中出现了越来越多的数学问题,而这些问题往往需要求数值解。在进行数值求解时,经离散后,常常归纳名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 7 页 - - - - - - - - - 为求解形如Axb的大型线性方程组。 20世纪50年代至70年代,由于电子计算机的发展, 人们开始考虑和研究在计算机上用迭代法求线性方程组Axb的近似解,用某中极限过程去逐渐逼近精确解
4、,并发展了许多非常有效的迭代方法, 迭代法具有需要计算机存储单元少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点。例如Jacobi法、GaussSeidel法、SOR法、SSOR法,这几种迭代法是最常见的一阶线性定常迭代法。大量偏微分方程的离散形式是大规模线性代数方程组。其数值计算是科学工程计算的核心, 占有绝大部分的总体运算时间,解大规模稀疏线性方程组的krylov子空间方法显示出与众不同的有效性。当矩阵是对称正定时,常用的方法是具有短递推的共轭梯度法(CG) 。系数矩阵不对称时,常用的方法中有完全正交法(FOM)和广义最小残量方法(GMRES) 。还有很多迭代法正在被人们发现和研究
5、,新的有效的方法层出不穷,其中基于大型稀疏非Hermitian的正定阵的系数矩阵的Hermitian和Skew Hermitian分裂的HSS方法,HSS方法等具有非常好的实用性。但是没有一种算法是通用的, 对于具体问题必须根据所得到的线性方程组和算法的特点进行选择。一 经典迭代法概述20实际50年代至70年代,人们开始考虑和研究用迭代法求解线性方程组Axb(1)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 7 页 - - - - - - - - - 的近似解,发展了许
6、多有效的方法, 其中有Jacobi法、GaussSeidel法、SOR法、SSOR法,这几种迭代法均属一阶线性定常迭代法,即若系数矩阵 A的一个分裂 :AMN;M为可逆矩阵 ,线性方程组( 1)化为11()MN XbMXNXbXMNXMb得到迭代法的一般公式(1)()kkXHXd(2)其中:1HMN,1dMb. 对任意初始向量(0)X一阶定常迭代法收敛的充分必要条件是:迭代矩阵 H的谱半径小于 1,即()1H,又因为对于任何矩阵范数恒有()HH,故又可得到收敛的一个充分条件:1H。1 Jacobi迭代法若D为A的对角素构成的对角矩阵,且对角线元素全不为零 ,系数矩阵 A的一个分解: A=D(L
7、+U) ;这里D为A的对角素构成的对角矩阵, L为严格下三角阵, U为严格上三角矩阵。于是Jacobi迭代法公式的矩阵形式为定理1.1 若(某种向量范数导出的矩阵范数),则解 Ax=b的Jacobi迭代法收敛。定理1.2 设A为严格对角占优或不可约弱对角占优矩阵,则解Ax=b的Jacobi迭代法收敛2 Gauss Seidel迭代法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 7 页 - - - - - - - - - 对于非奇异方程组, 若D为A的对角素构成的对角矩阵
8、, 且对角线元素全不为零;系数矩阵A的一个分解定理 2.1 Gauss Seidel 法收敛的充要条件是其迭代矩阵的谱半径定理 2.2 若(某种向量范数导出的矩阵范数),则解 Ax=b的Gauss-Seidel 迭代法收敛。3 SOR(successive over relaxation)迭代法对于非奇异方程组 , 若D为A的对角素构成的对角矩阵, 且对对角线元素全不为零 , 系数矩阵 A的一个分解这里D为A的对角素构成的对角矩阵,L 为严格下三角阵 ,U为严格上三角阵。SOR 迭代法的矩阵形式为定理3.1 对任意的 A,设其对角元皆为零,则对所有实数,有推论如果解Ax=b的SOR 方法收敛,
9、则有定理3.2 设A,A对称正定,且,则解 Ax=b的SOR 法收敛。定理3.3 设A, A为对称阵,且对角元,若Ax=b的SOR 方法收敛,则A正定,且4 SSOR 迭代法 SSOR (synmertric successive over relaxation)迭代法的矩阵形式为三种迭代法的比较:(1)一般情况下, J法与GS法比较并无优劣,收敛情况与速名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 7 页 - - - - - - - - - 度均不一定。(2)但是,具
10、有相容次序的矩阵,在相同精度要求下,GS法比J法快一倍,而 SOR法的收敛速度可提高一个数量级。(3)若线性方程组系数A是严格对角占优或不可约对角占优矩阵,则1) J法和GS法都收敛2) 当0时,SOR 法收敛。二Krylov 子空间方法Krylov 子空间方法是解决大型线性方程组的一类十分有效的方法,其主要代表是对称正定线性方程组的共轭梯度法和非对称线性方程组的 GMRES方法。 20世纪50年代初期由 Hestenes 和Stiefel首先提出共轭梯度法(或简称 CG法) ,近20年来的有关研究取得了前所未有的发展,目前有关的方法和理论已经相互成熟,并且成为求解大型稀疏线性方程组十分有效的
11、一类方程。 5. 共轭梯度法( CG 方法)通过对经典迭代法的总结,发现SOR 迭代法在松弛因子取最优松弛因子的情况下,迭代收敛很快。但是, 计算还需要求得对应的 Jacobi迭代矩阵的谱半径,这常常比较困难的。考虑线性方程组 Ax=b (16) 的求解问题,其中 A是给定的 n阶对称正定阵, b是给定的 n维向量, x是待求的 n维向量。为此定义二次泛函名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 7 页 - - - - - - - - - 则可以证明求方程组( 16
12、)的解等价于二次泛函(17)的极小点。由此,给定了初始向量,按某一方向去求式(17)的极小值点,就得到下一个迭代值,再由出发,求等等。这样来逼近精确解。若取求最小值的方向为处的负梯度方向,就是所谓的最速下降法。然而理论和实际计算表明这个方法的收敛速度较慢,共轭梯度法则是在处的梯度方向和这一步的修正方向所构成的二维平面内,寻找使减少最快的方向作为下一步的修正方向,即求最小值的方向 (其第一步仍取负梯度方向)。计算公式为:再逐次计算从而,形成一共轭向量组,形成一正交向量组。后者说明若没有舍入误差的话,至少 n次迭代就可以得到线性方程组(16)的精确解。然而,在实际计算中一般都有舍入误差,所以并不是
13、真正相交,而等也只是逐步逼近式( 16)的真解,故我们将共轭梯度法作为迭代法来使用。 6. HSS迭代法。线性方程组(1) 求解的迭代法要求对系数矩阵A进行有效的分裂,例如 Jacobi 迭代法和 Gauss-Seidel 迭代法把系数矩阵A分裂为对角阵,严格上三角阵和严格下三角阵;对于线性方程组(1)若系数矩阵A为非 Hermit 矩阵,且为正定的。那么我们有Hermitaian( 简称 HS分裂)。由于, 所以A又有以下两种分裂名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6
14、页,共 7 页 - - - - - - - - - 为一给定正常数,基于式(19)的分裂,我们得到 HSS 迭代法的迭代公式:解线性方程组的迭代法是层出不穷的,但是没有一种是通用的,对于具体的问题必须根据所得到的线性方程组和算法的特点来进行选择。参考文献1. 许树方,高立数值线性代数,北京;北京大学出版社,2000. 2. 刘新国数值代数基础,青岛;青岛大学出版社,1996. 3. 李维国,黄炳家,刘新海等数值计算方法,北京;石油大学出版社, 2004. 4. 戴华求解大规模矩阵问题的 Krylov 子空间方法, 南京;南京航天航空大学出版社, 2001. 5. 李庆杨,王能超,易大义数值分析,武汉;华中科技大学出版社,2006. 6. 关治,陆金甫数值分析基础;高等教育出版名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 7 页 - - - - - - - - -