目录
摘要 I
ABSTRACT 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 ARNOLDI算法 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
参考文献 36
REPORT OF LITERATURE 37
文献报告 41

摘要
随着科学和工程技术的发展，越来越多的问题需要求解大规模的线性方程组，对这类方程的快速求解已成为数值代数研究的热点之一，特别是具有稀疏结构的大型方程组的求解。基于Galerkin原理的Arnoldi算法是求解这种线性代数方程组的近似算法，以下称这种方法为广义极小残余算法(GMRES算法)。GMRES方法是目前求解大型稀疏非对称线性方程组最为流行的一种迭代方法。GMRES算法在迭代过程中通常表现出一种加速收敛行为，随着迭代次数的增加，这种加速收敛现象越明显，即残量收敛会随着迭代步数的增加而逐渐得到改善。在CG方法中，这种加速收敛与Ritz值有密切关系。通过分析，我们发现GMRES的加速收敛与其斜投影过程中产生的Ritz值对特征值的逼近程度有关系。在实际应用中，为了减少存储量和计算量，我们通常使用GMRES算法的重新开始版本来求解大型非对称线性方程组。本文描绘了GMRES和GMRES(m)的加速收敛现象，并通过实验给予解释。

关键字： 广义最小残量； Krylov子空间； Ritz值； 加速收敛； 正交投影方法； 非对称线性方程组

On The Superlinear Convergence of GMRES
Abstract
With the development of science and project technology, more and more questions need the solution of big linear /systems. This solution is one of the fastest ways for researching numerical algebra, especially for the big sparse /matrix. The way of Arnoldi is based upon the principle of Galerkin, which is closed to the solution of the linear numerical /system. Here, we call the solution as Generalized Minimum Residual (GMRES). GMRES is one of the most popular iterative methods for the solution of big nonsingular nonsymmetric linear /systems. It usually 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 increase 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 usually use GMRES(m) for reducing storage and counter solving big linear /systems. This paper studies the superlinear convergence behavior of GMRES and GMRES(m), and supplies explain through /experiment.

Keyword: GMRES; Krylov subspace; Ritz value; superlinear convergence; orthogonalization method; nonsymmetric linear system