張燕婷, 黃敬頻

(廣西民族大學(xué)數(shù)學(xué)與物理學(xué)院, 南寧 530006)

大型結(jié)構(gòu)矩陣方程問題廣泛出現(xiàn)在科學(xué)與工程領(lǐng)域中,如固體力學(xué)、流體力學(xué)、最優(yōu)化問題和鞍點問題都需要對大型線性系統(tǒng)進(jìn)行求解[1-5]。在一般情況下,方程組的系數(shù)矩陣較為龐大,且有稀疏性,因此更適合對其進(jìn)行迭代求解。多年來,許多學(xué)者針對不同結(jié)構(gòu)的復(fù)系統(tǒng)進(jìn)行過深入研究,形成較為豐富的研究成果。Bai等[6]于2003年對復(fù)亞正定系統(tǒng)首次提出了Hermitian 和斜Hermitian分裂迭代方法(Hermitian and skew-Hermitian splitting,HSS),該方法將系數(shù)矩陣A進(jìn)行了Hermitian 和反Hermitian分裂(Hermitian and skew-Hermitian,HS),使得迭代具有格式對稱、收斂速度快且無條件收斂等特點。此后,一些學(xué)者針對HSS迭代方法開展了一系列研究[7-9]。Li等[10]基于HS分裂,提出了非對稱Hermitian 和斜Hermitian分裂迭代方法(asymmetric Hermitian and skew-Hermitian splitting,AHSS),并證明了該方法的收斂因子的上界取決于兩個參數(shù)的選擇、Hermitian部分H的譜、以及斜自共軛部分S的奇異值。初魯?shù)萚11]提出了一類廣義的非對稱Hermitian 和斜Hermitian二步迭代(generalized lopsided Hermitian and skew-Hermitian splitting,GLHSS)迭代方法。文獻(xiàn)[12]通過引入新參數(shù)并結(jié)合迭代松弛技術(shù),提出一類外推的HSS迭代(extrapolation Hermitian and skew-Hermitian splitting,EHSS)。吳思婷等[13]將系數(shù)矩陣分解成正定矩陣和反Hermitian矩陣后進(jìn)行非對稱二步迭代,提出了外推的正定和反Hermitian方法(extrapolation positive definite and skew-Hermitian splitting,EPSS)。文獻(xiàn)[14]對系數(shù)矩陣進(jìn)行廣義HS分裂,并結(jié)合外推技術(shù),提出了外推的廣義HSS迭代方法(extrapolation of generalized Hermitian and skew-Hermitian splitting,EGHSS)。文獻(xiàn)[15]利用松弛迭代加速技巧,提出一種含有3個參數(shù)的超松弛迭代方法(successive over relaxation asymmetric Hermitian and skew-Hermitian splitting,SAHSS)。然而,這些成果均是針對復(fù)數(shù)域上的方程組進(jìn)行討論,缺少對大型結(jié)構(gòu)四元數(shù)系統(tǒng)的迭代研究。

四元數(shù)是一種超復(fù)數(shù),目前四元數(shù)在彩色圖像恢復(fù)、量子物理、核濾波、自動控制與工程技術(shù)等領(lǐng)域發(fā)揮著越來越重要的作用[16]。因此,關(guān)于四元數(shù)矩陣方程的研究自然成為數(shù)值代數(shù)的熱點課題。但由于四元數(shù)乘法的非交換原因,使得關(guān)于大型四元數(shù)系統(tǒng)的迭代研究尚鮮見報道[17]。鑒于此,針對四元數(shù)亞正定結(jié)構(gòu)系統(tǒng),運(yùn)用松弛加速技巧,構(gòu)建出新的混參分裂迭代方法,為解決實際問題提供理論基礎(chǔ)。

1 ANPSS迭代構(gòu)建

大規(guī)模線性方程組的求解,常常出現(xiàn)在科學(xué)與工程計算領(lǐng)域。在四元數(shù)體上考慮如式(1)所示的大型結(jié)構(gòu)系統(tǒng)的迭代求解問題。

AX=B

(1)

(2)

為提高NPSS迭代中參數(shù)選取的靈活性,引進(jìn)新參數(shù)β>0,并構(gòu)建如式(3)所示的迭代。

(3)

由式(3)中的第1個等式可得

X(k+1/2)=(αP+R)-1(αP-S)X(k)+
(αP+R)-1B

(4)

將式(4)代入式(3)中的第2個等式可得

X(k+1)=M(α,β)X(k)+N(α,β)

(5)

式(5)中:M(α,β)=(βP+S)-1(βP-R)(αP+R)-1(αP-S);N(α,β)=(βP+S)-1[(βP-R)(αP+R)-1+I],其中I為n階單位矩陣。

于是迭代式(3)與式(5)等價。把式(5)稱為非對稱新自共軛正定和斜自共軛分裂迭代 (asymmetric new positive definite and skew-self-conjugate splitting,ANPSS),M(α,β)是其迭代矩陣。

2 ANPSS迭代收斂性

主要對ANPSS迭代進(jìn)行收斂性分析,并給出收斂因子的上界。

引理1[19]矩陣A∈Qn×n的譜值半徑ψ(A)不超過其任意一種相容范數(shù)。特別地當(dāng)A是正規(guī)矩陣時有ψ(A)=‖A‖2。

?δ(α,β)

(6)

對式(5)中迭代矩陣M(α,β),其相似矩陣為

=P-1/2(βP+S)(βP+S)-1(βP-R)(αP+
R)-1(αP-S)(βP+S)-1P1/2

=P-1/2(βP-R)(αP+R)-1(αP-S)(βP+
S)-1P1/2

=(βI-P-1/2RP-1/2)(αI+P-1/2RP-1/2)-1(αI-
P-1/2SP-1/2)(βI+P-1/2SP-1/2)-1

(7)

(8)

從而有

(9)

(10)

(11)

于是由式(7)、式(9)、式(11)可得

=δ(α,β)

(12)

證畢。

根據(jù)定理1中的上界δ(α,β),接下來給出ANPSS迭代的收斂條件。

(13)

(14)

則ψ[M(α,β)]≤δ(α,β)<1,即ANPSS迭代收斂。

(15)

分兩種情況討論δ(α,β)的值。

(1)若β>α≥0,則由式(15)可知:

(16)

由式(16)的右邊不等式組及β>α得

(17)

(18)

所以f(x)在[0,+∞)是單調(diào)減函數(shù),其最大值為f(0),由此可得

(19)

又根據(jù)式(12)可知,

(20)

由式(20)的右側(cè)不等式組及0<β≤α解得

(21)

(22)

3 廣義超松弛迭代

為進(jìn)一步提高NPSS迭代的效率,運(yùn)用松弛加速技術(shù),構(gòu)建一種新的求解四元數(shù)亞正定矩陣方程[式(1)]的混參分裂迭代方法。

首先,對式(3)中第一個等式進(jìn)行變形,可得

RX(k+1/2)=(αP-S)X(k)-αPX(k+1/2)+B

(23)

將式(23)代入式(3)中第2個方程化簡整理可得

(βP+S)X(k+1)=(S-αP)X(k)+(α+β)PX(k+1/2)

(24)

其次,通過引入松弛參數(shù)ω≥0來改進(jìn)迭代序列式(24),即

(25)

于是,聯(lián)立ANPSS迭代式(3)中第1行等式和式(25)可得

(26)

式(26)中:α≥0,β>0,ω≥0為3個給定的參數(shù)。

顯然,當(dāng)ω=0時,式(25)即為式(24),迭代式(26)正是ANPSS迭代;當(dāng)ω=0,α=β時,迭代式(26)退化為NPSS迭代方法[17]。

將式(26)等價地表示為

X(k+1)=M(α,β,ω)X(k)+N(α,β,ω)B,
k=0,1,…

(27)

式(27)中:

(28)

(29)

稱迭代式(26)為超松弛非對稱新自共軛正定和斜自共軛分裂迭代(successive over relaxation asymmetric new positive definite and skew-self-conjugate splitting,SANPSS),M(α,β,ω)是其迭代矩陣。

引理2ANPSS迭代式(5)的迭代矩陣M(α,β)與SANPSS迭代式(27)的迭代矩陣M(α,β,ω)的關(guān)系為

(30)

證明先對M(α,β,ω)變形運(yùn)算可得

M(α,β,ω)

(31)

再對ωI+(2-ω)M(α,β)變形運(yùn)算可得

ωI+(2-ω)M(α,β)

=ωI+(2-ω)(βP+S)-1(βP-R)(αP+
R)-1(αP-S)

(32)

對比式(31)和式(32)可知,式(30)成立。證畢。

于是,關(guān)于SANPSS迭代的收斂性有如下結(jié)果。

證明根據(jù)引理2有

(33)

設(shè)迭代矩陣M(α,β)、M(α,β,ω)的任意一個右特征主值分別為γj和μj,則由式(33)有

(34)

當(dāng)ω≥0時,利用式(34)可得

(35)

又根據(jù)定理1和式(35)有

(36)

因此有

(37)

由式(37)可知,要使ψ[M(α,β,ω)]<1,只要不等式[式(38)]成立

(38)

求解式(38)并結(jié)合ω≥0可得

(39)

此時,再根據(jù)推論和式(39)可知,當(dāng)條件①或②成立時,必有ψ[M(α,β,ω)]<1,證畢。

4 算法實現(xiàn)

設(shè)四元數(shù)矩陣X=X1+X2j∈Qm×n,記

(40)

式(40)中:Xσ為X的復(fù)表示矩陣。

利用四元數(shù)矩陣的復(fù)表示及其運(yùn)算性質(zhì),ANPSS迭代式(5)和SANPSS迭代式(27)均可轉(zhuǎn)化成復(fù)數(shù)域C上等價的迭代,則有

(Xσ)(k+1)=[M(α,β)]σ(Xσ)(k)+
[N(α,β)]σ

(41)

(Xσ)(k+1)=[M(α,β,ω)]σ(Xσ)(k)+
[N(α,β,ω)]σ

(42)

式中:(·)σ為四元數(shù)矩陣(·)的復(fù)表示矩陣。

ANPSS迭代(5)和SANPSS迭代(27)分別給出M(α,β)、N(α,β)和M(α,β,ω)、N(α,β,ω)。

(43)

式(43)中:‖?‖F(xiàn)為F范數(shù)。

5 數(shù)值示例

對所提方法進(jìn)行數(shù)值實驗,并將ANPSS和SANPSS迭代與文獻(xiàn)[17]中的NPSS迭代進(jìn)行比較與分析,以檢驗所提方法的有效性。

假設(shè)迭代步數(shù)為IT,運(yùn)算滿足收斂要求所需時間記為CPU(以s為單位),矩陣的階數(shù)為n,并選取初始迭代矩陣為單位矩陣,即X=I。

在數(shù)值實驗中,所有的迭代實驗都在個人計算機(jī)上的MATLAB(R2022a)中運(yùn)行,并且當(dāng)?shù)`差ERR滿足ERR<10-8或者迭代次數(shù)超過500次時終止。

示例1給定下列n階矩陣,其中矩陣A是亞正定矩陣,矩陣B是四元數(shù)矩陣。

式中:A11=24-25k,A12=-3+12i-4j+6k,A21=-3+4i-14j-6k,A22=24-25k,A(n-1)n=-3+12i-4j+6k,An(n-1)=-3+4i-14j-6k,Ann=24-25k,i、j、k為虛數(shù)單位;

用SANPSS迭代求解式(1)。

解 首先求出矩陣A的自共軛分支R,斜自共軛分支S和矩陣B的復(fù)分解矩陣,即

R=R1+R2j,S=S1+S2j,B=B1+B2j

(44)

式(44)中:

其次選擇自共軛正定矩陣P。

(45)

式(45)中:P12=1+3i+3j+3k,P21=1-3i-3j-3k,P(n-1)n=1+3i+3j+3k,Pn(n-1)=1-3i-3j-3k。

P的復(fù)分解矩陣為P=P1+P2j,其中,

分別利用文獻(xiàn)[17]中的NPSS迭代方法和迭代格式[式(41)、式(42)]對方程組進(jìn)行求解。其中,NPSS迭代中選取的α、ω滿足文獻(xiàn)[17]中的選取條件,ANPSS迭代所選取的α、β滿足推論的條件[式(13)],SANPSS迭代中所選取的α、β、ω滿足定理2的條件①,則對于不同階數(shù)的矩陣,3種迭代方法的計算結(jié)果如表1～表3所示。

表1 NPSS方法不同階數(shù)的迭代結(jié)果(示例1)Table 1 Iterative results of different orders of NPSS method(example 1)

表1、表2、表3分別為示例1中NPSS迭代、ANPSS迭代和SANPSS迭代的收斂次數(shù)、收斂時間以及迭代誤差。表1和表2的實驗結(jié)果表明,ANPSS迭代的收斂速度比NPSS迭代的收斂速度快。表2和表3的實驗結(jié)果表明,當(dāng)選擇合適的參數(shù)時,SANPSS迭代比ANPSS迭代有較快的收斂速度,以及較少的迭代次數(shù),即SANPSS迭代起到加速收斂的效果,效果如圖1、圖2所示。

圖1 當(dāng)n=50、500時不同方法的迭代收斂情況(示例1)Fig.1 When n=50, 500 the iterative convergence diagram of different methods(example 1)

圖2 不同矩陣階數(shù)下NPSS、ANPSS、SANPSS方法的迭代時間對比(示例1)Fig.2 Comparison of iteration times of NPSS, ANPSS, and SANPSS methods under different matrix orders(example 1)

表2 ANPSS方法不同階數(shù)的迭代結(jié)果(示例1)Table 2 Iterative results of different orders of ANPSS method(example 1)

表3 SANPSS方法不同階數(shù)的迭代結(jié)果(示例1)Table 3 Iterative results of different orders of SANPSS method(example 1)

圖1(a)展示了示例1取n=50的情況下,NPSS迭代、ANPSS迭代和SANPSS迭代的迭代誤差隨著迭代次數(shù)的變化趨勢。可以看出,SANPSS迭代方法的殘差下降曲線位于NPSS迭代方法、ANPSS迭代方法的殘差下降曲線之下。說明了SANPSS迭代比NPSS迭代、ANPSS迭代的迭代次數(shù)更少,迭代時間更短。圖1(b)說明當(dāng)系數(shù)矩陣的規(guī)模較大時,SANPSS迭代仍比NPSS迭代和ANPSS迭代都有更高的收斂效率。

圖2展示了示例1在不同矩陣階數(shù)的情況下,NPSS方法、ANPSS方法和SANPSS方法的迭代時間變化趨勢圖。可以看出,隨著矩陣階數(shù)變大,SANPSS迭代比NPSS迭代、ANPSS迭代所需時間更短,對比更明顯。

示例2考慮如下大型結(jié)構(gòu)系統(tǒng)的迭代求解問題,其中矩陣A是亞正定矩陣,矩陣B是四元數(shù)矩陣。

式中:A11=16.5+5i,A12=-1+2j,A21=-1-2i-2.4k,A22=16.5+5i,A(n-1)n=-1+2j,An(n-1)=-1-2i-2.4k,Ann=16.5+5i;

用SANPSS迭代求解。

解 先求出矩陣A的自共軛分支R,斜自共軛分支S和矩陣B的復(fù)分解矩陣,即

其次,選擇自共軛正定矩陣P。

式中:P12=0.8+3i+3j+3k,P21=0.8-3i-3j-3k,P(n-1)n=0.8+3i+3j+3k,Pn(n-1)=0.8-3i-3j-3k。

其復(fù)分解矩陣為

分別利用文獻(xiàn)[17]中的NPSS方法和迭代格式[式(41)、式(42)]求解方程組。其中,NPSS迭代中選取的α,ω滿足文獻(xiàn)[17]中的選取條件,ANPSS迭代所選取的α、β滿足推論的條件[式(14)], SANPSS迭代方法中所選取的α、β、ω滿足定理2的條件②。則對于不同階數(shù)的矩陣,3種迭代方法的計算結(jié)果如表4～表6所示。

表4 NPSS方法不同階數(shù)的迭代結(jié)果(示例2)Table 4 Iterative results of different orders of NPSS method(example 2)

表4～表6分別給出示例2中不同矩陣階數(shù)下,NPSS迭代、ANPSS迭代和SANPSS迭代的收斂次數(shù)、收斂時間以及迭代誤差。表4和表5的實驗結(jié)果顯示,ANPSS的收斂速度比NPSS的收斂速度快。表5和表6的實驗結(jié)果表明,當(dāng)選擇合適的參數(shù)時,SANPSS迭代比ANPSS迭代收斂速度快,迭代次數(shù)也較少,即也說明SANPSS迭代起到了加速收斂的作用。效果如圖3、圖4所示。

圖3 當(dāng)n=50、500時NPSS、ANPSS、SANPSS方法的迭代收斂情況圖(示例2)Fig.3 When n=50, 500, iterative convergence of NPSS, ANPSS, SANPSS methods(example 2)

圖4 不同矩陣階數(shù)下NPSS、ANPSS、SANPSS方法的迭代時間對比(示例2)Fig.4 Comparison of iteration times of NPSS, ANPSS, and SANPSS methods under different matrix orders(example 2)

表5 ANPSS方法不同階數(shù)的迭代結(jié)果(示例2)Table 5 Iterative results of different orders of ANPSS method(example 2)

表6 SANPSS方法不同階數(shù)的迭代結(jié)果(示例2)Table 6 Iterative results of different orders of SANPSS method(example 2)

在圖3(a)、圖3(b)中,SANPSS迭代方法的迭代收斂曲線位于NPSS迭代方法、ANPSS迭代方法的迭代收斂曲線之下,即說明SANPSS迭代方法在計算上所需迭代次數(shù)更少,所用時間更短。同時,通過對比圖3(a)和圖3(b)可知,當(dāng)矩陣階數(shù)較大時,SANPSS迭代方法展現(xiàn)的優(yōu)勢更明顯。

從圖4可以看出,SANPSS迭代方法的迭代時間曲線位于NPSS迭代方法、ANPSS迭代方法的迭代時間曲線之下。說明隨著矩陣階數(shù)的不斷增大,SANPSS迭代比NPSS迭代、ANPSS迭代所需的迭代時間更短。

綜合示例1和示例2,當(dāng)滿足定理2的條件①或條件②時,選擇適當(dāng)?shù)摩?、β、ω參?shù),SANPSS迭代有一定程度的改進(jìn)效果。

6 結(jié)論

討論四元數(shù)亞正定系統(tǒng)的混參分裂迭代求解問題。首先,在NPSS迭代基礎(chǔ)上,通過引入新的參數(shù),構(gòu)建出雙參ANPSS迭代,然后運(yùn)用四元數(shù)矩陣特征值理論,獲得該迭代收斂的參數(shù)選取方法。同時利用超松弛加速技術(shù),提出了混參SANPSS迭代,并討論該迭代與ANPSS迭代的關(guān)聯(lián)性,從而獲得其參數(shù)選取方法。運(yùn)用四元數(shù)矩陣的復(fù)表示,在MATLAB環(huán)境下實現(xiàn)方程的求解。數(shù)值算例表明,當(dāng)選擇適當(dāng)?shù)膮?shù)時,SANPSS迭代比ANPSS具有更高的收斂效率。所提的ANPSS迭代和SANPSS迭代均較大程度改進(jìn)了相關(guān)文獻(xiàn)的結(jié)果。