【作者】 牛大田；

【导师】 贾仲孝；

【作者基本信息】 大连理工大学 ， 计算数学， 2003， 博士

【摘要】 本文研究大规模矩阵奇异值问题的Lanczos类算法、算法的收敛性以及算法的重新启动等问题，全文共分六章。 引言部分介绍大规模矩阵奇异值问题的来源、解决此类问题的基本方法以及本学科的发展状况，最后介绍本文的工作。 第一章给出了投影类方法收敛性分析方面已有的重要结果，表明传统投影类方法存在着近似特征值收敛而近似奇异值可能不收敛的严重隐患，而贾提出的精化投影方法则可以克服这一隐患。只要近似特征值收敛，则对应的精化近似特征向量必然收敛。 第二章研究了增广矩阵在一类特殊子空间上Ritz对的性质，证明投影后的特征问题可以通过计算阶数降低一半的小规模奇异值问题来求解。这一性质可以用于双对角化Lanczos方法以及计算隐式重新启动的精化双对角化Lanczos方法中的精化位移，从而显著地节省存储量和计算量。 第三章研究了计算部分最大(或最小)奇异组的隐式重新启动的下双对角化Lanczos方法，分析了其收敛性，指出这一方法存在着近似奇异值收敛而近似奇异向量可能不收敛的隐患。为克服这一隐患，借鉴贾的精化策略，本章做了两方面的工作：第一，用精化近似奇异向量代替Ritz近似奇异向量来作为待求奇异向量的近似，并证明，只要对应的近似奇异值收敛，则精化近似奇异向量必然收敛；第二，用可以廉价、可靠地得到的精化位移来代替准确位移，并从理论上证明精化位移要优于准确位移。理论和数值实验都表明，改进后的隐式重新启动的精化下双对角化Lanczos方法要明显优于隐式重新启动的下双对角化Lanczos方法。 第四章研究了计算部分奇异值分解的上双对角化Lanczos方法，并给出了其精化版本，并做了收敛性分析，理论和数值实验都表明，精化版本明显优越，最后还就上双对角化Lanczos方法以及下双对角化Lanczos方法做了初步的比较。 第五章研究了计算内部奇异值问题的调和双对角化Lanczos方法，分析了其收敛性，结果表明，第一，调和Ritz值收敛，但严重依赖目标点的选择，用调和Ritz近似奇异向量的Rayleigh商来代替调和Ritz值则可以消除这一依赖性；第二，只要某调和Ritz值与其它调和Ritz值分隔的比较开，则对应的调和Ritz近似奇异向量收敛。借鉴Morgan的调和位移策略，本章还给出了隐式重新启动的位移策略，仍称之为调和位移。最后的数值实验表明，带调和位移的隐式重新启动的调和双对角化Lanczos方法可以用于求解内部奇异值问题。 第六章就未完成的工作做了一下总结，主要包括：一、细致分析精化上、下双对角化Lanczos方法的差别，以便选择合适的投影策略；第二，就调和双对角化Lanczos方法收敛性方面存在的隐患，引入精化策略，用新的近似奇异向量，称之为精化调和近似奇异向量，来代替调和近似奇异向量，以及如何利用精化调和近似奇异向量的信息来构造新的位移，使算法收敛更快更准确。更多还原

【Abstract】 This thesis presents some algorithms for large scale singular value problems and investigates their convergence and restart issues. It consists of six chapters.First we introduces the background of large scale singular value problems and basic numerical algorithms and the state of this subject. Finally, we describe the work of this thesis.Chapter One gives the main results of projection methods and shows that classic projection methods have convergence problem, that is, approximate eigenvectors may fail to converge. Instead refined projection methods proposed by Jia can overcome this problem.In Chapter Two, we study some properties of the Ritz pairs of an argumented matrix with respect to a kind of special subspaces. It is proved that the projected eigenproblem can be reduced to a half dimensional singular value problem. As an important application, this equivalence allows one to compute a partial SVD of a large scale matrix and refined shifts for use within an implicitly restarted refined bidiagonalization Lanczos algorithm (IRRBL), so that the computational cost and the storage requirement can be saved significantly.In Chapter Three we investigates the lower bidiagonalization Lanczos method and show that the method may encounter some convergence problems. We analyze the convergence of the method, showing why it may converge erratically and even may fail to converge. To correct this possible nonconvergence and improve the method, we propose a refined bidiagonalization Lanczos method and apply the implicitly restarting technique due to Sorensen to the method. We then develop an implicitly restarted refined bidiagonalization Lanczos algorithm (IRRBL). We propose a new selection of shifts for use within IRRBL, called refined shifts, and present a reliable and efficient algorithm for computing the refined shifts. Numerical experiments show that IRRBL can perform better than the implicitly restarted bidiagonalization Lanczos algorithm (IRBL) proposed by LarsenIn Chapter Four, we discuss the upper bidiagonalization Lanczos method and its refined version, analyze their convergence and compare the upper and lower bidiagonalization Lanczos methods.In Chapter Five we investigate the harmonic bidiagonalization Lanczos algorithm for computing interior singular values and analyze its convergence. Theoretical analysis shows that harmonic Ritz values converge, and harmonic approximate singular vectors also converge if the desired harmonic Ritz values are well separated from other harmonic Ritz values. A selection of shifts, called harmonic shifts, is proposed. Numerical results comfirm the efficency of the new algorithm.In Chapter Six we are devoted to some future work. The first is how to compare the refined upper and lower bidiagonalization Lanczos method. The second is how to apply the refined idea to the harmonic bidiagonalization Lanczos method to correct its deficiency.更多还原