摘要
随着科学和工程技术的发展，越来越多的问题需要求解大规模的线性方程组，对这类方程的快速求解已成为数值代数研究的热点之一，特别是具有稀疏结构的大型方程组的求解。基于Galerkin原理的Arnoldi算法是求解这种线性代数方程组的近似算法，以下称这种方法为广义极小残余算法(GMRES算法)。GMRES 方法是目前求解大型稀疏非对称线性方程组最为流行的一种迭代方法。GMRES算法在迭代过程中通常表现出一种加速收敛行为，随着迭代次数的增加，这种加速收敛现象越明显，即残量收敛会随着迭代步数的增加而逐渐得到改善。在CG方法中，这种加速收敛与Ritz值有密切关系。通过分析，我们发现GMRES的加速收敛与其斜投影过程中产生的Ritz值对特征值的逼近程度有关系。在实际应用中，为了减少存储量和计算量，我们通常使用GMRES算法的重新开始版本来求解大型非对称线性方程组。本文描绘了GMRES和GMRES(m)的加速收敛现象，并通过实验给予解释。
关键字：广义最小残量；  Krylov子空间；  Ritz值；加速收敛；正交投影方法；非对称线性方程组
On The Superlinear Convergence of GMRES
Abstract
Wit h the d evelo p me nt o f science and p ro ject techno lo g y,mo re and mo re q uestio ns need the so
lut io n o f b ig linear syste ms. T h is so lut io n is o ne o f the fastest ways fo r researchin g nu mer ica l algeb ra,esp ecia lly fo r the b ig sparse matr ix. The way o f Arno ld i is b ased up o n the p rinc ip le o f Galerk in, wh ich is clo se d to the so lut io n o f the linear nu mer ica l system.Here, we call the so lut io n as Generalized Min imu m Res id ua l (GMRES).GMRES is o ne o f the mo st p op u lar iterat ive met ho d s fo r the so lut io n o f b ig no ns in gu lar no nsy mmetr ic linear syste ms.It us ua lly has    a so-called sup er linear co n vergence b ehav io r.The rate o f co nverge nce seems to imp ro ve as the iterat io n p ro ceed s.F o r ano ther say,the rate o f resid ua l var iab le w ill b e imp ro ved as we increase its iterat io n.F o r the co nju gate grad ie nts metho d, th is met ho d has b een related to a d egree o f co nverge nce o f t he Rit z va lue. Thro u g h so me ana lys is,we fo und that fo r GMRES to o, changes in co n vergence b ehav io r seem to be related to the co nverge nce o f R it z va lue. In o ur p ractica l app licat io n,we also usua lly use GMRES(m) fo r red uc in g sto rage and co unter so lv in g b ig linear systems.Th is p ap er stud ies the sup erlinear co nvergence b ehav io r o f GMRES and GMRES(m),and sup p lies exp la in thro u g h exp erimen t.
Key wo rd: GMRES; K ry lo v sub sp ace; R it z va lue; sup er linear co nverge nce;
o rtho go na lizat io n metho d; no nsy mmetr ic linear system
目录
摘要 ...................................................... I A B S T RA C T ................................................. I I 第一章引言.. (1)
第二章G M R E S算法基础知识 (3)
§2.1向量范数 (3)
§2.2线性方程组最小二乘问题 (4)
§2.2.1Gr a m-S ch m id t正交化方法 (4)
§2.2.2Gi v en s变换 (4)
第三章G M R E S算法理论 (6)
§3.1K RYLOV子空间方法的基本理论 (6)
§3.2A RNOLDI算法 (7)
§3.3G MR E S算法结构 (8)
正则化收敛速率第四章G M R E S算法的加速收敛现象分析 (9)
第五章数值示例与算法实现 (19)
§5.1数值实验 (19)
§5.2算法改进与实现 (22)
§5.2.1预处理技术 (22)
§5.2.2算法实现 (24)
§5.3实验总结 (34)
致谢 (35)
参考文献 (38)
R E P O RT OF LI T E RA T UR E (39)
文献报告 (43)
第一章  引言
关于线性方程组的数值解法一般分为两大类：直接法和迭代法。
直接法是在没有舍入误差的情况下，通过有限步四则运算可以求得方程组精确解的方法。但是，在实际计算时，由于初始数据变为机器数而产生的误差以及计算过程所产生的舍入误差等都对解的精确度产生影响，因此直接法实际上也只能算出方程组真解的近似值。直接法的基本思想是将结构上比较复杂的原始方程组，通过等价变换化成结构简单的方程组，使之变成易于求解的形式，然后再通过求解结构简单的方程组来得到原始方程组的解。即
Ax b Gx d =⇔=
G 通常是对角矩阵、三角矩阵或者是一些结构简单的矩阵。目前较实用的直接法是Gauss 消去法的一些变形，例如选主元的Gauss 消去法和矩阵的三角分解法，它们都是目前计算机上常用的有效方法。
迭代法就是对任意给定的初始近似解向量(0)x ，按照某种方法逐步生成近似解序列(0)(1)(2)(),,,.....,,...k x x x x ，使极限()lim k k x x *→∞
=为方程组的解，即()Ax b *=。因此迭代法是用某种极限过程去逐步逼近真解的方法，从而也可以用有限步运算出具有指定精确度的近似解。迭代法主要有Jacobi 迭代法、Gauss-Seidel 迭代法、逐次超松弛法以及共轭斜量法。
直接法的优点是计算量小，并且可以事先估计，缺点是所需存储单元较多，编写程序复杂；迭代法的优点是原始系数矩阵始终不变，因而算法简单，编写程序也比较方便，且所需存储单元也较少，缺点是只有近似解序列收敛时才能被采用，而且存在收敛性和收敛速度的问题。对于中等规模的n 阶(n<100)线性方程组，由于直接法的准确性和可靠性，所以它们是经常被采用的方法。对于较高阶的方程组，特别是对某些偏微分方程离散化后得到的大型稀疏方程组(系数矩阵中绝大多数为零元素)，由于直接解法的计算代价较高，使得迭代更具竞争力。
随着大规模并行计算机的快速发展，现在可以计算的规模越来越大，这些计算多数来源于偏微分方程离散后得到的大型稀疏线性方程组。因此，大型稀疏线性代数方程组的求解已成为数值算法研究的热点问题。在许多应用学科和工程领域中，如流体力学、结构力学、航空航天工程、电子工程等等，经常会遇到大型
稀疏非对称线性方程组问题。目前求解这类问题最流行的算法便是GMRES算法。
本文主要分析GMRES算法的加速收敛现象和重新开始版本的GMRES(m)算法的加速收敛现象。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。