求解線(xiàn)性互補(bǔ)問(wèn)題的非精確松弛多分裂算法

0多分裂松弛迭代算法線(xiàn)性補(bǔ)償問(wèn)題是一個(gè)重要的優(yōu)化問(wèn)題。它廣泛應(yīng)用于經(jīng)濟(jì)分析、交通戰(zhàn)略、平衡策略等社會(huì)經(jīng)濟(jì)模式中，為線(xiàn)性和二次計(jì)劃的研究提供了一個(gè)普遍框架，這與非動(dòng)態(tài)點(diǎn)理論、離散度等問(wèn)題密切相關(guān)。線(xiàn)性分析和其他應(yīng)用數(shù)學(xué)（經(jīng)濟(jì)、平衡等）。30年來(lái)，互聯(lián)互通問(wèn)題得到了充分發(fā)展，但在一定的精度下，驗(yàn)證相似解的重復(fù)時(shí)間仍然非常長(zhǎng)。參考文獻(xiàn)如下：n級(jí)實(shí)體矩陣mun和n級(jí)實(shí)體向量qni，以滿(mǎn)足以下條件的實(shí)體向量zni。z≥0,q+Μz≥0,zΤ(q+Μz)=0(1)并行多分裂迭代算法最初是O’Leary和White在研究線(xiàn)性方程組Ax=b時(shí)提出的概念,FrommerA.和MayerG.發(fā)展了這類(lèi)算法,給出一個(gè)松弛因子,提出了并行多分裂松弛迭代算法.針對(duì)大規(guī)模稀疏矩陣M,為加快收斂速度,文把該算法推廣到線(xiàn)性互補(bǔ)問(wèn)題,提出了求解線(xiàn)性互補(bǔ)問(wèn)題的并行多分裂迭代算法.定義1設(shè)M為非奇異的n×n實(shí)矩陣,Bi,Ci,Ei∈Rn×n,i=1,2,…,α,滿(mǎn)足下列條件:①M(fèi)=Bi+Ci,i=1,2,…,α,②Mi非奇異,i=1,2,?,α,③α∑i=1Ei=Ι(n×n單位陣),則稱(chēng)三元素集(Mi,Bi,Ci)(i=1,2,…,α)為矩陣M的多分裂.基于矩陣的多分裂,則求解線(xiàn)性互補(bǔ)問(wèn)題的多分裂松弛迭代算法定義如下:算法1(多分裂松弛迭代算法)(1)任意給定初始值z(mì)0∈Rn,置r=0;(2)對(duì)M的多重分裂:M=Bi+Ci(i=1,2,…,α),并行求解:{zk,i≥0,q+Νizk+Μizk,i≥0,(zk,i)Τ(q+Νizk+Μizk,i)=0;(3)zk+1=ωα∑i=1Eizk,i+(1-ω)zk(ω為松弛因子);(4)k:=k+1,轉(zhuǎn)第(2)步,直至收斂.當(dāng)α≡1時(shí),上述算法1就成為一般的分裂算法.但在實(shí)際求解子問(wèn)題時(shí),往往使用迭代求解,所得結(jié)果為近似解,由此產(chǎn)生非精確方法.基于非精確求解與松弛多分裂算法,本文提出了求解線(xiàn)性互補(bǔ)問(wèn)題的非精確松弛多分裂迭代算法,當(dāng)問(wèn)題的系數(shù)矩陣M為對(duì)角元為正的H-矩陣或?qū)ΨQ(chēng)正定陣時(shí),分析了算法的收斂性.最后,針對(duì)內(nèi)迭代,提出了一種求解非精確松弛分裂算法的特殊形式,其內(nèi)迭代利用矩陣的二級(jí)分裂算法,分析了該情形下算法的收斂特性.1材料中多個(gè)條件自由博弈的特性,一個(gè)是一個(gè)跨m首先給出全文使用的一些基本概念:定義1.1對(duì)于向量x∈Rn,如果它的所有分量xi≥0(>0)(i=1,2,…,n),則稱(chēng)x≥0(x>0),設(shè)x,y∈Rn,如果x-y≥0(x-y>0),則稱(chēng)x≥y(x>y),用|x|=(|x1|,|x2|,…,|xn|)表示x的絕對(duì)值向量.C=(cij)∈Rn×n為n×n階實(shí)矩陣,用diag(C)表示C的對(duì)角陣,對(duì)于A(yíng)=(aij),B=(bij)∈Rn×n,若aij≤bij,i,j=1,2,…,n,則稱(chēng)A≤B.稱(chēng)|A|=(|aij|)∈Rn×n為A=(aij)的絕對(duì)值矩陣,顯然有|AB|≤|A‖B|.定義1.2設(shè)A∈Rn×n,如果A-1≥0,則稱(chēng)A為單調(diào)矩陣;如果對(duì)任意給定的i≠j,有aij≤0,且A為單調(diào)矩陣,稱(chēng)A為非奇異M-矩陣.設(shè)<A>=(bij)∈Rn×n,其中bij={|aij|,i=j,-|aij|,i≠j,i,j=1,2,?,n.稱(chēng)<A>為A的比較矩陣;如果Α的比較矩陣<A>是非奇異的M-矩陣,則稱(chēng)A為非奇異的H-矩陣,簡(jiǎn)稱(chēng)為H-矩陣.定義1.3設(shè)M∈Rn×n,如果對(duì)于任意的q∈Rn,線(xiàn)性互補(bǔ)問(wèn)題LCP(q,M)有唯一解,則稱(chēng)M為Q-矩陣;線(xiàn)性互補(bǔ)問(wèn)題LCP(0,M)只有一個(gè)0解,則稱(chēng)M為R0-矩陣;如果M的所有主子式矩陣都為正,則稱(chēng)M為P-矩陣;一個(gè)矩陣M為P-矩陣當(dāng)且僅當(dāng)對(duì)任意的q∈Rn,線(xiàn)性互補(bǔ)問(wèn)題LCP(q,M)有唯一解.矩陣M為P-矩陣的一個(gè)充分條件為矩陣M對(duì)角元為正的H-矩陣.定義1.4設(shè)A∈Rn×n,如果M∈Rn×n是非奇異的且M-1≥0,稱(chēng)A=M+N為矩陣A的一個(gè)分裂;如果ρ(M-1N)<1,稱(chēng)分裂A=M+N為收斂的;如果M為Q-矩陣,則稱(chēng)該分裂為Q-分裂.如果<M>-|N|為單調(diào)矩陣,則稱(chēng)該分裂為H-分裂;如果<A>=<M>-|N|,則稱(chēng)A=M-N為矩陣A的H-相容分裂.引理1.1設(shè)A,M,N∈Rn×n,A=M+N為A的一個(gè)分裂,如果該分裂為H-分裂,則矩陣A,M都為H-矩陣且ρ(M-1N)≤ρ(<A>-1|N|)<1;如果該分裂為H-相容分裂且A為H-矩陣,則該分裂為H-分裂.引理1.2設(shè)T∈Rn×n且T≥0,如果存在向量u∈Rn,u>0和數(shù)θ>0,使得Tu≤θu成立,則有ρ(T)≤θ;設(shè)T1,T2,…,Ts,…∈Rn×n為非負(fù)矩陣序列,如果存在實(shí)數(shù)0≤θ<1和向量u∈Rn,u>0,使得Tlu≤θu,l=1,2,…,則有ρ(Hs)≤θs<1,這里Hs=TsTs-1…T1.2計(jì)算假設(shè)為登記對(duì)抗設(shè){Bi,Ci,Ei}αi=1為矩陣M的多分裂,首先給出求解線(xiàn)性互補(bǔ)問(wèn)題(1)的非精確松弛多分裂算法.算法2.1(非精確松弛多分裂算法)(1)給定初始值z(mì)0∈Rn,對(duì)每個(gè)i,令y0,0i=z0,置r=0;(2)對(duì)于給定的向量zr,令yr,0i=zr,對(duì)每個(gè)i,令yr,l+1i為下列互補(bǔ)子問(wèn)題的任意迭代解:{yr,l+1i≥0q+Ciyr,li+Biyr,l+1i≥0(yr,l+1i)Τ(q+Ciyr,li+Biyr,l+1i)=0(2)設(shè)yr,ˉl(r)i為滿(mǎn)足預(yù)先給定的內(nèi)迭代終止原則,如果yir,lˉ(r)=zr或yir,lˉ(r)滿(mǎn)足預(yù)先給定的外迭代終止原則,則停止計(jì)算,否則,令zr+1=ω∑i=1αEiyir,lˉ(r)+(1-ω)zr,轉(zhuǎn)下一步;(3)如果zr+1滿(mǎn)足預(yù)先給定的外迭代終止原則,則停止計(jì)算,否則,設(shè)yir+1,0=zr+1,r=r+1,轉(zhuǎn)第二步,直至收斂.注2.1顯然,當(dāng)z0≥0且子問(wèn)題(2)中的每個(gè)解為精確解時(shí),算法2.1就是算法1;當(dāng)α≡1且ω≡1時(shí),算法2.1就是文獻(xiàn)中的非精確分裂算法.此外,在算法1或其他求解線(xiàn)性互補(bǔ)問(wèn)題的分裂算法中,序列{zr}要求非負(fù),但在算法2.1中不做要求.注2.2對(duì)每個(gè)i=1,2,…,α和外迭代次數(shù)r,我們使用特殊的迭代算法求解子問(wèn)題(2):對(duì)每個(gè)矩陣Bi再進(jìn)行分裂:Bi=Fi+Gi,因此,我們得到矩陣M的二級(jí)多分裂,用{Bi,Ci,Fi,Gi,Ei}i=1α表示.特別,如果在算法2.1中,每個(gè)內(nèi)迭代使用分裂Bi=Fi+Gi來(lái)完成求解,整個(gè)迭代序列{zr},包括初始向量z0均非負(fù),則稱(chēng)算法2.1為二級(jí)多分裂算法.注2.3在每個(gè)外迭代和內(nèi)迭代,如果使用文獻(xiàn)中阻尼牛頓算法來(lái)求解,這里,要求初始向量z0非退化,即:對(duì)每個(gè)j=1,2,…,n,(z0)j≠(Mz0+q)j.進(jìn)而,在計(jì)算中選擇適當(dāng)?shù)臋?quán)矩陣,使得整個(gè)迭代序列{zr}非退化,例如,可以選擇權(quán)矩陣Ei=eiI(i=1,2,…,α),這里∑i=1αei=1,稱(chēng)該算法為多分裂阻尼牛頓算法.3收集劑分析本節(jié)我們給出算法2.1的收斂性定理.分兩種情況來(lái)證明:3.1單次給藥法假設(shè)算法2.1中的迭代序列滿(mǎn)足下列條件:∥ΗBi(yir,lˉ(r))∥≤Τr,i∥Η(zr)∥,i=1,2,?,α,(3)這里,‖·‖表示歐幾里德范數(shù),HBi(yir,l)=min{yir,l,Biyir,l+Cizr+q},H(zr)=min{zr,Mzr+q},對(duì)每個(gè)i=1,2,…,α,{Tr,i}為實(shí)數(shù)序列且滿(mǎn)足limr→∞Τr,i=0(4)定理3.1設(shè)M為對(duì)角元為正的H-矩陣,{Bi,Ci,Ei}i=1α為矩陣M的一個(gè)多分裂.對(duì)于任意的i=1,2,…,α,設(shè)Ei=eiI,M=Βi+Ci為H-相容分裂,即Bi為對(duì)角元為正的H-矩陣,0<ω≤1.假設(shè)有矩陣范數(shù)‖·‖,使得‖<Bi>-1|Ci‖<1和‖I‖=1成立.則對(duì)任意的初始值z(mì)0∈Rn,當(dāng)式(3)、式(4)成立時(shí),由算法2.1產(chǎn)生的序列{zr}收斂于線(xiàn)性互補(bǔ)問(wèn)題(1)有唯一解z*.證明:因?yàn)镸為對(duì)角元為正的H-矩陣,問(wèn)題(1)的有唯一解z*.對(duì)于任意的i=1,2,…,α,在第r次外迭代,根據(jù)引理1.1和文獻(xiàn)中的定理4.1的證明,當(dāng)內(nèi)迭代次數(shù)充分大時(shí),下述不等式成立∥yir,l-z*∥≤Lir∥zr-z*∥(5)這里L(fēng)ir=Τr,iμiλi+∥<Bi>-1|Ci|∥>0.上式中μi,λi為正實(shí)數(shù),因此Lir<1+∥<Bi>-1|Ci|∥2<1(6)設(shè)θ=max{‖<B1>-1|C1|‖,‖<B2>-1|C2|‖,…,‖<Bi>-1|Ci|‖},則由不等式(5)、(6)可得∥yir,l-z*∥≤1+θ2∥zr-z*∥,1+θ2<1.因此,∥zr+1-z*∥=∥ω∑i=1αEiyir,lˉ(r)+(1-ω)zr-z*∥=∥ω∑i=1αEi(yir,lˉ(r)-z*)+ω∑i=1αEiz*+(1-ω)zr-z*∥=∥ω∑i=1αEi(yir,lˉ(r)-z*)+(1-ω)(zr-z*)∥≤∥ω∑i=1αEi(yir,lˉ(r)-z*)∥+∥(1-ω)(zr-z*)∥≤ω∑i=1α∥Ei∥∥yir,lˉ(r)-z*∥+(1-ω)∥zr-z*∥≤ω∑i=1α∥Ei∥1+θ2∥zr-z*∥+(1-ω)∥zr-z*∥=ω∑i=1αei1+θ2∥zr-z*∥+(1-ω)∥zr-z*∥=[ω1+θ2+(1-ω)]∥zr-z*∥另外,因?yàn)?<ω≤1和1+θ2<1成立,則有ω1+θ2+(1-ω)<1.這就證明了定理.在定理3.1的證明過(guò)程中,存在一個(gè)單調(diào)矩陣范數(shù)‖·‖,使得‖<Bi>-1|Ci‖|<1成立.文獻(xiàn)中的推論5.3.16給出了這樣的矩陣范數(shù):引理3.1設(shè)M為對(duì)角元為正的H-矩陣,M=D+L+U,這里D,L和U分別為矩陣M的對(duì)角部分、下三角部分、上三角部分.設(shè)B=L+δ-1D,δ>0,則存在一個(gè)一個(gè)正向量dˉ,使得<Μ>dˉ>0成立.進(jìn)而,如果定義如下向量范數(shù)∥z∥dˉ:=maxidˉi-1|zi|(7)和正實(shí)數(shù)δˉ:=2minimijdˉi∑j|mij|dˉj(8)則有‖·‖為單調(diào)范數(shù),δˉ∈(1,2],并且對(duì)任意的δ∈(0,δˉ],由(6)式定義的矩陣范數(shù)是單調(diào)的且‖<B>-1|C|‖<1成立.由引理3.1給出的單調(diào)范數(shù)和定理3.1,有如下收斂性結(jié)果:推論3.1設(shè)M為對(duì)角元為正的H-矩陣,M=D+L+U,這里D,L和U分別為矩陣M的對(duì)角部分、下三角部分、上三角部分.對(duì)于任意的i=1,2,…,α,設(shè)Ei=eiI,Bi=L+δi-1D,這里δi>0為給定的向量,0<ω≤1.則存在δˉ∈(1,2],使得對(duì)所有的δi∈(0,δˉ],對(duì)任意的初始值z(mì)0∈Rn,當(dāng)式(3)、式(4)成立時(shí),由算法2.1產(chǎn)生的序列{zr}收斂于線(xiàn)性互補(bǔ)問(wèn)題(1)有唯一解z*.注3.1引理3.1給出了定理3.1中要求的一個(gè)特殊的單調(diào)范數(shù)實(shí)例,因此,推論3.1提供了定理3.1的一個(gè)特殊的認(rèn)識(shí),推論3.1的證明過(guò)程由定理3.1和引理3.1直接可得.3.2求解各含其一階段中p本節(jié)我們給出當(dāng)M為對(duì)稱(chēng)矩陣時(shí)算法2.1的收斂性定理.我們知道,當(dāng)M為對(duì)稱(chēng)矩陣時(shí),線(xiàn)性互補(bǔ)問(wèn)題(1)等價(jià)于如下二次規(guī)劃問(wèn)題:minf(z)=qΤz+12zΤΜz,s.t.z≥0.引理3.2[1,5.3.2]設(shè)M為對(duì)稱(chēng)矩陣,Bi+Ci(i=1,2,…,α)為M的弱正則分裂,則對(duì)任意向量q∈Rn及任意的初始向量z0∈Rn,z0≥0,由算法2.1產(chǎn)生的序列{zk},{yir,lˉ(r)}滿(mǎn)足f(zk)-f(yir,lˉ(r))≥12(zk-yir,lˉ(r))Τ(Bi-Ci)(zk-yir,lˉ(r))≥0(i=1,2,?,α).如果M為對(duì)稱(chēng)半正定矩陣,則f(z)為凸函數(shù),因此,當(dāng)0<ω≤1時(shí),f(zk+1)=f(ω∑i=1αEiyir,lˉ(r)+(1-ω)zk)≤f(ω∑i=1αEiyir,lˉ(r))+f((1-ω)zk)≤ω∑i=1αEif(yir,lˉ(r))+(1-ω)f(zk)≤ωmax1≤i≤αf(yir,lˉ(r))+(1-ω)f(zk)由此我們有下面的引理:引理3.3設(shè)M為對(duì)稱(chēng)半正定矩陣,0<ω≤1,Bi+Ci(i=1,2,…,α)為M的弱正則Q-分裂,則f(zk)-f(zk+1)≥ω2(zk-zk,iˉ)Τ(Bi-Ci)(zk-zk,iˉ)≥0(9)其中iˉ為滿(mǎn)足f(zk,iˉ)=max1≤i≤αf(yir,lˉ(r))的指標(biāo).證明:由上面的分析可得其中第2個(gè)不等式用到引理3.2.引理3.4設(shè)M為對(duì)稱(chēng)半正定矩陣,Bi+Ci(i=1,2,…,α)為M的正則Q-分裂,0<ω≤1,則由算法2.1產(chǎn)生的序列{zk}的每個(gè)聚點(diǎn)為問(wèn)題(1)的解.證明:設(shè)zˉ為序列{zk}的任意聚點(diǎn),不妨設(shè){zkj}為收斂于zˉ的子序列,則有f(zkj)→f(zˉ);又由引理3.3知f(zk)非增,因此整個(gè)序列f(zk)收斂.仍然設(shè)iˉ為滿(mǎn)足f(zk,iˉ)=max1≤i≤αf(yir,lˉ(r))的指標(biāo),由已知(B,C)為M的正則Q-分裂,則由式(9)知{zkj-zkj,}→0,所以zkj,→zˉ.而由zkj,為下述線(xiàn)性互補(bǔ)問(wèn)題的解:{zkj,iˉ≥0,q+Ciˉzkj+Biˉzkj,iˉ≥0,(zkj,iˉ)Τ(q+Ciˉzkj+Biˉzkj,iˉ)=0.(10)因?yàn)锽+C=M,且當(dāng)kj→∞時(shí)zkj,→zˉ,zkj→zˉ,對(duì)式(10)取極限可得,zˉ為問(wèn)題(1)的解.下面我們給出M為對(duì)稱(chēng)矩陣時(shí)松弛迭代算法的收斂性定理.定理3.2設(shè)M為對(duì)稱(chēng)矩陣,Bi+Ci(i=1,2,…,α)為M的正則Q-分裂,0<ω≤1,如果下面兩條件成立:(1)二次函數(shù)f(z)=qΤz+12zΤΜz對(duì)任意的z≥0有下界;(2)z≠0,z≥0,Mz≥0,zTMz=0?qTz>0.則由算法2.1產(chǎn)生的序列{zk}有界,且{zk}的每個(gè)聚點(diǎn)為問(wèn)題(1)的解.證明:首先用反證法證明序列{zk}有界.假設(shè){zk}無(wú)界,則存在子序列{zkj}使得‖zkj‖→∞,由條件(1)及引理3.3知{f(zk)}收斂,仍然設(shè)iˉ為滿(mǎn)足f(zk,iˉ)=max1≤i≤αf(yir,lˉ(r))的指標(biāo),(B,C)為M的正則Q-分裂,由式(9)知{zkj-zkj,}→0,即‖zkj,‖→∞.考慮正規(guī)化序列{zkj,iˉ∥zkj,iˉ∥},它有界,因此有聚點(diǎn)zˉ且zˉ≥0,∥zˉ∥=1.不失一般性,設(shè){zkj,iˉ∥zkj,iˉ∥}→zˉ.因?yàn)閦kj,為下述線(xiàn)性互補(bǔ)問(wèn)題的迭代解:{zkj,iˉ≥0,q+Ciˉzkj+Biˉzkj,iˉ≥0,(zkj,iˉ)Τ(q+Ciˉzkj+Biˉzkj,iˉ)=0.當(dāng)kj→∞時(shí),我們有Μzˉ≥0,zˉ≥0,zˉΤΜzˉ=0.由已知條件(1)知對(duì)任意的z≥0,有zTMz≥0(見(jiàn)文獻(xiàn)性質(zhì)3.7.14).又因?yàn)镸=B+C,zkj,≥0,所以從(zkj,iˉ)Τ(q+Ciˉzkj+Biˉzkj,iˉ)=0可得(zkj,iˉ)ΤΜzkj,iˉ=-(zkj,iˉ)Τ(q+Ciˉ(zkj-zkj,iˉ))≥0(11)而zkj-zkj,→0,對(duì)式(11)右邊不等式左右兩邊除以‖zkj,‖取極限(當(dāng)kj→∞時(shí))可得:qΤzˉ≤0,與已知條件(2)矛盾.故由算法2.1產(chǎn)生的序列{zk}有界.再由引理3.4可得{zk}的每個(gè)聚點(diǎn)為問(wèn)題(1)的解.證畢.4算法收斂性證明本節(jié)考慮非精確松弛多分裂算法2.1的特殊實(shí)現(xiàn)算法.對(duì)于任意的i=1,2,…,α,在第r次外迭代,運(yùn)用特殊的迭代算法來(lái)求解互補(bǔ)子問(wèn)題(2).算法4.1(二級(jí)松弛多分裂算法)對(duì)于任意的i=1,2,…,α,在第r次外迭代,運(yùn)用特殊的迭代算法來(lái)求解互補(bǔ)子問(wèn)題(2):對(duì)每個(gè)Bi進(jìn)行再分裂Bi=Fi+Gi,因此,對(duì)矩陣M,有二級(jí)多分裂{Bi,Ci,Fi,Gi,Ei}i=1α,稱(chēng)此算法為二級(jí)松弛多分裂算法.根據(jù)定理3.1和引理1.1,對(duì)算法4.1,我們有如下收斂性定理4.1,此結(jié)果直接來(lái)自?xún)?nèi)迭代的收斂特性和定理3.1.定理4.1設(shè)M為對(duì)角元為正的H-矩陣,{Bi,Ci,Fi,Gi,Ei}i=1α為矩陣M的二級(jí)多分裂.對(duì)于任意的i=1,2,…,α,設(shè)Ei=eiI,M=Bi+Ci為H-相容分裂,Bi=Fi+Gi為H-分裂,即Bi和Fi都為對(duì)角元為正的H-矩陣,0<ω≤1.假設(shè)有單調(diào)矩陣范數(shù)‖·‖,使得對(duì)每個(gè)i,‖<Bi>-1|Ci|‖<1和‖I‖=1成立.則對(duì)任意向量q和任意的初始值z(mì)0∈Rn,當(dāng)式(3)、式(4)成立時(shí),由算法4.1產(chǎn)生的唯一定義的序列{zr}收斂于線(xiàn)性互補(bǔ)問(wèn)題(1)有唯一解z*.下面,我們給出另外的收斂性結(jié)論以降低定理3.1和定理4.1的收斂性條件.事實(shí)上,從下面定理的證明過(guò)程可以看出單調(diào)矩陣范數(shù)不再需要,在條件中權(quán)矩陣Ei被放松了.特別,在第r次外迭代中,內(nèi)迭代次數(shù)lˉ(r)僅要求滿(mǎn)足:2(<Fi>-1|Gi|)lˉ(r)<Μ>-1-(Ι+(<Fi>-1|Gi|)lˉ(r))<Bi>-1<0(12)定理4.2設(shè)M為對(duì)角元為正的H-矩陣,{Bi,Ci,Fi,Gi,Ei}i=1α為矩陣M的二級(jí)多分裂.對(duì)于任意的i=1,2,…,α,設(shè)M=Bi+Ci為H-相容分裂,Bi=Fi+Gi為H-分裂,即Bi和Fi都為對(duì)角元為正的H-矩陣,0<ω≤1.則對(duì)任意向量q和任意的初始值z(mì)0∈Rn,z0≥0,當(dāng)式(12)成立時(shí),由算法4.1產(chǎn)生的唯一定義的序列{zr}收斂于線(xiàn)性互補(bǔ)問(wèn)題(1)的有一解z*.證明:因?yàn)镸為對(duì)角元為正的H-矩陣,問(wèn)題(1)的有唯一解z*.對(duì)于任意的i=1,2,…,α,由引理1.1可得M=Bi+Ci為H-分裂,再由文獻(xiàn)中的定理4.3可得∥yir,lˉ(r)-z*∥≤Lˉir∥zr-z*∥.這里L(fēng)ˉir=(<Fi>-1|Gi|)lˉ(r)+(Ι+(<Fi>-1|Gi|)lˉ(r))<Bi>-1|Ci|>0.因此|zr+1-z*|=|ω∑i=1αEiyir,lˉ(r)+(1-ω)zr-z*|=|ω∑i=1αEi(yir,lˉ(r)-z*)+ω∑i=1αEiz*+(1-ω)zr-z*|=|ω∑i=1αEi(yir,lˉ(r)-z*)+(1-ω)(zr-z*)|≤|ω∑i=1αEi(yir,lˉ(r)-z*)|+|(1-ω)(zr-z*)|≤ω∑i=1αEi|yir,lˉ(r)-z*|+(1-ω)|zr-z*|≤ω∑i=1αEiLˉir|zr-z*|+(1-ω)|zr-z*|=[ω∑i=1αEiLˉir+(1-ω)Ι]|zr-z*|(13)設(shè)Τr=[ω∑i=1αEiLˉir+(1-ω)Ι],由不等式(13)可得|zr+1-z*|≤ΤrΤr-1?Τ0|z0-z*|.令Hr=TrTr-1…T0,為證明算法的收斂性,我們只需證明limr→∞Ηr=0.考慮向量e=(1,1,…,1)T∈Rn,令u=<M>-1e,由定理的條件M=Bi+Ci為H-相容分裂,即:<M>=<Bi>-|Ci|,我們有<M>-1≥0,同時(shí)注意<M>-1沒(méi)有全部為空元素的行和列,因此,u>0,且有Lˉiru=((<Fi>-1|Gi|)lˉ(r)+(Ι+(<Fi>-1|Gi|)lˉ(r))<Bi>-1|Ci|)u=(<Fi>-1|Gi|)lˉ(r)u+(Ι+(<Fi>-1|Gi|)lˉ(r))<Bi>-1(<Bi>-Μ)u=u+2(<Fi>-1|Gi|)lˉ(r)u-(Ι+(<Fi>-1|Gi|)lˉ(r))<Bi>-1<Μ>u=u+2(<Fi>-1|Gi|)lˉ(r)<Μ>-1e-(Ι+(<Fi>-1|Gi|)lˉ(r))<Bi>-1e(14