牛頓-矩陣多分裂多參數(shù)TOR 迭代法弱收斂性分析

張理濤，張一帆

（鄭州航空工業(yè)管理學院數(shù)學學院，河南 鄭州 450046）

0 引言

考慮光滑非線性方程組［1-2］

其中，F(xiàn)是非線性映像，Ω 是RN中任一有界集，x是Ω的一個向量。對于式（1）的求解，許多學者做了大量研究工作，得到了一系列有效的計算方法［1-8］。但求解非線性方程組的迭代方法大多由求解線性方程組的迭代方法衍生而來。對于線性方程組的求解，LEARY 等［9］提出了基于矩陣多分裂的并行多分裂迭代法。此后開展了許多相關(guān)研究并給出了收斂定理，如文獻［10-12］研究了系數(shù)矩陣的（局部松弛）SOR、AOR 和TOR 方法。文獻［13］對SOR、AOR和JOR 松弛方法的收斂速度和發(fā)散速度進行了比較。文獻［14］分析了不同權(quán)矩陣的收斂性。文獻［15］研究了系數(shù)矩陣的USAOR 迭代法。文獻［16］將該方法推廣至非線性方程組，構(gòu)造并研究了牛頓-并行多分裂方法。文獻［17］設(shè)計并研究了牛頓-全局松弛矩陣多分裂迭代法。本文將求解線性方程組的松弛矩陣多分裂迭代法推廣至求解非線性方程組，研究了牛頓-全局松弛非定常多分裂多參數(shù)迭代法，建立了局部收斂定理，估計了收斂速度。

求解式（1）的牛頓法為

其牛頓方程組為

則式（3）可表示為

式（1）的相關(guān)知識可參閱文獻［17-18］。若對A(xk)x=b(xk)應(yīng)用松弛矩陣多分裂迭代法，則可得到牛頓-全局松弛矩陣多分裂迭代法（NGRM 迭代法）。

算法1矩陣多分裂多參數(shù)迭代法

任取初始近似x(0)∈RN，對m=0，1，…，重復(fù)步驟1和步驟2，直至收斂。

步驟1對t=1，2，…，α，(并行）求解yt：

步驟2計算

注1yt表示第t臺處理機得到的解，Mt表示第t臺處理機對應(yīng)于A(xk)的分裂，Et表示第t臺處理機的加權(quán)矩陣。

注2如果Et的對角線元素之一為零，則yt不需要計算相應(yīng)分量，從而大大節(jié)省了工作量。這表明Et還扮演著分配每個處理器工作負載的角色。應(yīng)盡最大努力平衡處理器之間的負載，以降低同步等待的成本。由此可見，算法1 具有天然的并行性。

定義1A=(aij)∈RN×N，ZN×N={A∈RN×N|aij≤0，i≠j}。

（4）若aij≥0，i，j=1，2，…，n，則稱A為非負矩陣，并表示為A≥0，記|A|=（|aij|）。

若A?B≥0，則表示為A≥B，可得

引理1若A，B∈RN×N，D=diag(A)，

（1）若A為M-矩陣，則D≥0，且D非奇異；

（2）若A為M-矩陣，B∈ZN×N，且A≤B，則B為M-矩陣；

（3）若A為H-矩陣，則A非奇異，且；

（4）已知A，B均為M-矩陣，若A≤B，則A?1≥B?1；

（5）若A為H-矩陣，且A=D?B，則D非奇異，且ρ(|D|?1|B|)<1。

1 牛頓-矩陣非定常多分裂多參數(shù)TOR 迭代法

算法2矩陣多分裂多參數(shù)TOR迭代法（MTOR）

任取初始近似x(0)∈RN，對m=0，1，…，重復(fù)步驟1和步驟2，直至收斂。

步驟1對k=1，2，…，l，(并行）求解yk：

步驟2計算

算法2 可改寫為

引理2若A∈Rn×n是H-矩 陣，令A(yù)=D?B=D?Lk?Fk?Uk(1≤k≤l)，其 中D=diag(A)，Lk，F(xiàn)k是嚴 格意義下的三角矩 陣，而Uk是一般矩陣，且(D?Lk?Fk，Uk，Ek)，k=1，2，…，l，是矩陣A的多分裂TOR 法且滿足。如果

引理3［20］若A∈Rn×n是H-矩陣，令A(yù)=D?B=D?Lk?Fk?Uk(1≤k≤l)，其 中D=diag(A)，Lk，F(xiàn)k是嚴格意義下的三角矩陣，而Uk是一般矩陣，且(D?Lk?Fk，Uk，Ek)，k=1，2，…，l，是矩陣A的多分裂TOR 迭代法且滿足。如果

則ρ(HMTOR(ω，α，β))≤ρ(|HMTOR(ω，α，β)|)<1。

則ρ(HMTOR(ω，α，β))≤ρ(|HMTOR(ω，α，β)|)<1。

3 收斂性分析

為證明引理2，需證明9 種可能的情況（表1）。

表1 參數(shù)α，β 的不同區(qū)域Table 1 Different areas of the parameter α，β

引理2的證明由于ρ(S(α，β))≤ρ(|S(α，β)|)，只需證明ρ(|S(α，β)|)<1。定義

由假設(shè)條件易知，D?αLk?βFk是H-矩陣，k=1，2，…，l。由引理5 及比較矩陣定義，知

因此，可得

考慮矩陣A′k，k=1，2，…，l的分裂：

令γmin=min {α，β}，有

由于α≤0，0 ≤β≤1和?1≥?(1?2α)，可得

（i）當 1?2α≥2β?1 時，有?(1?2α)≥?(2β?1)，由于α≤0 和?(1?2α)≤?1，可得

（ii）當1?2α≥2β?1 時，有?(2β?1)≤?(1?2α），由于β≥1 和?(2β?1)≤?1，可得

由于β≤0和?1≥?(1?2β)，可得

由于A是H-矩 陣，是單調(diào)矩陣，k=1，2，…，l且ρ<1。由引理6 和式（12），可得

由于β≥1和?1≥?(2β?1)，可得

（i）當2α?1≥1?2β時，有?(2α?1)≤?(1?2β)，由于α≥1 和?(2α?1)≤?1，可得

（ii）當2α?1≤1?2β時，有?(1?2α)≤?(2β?1)，由于β≤0 和?(1?2β)≤?1，可得

由于α≥1和?1≥?(2α?1)，可得

令γmax=max {α，β}，則

4 結(jié)論

當牛頓方程的維數(shù)較高時，牛頓法的計算量將非常大，其精確解的計算成本較高。在已有研究基礎(chǔ)上，通過引入多重松弛因子，提出了牛頓-矩陣多分裂多參數(shù)TOR 迭代法，建立了局部收斂定理，并估計了收斂速度。