论文部分内容阅读
本文针对由离散时间马尔科夫链产生的线性代数系统和一般线性代数系统的数值求解问题，深入研究其迭代、加速和预处理等求解方法，并将这些新方法应用到网页排序问题求解中。 研究了利用广义极小残量法求解大规模线性代数系统的问题，通过引入向量外推法改进迭代循环时的初值，达到加速的效果。然后研究了马尔科夫链问题求解的外推加速极小残量法。数值实验验证了加速算法能提高广义极小残量法的鲁棒性，并在计算时间和迭代次数等方面具有明显的加速效果。 研究了马尔科夫链问题求解的代数多重网格法。鉴于在插值算子、限制算子和各层迭代矩阵的构造所需时间不可小觑，本文引入外推加速策略，通过对最细层的加速，改进了各层循环的初值，数值效果好。之后将这种新的加速的代数多重网格法用于网页排序问题求解，数值实验和比较结果验证了所提出的新算法具有比传统的网页排序算法更好的性能。 研究了网页排序算法转化为线性代数系统求解的问题。针对阻尼因子接近1时重启的GMRES方法可能在该迭代系统中出现不收敛或崩溃的情形，提出了多项式右预处理策略，并给出了改进的新算法。随后，提出并证明了新算法的收敛性定理。另外，在预处理基础上进行了混合策略的加速并给出了相应算法。数值实验部分，首先验证了预处理技术能显著改善系数矩阵特征值的分布，同时从求解所需迭代次数、CPU时间等方面验证了预处理技术改进了算法的收敛性，提高了收敛速度。 针对经典PageRank算法缺憾–平均分配权威值导致的搜索网页排序质量下降和可能引起的商业投机行为及网页作弊问题，本文提出了三种改进策略将网页的权威值按不同权重分配给它所外链接的网页，然后给出了基于链接的加权网页排序新算法，最后通过数值实验对新算法的有效性进行了验证。 研究了线性代数系统的预处理问题，包括交替迭代和新型预处理子等的Gauss-Seidel预处理方法。从理论角度分析了预处理在改进收敛性方面的效果，数值实验进行了验证。