【作者】 张兰；

【导师】 雷秀仁；

【作者基本信息】 华南理工大学 ， 计算数学， 2010， 硕士

【摘要】 大型稀疏线性方程组的求解是对自然科学和社会科学中许多问题进行数值模拟的关键技术之一。而GMRES算法是目前求解大型稀疏非对称线性方程组最为有效的迭代算法之一。在执行整体的GMRES算法时,所需的计算量和存储量会随着迭代步数的增加而变得不可接受。为了克服这一困难,可以使用重新开始策略或混合迭代策略。最近,重新开始GMRES算法在迭代过程中表现出的补足收敛性质引起了人们的兴趣。特别地,基于这一性质所提出的积混合GMRES算法能够显著改善混合迭代策略求解方程组的效率。积混合GMRES算法在执行过程中,需要首先计算出多次迭代GMRES迭代循环的残量多项式,然后重复使用这些多项式的乘积进行Richardson迭代。然而,当迭代循环的步长较大时,计算出的残量多项式可能是不稳定的,从而导致Richardson迭代的发散。为了提高积混合GMRES算法的稳定性以及收敛速率,本文提出了多项式预处理积混合广义极小剩余算法。首先,本文介绍了求解大型稀疏矩阵的预处理Krylov子空间方法的原理以及在此基础上发展起来的各种迭代法,包括共轭梯度法,广义极小剩余法。其次,本文重点介绍了在重新开始GMRES循环的残量多项式在矩阵的谱上收敛的互补性以及在此基础了得到的积混合广义极小剩余算法,构造出了多项式预处理矩阵,并将该矩阵作为积混合广义极小剩余算法的预处理矩阵,改善其系数矩阵谱的性质,提高了该算法的收敛速率和稳定性。最后,本文对预处理后的新算法做了数值实验模拟与分析,将新算法与经典的成熟算法进行了对比,结果均表明,新算法更适合大型稀疏矩阵问题的求解,在计算量和存储量方面都有相应的改进。求解大型稀疏矩阵的积混合广义极小剩余算法得到了进一步的改善。更多还原

【Abstract】 The solving of large sparse linear systems is one of the most important technologies for carrying out numerical simulation to many of the problems in natural and social sciences,and GMRES is one of the most popular algorithms for solving large nonsymmetrical linear systems. Unfortunately, the computational cost of full GMRES usually becomes unacceptable as the iteration number increases. To overcome the difficulty, restarting scheme or hybrid scheme of GMRES can be employed. Recently, the complementary behavior of restarted GMRES has attracted a wide interest. In particular, based on the study of complementary behavior,a product hybrid GMRES algorithm has been proposed, which improves the efficiency of hybrid scheme significantly.To implement the product hybrid GMRES algorithm ,a couple of GMRES polynomials are constructed, and then the product of the polynomials are used repeatedly via a Richardson iteration.However, if the restarting frequency is not small,the GMRES polynomials may undergo a great instability. In consequence, the Richardson iteration may diverge. Polynomial preconditioned hybrid generalized minimal residual algorithm is proposed to accelerate its convergence rate and improve its stability.Firstly, the principle of Krylov methods for solving large sparse linear systems is introduced. Then, GMRES algorithm and CG algorithm are introduced, which are based on the principle of Krylov methods.Secondly, we discuss the complementary behavior of restarted GMRES and the product hybrid GMRES algorithm which is based on the study of complementary behavior.Then, calculating the polynomial preconditioned matrix, and using it as preconditioned matrix for the product hybrid GMRES algorithm to improving spectral nature of the coefficient, accelerating its convergence rate and improving its stability.This paper gives some numerical experiments simulation and analysis for new preconditioned methods with classical algorithm of mature. The results show that the new algorithms is more suitable for large sparse matrix linear systems,computing and storage has a corresponding improvement. The product hybrid GMRES algorithm for solving large sparse matrix have been further improved.更多还原