计算部分奇异值分解的隐式重新启动的双对角化Lanczos方法和精化的双对角化Lanczos方法  

IMPLICITLY RESTARTING THE LANCZOS METHOD AND THE REFINED LANCZOS METHOD FOR COMPUTING A PARTIAL SINGULAR VALUE DECOMPOSITION

作　　者：贾仲孝[1] 牛大田[2] 

机构地区：[1]清华大学数学科学系,北京100084 [2]大连理工大学应用数学系,大连116024

出　　处：《计算数学》2004年第1期13-24,共12页Mathematica Numerica Sinica

基　　金：国家重点基础研究专项基金(G19990328)资助项目.

摘　　要：The singular value decomposition problem is mathematically equivalent to the eigenproblem of an argumented matrix. Golub et al. give a bidiagonalization Lanczos method for computing a number of largest or smallest singular values and corresponding singular vertors, but the method may encounter some convergence problems. In this paper we analyse the convergence of the method and show why it may fail to converge. To correct this possible nonconvergence, we propose a refined bidiagonalization Lanczos method and apply the implicitly restarting technique to it, and we then present an implicitly restarted bidiagonalization Lanczos algorithm(IRBL) and an implicitly restarted refined bidiagonalization Lanczos algorithm (IRRBL). A new implicitly restarting scheme and a reliable and efficient algorithm for computing refined shifts are developed for this special structure eigenproblem.Theoretical analysis and numerical experiments show that IRRBL performs much better than IRBL.The singular value decomposition problem is mathematically equivalent to the eigenproblem of an argumented matrix. Golub et al. give a bidiagonalization Lanczos method for computing a number of largest or smallest singular values and corresponding singular vertors, but the method may encounter some convergence problems. In this paper we analyse the convergence of the method and show why it may fail to converge. To correct this possible nonconvergence, we propose a refined bidiagonalization Lanczos method and apply the implicitly restarting technique to it, and we then present an implicitly restarted bidiagonalization Lanczos algorithm (IRBL) and an implicitly restarted refined bidiagonalization Lanczos algorithm (IRRBL). A new implicitly restarting scheme and a reliable and efficient algorithm for computing refined shifts are developed for this special structure eigenproblem. Theoretical analysis and numerical experiments show that IRRBL performs much better than IRBL.

关 键 词：奇异值分解 双对角化 收敛性 增广矩阵 特征值 Lanczos法 隐式重新启动 

分 类 号：O19[理学—数学]