基于矩陣半張量積求解四元數(shù)Toeplitz線性系統(tǒng)

李 瑩,王玉珊,丁文旭,韋安麗

(聊城大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山東 聊城 252059)

近年來, Toeplitz矩陣已經(jīng)成為科學(xué)研究中較為熱門的一類特殊矩陣, 它被廣泛應(yīng)用于眾多科學(xué)領(lǐng)域, 如數(shù)字信號(hào)處理、數(shù)字圖像處理、排隊(duì)網(wǎng)絡(luò)、數(shù)值分析、微分方程數(shù)值解等[1]. 在數(shù)字信號(hào)處理方面, 應(yīng)用Toeplitz矩陣的特殊結(jié)構(gòu), 將共軛Toeplitz結(jié)構(gòu)和中央對(duì)稱Toeplitz結(jié)構(gòu)納入?yún)f(xié)方差模型中, 設(shè)計(jì)了一種基于MOS(model order selection)理論的先分類再檢測(cè)的檢測(cè)體系, 來判斷接收到的回波信號(hào)中是否有目標(biāo)[2]. 在數(shù)字圖像處理方面, 將圖像退化的過程等價(jià)為傳輸函數(shù)和噪聲對(duì)原始圖像矩陣進(jìn)行線性變換, 而圖像恢復(fù)過程等價(jià)為當(dāng)傳輸函數(shù)可分離時(shí), 將最小二乘問題轉(zhuǎn)化為Toeplitz矩陣的求逆[3]. 利用系數(shù)矩陣Toeplitz的性質(zhì)打破了在電磁法理論研究中一維理論以及積分方程方法存在的局限性, 使傳統(tǒng)積分方程方法中遇到的稠密矩陣的存儲(chǔ)困境得到了有效解決. 同時(shí), 利用其所具有的特殊性質(zhì), 用快速傅里葉變換實(shí)現(xiàn)了迭代算法中的矩陣向量乘積, 加速了傳統(tǒng)積分方程技術(shù)中直接求矩陣向量乘積的過程[4]. 此外, 針對(duì)Toeplitz矩陣特征值的漸近行為, 給出了其在時(shí)間序列分析中的應(yīng)用[5]. 利用上三角Toeplitz矩陣分別給出了常系數(shù)線性微分方程和差分方程特解的表達(dá)式, 這對(duì)求解常系數(shù)線性微分方程和差分方程帶來了極大的方便[6-7]. 由此可見, 對(duì)Toeplitz矩陣的研究具有重要的應(yīng)用價(jià)值.

作為一類特殊的矩陣, 對(duì)以Toeplitz矩陣為系數(shù)矩陣的線性方程組的求解問題, 以及怎樣用計(jì)算機(jī)來實(shí)現(xiàn)算法是主要研究方向之一[8]. 研究方法分為兩大類：直接法[9]、迭代法.文獻(xiàn)[10]提出了通過分裂Toeplitz矩陣迭代求解線性方程組的HSS方法(skew-Hermitian splitting). 文獻(xiàn)[11]提出了將Toeplitz矩陣分裂成一個(gè)循環(huán)和一個(gè)反循環(huán)矩陣, 再進(jìn)行雙步迭代求解的CSCS(circulant and skew circulant splitting)方法. 文獻(xiàn)[12]提出了將CSCS方法中一個(gè)參數(shù)形式改進(jìn)成為兩個(gè)參數(shù)形式的ACSCS(accelerated circulant and skew circulant splitting)方法. Toeplitz系統(tǒng)求解的最新研究進(jìn)展參見文獻(xiàn)[13]. 論文將基于矩陣半張量積,提出一種新的研究四元數(shù)上三角Toeplitz線性系統(tǒng)求解的直接方法.

問題1設(shè)A∈TQn×n, 令

S={x|x∈n,Ax=b}，

1 預(yù)備知識(shí)

定義1[14]設(shè)M∈m×n,U∈p×q,則

其中：t為n與p的最小公倍數(shù), 當(dāng)n=p時(shí), 矩陣半張量積轉(zhuǎn)化為普通矩陣乘積.

引理1[14]設(shè)x∈m,y∈n, 則

x×y=x?y.

注矩陣半張量積是普通矩陣乘積的推廣, 具備普通矩陣乘積所具備的性質(zhì). 相較于普通矩陣乘積, 學(xué)者在矩陣半張量積可交換性方面的研究有著重要的突破.

引理2[14]設(shè)x∈t,A為任意矩陣, 則

x×A=(It?A)×x.

定義2[14]定義換位矩陣

直接計(jì)算即可檢驗(yàn)換位矩陣的如下性質(zhì)

借助于換位矩陣, 可以對(duì)矩陣半張量積中的兩向量因子的順序進(jìn)行交換.

引理3[14]設(shè)x∈m,y∈n, 則

W[m,n]×x×y=y×x,(x)T×(y)T×W[m,n]=(y)T×(x)T.

MF稱為F的結(jié)構(gòu)矩陣.

引理4[16]設(shè)A∈m×n,b∈m,當(dāng)且僅當(dāng)AA?b=b時(shí)，線性方程組Ax=b有解，且通解表示形式為x=A?b+(In-A?A)y,?y∈n.

2 四元數(shù)矩陣的實(shí)向量表示

定義4[17]設(shè)q=q1+q2i+q3j+q4k∈, 其中：qi∈(i=1,2,3,4), 并且基底的乘積滿足

i2=j2=k2=-1,ij=-ji=k,jk=-kj=i,ki=-ik=j.

定義5設(shè)四元數(shù)a=a1+a2i+a3j+a4k∈, 稱

vE(a)=(a1,a2,a3,a4)T

為四元數(shù)a的實(shí)向量表示.

根據(jù)定義5, 知兩個(gè)四元數(shù)乘積的實(shí)向量表示可以轉(zhuǎn)化為兩個(gè)四元數(shù)的實(shí)向量表示與四元數(shù)乘積的結(jié)構(gòu)矩陣的矩陣半張量積運(yùn)算, 即引理5.

引理5[18]設(shè)l,m∈, 則

vE(lm)=MQ×vE(l)×vE(m),

定義6設(shè)xT,y∈n, 稱

vE(x)=((vE(x1))T,(vE(x2))T,…,(vE(xn))T)T,

vE(y)=((vE(y1))T,(vE(y2))T,…,(vE(yn))T)T

為四元數(shù)向量x，y的實(shí)向量表示.

(2) ‖x‖=‖vE(x)‖;

證明(1)，(2)容易驗(yàn)證, 僅對(duì)(3)進(jìn)行證明.

設(shè)x=(x1,x2,…,xn),y=(y1,y2,…,yn)T, 則

vE(xy)=vE(x1y1+…+xnyn)=vE(x1y1)+…+vE(xnyn)=

MQ×[vE(x1)×vE(y1)+…+vE(xn)×vE(yn)]=

(3)得證.

借助于四元數(shù)向量的實(shí)向量表示, 給出四元數(shù)矩陣的實(shí)向量表示的定義及性質(zhì).

定義7設(shè)A∈m×n, Colj(A),Rowi(A)分別代表四元數(shù)矩陣A的第j列與第i行,j=1,2,…,n,i=1,2,…,m, 分別稱

為四元數(shù)矩陣A的實(shí)列排與實(shí)行排.

證明(1)～(3)易檢驗(yàn), 僅對(duì)(4)進(jìn)行證明. 首先, 將矩陣A按行分塊如下

可以得到Ax=(Row1(A)x,Row2(A)x,…,Rowm(A)x)T, 則

3 問題1的代數(shù)解

定理3設(shè)

則

其中

定理4設(shè)A∈TQn×n,x∈n, 則問題1中解的集合S可以表示為

S={x|x∈n,vE(x)=L?vE(b)+(I4n-L?L)y,?y∈4n},

(1)

vE(xL)=L?vE(b).

(2)

證明根據(jù)定理1，3, 可得

所以,有

‖Ax-b‖=0?‖LvE(x)-vE(b)‖=0?LvE(x)=vE(b).

對(duì)于實(shí)矩陣方程LvE(x)=vE(b), 利用引理4, 即得(1)，(2)式.

推論設(shè)A∈TQn×n,x∈n, 則四元數(shù)上三角Toeplitz線性系統(tǒng)Ax=b有解的充要條件為

(LL?-I4n)vE(b)=0.

(3)

證明利用定理4的證明過程, 可得

‖Ax-b‖=‖LvE(x)-vE(b)‖=

‖LL?LvE(x)-vE(b)‖=‖LL?vE(b)-vE(b)‖=‖(LL?-I4n)vE(b)‖,

則

‖Ax-b‖=0?‖(LL?-I4n)vE(b)‖=0?(LL?-I4n)vE(b)=0，

從而(3)式得證.

4 算法與數(shù)值算例

算法(問題1) 設(shè)四元數(shù)上三角Toeplitz線性系統(tǒng)Ax=b相容，該算法用于計(jì)算極小范數(shù)解.

(2) 輸入F,G,J, 輸出L;

(3) 根據(jù)(2)計(jì)算Ax=b的極小范數(shù)解xL.

算例

在MATLAB中, 借助‘rand’函數(shù)隨機(jī)生成兩個(gè)向量, 通過‘Toeplitz’ ‘triu’ 函數(shù)構(gòu)造出上三角Toeplitz矩陣Ai與實(shí)向量xi(i=1,2,3,4), 借助四元數(shù)工具包生成四元數(shù)矩陣A∈TQn×n與四元數(shù)向量x∈n,計(jì)算b=Ax.利用該算法計(jì)算得到四元數(shù)上三角Toeplitz線性方程Ax=b的極小范數(shù)解xL, 將其與真實(shí)解x進(jìn)行比較, 令ε=log10‖xL-x‖, 則ε在不同規(guī)模的系統(tǒng)下的值如圖1所示.從圖1可以看出, 所得到的誤差數(shù)量級(jí)均小于-12, 從而驗(yàn)證了該算法的有效性.

圖1 不同規(guī)模系統(tǒng)下的誤差的數(shù)量級(jí)