求解線性互補(bǔ)問題的改進(jìn)加速迭代方法

沈海龍, 魏 彤

(東北大學(xué) 理學(xué)院, 遼寧 沈陽 110819)

?

求解線性互補(bǔ)問題的改進(jìn)加速迭代方法

沈海龍, 魏 彤

(東北大學(xué) 理學(xué)院, 遼寧 沈陽 110819)

從基于模系數(shù)矩陣分裂迭代方法的演變方法出發(fā),將收斂所需滿足的條件一般化,提出了一種改進(jìn)的加速分裂迭代方法.理論分析表明新方法可以和線性互補(bǔ)問題等價(jià)轉(zhuǎn)換,將新方法與其他幾種方法進(jìn)行比較分析,給出了系數(shù)矩陣是H+-矩陣的收斂定理.最后,通過數(shù)值算例證明了提出的新方法在運(yùn)算過程中需要更少的迭代步數(shù)和更短的運(yùn)行時(shí)間.

線性互補(bǔ)問題; 矩陣分裂; 迭代方法; H-矩陣; 收斂

線性互補(bǔ)問題LCP(q,A)就是找到向量r,z∈C滿足如下條件[1-3]:

式中,A=(aij)∈Cn×n是給定的大型稀疏實(shí)數(shù)矩陣,q=(q1,q2,…,qn)T∈C是一個(gè)給定實(shí)向量.

線性互補(bǔ)問題LCP(q,A)在20世紀(jì)60年代被首次提出,由于其在數(shù)學(xué)規(guī)劃方面是一類非常重要的分支,同時(shí)又是一個(gè)交叉的研究領(lǐng)域,因此,引起了很多數(shù)學(xué)研究者的高度重視[4-16].隨著線性互補(bǔ)問題LCP(q,A)在算法和理論上的不斷發(fā)展和完善,其實(shí)際應(yīng)用的范圍也逐步擴(kuò)大,現(xiàn)已經(jīng)拓展到了金融,交通和經(jīng)濟(jì)的問題中.自從線性互補(bǔ)問題LCP(q,A)被提出以來,在其算法方面和理論方面的研究都已取得了非常豐富的研究成果.主要的數(shù)值解算法分為直接算法和迭代算法,本文主要討論迭代算法.迭代算法有多重分裂法[6-9],投影迭代法[10-12]等.很多學(xué)者利用多重分裂法的多分裂思想構(gòu)造可行有效的算法將其應(yīng)用到并行計(jì)算中來解決大型線性互補(bǔ)問題LCP(q,A)[13-16],雖然在求解線性互補(bǔ)問題LCP(q,A)方面已經(jīng)有了許多算法,但是這些算法大都存在著限制條件.

1 改進(jìn)的加速分裂迭代方法

1.1 迭代格式的建立

對(duì)于任意向量x∈Cn,向量|x|+x和向量|x|-x都是非負(fù)向量而且各個(gè)分量之間乘積為零.Van Bokhoven利用了這個(gè)性質(zhì),在線性互補(bǔ)問題LCP(q,A) 中,令z:=|x|+x,r:=|x|-x,巧妙地將線性互補(bǔ)問題LCP(q,A)轉(zhuǎn)化成為一個(gè)不動(dòng)點(diǎn)方程,

(1)

此方法為求解線性互補(bǔ)問題LCP(q,A)的模迭代方法[7].

為了使模迭代方法的收斂速度能夠提高,Dong和Jiang在模迭代方法的基礎(chǔ)上引入了一個(gè)移位因子α>0,提出了改進(jìn)型的模迭代方法[8],其格式為

(2)

接著,Zhong-Zhi Bai在線性互補(bǔ)問題LCP(q,A) 中令z:=γ-1(|x|+x),r:=γ-1Ω(|x|-x).其中,γ>0,Ω是一個(gè)正對(duì)角矩陣,得到如下不動(dòng)點(diǎn)方程

(3)

因此,線性互補(bǔ)問題LCP(q,A)就轉(zhuǎn)化為了求解不動(dòng)點(diǎn)方程式(3)[9].為了更容易的求解式(3),將不動(dòng)點(diǎn)方程左邊的矩陣A∈Cn×n分裂成A=M-N,得到了基于模系數(shù)矩陣分裂迭代方法:

(4)

(5)

(6)

其中Ω=diag(ωi)是一個(gè)正對(duì)角矩陣,Φ=(κij)是一個(gè)非負(fù)矩陣.

下面引理將證明線性互補(bǔ)問題LCP(q,A)可以和擴(kuò)展之后得到的新方程等價(jià)轉(zhuǎn)換.

(ⅱ) 若x滿足不動(dòng)點(diǎn)方程(6),則r=Φ(|x|-x),z=Ω(|x|+x)是線性互補(bǔ)問題LCP(q,A)的解.

證明 首先證明(ⅰ):假設(shè)向量(z,r)是線性互補(bǔ)問題LCP(q,A)的一個(gè)解,向量(z,r)是一組非負(fù)的向量,可以表示為z=Ω(|x|+x),r=Φ(|x|-x).根據(jù)線性互補(bǔ)問題LCP(q,A)的定義,可知,zTr=0,r=Az+q,因此,可以得到表示形式Φ(|x|-x)=AΩ(|x|+x)+q.

這樣就驗(yàn)證了(ⅰ)的結(jié)論.

線性互補(bǔ)問題LCP(q,A)的表達(dá)形式為r=Az+q,設(shè)r=Φ(|x|-x)和z=Ω(|x|+x),易知

(a) 如果xi>0,那么zi>0,ri=0; (b) 如果xi=0,那么zi=0,ri=0; (c) 如果xi<0,那么zi=0,ri>0.

因此,可知zTr=0恒成立,它滿足線性互補(bǔ)問題LCP(q,A)的條件,所以r=Φ(|x|-x)和z=Ω(|x|+x)是線性互補(bǔ)問題LCP(q,A)的一個(gè)解.這就驗(yàn)證了(ⅱ)的結(jié)論.

注:引理1說明了可以通過求解不動(dòng)點(diǎn)方程(6)得到了線性互補(bǔ)問題LCP(q,A)的解.

迭代方程(6)只提供了求解線性互補(bǔ)問題LCP(q,A)的一個(gè)方程模型,為了能夠在實(shí)際運(yùn)算的時(shí)候更加快速的求解線性互補(bǔ)問題LCP(q,A),可以基于AOR,SOR,GS,J分裂迭代方法,提出了相應(yīng)的分裂迭代方法,本文僅介紹基于模系數(shù)矩陣分裂形式的改進(jìn)加速快速松弛方法.

在還原環(huán)境中，當(dāng)有機(jī)質(zhì)存在時(shí)，脫硫酸細(xì)菌能使SO42-還原為H2S，結(jié)果使得地下水中SO42-減少，pH值變大。

在實(shí)際運(yùn)算中選取了合適的松弛參數(shù)α和β,會(huì)使方程的收斂性大大提高,加快運(yùn)算速度.

1.2 收斂性分析

(7)

證明 由式(6)～式(7)可知,誤差向量滿足如下方程:

整理可得

(8)

對(duì)角部分元素:

非對(duì)角部分元素:

2 數(shù)值算例

例1 在線性互補(bǔ)問題LCP(q,A)中,令矩陣A為

在式(6)中,令Ω=I,κij=0(i≠j),則式(6)將變?yōu)槿缦滦问?

表1是迭代方程(5)(κij=0(i≠j))的數(shù)值算例結(jié)果,表2是迭代方程(6)(κij≠0(i≠j))的數(shù)值算例結(jié)果,從迭代步數(shù)和迭代時(shí)間兩方面進(jìn)行比較.矩陣的階數(shù)分為三種情況考慮.

表1 文獻(xiàn)[16]中的迭代結(jié)果

表2 本文方法的迭代結(jié)果

在迭代方程(6)中,令Ω=5I,下面表3是迭代方程(5)(κij=0(i≠j))的數(shù)值算例結(jié)果,表4是迭代方程(6)(κij≠0(i≠j))的數(shù)值算例結(jié)果，從迭代步數(shù)和迭代時(shí)間兩方面進(jìn)行比較。矩陣的階數(shù)分為三種情況考慮。

表3 文獻(xiàn)[16]中的迭代結(jié)果

表4 本文方法的迭代結(jié)果

從表1～表4可以看出,相比迭代方程(5),迭代方程(6)需要更少的迭代步數(shù)和更短的迭代時(shí)間,因此,本文給出的方法需要更少的迭代步數(shù)和更短的迭代時(shí)間,對(duì)于求解線性互補(bǔ)問題是可行和有效的.

3 結(jié) 語

本文是從一般加速的基于模系數(shù)矩陣分裂迭代方法出發(fā),將收斂所需滿足的條件一般化,提出了一種改進(jìn)加速分裂迭代方法,且給出了系數(shù)矩陣是 矩陣的收斂定理,通過數(shù)值算例說明了在選擇了合適的參數(shù)矩陣的條件下提出的改進(jìn)加速分裂迭代方法是可行和有效的.

[ 1 ] YANG H J, LI Q. A multiplicative multisplitting method for solving the linear complementarity problem[J]. Computers and Mathematics with Applications, 2009,58(10):1970-1978.

[ 2 ] MEHDI D, MASOUD H. Two class of synchronous matrix multisplitting schemes for solving linear complementarity problems[J]. Journal of Computational and Applied Mathematics, 2011, 235(15):4325-4336.

[ 3 ] ZHENG N, YIN J F. On the convergence of projected triangular decomposition methods for pricing American options with stochastic volatility[J]. Applied Mathematics and Computation, 2013,223(3):411-422.

[ 4 ] ZHANG L T, ZUO X Y, GU T X, et al. Improved convergence theorems of multisplitting methods for the linear complementarity problem[J]. Applied Mathematics and Computation, 2014,243(4):982-987.

[ 5 ] ZHANG L T, LI J L. The weaker convergence of modulus-based synchronous multisplitting multi-parameters methods for linear complementarity problems[J]. Computers and Mathematics with Applications, 2014,67(10):1954-1959.

[ 6 ] ZHANG L L. Two-step modulus-based matrix splitting iteration method for linear complementarity problems[J]. Numerical Algorithms, 2011,57(1):83-99.

[ 7 ] KE Y F, MA C F. On the convergence analysis of two-step modulus-based matrix splitting iteration method for linear complementarity problems[J]. Applied Mathematics and Computation, 2014,243:413-418.

[ 8 ] DONG J L, JIANG M Q. A modified modulus method for symmetric positive-definite linear complementarity problems[J]. Numerical Linear Algebra with Applications, 2009,16(2):129-143.

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

[10] ZHANG L L, REN Z R. Improved convergence theorems of modulus-based matrix splitting iteration methods for linear complementarity problems[J]. Applied Mathematics Letters, 2013,26(6): 638-642.

[11] ZHANG L L , ZHANG Y P , REN Z R. New convergence proofs of modulus-based synchronous multisplitting iteration methods for linear complementarity problems[J]. Linear Algebra and its Application, 2015,481:83-93.

[12] ZHONG Z B, ZHANG L L. Modulus-based synchronous multisplitting iteration methods for linear complementarity problems[J]. Numerical Linear Algebra with Applications, 2013,20(3):425-429.

[13] 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.

[14] Zhang L L. Two-stage multisplitting iteration methods using modulus-based matrix splitting as inner iteration for linear complementarity problems[J]. Journal of Optimization Theory and Applications, 2014,160(1):189-203.

[15] ZHENG N, YIN J F. Accelerated modulus-based matrix splitting iteration methods for linear complementarity problem[J]. Numerical Algorithms, 2013,64(2):245-262.

[16] LI W. A general modulus-based matrix splitting method for linear complementarity problems of matrices[J]. Applied Mathematics Letters, 2013,26(12):1159-1164.

【責(zé)任編輯: 肖景魁】

Modified Accelerated Splitting Iteration Method for Linear Complementarity Problem

ShenHailong,WeiTong

(Department of Mathematics, Northeastern University, Shenyang 110819, China)

Based on evolution method of modulus-based matrix splitting iteration method, the convergence condition was generalized; a modified accelerated splitting iteration method was proposed. The new method can be proved to be equivalent to the linear complementarity problem theoretically and compared to other methods; a new convergence theorem with matrix was put forward. With numerical examples, the new method was proved to need less iteration step numbers and shorter running time.

linear complementarity problem; matrix splitting; iteration method; matrix; convergence

2016-04-29

國家自然科學(xué)基金資助項(xiàng)目(11071033).

沈海龍(1971-),男,吉林延吉人,東北大學(xué)講師,博士.

2095-5456(2016)05-0420-05

O 241 6

A