毕业设计-算法的加速收敛现象分析-论文.doc

算法的加速收敛现象分析 摘要 随着科学和工程技术的发展，越来越多的问题需要求解大规模的线性方程组，对这类方程的快速求解已成为数值代数研究的热点之一，特别是具有稀疏结构的大型方程组的求解。基于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 目录 摘要 I Abstract II 第一章 引言 1 第二章 GMRES算法基础知识 3 §2.1 向量范数 3 §2.2 线性方程组最小二乘问