带BTTB矩阵线性互补问题的块预处理模系矩阵分裂迭代方法

吴敏华， 李郴良

(桂林电子科技大学 数学与计算科学学院，广西 桂林 541004)

弹塑性接触模型根据力学现象可以转化为线性互补问题，接触面经离散后的系数矩阵往往非常大且具有Toeplitz结构。Zhao等[1]利用多重网格求解，将多重网格方法嵌套到有效集，提出了完全多重网格方法。Vollebregt[2]基于共轭梯度法和快速傅里叶变换，提出了BCCG+FAI方法，同时给出了一个新的预处理算子。Bai[3]将线性互补问题转化为不动点问题，将矩阵适当分裂，提出了更具一般性的模系矩阵分裂迭代方法。Bai等[4]还利用并行技术，提出了模系矩阵多分裂方法。1986年Strang[5]引入循环矩阵作为预优共轭梯度法的预处理矩阵来求解Toeplitz系统Tx=b，从此，基于预优共轭梯度法的Toeplitz迭代解法在过去的几十年里有了飞速发展[6-8]。

用模系矩阵迭代方法求解大型线性互补问题十分高效。为此，将预优共轭梯度法和模系矩阵迭代方法结合，利用系数矩阵是正定的二级对称BTTB矩阵的优点，构造BCCB块预处理算子[8]，用共轭梯度法求解线性互补问题。

1 预备知识

对于线性互补问题，求一对可行的互补解w,z∈Rn，使

w=Tz+q≥0,z≥0,zTw=0，

(1)

其中T∈Rn×n为对称正定的矩阵，q=(q1,q2,…,qn)T∈Rn。

引理1[9]对给定的线性互补问题(1)和标量α>0，若αI+T是非奇异的，则线性互补问题(1)与

(αI+T)x=(αI-T)|x|-q

(2)

的不动点问题等价，求x∈Rn的方程(2)。

1)若x是方程(2)的解，则

w=α(|x|-x),z=|x|+x

是问题(1)的解。

2)若向量w、z是问题(1)的解，则x=(z-α-1w)/2是不动点方程(2)的解。

若对角线元素tij=ti-j，则矩阵Tn=(tij)n×n∈Rn×n称为Toeplitz矩阵。一个m×m块Toeplitz矩阵

且每块T(k)(k=0,±1,…,±(m-1))均是n×n的Toeplitz矩阵，则称为BTTB矩阵。若每块都是对称的，则称为二级对称BTTB矩阵。若元素满足v-k=vn-k，1≤k≤n-1，则矩阵V∈Rn×n为循环矩阵，

一个m×m块的块循环矩阵，若每块均为n×n的循环矩阵，则称为BCCB矩阵。

2 块预处理算子Cmn

其中0≤j≤m-1，0≤k≤n-1。

方法1

1)置k=0，取x0∈Rmn。

2)共轭梯度法计算

Pmn(αImn+Tmn)xk+1=Pmnbk，

(3)

其中Pmn=Cmn(Tmn)，bk=(αImn-Tmn)|xk|-q，k=0,1,2,…。

3)计算zk+1=|xk+1|+xk+1，wk+1=Tzk+1+q。

Pmn(αImn+Tmn)x=Pmn(αImn-Tmn)|x|-q。

(4)

将式(4)减式(3)得，

Pmn(αImn+Tmn)(x*-xk+1)=

Pmn(αImn-Tmn)(|x*|-|xk|)，

等价于

(x*-xk+1)=[Pmn(αImn+Tmn)]-1×

[Pmn(αImn-Tmn)]×

(|x*|-|xk|)=(αImn+Tmn)-1×

(αImn-Tmn)(|x*|-|xk|)，

(5)

则

‖x*-xk+1‖≤‖(αImn+Tmn)-1×

(αImn-Tmn)‖‖x*-xk‖。

3 数值实验

方法1的实验中，利用2个方面的数据验证实验效果：1)方法的迭代步数；2)CPU的运行时间t。记

e(zk)=min(|(zk+1，wk+1|)，

另x0=(0,0,…,0)T∈Rnm，b=(1,1,…,1)T，迭代终止条件为e(zk)<10-7。

例1系数矩阵对角线元素[7]为

为了验证方法1的实验效果，方法1式(3)中令Pmn=Imn，即未预处理，与使用块预处理算子Cmn的实验数据进行对比。实验结果如表1、2所示。

表1 例1在α=1时方法1的实验结果

表2 例1在α=1.36时方法1的实验结果

为了进一步验证方法1的实验效果，方法1式(3)中令Pmn=Imn，即未预处理，与使用块预处理算子Cmn的实验数据进行对比。实验结果如表3、4所示。

表3 例2在α=1时方法1的实验结果

表4 例2在α=2时方法1的实验结果

为了进一步验证方法1的实验效果，方法1式(3)中令Pmn=Imn，即未预处理，与使用块预处理算子Cmn的实验数据进行对比。实验结果如表5、6所示。

表5 例3在α=1时方法1的实验结果

表6 例3在α=2时方法1的实验结果

例4生成函数f(x)=cos3x+1，系数矩阵对角线元素[10]为

为了进一步验证方法1的实验效果，方法1式(3)中令Pmn=Imn，即未预处理，与使用块预处理算子Cmn的实验数据进行对比。实验结果如表7、8所示。

表7 例4在α=1时方法1的实验结果

从表1～8可看出，无论是否使用块预处理算子，迭代步数都相同，这也可从定理1的证明过程中看出预处理矩阵的使用不影响收敛速度。但使用预处理矩阵的计算时间比未使用预处理矩阵的短，这是因为在方法1中利用了BCCB块预处理算子，减少了方法1式(3)即内迭代相应的运行时间，提高了算法整体的运行效率。

表8 例4在α=1.49时方法1的实验结果

4 结束语

为快速求解基于正定的二级对称BTTB矩阵的线性互补问题，利用模系矩阵迭代方法，结合预优共轭梯度法，采用文献[8]给出的块处理算子构造预处理矩阵，提出了求解带BTTB矩阵的线性互补问题的块预处理模系矩阵迭代方法，实验结果表明该方法是可行有效的。