论文摘要
从20世纪60年代线性互补问题的提出到现在,尤其是最近20多年来,线性互补问题发展迅速。它被广泛地应用于工程、经济和运筹学中,对线性互补问题的研究可以分为理论和算法两个方面,前者主要研究问题解的存在性、唯一性、稳定性以及灵敏度分析等性质;后者集中研究如何构造有效算法及其理论分析。本文主要研究一种解线性互补问题的数值解法:广义加速超松弛算法。在本文中我们主要研究用广义加速超松弛迭代方法（简称为GAOR方法）来解线性互补问题LCP （ M,q）,其中M是一个n×n阶的非奇异矩阵, q∈Rn。在论文的第一部分,我们首先提出了一类解决线性互补问题的广义AOR方法,其特殊情况转化为广义的SOR方法。在第二部分中我们讨论了所提出的两种算法的收敛性,对于GAOR方法给出了下面的结论:当系数矩阵M = ( mkj )∈Rn×n是对角元素均为正数的H ?矩阵,且分裂M = D+L+U满足时,若α∈R+,其中J = D-1（L+U）,则对任一初始向量z0∈Rn,由GAOR方法产生的迭代序列{ zp}收敛于LCP （ M,q）的唯一解z*∈Rn,并且满足:当0 <α≤1时,当α≥1时。作为GAOR方法的特殊情况,我们也得到了GSOR方法的收敛性质,而由于一个M -矩阵也是一个H -矩阵,所以上面的结论也适用于M -矩阵,而且对角元素均为正的严格或不可约对角占优矩阵也满足结论的条件,则上述结果对这些矩阵也成立。第三部分中我们主要考虑两种算法的单调收敛性质,我们得到了这样的结论:当M∈Rn×n是L ?矩阵,且当0 <ωi≤1,i=1,2,n,0<α≤1时,则对任一初始向量z 0∈?,由GAOR方法或GSOR方法产生的迭代序列{ zp },p=0,1,2,有下面的两个性质:（1） 0≤z p +1≤zp≤z0;（2） lim zpz*p→∞=,其中z *是LCP （ M,q）的唯一解。在这一部分中我们还讨论了参数ωi , i=1,2,n和参数α对GAOR方法和GSOR方法的收敛速度的影响,得出了当参数ω1 =ω2=ωn =α=1时能导致更快的收敛速度,这也意味着导致两种方法收敛速度最快的参数可能在[1 ,∞)中,也即在最后一部分中,我们用一个数值例子来验证第三部分所得出的结论,也即当各个参数越接近于1时,由GAOR方法所产生的迭代序列收敛于所求线性互补问题的精确解所需的迭代次数就越少,也就是说收敛速度越快。