计算大规模矩阵部分奇异值分解的精化Lanczos型算法

摘要

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

目录

文摘

英文文摘

0引言

0.1问题的来源

0.2投影类方法

0.2.1正交投影方法

0.2.2斜投影方法

0.2.3精化投影方法

0.3本文的工作及有关的符号

1 理论基础

1.1传统投影方法的收敛性分析

1.2精化投影方法的收敛性

2一类特殊类型子空间上 Ritz对的性质及其应用

2.1引言

2.2主要结果

2.3重要应用

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

3.1引言

3.2对角化Lanczos过程及Lanczos算法

3.2.1对角化Lanczos过程

3.2.2双对角化Lanczos方法

3.3精化Lanczos算法

3.4隐式重新启动技术

3.5位移选取策略

3.6重新正交化

3.7数值实验

3.8总结

4上双对角化Lanczos方法及其精化版本

4.1引言

4.2 Lanczos双对角化过程及Lanczos算法

4.2.1双对角化Lanczos过程

4.2.2计算部分奇异值及其对应的左右奇异向量

4.3精化Lanczos算法

4.4隐式重新启动技术

4.5位移选取策略

4.6重新正交化

4.7上、下双对角化Lanczos方法的比较

4.8数值实验

5计算内部奇异组的隐式重新启动的调和双对角化Lanczos方法

5.1引言

5.2上双对角化Lanczos过程及调和双对角化Lanczos算法

5.2.1上双对角化Lanczos过程

5.2.2调和双对角化Lanczos方法

5.2.3调和双对角化Lanczos方法的收敛性分析

5.3隐式重新启动技术以及位移选取策略

5.4数值实验

5.5总结

6将来要解决的问题

6.1上、下双对角化Lanczos方法的精化版本的比较

6.2隐式重新启动的精化调和双对角化Lanczos方法

6.2.1精化调和近似奇异向量

6.2.2精化调和位移

参考文献

作者攻读博士期间完成论文

论文创新点摘要

致谢