论文部分内容阅读
鞍点线性系统是一类对称不定的线性系统，它来源于鞍点型偏微分方程问题、最优化问题、最小二乘问题等研究领域．实际应用中导出的这类系统通常都是大规模的，并且系数矩阵具有稀疏性，因此应采用迭代法进行求解．然而，鞍点线性系统本身特殊的结构特点使得一些著名的算法，诸如逐次超松弛迭代法(SOR)或共轭梯度法(CG)均失去效力．因此寻求解决大稀疏鞍点线性系统的有效的迭代解法具有重要的现实意义． 目前为人们所熟知的Uzawa算法和MINRES算法是两类求解鞍点线性系统的有效方法．Uzawa算法格式简单，但收敛速度较慢．MINRES算法计算效率高，但计算格式比较复杂．寻求具有更简单的计算格式或者更快收敛速度的迭代算法，成为热门的研究课题． 经典的SOR算法同样具有格式简单、存储量小的特点，因而早为人们所关注．近年来有学者开始研究广义化的SOR算法来求解鞍点线性系统．李长军等学者于1998年首次提出了一种广义化的SOR算法：GSOR算法．Golub等学者于2001年提出了SOR-like算法．这两种算法本质相同，因此我们将其统称为广义化SOR方法．这类算法具有同Uzawa算法一样简单的计算格式，并带有一个预优矩阵． 本文首先对SOR-like算法重新进行了深入的研究，采用比较初等的方法详细地刻划了SOR-like算法迭代矩阵谱半径的基本特征；给出了SOR-like算法最优迭代参数以及迭代矩阵谱半径的显式表达式；进一步证明了，通过选取合适的预优矩阵，可以使SOR-like算法的迭代矩阵只含有实特征值，从而可以采用Chebyshev多项式加速．这一结果是令人振奋的，丰富了D．M．Young的超松弛理论；同时我们还更正了Golub在2001年关于SOR-like算法的收敛性分析中出现的错误． 基于对SOR-like算法的理论分析，我们深入研究采用Chebyshev多项式对SOR-like算法进行加速，从而给出了GSOR-SI算法．理论分析和数值计算表明，这一算法具有和SOR-like算法相近的计算开销，却拥有比SOR-like算法快得多的收敛速度． 针对鞍点线性系统的特有的结构特点，我们提出两种含有两个迭代参数的广义化SOR算法，即GAOR算法和TPGSOR算法．给出了TPGSOR算法的最优参数的显式表达式以及相应的最优迭代矩阵谱半径的显式表达式．TPGSOR算法的计算格