论文部分内容阅读
“互补问题”作为一类新的数学模型,是由美国的著名运筹学家R.W Cottle在1964年提出的,它是指这样的问题:它包含的两组决策变量之间满足一种“互补关系”.而线性互补问题中的两组决策变量之间除了满足“互补关系”外,还具有线性函数关系.互补问题被提出后,经过几十年的研究,很快在工程技术中得到了重要应用,许多文献讨论了它在力学、交通、经济、金融以及控制等许多领域的广泛应用.研究关于这类问题的快速迭代方法,是一项具有重要的理论意义和很高的实用价值的课题.
矩阵分裂类迭代方法是求解线性互补问题的一类常用的有效迭代方法,这类方法主要来源于线性方程组的矩阵分裂迭代算法,具有形式简单,运算方便以及便于进行数值分析等特点.同时,我们又可以充分利用系数矩阵本身的结构特点来构造不同的矩阵分裂,以提高对应的矩阵分裂迭代方法的计算效率.
本文主要针对几类不同的线性互补问题,根据每类问题中系数矩阵的结构特点,提出了几种有效的迭代方法,包括特殊的矩阵分裂类迭代方法,牛顿类迭代方法以及模迭代方法.在此基础上,为进一步提高这些方法的计算效率,我们又结合矩阵分裂的技巧,讨论了这些方法分别对应的不精确矩阵分裂迭代格式,同时,这些不精确迭代过程也为一般的矩阵分裂迭代方法提供了很好的实现方式.
我们首先针对非退化线性互补问题,提出了一种改进的阻尼牛顿迭代方法.这一方法在迭代过程中,需要避免出现关于线性互补问题退化的迭代向量.为此,我们在每一牛顿迭代步,采取一种新的步长选择策略,使得改进后的方法得以整体收敛,而且每一收敛点都是线性互补问题的一个解.在此基础上,我们又提出了一种一般的不精确矩阵分裂迭代方法,以及内迭代过程采用改进的阻尼牛顿方法时对应的不精确分裂迭代过程,其中,我们给出了一种新的内迭代停止标准,这一标准具有形式简单且便于实现等优点,同时也保证了整个不精确迭代过程的收敛性.最后,我们又给出了相关的数值试验,试验结果充分说明了我们的改进与分析是可行和有效的.
其次,对于非对称正定矩阵或者非对称半正定矩阵所对应的线性互补问题,传统的矩阵分裂类迭代方法,例如投影SOR方法等,一般不再有效.为此,我们构造了一种特殊的矩阵分裂迭代方法,即对称/反对称分裂迭代方法,并且通过引入一参数因子,使得分裂后的线性互补子问题是可解的.我们给出了方法的可行性和收敛性分析.同时,通过调整参数因子的取值,每一迭代步对应的线性互补子问题又能利用已有的迭代方法进行近似求解,为此,我们又讨论了这一方法的不精确分裂迭代格式.相应的数值算例验证了我们所做分析的正确性,同时也说明了我们的方法是可行和有效的.
再次,针对求解线性互补问题的矩阵多重分裂迭代方法,我们又给出了实现这一方法的不精确迭代格式.在每一迭代步,我们用已知的迭代方法来近似求解一定数量的线性互补子问题,用得到的近似解来代替精确解进行随后的迭代过程,从而使得矩阵多重分裂方法得以更好的实现.同时,我们又给出了两种具体的不精确多重分裂迭代格式,即二级多重分裂迭代法和多分裂—阻尼牛顿迭代方法,我们分析了系数矩阵为H+矩阵时这两种具体迭代过程的收敛性.另外,我们又讨论了当系数矩阵为对称矩阵时二级多重分裂迭代法的收敛性.所有的这些不精确迭代过程,都为矩阵多重分裂方法提供了很好的具体实现方式.
最后,针对对称正定矩阵对应的线性互补问题,以及传统的模迭代方法运算过程的特点,我们在原来的模迭代方法的迭代过程中引入一参数因子,亦称为移位因子,对原来的迭代过程做一改进和推广.通过对改进方法的收敛性以及最优参数的分析,可以看出我们的改进能更好的促进整个迭代序列的收敛,因此是合理和必要的,最后的数值试验也表明了这一点.在此基础上,为得到更有效的求解,我们又给出了其不精确迭代格式,以及两种具体的不精确模迭代方法.这些不精确迭代过程,充分利用了线性方程组的快速迭代方法,使得迭代过程中对应的线性方程组的精确求解过程被近似求解所代替,从而提高了整个迭代过程的计算效率.最后的数值试验也充分说明了我们的改进与分析是合理且有效的.