线性互补问题的不精确分裂迭代方法

来源 :中国科学院数学与系统科学研究院 | 被引量 : 0次 | 上传用户:shiguanghuai
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
“互补问题”作为一类新的数学模型,是由美国的著名运筹学家R.W Cottle在1964年提出的,它是指这样的问题:它包含的两组决策变量之间满足一种“互补关系”.而线性互补问题中的两组决策变量之间除了满足“互补关系”外,还具有线性函数关系.互补问题被提出后,经过几十年的研究,很快在工程技术中得到了重要应用,许多文献讨论了它在力学、交通、经济、金融以及控制等许多领域的广泛应用.研究关于这类问题的快速迭代方法,是一项具有重要的理论意义和很高的实用价值的课题.   矩阵分裂类迭代方法是求解线性互补问题的一类常用的有效迭代方法,这类方法主要来源于线性方程组的矩阵分裂迭代算法,具有形式简单,运算方便以及便于进行数值分析等特点.同时,我们又可以充分利用系数矩阵本身的结构特点来构造不同的矩阵分裂,以提高对应的矩阵分裂迭代方法的计算效率.   本文主要针对几类不同的线性互补问题,根据每类问题中系数矩阵的结构特点,提出了几种有效的迭代方法,包括特殊的矩阵分裂类迭代方法,牛顿类迭代方法以及模迭代方法.在此基础上,为进一步提高这些方法的计算效率,我们又结合矩阵分裂的技巧,讨论了这些方法分别对应的不精确矩阵分裂迭代格式,同时,这些不精确迭代过程也为一般的矩阵分裂迭代方法提供了很好的实现方式.   我们首先针对非退化线性互补问题,提出了一种改进的阻尼牛顿迭代方法.这一方法在迭代过程中,需要避免出现关于线性互补问题退化的迭代向量.为此,我们在每一牛顿迭代步,采取一种新的步长选择策略,使得改进后的方法得以整体收敛,而且每一收敛点都是线性互补问题的一个解.在此基础上,我们又提出了一种一般的不精确矩阵分裂迭代方法,以及内迭代过程采用改进的阻尼牛顿方法时对应的不精确分裂迭代过程,其中,我们给出了一种新的内迭代停止标准,这一标准具有形式简单且便于实现等优点,同时也保证了整个不精确迭代过程的收敛性.最后,我们又给出了相关的数值试验,试验结果充分说明了我们的改进与分析是可行和有效的.   其次,对于非对称正定矩阵或者非对称半正定矩阵所对应的线性互补问题,传统的矩阵分裂类迭代方法,例如投影SOR方法等,一般不再有效.为此,我们构造了一种特殊的矩阵分裂迭代方法,即对称/反对称分裂迭代方法,并且通过引入一参数因子,使得分裂后的线性互补子问题是可解的.我们给出了方法的可行性和收敛性分析.同时,通过调整参数因子的取值,每一迭代步对应的线性互补子问题又能利用已有的迭代方法进行近似求解,为此,我们又讨论了这一方法的不精确分裂迭代格式.相应的数值算例验证了我们所做分析的正确性,同时也说明了我们的方法是可行和有效的.   再次,针对求解线性互补问题的矩阵多重分裂迭代方法,我们又给出了实现这一方法的不精确迭代格式.在每一迭代步,我们用已知的迭代方法来近似求解一定数量的线性互补子问题,用得到的近似解来代替精确解进行随后的迭代过程,从而使得矩阵多重分裂方法得以更好的实现.同时,我们又给出了两种具体的不精确多重分裂迭代格式,即二级多重分裂迭代法和多分裂—阻尼牛顿迭代方法,我们分析了系数矩阵为H+矩阵时这两种具体迭代过程的收敛性.另外,我们又讨论了当系数矩阵为对称矩阵时二级多重分裂迭代法的收敛性.所有的这些不精确迭代过程,都为矩阵多重分裂方法提供了很好的具体实现方式.   最后,针对对称正定矩阵对应的线性互补问题,以及传统的模迭代方法运算过程的特点,我们在原来的模迭代方法的迭代过程中引入一参数因子,亦称为移位因子,对原来的迭代过程做一改进和推广.通过对改进方法的收敛性以及最优参数的分析,可以看出我们的改进能更好的促进整个迭代序列的收敛,因此是合理和必要的,最后的数值试验也表明了这一点.在此基础上,为得到更有效的求解,我们又给出了其不精确迭代格式,以及两种具体的不精确模迭代方法.这些不精确迭代过程,充分利用了线性方程组的快速迭代方法,使得迭代过程中对应的线性方程组的精确求解过程被近似求解所代替,从而提高了整个迭代过程的计算效率.最后的数值试验也充分说明了我们的改进与分析是合理且有效的.
其他文献
学位
本文提出了简约代数群G中一类特殊一维环面构成的根系。初衷在于证明如下结果:如果半单代数群G的正则环面S对应的Weyl群NG(S)/CG(S)是极大的,那么S必然是极大环面(参见定理1.6)
学位
单峰函数是指在其定义区间上只有一个极值点的函数。无论是在实际应用或是在理论研究中,这类函数都有着举足轻重的地位.例如许多数学、物理问题都可以表示为多峰函数的形式,而多
本文通过两种不同的方法,对多孔介质一类Binkman-Forchheimer双向扩散流方程分别在Dirichlet和Neumann边界两种不同条件下结构稳定性进行了研究。首先求得了Binkman-Forchheim
本文主要研究具有平坦度量的orbifold以及与之相对应的有理函数,解释这样的有理函数的Julia集都有光滑的流形结构。另外介绍了Kahn关于Mandelbrot集连通性的一个完全拓扑的证
学位
职业院校是我国高等职业教育的重要组成部分,为国家和社会培养高素质高技能人才,高职院校的教师不光是理论和技能的传输者,同时也是一线技能专家,在培养人才的过程当中,职业
中铁四局施工队伍分布在全国20多个省、市、自治区及蒙古、委内瑞拉等多个国家,点多线长,高度分散,工期短快,流动频繁,给党员集中教育带来了许多困难。同时,信息传播渠道的多
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
班主任的班级管理工作直接关系到学校教育工作的质量,对其管理策略展开探讨十分必要.本文指出了当前高中班主任班级管理工作中存在的问题,并针对这些问题,提出了高中班主任做
本文主要讨论以下两部分内容:   一、射影几何中有理不变量的重要性和应用;   二、外余代数即Grassmann余代数的性质与应用。   考虑这两个问题的主要动机来自于以下
学位