求解線性互補問題的模系瀑布型多重網格方法

王　艷，李郴良

(桂林電子科技大學 數學與計算科學學院，廣西 桂林　541004)

求解線性互補問題的模系瀑布型多重網格方法

王艷，李郴良

(桂林電子科技大學 數學與計算科學學院，廣西 桂林541004)

摘要：為快速求解一類線性互補問題，提出了模系瀑布型多重網格方法。該方法利用模系矩陣分裂迭代法作為瀑布型多重網格方法的光滑子，得到了滿足要求的近似解。數值結果表明，該算法是有效的。

關鍵詞：線性互補問題；模系矩陣分裂；瀑布型多重網格方法

線性互補問題廣泛應用于工程物理、經濟、金融、控制與交通等領域[1]，對于線性互補問題的求解，Bai[2]提出了一類模系矩陣分裂迭代算法。該算法將線性互補問題變換為一類與它等價的不動點方程組進行迭代計算?；贐ai Zhongzhi等的研究，張麗麗總結了求解線性互補問題的模系矩陣分裂迭代算法以及算法的松弛迭代模型[3]。

多重網格方法對于求解大規模問題是非常有效的。Zhao等[4]結合有效集算法和套迭代技巧，提出了由彈性接觸問題引出的線性互補問題的完全多重網格方法，但該方法的有效集是不停變換的，且求解過程麻煩。瀑布型多重網格方法也稱為單步多重網格法，其不要求粗網格校正，計算簡單且不失有效性[5]。石鐘慈等[6]利用瀑布型多重網格方法求解了橢圓問題。瀑布型多重網格方法對于求解互補問題是非常有效的[7]，為此，結合瀑布型多重網格方法和模系矩陣分裂迭代方法的優點，提出了求解線性互補問題的模系瀑布型多重網格方法。

1預備知識

線性互補問題:

(1)

其中：A∈Rn×n為給定的矩陣；q∈Rn為已知向量。問題(1)記為LCP(q,A)。

引理1[2]設A=M-N為矩陣A的一個分裂，Ω為正對角陣，γ為正常數。

(2)

方法1模系矩陣分裂迭代方法[2]。設A=M-N為矩陣A的一個分裂，給定初始向量x(0)∈Rn，通過求解

(3)

對于模系矩陣分裂迭代方法，取M=(1/α)(D-βL)，N=(1/α)[(1-α)D+(α-β)L+αU]，選取適當的分裂A=M-N，使得線性方程組(3)易于求解。

進一步，得到模系加速超松弛迭代(MAOR)方法：

其中D、L、U分別為A的對角矩陣、嚴格下三角矩陣、嚴格上三角矩陣。若松弛參數(α,β)分別取(α,α)、(1,1)、(1,0)，則MAOR方法退化為MSOR、MGS、MJ方法。

2模系瀑布型多重網格方法(MCMG)

1)j=1。

2)j>1。

3數值實驗

其中：

f=2x(1-x)+2y(1-y)。

線性互補問題的真解u=x(1-x)y(1-y)。

模系瀑布型多重網格方法的實驗結果如表1所示。其中：n為矩陣A的階數；t為迭代時間；E0為初始誤差，E為最終誤差。從表1可以看出，隨著網格剖分越來越密，矩陣維數的增大，模系瀑布型多重網格方法可以求解互補問題。

表1　模系瀑布型多重網格方法的實驗結果

模系瀑布型多重網格方法(MCMG)和模系矩陣分裂Jacobic方法(MJ)的實驗結果如表2所示，其中d為迭代步數。從表2可以看出，模系矩陣分裂和二次插值為瀑布型多重網格提供了較好的初始解，加速了收斂速度，降低了迭代步數，實驗結果說明了算法的有效性。

表2　MJ和MCMG的實驗結果

4結束語

基于文獻[2]的思想，利用瀑布型多重網格方法，將模系矩陣分裂迭代方法作為一個光滑子，提出了求解線性互補問題的模系瀑布型多重網格方法，實驗結果說明了該方法的有效性。

參考文獻:

[1]COTTLE R E, PANG J S, STONE R E. The Linear Complementarity Problem[M].San Diego：Academic Press,1992.

[2]BAI Zhongzhi.Modulus-based matrix splitting iteration methods for linear complementarity problems[J].Numerical Linear Algebra with Applications,2010,17(6): 917-933.

[3]張麗麗.關于線性互補問題的模系矩陣分裂迭代方法[J].計算數學，2012,34(4):373-386．

[4]ZHAO Jing,VOLLEBREGT E A H，OOSTERLEE C W.A full multigrid method for linear complementarity problems arising from elastic normal contact problems[J].Mathematical Modelling and Analysis,2014,19(2):216-240.

[5]BORNEMANN F, DEUFLHARD P. The cascadic multigrid method for elliptic problems[J].Numerische Mathematik,1996,75(2):135-152.

[6]SHI Zhongci,XU Xuejun.Cascadic multigrid method for elliptic problems[J].East-West Journal of Numerical Mathematics,1999,7(3):199-209.

[7]BLUM H,BRAESS D,SUTTMEIER F T.A cascadic multigrid algorithm for variational inequalities[J].Computing and Visualization in Science,2004,7(3):153-157.

[8]周叔子.變分不等式的有限元方法[M].長沙：湖南大學出版社，1988.

編輯：曹壽平

A modulus-based cascadic multigrid method for linear complementarity problem

WANG Yan, LI Chenliang

(School of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin 541004, China)

Abstract：A modulus-based cascadic multigrid method is presented to solve linear complementarity problem, which uses a modulus-based matrix splitting method as a smoother of cascadic multigrid method for obtaining effective approximate solution. The numerical experiments show that the new algorithm is effective.

Key words：linear complementarity problem; modulus-based matrix splitting; cascadic multigrid method

收稿日期：2015-11-18

基金項目：國家自然科學基金(11161014)；廣西自然科學基金(2015GXNSFAA139014)；桂林電子科技大學研究生教育創新計劃(YJCXS201556)

通信作者：李郴良(1969-)，男，湖南邵東人，教授，博士，研究方向為偏微分方程數值解。E-mail:chenli@guet.edu.cn

中圖分類號：O242.26

文獻標志碼：A

文章編號：1673-808X(2016)02-0151-03

引文格式： 王艷，李郴良.求解線性互補問題的模系瀑布型多重網格方法[J].桂林電子科技大學學報，2016,36(2)：151-153.