GMRES算法的加速收敛现象分析论文.docx

摘要随着科学和工程技术的发展，越来越多的问题需要求解大规模的线性方程 组，对这类方程的快速求解已成为数值代数研究的热点之一， 特别是具有稀疏结构的大型方程组的求解基于 Galerkin原理的Arnoldi算法是求解这种线性代 数方程组的近似算法，以下称这种方法为广义极小残余算法 (GMRES算法)GMRES方法是目前求解大型稀疏非对称线性方程组最为流行的一种迭代方法 GMRES算法在迭代过程中通常表现出一种加速收敛行为， 随着迭代次数的增加，这种加速收敛现象越明显，即残量收敛会随着迭代步数的增加而逐渐得到改善在 CG方法中，这种加速收敛与 Ritz值有密切关系通过分析，我们发现 GMRES的加速收敛与其斜投影过程中产生的 Ritz值对特征值的逼近程度有关系在实际应用中，为了减少存储量和计算量， 我们通常使用GMRES算法的重新开始版本来求解大型非对称线性方程组本文描绘了 GMRES和GMRES(m)的加速收敛现象，并通过实验给予解释关键字： 广义最小残量； Krylov子空间； Ritz值； 加速收敛； 正交投影方法； 非对称线性方程组On The Superlinear Convergence of GMRESAbstractproject technology, more andystems. This solution is one,especiall y for the bigupon the principle of Galerkin ,With the development of science and more questions need the solution of big linear s of the fastest ways for researching numerical algebra sparse matrix. The way of Arnoldi is based which is closed to the solution of the linear numerical system. Here, we callthe solution as Generalized Minimum Residual (GMRES). GMRES is one ofthe most popular iterative methods for the so lution of big nonsingular nonsymmetric linear systems. It usuall y has a so -called superlinear convergence behavior. The rate of convergence seems to improve as the iteration proceeds. For another say, the rate of residual variable will be improved as we in crease its iteration. For the conjugate gradients method,this method has been related to a degree of convergence of the Ritz value.Through some analysis, we found that for GMRES too, changes in convergence behavior seem to be related to the convergence of Ritz value.In our practical application, we also usuall y use GMRES(m) for reducingstorage and counter solving big linear systems. This paper studies thesuperlinear convergence behavior of GMRES and GMRES(m), and suppliesexplain through experiment.convergence;Keyword : GMRES; Krylov subspace; Ritz value; superlinearymmetric linear systemorthogonalization method; nons目录摘要 IABSTRACT II第一章引言 1第二章 GMRES算法基础知识 3§2.1 向量范数 3§2.2 线性方程组最小二乘问题 4§2.2.1 Gram -Schmidt 正交化方法 4§2.2.2 Givens 变换 4第三章 GMRES算法理论 6§3.1 Krylov 子空间方法的基本理论 6§3.2 Arnold:算法 7§3.3 GMRES算法结构 8第四章GMRES算法的加速收敛现象分析 9第五章数值示例与算法实现 19§5.1 数值实验 19§5.2 算法改进与实现 22§5.2.1 预处理技术 22§5.2.2算法实现 24§5.3 实验总结 34致谢 35参考文献 36REPORT OF LITERATURE 37文献报告 41iii第一章引言关于线性方程组的数值解法一般分为两大类：直接法和迭代法。

直接法是在没有舍入误差的情况下， 通过有限步四则运算可以求得方程组精确解的方法但是，在实际计算时，由于初始数据变为机器数而产生的误差以及 计算过程所产生的舍入误差等都对解的精确度产生影响， 因此直接法实际上也只能算出方程组真解的近似值直接法的基本思想是将结构上比较复杂的原始方程 组，通过等价变换化成结构简单的方程组，使之变成易于求解的形式，然后再通 过求解结构简单的方程组来得到原始方程组的解即Ax - b 0 Gx - dG通常是对角矩阵、三角矩阵或者是一些结构简单的矩阵目前较实用的直 接法是Gauss消去法的一些变形，例如选主元的Gauss消去法和矩阵的三角分解 法，它们都是目前计算机上常用的有效方法迭代法就是对任意给定的初始近似解向量 x（0），按照某种方法逐步生成近似解序列x（0）, x（1,）x（2）..., xk（）,,.使极限limx（k）- x*为方程组的解，即 Ax（*）- b因此 k T3迭代法是用某种极限过程去逐步逼近真解的方法， 从而也可以用有限步运算出具 有指定精确度的近似解迭代法主要有 Jacobi迭代法、Gauss-Seidel迭代法、 逐次超松弛法以及共轭斜量法。

直接法的优点是计算量小，并且可以事先估计，缺点是所需存储单元较多， 编写程序复杂；迭代法的优点是原始系数矩阵始终不变，因而算法简单，编写程 序也比较方便，且所需存储单元也较少，缺点是只有近似解序列收敛时才能被采 用，而且存在收敛性和收敛速度的问题对于中等规模的 n阶（n<100）线性方程组，由于直接法的准确性和可靠性，所以它们是经常被采用的方法对于较高阶 的方程组，特别是对某些偏微分方程离散化后得到的大型稀疏方程组 （系数矩阵中绝大多数为零元素），由于直接解法的计算代价较高，使得迭代更具竞争力随着大规模并行计算机的快速发展， 现在可以计算的规模越来越大， 这些计算多数来源于偏微分方程离散后得到的大型稀疏线性方程组 因此，大型稀疏线性代数方程组的求解已成为数值算法研究的热点问题 在许多应用学科和工程领域中，如流体力学、结构力学、航空航天工程、电子工程等等，经常会遇到大型稀疏非对称线性方程组问题目前求解这类问题最流行的算法便是GMRES算法GMRES(m)算法本文主要分析GMRES算法的加速收敛现象和重新开始版本的 的加速收敛现象第二章 GMRES算法基础知识§ 2.1向量范数为了研究迭代法的收敛性，我们需要对n维向量和n阶方阵引进某种度量 一 向量范数的概念。

向量范数是三维 Euclid空间向量长度概念的推广，向量范数在数值分析中起着极其重要的作用设R(n为实n维向量空间，C(n为复n维向量空间我们记 ")为R(n)或C(n， K为实数域R或复数域C若K(n)上任一向量X，对应一个非负实数11 X II，对于 X，Y e "及g K，满足如下条件：非负性：II X II >0，且IIX I= 0的充要条件是X = 0 ；齐次性：II 以X I= I以 IIIX II•；三角不等式:11X + Y陌X II + IIYIIO则称11 X "为向量X的范数(上述三个条件称为向量范数公理)常用的向量范数有(1)1范数II X II =乎 I x |i=1 ；(2)2范数e 2 1II X II =(才 I X 1)2i=1 ；(3) s范数II X II = max I x I* 1

其解亦称为方程组 AX = b的最小二乘解现在介绍两种在GMRES算法中用到的正交变换方法，Gram-Schmidt正交化 方法、Givens变换§ 2.2.1 Gram-Schmidt 正交化方法设％，%••…,七是n维空间中n个线性无关的向量，则P =a /IIa II1 1 1 2P2 = P2/IIP2II2p，= p 711 P '1128〃 =a "芝 1(«^, p j )p j,j=1这时P1，%，•••，Pn是n个正交基向量fII a II (a , P ) (a , P )…(a , P ))1 2 2 1 3 1 n 1(a ,a ,.....,a ) = (p , p ,•••, P )12 12II P 'II (a , P ) ••• (a , P )2 2 3 2 n 2II 叩I2 ...(气,P3)( IIP 'II )n2=QR这时Q是正交矩阵，R是上三角矩阵Schmidt正交化过程就是将矩阵 A分解为正交矩阵与上三角矩阵的乘积A = QR即A的QR分解§ 2.2.2 Givens 变换欲把一个向量中许多分量化为零， 可以用Householder变换；如果只将其中一个分量化为零，则采用Givens旋转得到Hk的QR分解。