求解非奇异-张量方程的加速超松弛算法

2020-03-18孙冯程刘奇龙

贵州师范大学学报（自然科学版） 2020年2期

关键词：迭代法收敛性对角

孙冯程，陈震，刘奇龙

(贵州师范大学数学科学学院，贵州贵阳 550025)

0 引言

m阶n维实张量是包含了nm个实数的多维数组，可以表示为：

其中[n]={1,2,…,n}。记所有m阶n维实张量所构成的集合为 R[m,n]，所有实向量构成的集合为 Rn。近年来，源于科学与工程计算，出现了如下多线性方程组：

(1)

(2)

其中xi表示x的第i个分量。2016年，Ding[1]证明了当b>0，为-张量时，方程(1)有唯一正解，并研究了方程(1)的数值解。2017年，Han[2]提出了求解-张量方程的同伦算法。2017年，Li等[3]运用张量的分裂技术，提出了求解-张量方程的迭代算法，并证明了该算法的全局收敛性和局部-线性收敛性。2018年，Liu等[4]提出了张量的正则分裂，并将求解线性方程的经典迭代方法推广至求解多线性系统上。基于不同形式的正则分裂，提出了求解多线性系统的Jacobi迭代法，Gauss-Seidel迭代法，SOR迭代法，Full迭代法和Newton 迭代法，并对这些算法进行了收敛性分析。

本文继续研究多线性系统的数值算法，所提出的算法有别于文[5]所用的梯度法和文[6]所用的PARAFAC2分解算法。本文则是将求解线性方程组的加速超松弛方法[7]推广到高阶张量方程的情形，提出求解张量方程的加速超松弛方法(简称AOR型方法)，并证明该算法是收敛的。数值例子表明在某些情况下AOR型方法比Jacobi 迭代法，Gauss-Seidel迭代法，SOR 迭代法的收敛速度更快。

1 预备知识

本节给出本文将要用到的定义和符号。首先回顾矩阵-张量乘法和张量的特征值和特征向量。

定义1(矩阵-张量乘法) 设B∈ R[2,n]和∈ R[m,n]，则矩阵B与张量的乘积是一个m阶n维的张量，记为B，其元素定义为：

(3)

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

定义3([4,8,9]) 设∈ R[m,n]，若张量的非对角元素非正，则称为-张量。设=s-，其中为非负张量，若s≥ρ()，则称张量为-张量；若s>ρ()，则称张量为非奇异-张量。

接着介绍优矩阵，行子对角张量和张量左(右)逆的概念。

定义4[9]设∈▯[m,n]，则称矩阵M()∈ R[2,n]是的优矩阵，其元素为：

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)

根据迭代格式(7)，给现求解张量方程(1)的AOR型方法。

算法1求解非奇异-张量的AOR型方法输入:初始值x0,最大迭代次数K,容许误差ε>0,正向量b,非奇异-张量输出:迭代次数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 收敛性分析

本节将证明算法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。

为了讨论参数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)式是正则分列。现设∈ 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 数值实验

本节使用数值算例来说明两个算法的有效性。所有程序在配置为Intel(R)Core(TM)i5-7500 CPU @ 3.40GHz 3.41GHz的台式电脑环境下使用Matlab 2015b编写，涉及到张量计算的部分使用了工具箱Tensor toolbox 2.5[14]。迭代过程中，“IT”表示迭代次数，其不能超过1 000次；“CPU(s)”表示CPU运行时间，迭代的容许误差取为‖其中，算法1所使用的AOR型算法中，不同的参数所对应的实验结果是不同的。

下面的例子4.1可以得到和文[1]中的例子3.1类似的结果，同样有文[4，15]的作者所选用的实例也可以获得类似的结果。