孫馮程，陳 震，劉奇龍

(貴州師范大學 數(shù)學科學學院，貴州 貴陽 550025)

0 引言

m階n維實張量是包含了nm個實數(shù)的多維數(shù)組，可以表示為：

其中[n]={1,2,…,n}。記所有m階n維實張量所構成的集合為 R[m,n]，所有實向量構成的集合為 Rn。近年來，源于科學與工程計算，出現(xiàn)了如下多線性方程組：

(1)

(2)

其中xi表示x的第i個分量。2016年，Ding[1]證明了當b>0，為-張量時，方程(1)有唯一正解，并研究了方程(1)的數(shù)值解。2017年，Han[2]提出了求解-張量方程的同倫算法。2017年，Li等[3]運用張量的分裂技術，提出了求解-張量方程的迭代算法，并證明了該算法的全局收斂性和局部-線性收斂性。2018年，Liu等[4]提出了張量的正則分裂，并將求解線性方程的經典迭代方法推廣至求解多線性系統(tǒng)上。基于不同形式的正則分裂，提出了求解多線性系統(tǒng)的Jacobi迭代法，Gauss-Seidel迭代法，SOR迭代法，F(xiàn)ull迭代法和Newton 迭代法，并對這些算法進行了收斂性分析。

本文繼續(xù)研究多線性系統(tǒng)的數(shù)值算法，所提出的算法有別于文[5]所用的梯度法和文[6]所用的PARAFAC2分解算法。本文則是將求解線性方程組的加速超松弛方法[7]推廣到高階張量方程的情形，提出求解張量方程的加速超松弛方法(簡稱AOR型方法)，并證明該算法是收斂的。數(shù)值例子表明在某些情況下AOR型方法比Jacobi 迭代法，Gauss-Seidel迭代法，SOR 迭代法的收斂速度更快。

1 預備知識

本節(jié)給出本文將要用到的定義和符號。首先回顧矩陣-張量乘法和張量的特征值和特征向量。

定義1(矩陣-張量乘法) 設B∈ R[2,n]和∈ R[m,n]，則矩陣B與張量的乘積是一個m階n維的張量，記為B，其元素定義為：

(B

(3)

定義2 設∈ R[m,n]，若存在(λ,x)∈C×(Cn{0})，滿足如下方程：

定義3([4,8,9]) 設∈ R[m,n]，若張量的非對角元素非正，則稱為-張量。設=s-，其中為非負張量，若s≥ρ()，則稱張量為-張量；若s>ρ()，則稱張量為非奇異-張量。

接著介紹優(yōu)矩陣，行子對角張量和張量左(右)逆的概念。

定義4[9]設∈?[m,n]，則稱矩陣M()∈ R[2,n]是的優(yōu)矩陣，其元素為：

M()ij=aij…j,(i,j=1,2,…,n)。

定義5[10]設∈ R[m,n]，則稱m-1階n維張量i(為的行子張量，其中aii2…im=hii2…im。若張量的所有的行子張量1(),…,n()是對角張量，則稱為行對角張量。

行對角張量具有如下性質：

引理1[10]設∈ R[m,n]，則是行對角張量當且僅當=M()。

定義6[4]設=(aii2…im)∈ R[m,n]是行對角張量，且對于?j

定義7[11]設∈ R[m,n]，∈ R[k,n]且=則稱為的一個m階左逆，為的一個k階右逆。

定義8[12]設∈ R[m,n]，若存在一個非空指標子集I?{1,2,…,n}使得

Ai1i2…in=0,?i1∈I,?i2,…,in?I,

下面介紹張量的正則分裂和弱正則分裂。

定義9[4]設,,∈ R[m,n]。如果是左非奇異的，則=-被叫做的一種分裂；若是非奇異的，且M()-1≥0和≥0，則稱為張量的正則分裂；若是非奇異的，且M()-1≥0和M()-1≥0，則稱為張量的弱正則分裂； 若ρ(M()-1)<1，則是一個正則分裂。

2 AOR迭代算法

M()=D-L-U,

(5)

其中D=diag(M()11,M()22,…,M()nn)，L和U分別是嚴格下三角和嚴格上三角矩陣。 基于分裂(5)，張量可分裂為如下形式：

(6)

構造如下格式：

(7)

根據(jù)迭代格式(7)，給現(xiàn)求解張量方程(1)的AOR型方法。

算法1求解非奇異-張量的AOR型方法輸入:初始值x0,最大迭代次數(shù)K,容許誤差ε>0,正向量b,非奇異-張量 輸出:迭代次數(shù)IT和近似解x,迭代時間CPU(s)。輸入:k=1While k

注1. 當m=2時，算法1退化為文[6]中求解線性方程組的加速超松弛方法。當m>2時, 若取w=1,r=0，則算法1退化為文[4]中的Jacobi方法；若取w=1,r=1，則算法1退化為文[4]中的G-S方法; 若取w=r，則算法1退化為文[4]中的SOR方法。

3 收斂性分析

本節(jié)將證明算法1的收斂性。

引理2[4]設=(ai1i2…im)∈ R[m,n]是非奇異-張量，則M()是非奇異-矩陣。

定理1 設=(ai1i2…im)∈ R[m,n]是非奇異-張量，則式(6)是正則分裂。

證明因為是非奇異-張量，由引理2得M()是非奇異-矩陣。又因為M()=D-L-U,易知D-rL是-矩陣。結合引理3，對于?0

引理4[4]設=(ai1i2…im)∈ R[m,n]是一個- 張量，則下列條件等價：

定理2 設=(ai1i2…im)∈ R[m,n]是非奇異-張量，則ρ(r,w)<1。

證明由于=(ai1i2…im)∈ R[m,n]是非奇異-張量，再由定理1可知式(6)是正則分裂，再由引理4可知式(6)是張量的正則收斂分裂，所以ρ(r,w)<1。

為了討論參數(shù)r和w和收斂譜半徑的關系，于是提出了定理3。

定理3 設=(ai1i2…im)∈ R[m,n]是非奇異-張量，且0≤ri≤wi≤1,wi≠0,i=1,2。對于的兩種分裂

(8)

和

(9)

若w1≤w2,r1≤r2，則有下列命題之一成立。

證明對張量兩種的分列，即(8)和(9)，它們的迭代張量分別為r1 ,w1和r2 ,w2。由張量=(ai1i2…im)∈ R[m,n]是非奇異的，所以由引理3知(8)和(9)式是正則分列?，F(xiàn)設∈ R[m,n]是一個全1張量(即其每個元素都是1)，設張量，由于(8)和(9)式是正則分列，則有wi(D-riL)-1≥0和+(wi-ri)+wi(+))≥0，i=1,2。

(10)

因為r1≤w1， 正如分裂式(8),則有

(11)

結合(10)和(11)可得

M()(ρl+(w1-r1)+w1(++(w1-r1)+w1(+))(ρl+(w1-r1)+w1(+))+(w1-r1)+w1(+))+(w1-r1)+w1(++(w1-r1)+w1(+)))xm-1

(12)

又因為r1≤r2，w1≤w2，則有

(13)

(14)

易得M(-r2+(w2-r2)+w2(+))結合(12)得

(15)

(16)

結合(8)式可得

(17)

(18)

結合式(9)得

(19)

又因為w2(D-r2L)-1≥0，則有

(20)

4 數(shù)值實驗

本節(jié)使用數(shù)值算例來說明兩個算法的有效性。所有程序在配置為Intel(R)Core(TM)i5-7500 CPU @ 3.40GHz 3.41GHz的臺式電腦環(huán)境下使用Matlab 2015b編寫，涉及到張量計算的部分使用了工具箱Tensor toolbox 2.5[14]。迭代過程中，“IT”表示迭代次數(shù)，其不能超過1 000次；“CPU(s)”表示CPU運行時間，迭代的容許誤差取為‖其中，算法1所使用的AOR型算法中，不同的參數(shù)所對應的實驗結果是不同的。

下面的例子4.1可以得到和文[1]中的例子3.1類似的結果，同樣有文[4，15]的作者所選用的實例也可以獲得類似的結果。

表1 例4.1的數(shù)值結果Tab.1 Numerical results for example 4.1

注2. 由表1可知，若選取不同的參數(shù)因子r和w(?0≤r≤w≤1且w≠0)，則可以得到不同的結果，由此可以說明AOR型方法求解方程(1)的有效性。與此同時，也表明了AOR型方法的一般性，即Jacobi經典方法，G-S經典方法和SOR經典方法都可以歸結為該方法的特殊情形。

接下來的例子中，運用了類似文[1]中給出的例子3.2，但是用了文[4,15]中作者修正了的例6.2。

表2 例4.2的數(shù)值結果Tab.2 Numerical results for example 4.2