求解大型非对称线性方程组的不完全广义最小向后扰动法

An Incomplete Generalized Minimum Backward Perturbation Algorithm for Large Nonsymmetric Linear Systems

本文给出了求解大型非对称线性方程组的广义最小向后扰动法(GMBACK)的截断版本——不完全广义最小向后扰动法(IGMBACK).该方法基于Krylov向量的不完全正交化,从而在Krylov子空间上求出一个近似的或者拟最小向后扰动解.本文对新算法IGMBACK做了一些理论研究,包括算法的有限终止、解的存在性和唯一性等方面的研究;且给出了IGMBACK的执行.数值实验表明:IGMBACK通常比GMBACK和广义最小残量法(GMRES)更有效;且IGMBACK和GMBACK经常比GMRES收敛得更好.特殊地,如果系数矩阵是敏感矩阵,且方程组右侧的向量平行于系数矩阵的最小奇异值对应的左奇异向量时,重新开始的GMRES不一定收敛,而IGMBACK和GMBACK一般收敛,且比GMRES收敛得更好.

This paper gives the truncated version of the generalized minimum backward error algorithm （GMBACK）--the incomplete generalized minimum backward perturbation al- gorithm （IGMBACK） for large nonsymmetric linear systems. It is based on an incomplete orthogonalization of the Krylov vectors in question, and gives an approximate or quasi-minimum backward perturbation solution over the Krylov subspace. Theoretical properties of IGMBACK including finite termination, existence and uniqueness are discussed in details, and practical im- plementation issues associated with the IGMBACK algorithm are considered. Numerical experiments show that, the IGMBACK method is usually more efficient than GMBACK and GMRES, and IGMBACK, GMBACK often have better convergence performance than GMRES. Specially, for sensitive matrices and right-hand sides being parallel to the left singular vectors corresponding to the smallest singular values of the coefficient matrices, GMRES does not necessarily converge, and IGMBACK, GMBACK usually converge and outperform GMRES.