求解大规模矩阵问题的非准确方法和全局投影方法

结题报告

项目介绍

AI项目解读

基本信息

批准号：
11071140
项目类别：
面上项目
资助金额：
25.0万
负责人：
贾仲孝
依托单位：
清华大学
学科分类：
A0502.数值代数
结题年份：
2013
批准年份：
2010
项目状态：
已结题
起止时间：
2011-01-01 至2013-12-31

项目参与者：
李冰玉；段聪颖；李岑；张芡；吕慧；
关键词：
非准确方法预处理大规模特征问题收敛性全局投影方法

项目摘要

大规模矩阵计算是大规模数值计算的基础，特征问题和相关问题的数值方法的理论研究和算法开发存在很多挑战性问题，具有十分重要的理论意义和应用价值。该项目的研究内容包括：大规模线性和非线性特征问题及相关问题的多种数值方法理论研究和算法开发，重点是多个全局投影型方法和多种关于标准特征值问题和广义特征值问题的非准确数值方法的理论分析与算法开发，包括全局精化Arnoldi型方法的提出与分析，开发隐式重启算法，用不带预处理和调谐预处理的迭代法求解内迭代线性方程组时标准对称与非对称特征问题及广义特征问题的非准确Rayleigh商迭代的收敛性分析，非准确的位移求逆Arnoldi型方法、非准确的位移求逆精化Arnoldi型方法和对应的非准确隐式重启算法；对非准确数值方法中的内迭代线性方程组提出合理的调谐预处理；研究一般大规模线性方程组的稀疏近似逆预处理技术。在这些课题上进行突破，取得具有国际水平的研究成果。

结项摘要

（1）将求解标准特征问题的Rayleigh-Ritz方法和精化Rayleigh-Ritz方法扩展到周期矩阵特征问题，建立了方法具有普遍意义的收敛性理论。（2）建立了求解特征问题的全局Arnoldi方法的框架。对于重特征问题，当确定特征值的重数并计算对应的特征空间时，全局方法比标准方法有明显的优势。开发了实用的隐式重启全局Arnoldi算法。（3）对于反Hamilton/Hamilton结构矩阵对的特征值问题，提出了保结构的各向异性精化Arnoldi方法，开发了隐式重启算法。（4）当Rayleigh商迭代每步（外）迭代涉及的线性方程组近似求解时，得到非准确的Rayleigh商迭代。建立了它的收敛性理论。当线性方程组用最小残量法(MINRES)和Lanczos方法分别求解时，建立了其精度如何影响外迭代的收敛性一系列新结果，本质上改进了文献中结论。（5）建立了求解二次特征值问题的标准Rayleigh-Ritz方法和精化 Rayleigh-Ritz方法的具有普适性的收敛性理论。(6) 建立了非准确的残量Arnoldi方法和 Jacobi-Davidson方法的内迭代精度选取的具有普适性的理论，为开发实用鲁棒的算法提供了理论基础。（7）研究了大规模稀疏线性方程组的旨在具有普适性的稀疏近似逆预处理技术。Grote & Huckle提出的自适应SPAI方法和Jia & Zhu提出的幂稀疏近似逆（PSAI）的自适应预处理方法具有代表性。然而，如果系数矩阵非规则，即它至少有一列比较稠密，则SPAI和PSAI构造预处理子的代价必然很昂贵，而且SPAI构造的预处理子质量可能很差。利用Sherman-Morrison公式，我们将原来的非规则问题等价地转化成规则问题，然后用SPAI和PSAI快速构造预处理子，通过求解规则问题，最后还原得到原方程组的近似解。这种新的方法和直接求解非规则问题相比，计算效率大为提高。（8）在近似稀疏逆预处理方法中，一个根本性的问题是“舍弃阈值”准则的选取。我们研究了PSAI方法的阈值准则，建立了严格的理论，给出了具有普适性的有效阈值准则，并将这些结果扩展到一大类静态的近似稀疏逆预处理方法。这是稀疏近似逆预处理技术关于阈值准则选取的实质性突破工作。（9）建立了整体最小二乘问题的条件数的紧致上下界，这些界表达式比文献中的结果更精确，涉及的量更少，能更有效地计算。