四元數亞正定系統混參分裂迭代方法

張燕婷, 黃敬頻

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

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

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

1 ANPSS迭代構建

大規模線性方程組的求解,常常出現在科學與工程計算領域。在四元數體上考慮如式(1)所示的大型結構系統的迭代求解問題。

AX=B

(1)

(2)

為提高NPSS迭代中參數選取的靈活性,引進新參數β>0,并構建如式(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迭代進行收斂性分析,并給出收斂因子的上界。

引理1[19]矩陣A∈Qn×n的譜值半徑ψ(A)不超過其任意一種相容范數。特別地當A是正規矩陣時有ψ(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)

證畢。

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

(13)

(14)

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

(15)

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

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

(16)

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

(17)

(18)

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

(19)

又根據式(12)可知,

(20)

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

(21)

(22)

3 廣義超松弛迭代

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

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

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)

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

(25)

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

(26)

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

顯然,當ω=0時,式(25)即為式(24),迭代式(26)正是ANPSS迭代;當ω=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(α,β,ω)的關系為

(30)

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

M(α,β,ω)

(31)

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

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

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

(32)

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

于是,關于SANPSS迭代的收斂性有如下結果。

證明根據引理2有

(33)

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

(34)

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

(35)

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

(36)

因此有

(37)

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

(38)

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

(39)

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

4 算法實現

設四元數矩陣X=X1+X2j∈Qm×n,記

(40)

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

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

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

(41)

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

(42)

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

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

(43)

式(43)中:‖?‖F為F范數。

5 數值示例

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

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

在數值實驗中,所有的迭代實驗都在個人計算機上的MATLAB(R2022a)中運行,并且當迭代誤差ERR滿足ERR<10-8或者迭代次數超過500次時終止。

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

式中: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為虛數單位;

用SANPSS迭代求解式(1)。

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

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的復分解矩陣為P=P1+P2j,其中,

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

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

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

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

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

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

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

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

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

示例2考慮如下大型結構系統的迭代求解問題,其中矩陣A是亞正定矩陣,矩陣B是四元數矩陣。

式中: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的復分解矩陣,即

其次,選擇自共軛正定矩陣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。

其復分解矩陣為

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

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

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

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

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

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

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

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

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

綜合示例1和示例2,當滿足定理2的條件①或條件②時,選擇適當的α、β、ω參數,SANPSS迭代有一定程度的改進效果。

6 結論

討論四元數亞正定系統的混參分裂迭代求解問題。首先,在NPSS迭代基礎上,通過引入新的參數,構建出雙參ANPSS迭代,然后運用四元數矩陣特征值理論,獲得該迭代收斂的參數選取方法。同時利用超松弛加速技術,提出了混參SANPSS迭代,并討論該迭代與ANPSS迭代的關聯性,從而獲得其參數選取方法。運用四元數矩陣的復表示,在MATLAB環境下實現方程的求解。數值算例表明,當選擇適當的參數時,SANPSS迭代比ANPSS具有更高的收斂效率。所提的ANPSS迭代和SANPSS迭代均較大程度改進了相關文獻的結果。