王 爽，唐 嘉

求解線性互補(bǔ)問(wèn)題的一類矩陣分裂迭代算法

王 爽，*唐 嘉

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

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

線性互補(bǔ)問(wèn)題；矩陣分裂；迭代法；收斂性

0 引言

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

3 收斂性分析

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

在（5）中，對(duì)第一個(gè)方程的左右兩邊同時(shí)取絕對(duì)值，可以得到

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

因?yàn)?/p>

且

從而有

同樣，有

成立。因此

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

那么

類似地，有

所以，

4 數(shù)值實(shí)驗(yàn)

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

是LCP的唯一解。

3）數(shù)值實(shí)驗(yàn)表明，NTMSOR迭代法相比較NMSOR迭代法需要更少的迭代步數(shù)和CPU時(shí)間。這表明，當(dāng)這兩種方法被用于求解LCP時(shí)，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í)驗(yàn)表明，該方法在迭代步數(shù)和CPU時(shí)間方面均優(yōu)于現(xiàn)有的方法。此外，選擇不同的參數(shù)對(duì)計(jì)算結(jié)果有著顯著的影響。然而，在一般情況下很難找到其最優(yōu)參數(shù)，因此，理論上研究最優(yōu)參數(shù)的選取將是一個(gè)值得研究的課題。

[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

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

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

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