求解線性互補問題的一類矩陣分裂迭代算法

王 爽，唐 嘉

求解線性互補問題的一類矩陣分裂迭代算法

王 爽，*唐 嘉

（福建師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，福建，福州 350007）

通過改進 NMMS 方法，建立了一類新的基于模的兩步矩陣分裂 (NTMMS) 迭代法，給出了該算法在適當(dāng)條件下的收斂性，包括加速超松弛分裂的情況。數(shù)值實驗表明，該方法在實際應(yīng)用中優(yōu)于傳統(tǒng)的迭代法。

線性互補問題；矩陣分裂；迭代法；收斂性

0 引言

為了在實際計算中更靈活地求解LCP，通常使用矩陣分裂來構(gòu)造有效的迭代方法, 如投影松弛迭代法[2]，一般的不動點迭代法[3]，和矩陣多重分裂迭代法[4]。最近，基于線性互補問題的等價不動點形式，吳在文獻[5]給出了如下等價形式：

本文旨在進一步加速LCP的一類新的基于模的矩陣分裂 (NMMS) 迭代法。為了達到更高的計算效率，并充分利用系數(shù)矩陣中包含的信息，對LCP采用了兩步分裂技術(shù)，因此，我們提出了一類新的基于模的兩步矩陣分裂 (NTMMS) 迭代法。在適當(dāng)選擇矩陣分裂的情況下，這類新方法可以產(chǎn)生一系列松弛形式。此外，還討論了該方法的收斂性，并在適當(dāng)?shù)募僭O(shè)下給出它的一些收斂條件。數(shù)值實驗表明，所提出來的方法優(yōu)于現(xiàn)有的方法。

本文的其余部分組織如下：在第1節(jié)中，陳述了一些預(yù)備知識；在第2節(jié)中，我們提出了一類新的基于模的兩步矩陣分裂迭代法來求解LCP；在第3節(jié)中，給出了該方法的收斂性分析，包括加速超松弛分裂的情況；在第4節(jié)中，給出一個數(shù)值算例；在第5節(jié)中，對本文的工作進行了總結(jié)。

1 預(yù)備知識

在本節(jié)中，簡要地介紹一些符號，初步定義和必要的引理，以便在后續(xù)討論中使用。

然后，給出了在后續(xù)中有用的一些引理。

2 一類新的基于模的兩步迭代法

算法1（用于求解LCP的NTMMS迭代法）

3 收斂性分析

在本節(jié)中，給出了確保在適當(dāng)條件下算法1收斂的幾個充分條件。首先，我們給出了算法1的一般收斂性條件，見定理1。

在（5）中，對第一個方程的左右兩邊同時取絕對值，可以得到

同樣，由（5）式中的第二個方程可以得到

因為

且

從而有

同樣，有

成立。因此

基于上述結(jié)果，取

那么

類似地，有

所以，

4 數(shù)值實驗

本節(jié)給出一個數(shù)值例子說明所提出的算法1的有效性。數(shù)值結(jié)果從三個方面進行分析：迭代步驟 (以“IT”來表示)、以秒為單位的運行時間(以“CPU”來表示)和絕對殘差向量范數(shù) (以“RES”來表示)。在這里，

是LCP的唯一解。

3）數(shù)值實驗表明，NTMSOR迭代法相比較NMSOR迭代法需要更少的迭代步數(shù)和CPU時間。這表明，當(dāng)這兩種方法被用于求解LCP時，NTMSOR迭代法是優(yōu)于NMSOR迭代法。

表1 算例1的數(shù)值結(jié)果

Table 1 Numerical results of example 1

mNMSORNTMSOR ITCPURESITCPURES 2203040506026272829290.05180.16140.43401.00421.99936.4949e-067.3283e-066.1384e-068.2741e-065.7451e-0615151616160.04890.17120.46561.14452.16554.1632e-069.2305e-064.9328e-066.7204e-068.5076e-06 4203040506017181818190.04240.11640.30280.69621.37416.8128e-064.5957e-066.6315e-068.6670e-064.0932e-0610101010110.03470.11720.31810.76001.56702.4588e-064.5437e-066.6268e-068.7093e-061.9127e-06 6203040506014141515150.03470.10370.26180.57681.10424.5747e-067.8387e-063.2373e-064.1969e-065.1565e-06888880.03250.09910.26780.62171.20012.2640e-063.9763e-065.6877e-067.3987e-069.1096e-06

5 結(jié)論

本文建立了一類新的基于模的兩步矩陣分裂迭代法，研究了該方法的收斂性，在適當(dāng)條件下給出了保證該方法收斂的充分條件。數(shù)值實驗表明，該方法在迭代步數(shù)和CPU時間方面均優(yōu)于現(xiàn)有的方法。此外，選擇不同的參數(shù)對計算結(jié)果有著顯著的影響。然而，在一般情況下很難找到其最優(yōu)參數(shù)，因此，理論上研究最優(yōu)參數(shù)的選取將是一個值得研究的課題。

[1] Cottle R W, Dantzig G B. Complementary pivot theory of mathematical programming[J]. Mathematics of the decision sciences, part, 1968, 1(1):103-125.

[2] Bai Z Z.On the monotone convergence of the projected iteration methods for linear complementarity problems[J].Numerical Mathematics Theory Methods and Applications, 1996,5(2): 228-233.

[3] Hu J G. Scaling transformation and convergence of splittings of matrix[J]. Math. Numer. Sinica,1983,5(1):72-78.

[4] Bai Z, Huang Y. A class of asynchronous parallel multisplitting relaxation methods for large sparse linear complementarity problems[J]. Journal of Computational Mathematics, 2003(6): 773-790.

[5] Wu S, Li C. A class of new modulus-based matrix splitting methods for linear complementarity problem[J]. Optimization Letters, 2021,16:1427-1443.

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

[7] Ma C, Huang N. Modified modulus-based matrix splitting algorithms for a class of weakly nondifferentiable nonlinear complementarity problems[J]. Applied Numerical Mathematics, 2016, 108: 116-124.

[8] Hong J T, Li C L. Modulus-based matrix splitting iteration methods for a class of implicit complementarity problems[J]. Numerical Linear Algebra with Applications, 2016, 23(4): 629-641.

[9] Wu S L, Guo P. Modulus-based matrix splitting algorithms for the quasi-complementarity problems[J]. Applied Numerical Mathematics, 2018, 132: 127-137.

[10] Mezzadri F, Galligani E. Modulus-based matrix splitting methods for horizontal linear complementarity problems[J]. Numerical Algorithms,2020, 83(1): 201-219.

[11] Bai Z Z, Zhang L L. Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems[J]. Numerical Algorithms, 2013, 62(1): 59-77.

A CLASS OF MATRIX SPLITTING METHODS FOR LINEAR COMPLEMENTARITY PROBLEMS

WANG Shuang,*TANG Jia

（School of Mathematics and Statistics, Fujian Normal University, Fuzhou, Fujian 350007, China）

By improving the NMMS method, a class of new two-step modulus-based matrix splitting methods are established in this paper. The convergence of the algorithm under appropriate conditions is given, including the case of accelerated overrelaxation splitting. Numerical experiments show that the proposed method is superior to some existing methods in actual implementation.

linear complementarity problem; matrix splitting; iteration method; convergence

1674-8085（2022）04-0001-06

O241.6

A

10.3969/j.issn.1674-8085.2022.04.001

2022-03-18；

2022-04-15

國家自然科學(xué)基金青年基金項目(11901024)，福建省自然科學(xué)基金面上項目(2020J01166,2021J01661).

王 爽(1996-)，女，陜西渭南人，碩士生，主要從事數(shù)值代數(shù)方面研究(E-mail: ws2811814571@163.com)；

*唐 嘉(1983-)，女，湖南湘潭人，副教授，博士，主要從事數(shù)值代數(shù)及其應(yīng)用研究(E-mail: tang_jia@126.com).