孫馮程，陳 震，劉奇龍

(貴州師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，貴州 貴陽(yáng) 550025)

0 引言

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

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

(1)

(2)

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

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

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

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

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

(B

(3)

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

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

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

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

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

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

行對(duì)角張量具有如下性質(zhì)：

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

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

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

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

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

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

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

2 AOR迭代算法

M()=D-L-U,

(5)

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

(6)

構(gòu)造如下格式：

(7)

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

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

注1. 當(dāng)m=2時(shí)，算法1退化為文[6]中求解線性方程組的加速超松弛方法。當(dāng)m>2時(shí), 若取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]設(shè)=(ai1i2…im)∈ R[m,n]是非奇異-張量，則M()是非奇異-矩陣。

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

證明因?yàn)槭欠瞧娈?張量，由引理2得M()是非奇異-矩陣。又因?yàn)镸()=D-L-U,易知D-rL是-矩陣。結(jié)合引理3，對(duì)于?0

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

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

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

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

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

(8)

和

(9)

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

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

(10)

因?yàn)閞1≤w1， 正如分裂式(8),則有

(11)

結(jié)合(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)

又因?yàn)閞1≤r2，w1≤w2，則有

(13)

(14)

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

(15)

(16)

結(jié)合(8)式可得

(17)

(18)

結(jié)合式(9)得

(19)

又因?yàn)閣2(D-r2L)-1≥0，則有

(20)

4 數(shù)值實(shí)驗(yàn)

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

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

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

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

接下來(lái)的例子中，運(yùn)用了類似文[1]中給出的例子3.2，但是用了文[4,15]中作者修正了的例6.2。

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