网页排序的子空间算法和随机Kaczmarz算法及其应用

发布时间：2022-10-20 18:09

　　线性方程组的求解问题一直是国内外研究的重要领域.现代许多科学计算与工程应用问题往往需要求解大型稀疏线性方程组,实际应用问题的复杂性往往导致最终所得到的线性方程组不仅会出现维数比较高的情况,而且得到的系数矩阵的形式和性质也会各不相同.本文主要研究网页排序的PageRank问题和用随机Kaczmarz方法求解大型稀疏线性方程组的数值算法问题,并将改进的随机Kaczmarz重构算法应用到压缩感知信号重构的计算问题中.所做工作的内容具体概括如下:1.在网络排序PageRank问题中,当阻尼因子α接近于1时,现存的数值算法的收敛速度往往会变慢.针对这种情况,作者做了两方面的研究工作.第一方面,作者利用深度重启的Arnldi过程和多步分裂迭代方法,给出了一种预处理的多步分裂迭代算法,并对其收敛性给出了分析和证明,同时给出了相关的数值算例.第二方面,在利用Arnoldi过程计算PageRank问题时,作者发现当阻尼因子α充分接近于1时,收敛的残差曲线会出现不规则的跳动甚至不收敛的情况,通过分析原因,作者提出了 GMRES-Power方法.给出的数值实验验证了理论分析的结果,并表明该算法的数值有效性.... 

【文章页数】：139 页

【学位级别】：博士

【文章目录】：
摘要
ABSTRACT
第一章 绪论
    1.1 应用背景和意义
    1.2 问题研究现状
        1.2.1 PageRank问题
        1.2.2 线性方程组的随机算法
        1.2.3 压缩感知问题
    1.3 本文的主要工作和安排
        1.3.1 本文研究工作的创新点
        1.3.2 本文的章节安排
第二章 基于幂法求解PageRank问题的几种方法
    2.1 幂法求解PageRank问题
    2.2 内外迭代法求解PageRank问题
    2.3 基于幂法的两步分裂矩阵迭代方法
    2.4 两步分裂矩阵迭代算法的收敛性
    2.5 基于内外迭代法的两阶段矩阵分裂法求解PageRank问题
    2.6 数值实验
第三章 基于Arnoldi过程的多步分裂迭代算法求解PageRank问题
    3.1 Arnoldi过程
    3.2 深度重启的Arnoldi算法
    3.3 MSPI迭代方法求解PageRank问题
    3.4 预处理的MSPI迭代算法
    3.5 预处理的MSPI算法的收敛性分析
    3.6 数值实验
第四章 基于Krylov子空间GMRES-Power算法求解PageRank问题
    4.1 求解PageRank问题的GMRES方法
    4.2 重启的GMRES算法
    4.3 GMRES-Power算法
    4.4 GMRES-Power算法的收敛性分析
    4.5 数值实验
第五章 求解线性方程组的随机Kaczmarz方法
    5.1 Kaczmarz算法
    5.2 Randomized Kaczmarz算法
    5.3 贪婪Randomized Kaczmarz算法
    5.4 多步贪婪Randomized Kaczmarz算法
    5.5 多步贪婪Randomized Kaczmarz算法的收敛性分析
    5.6 数值实验
第六章 改进的松弛随机Kaczmarz算法
    6.1 松弛随机Kaczmarz算法
    6.2 自适应多步松弛贪心随机Kaczmarz算法
    6.3 自适应多步松弛贪心随机Kaczmarz算法收敛性分析
    6.4 数值实验
第七章 随机Kaczmarz算法在压缩感知中的应用
    7.1 压缩感知简要过程
        7.1.1 信号的稀疏表示
        7.1.2 测量矩阵的设计
        7.1.3 信号恢复的重构算法
    7.2 信号恢复稀疏解的Kaczmarz重构算法
        7.2.1 随机稀疏化的Kaczmarz算法
        7.2.2 自适应多步松弛贪婪的随机稀疏化Kaczmarz算法
    7.3 数值实验
第八章 总结和展望
参考文献
攻读博士学位期间完成的工作
致谢


【参考文献】：
博士论文
[1]基于先验信息的压缩感知重建算法研究[D]. 李志霖.北京邮电大学 2017
[2]广义鞍点问题和PageRank问题的若干预处理技术[D]. 董永新.上海大学 2017
[3]非对称鞍点问题的松弛型预处理子[D]. 张居丽.上海大学 2016
[4]两类线性方程组的预处理技术及数值求解方法[D]. 张科.上海大学 2014



本文编号：3695050