2PPJ迭代收敛的充要条件

高树玲，畅大伟

(1.周口师范学院 数学与统计学院，河南 周口 466001;2.陕西师范大学 数学与信息科学学院, 陕西 西安 710062)

近十几年来,并行算法的应用越来越广泛，所以并行算法的研究成为国内外许多学者的研究课题,并且已经取得较多的成果.对一些迭代方法,如Jacobi迭代方法虽然收敛性比较慢,但很适合用于并行算法的运算,因而从总体效果而言,反而比一些收敛速度较快的方法还要好一些.基于此, Missirlis于1983年首次提出了并行Jacobi型的方法[1],并在假设Jacobi矩阵的特征值均为实数的条件下对它的收敛性进行了探讨[2].在这里讨论有两个参数的情形,把它称为两参数并行Jacobi迭代方法,简记为2PPJ迭代法,而记Missirlis的方法为1PPJ迭代方法.

对线性方程组

Ax=b

(1)

的迭代格式

x(s+1)=x(s)-ωM-1(Ax(s)-f),s=0,1,….

(2)

M-1=(I+τJ)D-1代入到式(2)中即得2PPJ格式

x(s+1)=x(s)-ω(I+τJ)D-1(Ax(s)-f)，s=0,1,….

(3)

而ω=τ时,它就是1PPJ格式.式(3)中的迭代矩阵如下

Gω,τ=I-ω(I+τJ)D-1A=I-ω(I+τJ)(I-J)=(1-ω)I+ω[(1-τ)I+τJ]J=(1-ω)I+ωTτ这里

Tτ=[(1-τ)I+τJ]J.

(4)

故Gω,τ为Tτ的外插迭代矩阵,外插的参数为ω.本文正是根据这一点来讨论当线性方程组(1)的Jacobi矩阵的特征值为复数且它的实部和虚部的模相等情况下2PPJ迭代收敛范围问题.得出在此种条件下2PPJ迭代收敛的一个充分必要条件.

1 预备知识

引理1[3]设

G=(1-ω)I+ωT(其中ω为实数)，为T的外插迭代矩阵，矩阵T的特征值tj(j=1,2,…,n)的实部为xj,虚部为yj，即tj=xj+iyj，则存在ω使ρ(Gω)<1的充要条件为

xj<1(∀j),或xj>1(∀j).

引理2[4]在引理1的条件下，若xj<1(∀j),则ρ(Gω)<1当且仅当

而若xj>1(∀j)， 则ρ(Gω)<1当且仅当

2 主要结果

定理1 若线性方程组(1)中的系数矩阵A的Jacobi迭代矩阵J的特征值μj(j=1,2,…,n)的实部和虚部的模相等，设μj=aj±iaj(j=1,2,…,n) (aj∈R)，则迭代格式(3)的迭代矩阵

Gω,τ=(1-ω)I+ωTτ,

迭代收敛的充分必要条件为

10若对任意的j,μj的实部aj=0,即对任意的j,μj=0,则

τ∈R,0<ω<2.

20若μj的实部aj的值满足aj1>0(j1=1,2,…,k)，aj2<0(j2=k+1,k+2,…,n)或aj取值满足

aj1>0(j1=1,2,…,l)，aj2<0(j2=l+1,l+2,…,m),aj3=0(j3=m+1,m+2,…,n).则

NR,NL分别表示使aj取值大于0及小于0的所有j的集合.

证设Tτ的特征值tj=xj+iyj,则由引理1和引理2Tτ的特征值tj和J的特征值μj之间存在关系式

tj=(1-τ)J+τJ2,

把tj=xj+iyj和μj=aj±iaj代入上式有

整理则可得到

由两复数相等可得以下关系式

由于Gω,τ=(1-ω)I+ωTτ为Tτ的外插迭代矩阵,有引理1可得Gω,τ收敛的充分必要条件为：对任意的j有xj<1或对任意的j有xj>1成立.

下面就这两种情形分别进行讨论

I)当对任意的j,xj<1,即(1-τ)aj<1时.

a)若aj=0(j=1,2,…,k),则任意τ∈R有(1-τ)aj<1成立,此时xj=yj=0,所以有

c)若

此时把xj=(1-τ)aj代入仍然有

1)对任意的j,aj的值都等于0,即μj=0(j=1,2,…,n),从而由引理1及引理2和上述的讨论a),Gω,τ收敛的充分必要条件是

τ∈R,0<ω<2.

2)aj的值有大于0也有小于0的情况下,由引理1及上面的讨论b)c)从而有Gω,τ收敛的充分必要条件是

而根据引理2有ω的范围为

3)aj的值有大于0的亦有小于0的同时有等于0的情况下,此时根据引理1及上述的讨论a)b)c),Gω,τ收敛的充分必要条件是

II)当对任意的j,xj>1即(1-τ)aj>1时，有aj≠0,此时只有aj>0和aj<0两种情况.

综合I)、II)，有定理1结论成立.

定理1证毕.

3 相关数值例子

例1 若线性方程组Ax=b的系数矩阵

A的Jacobi迭代矩阵的特征值为1±i,-1±i满足定理1中的条件,并且容易算出τ的收敛性范围为(0,2).给定τ的一些取值,计算出相应的ω的收敛范围,并且给出一些收敛和不收敛的数值例子来验证定理1的结论如表1.

其中系数矩阵A是相容次序矩阵，并且此矩阵的Jacobi迭代不收敛(ρ(J)=1.414)，但在某一定的范围内2PPJ迭代是收敛的，说明在定理1的条件下2PPJ迭代方法明显要比Jacobi迭代方法优越，而定理1只要求Jacobi迭代矩阵的特征值满足实部和虚部的模相等.而不一定要求线性方程组的系数矩阵A是相容次序矩阵.下面再用一非相容次序矩阵的例子来对该定理作进一步说明.

例2 若线性方程组Ax=b的系数矩阵为

表1 相容次序矩阵下定理1中收敛范围的验证

表2 非相容次序矩阵下定理1中收敛范围的验证

本例中线性方程组的系数矩阵不是相容次序矩阵且该矩阵的Jacobi迭代是收敛的(ρ(J)=0.707)，可以看到在某一定范围内2PPJ迭代依然是收敛的，并且从表2的第三行可以看出当τ，ω适当取值时，2PPJ迭代的收敛速度明显比Jacobi迭代的收敛速度要快很多，从而又从另一方面进一步说明了2PPJ迭代法的优越性.