本文关注如何利用数值方法高效求解马尔科夫链(Markov chain)问题以及网页排序(PageRank)问题所对应的线性系统。研究了求解马尔科夫链问题的自适应聚合多重网格(adaptive aggregation multigrid)法和一些改进的技术策略,同时研究了网页排序问题的特殊结构和性质并基于此提出了几个数值方法以提高这类问题的求解效率。研究内容与成果可以归纳如下。1.研究了求解马尔科夫链问题的自适应聚合多重网格法以及它的平滑化形式。这类算法网格算子的构建基于将节点划分为聚合块的过程,因此具体执行该过程的聚合算法对迭代求解的效率有重要的影响。然而常用的基于邻点聚合法(Neighbourhood-Based aggregation)在实际应用中可能生成不合适的聚合块,以至于降低了迭代求解的效率。为改善此问题,本文分析了基于邻点聚合法设计上的弊端,提出了改进的方法。数值实验表明,改进的基于邻点聚合法能稳定地生成更合适的聚合块从而提高了自适应聚合多重网格法求解马尔科夫链的效率。2.自适应聚合多重网格法在每个迭代步都重新执行聚合过程以更新聚合块,这保证了粗层矫正的效果并提高了迭代过程的收敛速度,然而同时也带来了较大的单步迭代计算量。针对这个问题,本文分析了该类多重网格法中聚合块的生成机制并提出了一种动态更新聚合块的策略。理论分析和数值实验表明,应用该策略能在不影响此类多重网格法收敛行为的情况下大幅减少其中聚合过程的执行次数,从而显著降低该类方法求解马尔科夫链所需的时间。3.分析了自适应聚合多重网格法中聚合块的特性,展示了该类算法各层中的聚合块信息可用于将该层的概率方程转化为近似块对角占优的分块线性系统。基于此,结合Schwarz方法的相关理论构建了一种分块松弛方案以取代上述多重网格法中的逐点松弛方案来提高松弛过程的效率。分析得出了该分块松弛方案在求解马尔科夫链背景下的聚合多重网格法各层中的可执行性和收敛性。另外,网页排序问题也可表述为求解马尔科夫链线性系统,但此时系数矩阵通常是完全稠密的。针对此情况,本文给出了一些计算技巧使得所提出的分块松弛方案在求解稠密网页排序系统时避免直接计算有关稠密矩阵的操作。数值实验验证了上述基于聚合块的分块松弛方案对加速求解马尔科夫链问题和网页排序问题的有效性。4.研究了网页链接图的结构特征以及网页排序问题中转移概率矩阵的数值性质。基于这些研究结果提出了一种消元算法。该算法通过对比转移概率矩阵里各行的稀疏结构来选取一系列初等行变换以降低网页排序系统的稠密度。同时也分析得出了该算法对于改变网页排序系统特征值分布的效果。数值实验表明,该消元算法能有效地将网页排序问题转化为求解一个更简单的线性系统。5.基于上述对网页排序问题转移概率矩阵的研究,进一步导出了网页排序问题系数矩阵的特殊性质。基于此,提出了一套低秩分解方案结合一种矩阵分块算法将上述系数矩阵转化为分块形式然后对它的非对角部分进行压缩,得到了分块矩阵的低秩分解表达式。然后提出了一种基于这个低秩分解表达式的预处理子。证明了该预处理子的可执行性并分析了其对于加速迭代求解过程的效果。数值实验展示了这一整套预处理方案对于加速求解网页排序问题的有效性。