黎科良 ,柯藝芬 ,馬昌鳳

(1.福建師范大學數(shù)學與統(tǒng)計學院,福建 福州 350117;2.福建省分析數(shù)學及應(yīng)用重點實驗室,福建 福州 350117;3.福建省應(yīng)用數(shù)學中心,福建 福州 350117)

1.引言

近年來,隱式互補問題引起了廣泛的關(guān)注,其可視為線性互補問題的一種推廣.互補問題在經(jīng)濟學和工程中有著廣泛的應(yīng)用,如: 空間價格平衡、對策論模型、接觸力學問題、斷裂力學問題等[1].本文考慮如下隱式互補問題(ICP): 求Rn,滿足:

其中Rn×n是大型稀疏矩陣,Rn是一個給定的實向量,m(z)是一個從Rn到自身的映射.當m(z)0時,隱式互補問題(1.1)退化為線性互補問題(LCP).

目前,已經(jīng)有許多有效算法被提出用于求解隱式互補問題(1.1),如: 不動點方法[2]、投影法[3]、牛頓方法[4]等.2010年,BAI[5]提出了模系矩陣分裂迭代方法求解線性互補問題,該方法具有形式簡單、收斂速度快等優(yōu)點.隨后,HONG和LI[6]首次推廣了模系矩陣分裂迭代法和模系矩陣同步多分裂迭代法來求解隱式互補問題(1.1),研究了當系統(tǒng)矩陣A為正定矩陣或H+-矩陣時算法的收斂性質(zhì).值得一提的是,模系矩陣分裂方法這一思想已被推廣到求解其他互補問題,如: 二階錐互補問題[7]、旋轉(zhuǎn)錐互補問題[8]、水平線性互補問題[9]、弱線性互補問題[10]和擬互補問題[11]等.

為了解決文[6]對于初始向量的約束問題,ZHENG和Vong[12]在文[6]的基礎(chǔ)上建立了一種新的方法,并給出了算法對于任意初始向量都收斂的全局收斂性條件.特別地,當系統(tǒng)矩陣A是正定矩陣或H+-矩陣時,從理論上嚴格分析了算法的收斂性質(zhì).

為進一步加快求解隱式互補問題的收斂速度,并充分利用系統(tǒng)矩陣所包含的信息,本文提出了一類新的基于模系的兩步矩陣分裂迭代法(簡記為TMMS).進一步,討論了該方法在一定條件下的收斂性,并分析了該方法在系統(tǒng)矩陣為正定矩陣時的收斂性質(zhì).數(shù)值實驗表明所提出的方法優(yōu)于原來的模系矩陣分裂迭代方法.

本文分別用∥A∥和∥x∥表示矩陣A的譜范數(shù)和向量x的2-范數(shù).用I表示適當維數(shù)的單位矩陣.令A=M ?N,若矩陣M是非奇異的,則稱A=M ?N為A的一個分裂.

2.兩步模系矩陣分裂迭代法

下面先給出一個重要的引理.

引理2.1[6]假設(shè)A=M ?N是矩陣A的一個分裂,γ是一個正常數(shù),?是一個正對角矩陣.若g:RnRn是可逆映射且g(z):=z ?m(z)=(|x|+x),可得

進一步,下面兩個結(jié)論成立.

(i) 如果(z,w)是問題(1.1)的解,則x=(z ??-1w ?m(z))滿足隱式不動點方程:

(ii) 如果x滿足隱式不動點方程(2.1),則(z,w)是問題(1.1)的解,其中

基于引理2.1,文[12]提出了如下模系矩陣分裂迭代法(簡記為MMS)用于求解隱式互補問題(1.1).

算法2.1模系矩陣分裂迭代法[12]

步1 給定ε>0,γ>0,x(0)Rn,?為正對角矩陣.置k:=0.

步2 通過求解下列線性方程組,計算z(k):

步3 若∥min{Az(k)+q,z(k)?m(z(k))}∥<ε,算法停止;否則,轉(zhuǎn)步4.

步4 通過求解下列線性方程組,計算x(k+1):

置k:=k+1,返回步2.

當A是正定矩陣或H+-矩陣時,文[12]給出了算法2.1的收斂性證明.

為進一步加快算法2.1的收斂速度,基于文[13-17]的研究工作,本文提出一類新的兩步模系矩陣分裂迭代方法.

設(shè)A=M1?N1=M2?N2為矩陣A的兩個分裂,可得如下兩步迭代格式:

具體地,基于式(2.5)構(gòu)造如下兩步模系矩陣分裂迭代法(簡記為TMMS).

算法2.2兩步模系矩陣分裂迭代法

步1 給定ε>0,γ>0,x(0)Rn,?為正對角矩陣.置k:=0.

步2 通過求解下列線性方程組,計算z(k):

步3 若∥min{Az(k)+q,z(k)?m(z(k))}∥<ε,算法停止;否則,轉(zhuǎn)步4.

步4 通過求解下列線性方程組,計算x(k+1):

置k:k+1,返回步2.

算法2.2建立了求解隱式互補問題(1.1)的兩步模系矩陣分裂迭代法的一般框架.通過選取適當?shù)木仃嚪至押偷鷧?shù),可得一系列的兩步模系矩陣分裂迭代法.

當m(z)0時,算法2.2退化為求解線性互補問題的兩步模系矩陣分裂迭代法,即

設(shè)AD ?L ?U,這里D,?L,?U分別是矩陣A的對角部分、嚴格下三角部分和嚴格上三角部分.考慮如下兩個分裂AM1?N1M2?N2,其中

(i) 當α1,β0,稱算法2.2為基于兩步模系Jacobi迭代方法,記作TMMJ.

(ii) 當αβ1,稱算法2.2為基于兩步模系Gauss-Seidel迭代方法,記作TMMGS.

(iii) 當αβ,稱算法2.2為基于兩步模系SOR迭代方法,記作TMMSOR.

3.算法的收斂性

本節(jié)將建立系統(tǒng)矩陣A為正定矩陣情形下兩步模系矩陣分裂迭代法求解隱式互補問題(1.1)的收斂性分析.

定義3.1稱映射m:RnRn是利普希茲連續(xù)的,如果對于任意的向量z,Rn,存在一個正常數(shù)L>0,有∥m(z)?m(y)∥≤L∥z ?y∥.

下面考慮算法2.2的收斂性.假設(shè)x?為式(2.7)的精確解,即

基于式(3.2)建立算法2.2的收斂性定理.

定理3.1假設(shè)AM1?N1M2?N2為A的兩個分裂,?為正對角矩陣,γ為正常數(shù).假設(shè)矩陣?+M1和?+M2都是非奇異的,且函數(shù)m: RnRn為利普希茲連續(xù)的,即存在正常數(shù)L,使得對任意的向量z,Rn,有∥m(z)?m(y)∥≤L∥z ?y∥.

記

注意到對于任意的向量y,Rn,有∥|y|?|z|∥≤∥y ?z∥.從而

對式(3.3)的第一個等式兩邊同時取2-范數(shù),可得

同理,對式(3.3)的第二個等式兩邊同時取2-范數(shù),可得:

從而∥x(k+1)?x?∥≤ρ2ρ1∥x(k)?x?∥.當ρρ2ρ1<1時,定理3.1結(jié)論成立.

特別地,對于A為正定矩陣,M1,M2Rn×n為對稱正定矩陣,?ωIn,從定理3.1可得如下收斂性結(jié)論.

定理3.2假設(shè)AM1?N1M2?M2是正定矩陣A的兩個分裂,M1,M2Rn×n是對稱正定矩陣,?ωIn(ω>0),γ是一個正常數(shù).用μmax和μmin分別表示M1的最大特征值和最小特征值,λmax和λmin分別表示M2的最大特征值和最小特征值.假設(shè)函數(shù)m:RnRn為利普希茲連續(xù)的且利普希茲常數(shù)為L.記

假設(shè)迭代參數(shù)ω滿足下列情況之一:

整理可得,當ω滿足定理3.2的四個條件之一,可得s2s1<1.從而

4.數(shù)值實驗

本節(jié)將給出一些數(shù)值算例來驗證所提出的兩步模系矩陣分裂迭代法的有效性.數(shù)值實驗將所提出的TMMJ、TMMGS和TMMSOR算法與文[12]所提出的MMJ、MMGS和MMSOR算法進行對比,從迭代步數(shù)(IT)、所消耗的時間(CPU)和殘差范數(shù)(RES)三個方面來比較算法的優(yōu)劣,其中容忍誤差ε取值為10-6,殘差范數(shù)定義為:

這里z(k)是算法第k步的近似解.在實驗中,初始向量x(0)的每個分量取值為[?1,1]的隨機數(shù),正對角矩陣?取為:?ωDA,ω>0,這里DA為矩陣A的對角部分.實驗中的最大迭代步數(shù)設(shè)為600.所有數(shù)值實驗均在一臺CPU為1.8GHz、內(nèi)存為8GB的計算機上運行,編程語言為MATLAB R2021a.

例1設(shè)s為給定的正整數(shù)且ns2.考慮隱式互補問題(1.1),其中Rn×n為如下的塊三對角矩陣

這里Stridiag(?1,4+ν,?1)Rs×s且ν>0.向量q(?1,1,?1,1,...,(?1)n-1,(?1)n)TRn.容易驗證系統(tǒng)矩陣A是一個對稱正定的M-矩陣.函數(shù)m(z)分別選取sin(z)和|z|兩類非線性函數(shù).

對于例1,考慮取n3600和n4900兩種情形進行測試.在數(shù)值實驗中,參數(shù)γ ≡1.5,ν ≡4和ω ≡1.2,在TMMSOR分裂迭代法中,松弛參數(shù)α ≡β ≡1.5.表4.1-4.2給出了例1的數(shù)值結(jié)果.從表4.1-4.2的數(shù)值結(jié)果可以看出,所有的算法均能快速收斂到隱式互補問題的一個近似解,且隨著維數(shù)n的增加,TMMS和MMS的迭代步數(shù)和CPU會有所增加.在誤差方面,所有的算法都能在給定的最大迭代次數(shù)內(nèi)達到終止條件.特別地,從表4.1-4.2的數(shù)值結(jié)果可以看出,當非線性項的系數(shù)增大時,算法往往需要更多的迭代步數(shù)才能收斂,如: 當維數(shù)相同時,m(z)0.9|z|相比m(z)0.75|z|和m(z)0.5|z|,算法需要更多的迭代步數(shù)才能達到終止條件.

表4.1 例1的數(shù)值結(jié)果(ν=4)

數(shù)值結(jié)果表明,TMMJ、TMMGS和TMMSOR的迭代方法要比文[12]的收斂效果更好.因此,本文提出的算法優(yōu)于文[12]所提出的算法.

5.小結(jié)

本文建立了一類新的基于模系的兩步矩陣分裂迭代法來求解隱式互補問題.給出了算法收斂的充分條件.數(shù)值實驗表明,本文提出的方法是有效的,且在迭代步數(shù)和CPU時間方面優(yōu)于傳統(tǒng)的方法.然而,算法的收斂速度如何依賴于參數(shù)ω仍然是未知的.因此,理論上研究最優(yōu)參數(shù)的選取將是一個值得研究的課題.