论文部分内容阅读
在应用研究中,很多问题的数值求解涉及线性方程组Ax=b的求解问题,其中系数矩阵A有Toeplitz结构或分块Toeplitz结构.如卷积型积分方程的求解,图像去模糊等.近三十年来,这类线性方程组的预处理共轭梯度法(Preconditioned Conjugate Gradient Method,简记为PCG)的研究一直是研究热点.对于这类线性方程组, PCG方法的最大优点是在一定的条件下,该方法的计算量仅为O(n log n),其中n是未知量的个数. 本文研究有Toeplitz结构的线性方程组的快速求解方法及在求解积分方程中的应用.除了介绍这类线性方程组的求解方法的研究背景和一些相关知识外,本文主要由下列三个部分组成. 我们首先考虑块-Toeplitz-Toeplitz-块(Block-Toeplitz-Toeplitz-Block,简记为BTTB)线性方程组的预处理共轭梯度法.我们提出几种新的预处理矩阵,包括基于广义杰克逊核的块-循环-循环-块(Block-Circulant-Circulant-Block,简记为BCCB)预处理矩阵、基于循环-反循环分解的BTTB预处理矩阵以及基于矩阵嵌入的BTTB预处理矩阵.这些预处理矩阵推广了Chan, Yip和Ng[18,19], Chan和Ng[14]提出的Toeplitz线性方程组的预处理矩阵.我们还比较详细地介绍了这些预处理矩阵计算机实现的细节.数值例子说明基于嵌入的BTTB预处理矩阵在多数情况下效果最好. 接着,我们研究一类卷积型积分方程—Love方程的数值解法.我们用复合高斯-勒让德求积公式对Love方程进行离散化,并对未知量进行适当的排序,再对离散方程组作适当的处理,使得最终的系数矩阵对称,且具有分块Toeplitz结构.这样,我们可以应用预处理共轭梯度法有效地求解所得的线性方程组.根据系数矩阵的结构特征,我们选择了分块循环矩阵作为预处理矩阵. 最后,我们考虑带状Toeplitz矩阵的快速求行列式和求逆的问题.我们利用带状Toeplitz矩阵的生成函数的分解构造了新的快速算法并仔细分析算法的计算复杂性.我们还给出了关于带状对称Toeplitz矩阵的逆的一个重要性质(该性质由Noutsos和Vassalos首次提出[54])的一个比较简明的证明.我们的算法的计算次数略多于由Lv, Huang和Le提出的的算法[50],但我们的算法更稳定.数值例子也充分地说明这一点.