2PPJ迭代收斂的充要條件

高樹玲，暢大偉

(1.周口師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 周口 466001;2.陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院, 陜西 西安 710062)

近十幾年來,并行算法的應(yīng)用越來越廣泛，所以并行算法的研究成為國(guó)內(nèi)外許多學(xué)者的研究課題,并且已經(jīng)取得較多的成果.對(duì)一些迭代方法,如Jacobi迭代方法雖然收斂性比較慢,但很適合用于并行算法的運(yùn)算,因而從總體效果而言,反而比一些收斂速度較快的方法還要好一些.基于此, Missirlis于1983年首次提出了并行Jacobi型的方法[1],并在假設(shè)Jacobi矩陣的特征值均為實(shí)數(shù)的條件下對(duì)它的收斂性進(jìn)行了探討[2].在這里討論有兩個(gè)參數(shù)的情形,把它稱為兩參數(shù)并行Jacobi迭代方法,簡(jiǎn)記為2PPJ迭代法,而記Missirlis的方法為1PPJ迭代方法.

對(duì)線性方程組

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)

而ω=τ時(shí),它就是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τ的外插迭代矩陣,外插的參數(shù)為ω.本文正是根據(jù)這一點(diǎn)來討論當(dāng)線性方程組(1)的Jacobi矩陣的特征值為復(fù)數(shù)且它的實(shí)部和虛部的模相等情況下2PPJ迭代收斂范圍問題.得出在此種條件下2PPJ迭代收斂的一個(gè)充分必要條件.

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

引理1[3]設(shè)

G=(1-ω)I+ωT(其中ω為實(shí)數(shù))，為T的外插迭代矩陣，矩陣T的特征值tj(j=1,2,…,n)的實(shí)部為xj,虛部為yj，即tj=xj+iyj，則存在ω使ρ(Gω)<1的充要條件為

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

引理2[4]在引理1的條件下，若xj<1(?j),則ρ(Gω)<1當(dāng)且僅當(dāng)

而若xj>1(?j)， 則ρ(Gω)<1當(dāng)且僅當(dāng)

2 主要結(jié)果

定理1 若線性方程組(1)中的系數(shù)矩陣A的Jacobi迭代矩陣J的特征值μj(j=1,2,…,n)的實(shí)部和虛部的模相等，設(shè)μj=aj±iaj(j=1,2,…,n) (aj∈R)，則迭代格式(3)的迭代矩陣

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

迭代收斂的充分必要條件為

10若對(duì)任意的j,μj的實(shí)部aj=0,即對(duì)任意的j,μj=0,則

τ∈R,0<ω<2.

20若μj的實(shí)部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的集合.

證設(shè)Tτ的特征值tj=xj+iyj,則由引理1和引理2Tτ的特征值tj和J的特征值μj之間存在關(guān)系式

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

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

整理則可得到

由兩復(fù)數(shù)相等可得以下關(guān)系式

由于Gω,τ=(1-ω)I+ωTτ為Tτ的外插迭代矩陣,有引理1可得Gω,τ收斂的充分必要條件為：對(duì)任意的j有xj<1或?qū)θ我獾膉有xj>1成立.

下面就這兩種情形分別進(jìn)行討論

I)當(dāng)對(duì)任意的j,xj<1,即(1-τ)aj<1時(shí).

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

c)若

此時(shí)把xj=(1-τ)aj代入仍然有

1)對(duì)任意的j,aj的值都等于0,即μj=0(j=1,2,…,n),從而由引理1及引理2和上述的討論a),Gω,τ收斂的充分必要條件是

τ∈R,0<ω<2.

2)aj的值有大于0也有小于0的情況下,由引理1及上面的討論b)c)從而有Gω,τ收斂的充分必要條件是

而根據(jù)引理2有ω的范圍為

3)aj的值有大于0的亦有小于0的同時(shí)有等于0的情況下,此時(shí)根據(jù)引理1及上述的討論a)b)c),Gω,τ收斂的充分必要條件是

II)當(dāng)對(duì)任意的j,xj>1即(1-τ)aj>1時(shí)，有aj≠0,此時(shí)只有aj>0和aj<0兩種情況.

綜合I)、II)，有定理1結(jié)論成立.

定理1證畢.

3 相關(guān)數(shù)值例子

例1 若線性方程組Ax=b的系數(shù)矩陣

A的Jacobi迭代矩陣的特征值為1±i,-1±i滿足定理1中的條件,并且容易算出τ的收斂性范圍為(0,2).給定τ的一些取值,計(jì)算出相應(yīng)的ω的收斂范圍,并且給出一些收斂和不收斂的數(shù)值例子來驗(yàn)證定理1的結(jié)論如表1.

其中系數(shù)矩陣A是相容次序矩陣，并且此矩陣的Jacobi迭代不收斂(ρ(J)=1.414)，但在某一定的范圍內(nèi)2PPJ迭代是收斂的，說明在定理1的條件下2PPJ迭代方法明顯要比Jacobi迭代方法優(yōu)越，而定理1只要求Jacobi迭代矩陣的特征值滿足實(shí)部和虛部的模相等.而不一定要求線性方程組的系數(shù)矩陣A是相容次序矩陣.下面再用一非相容次序矩陣的例子來對(duì)該定理作進(jìn)一步說明.

例2 若線性方程組Ax=b的系數(shù)矩陣為

表1 相容次序矩陣下定理1中收斂范圍的驗(yàn)證

表2 非相容次序矩陣下定理1中收斂范圍的驗(yàn)證

本例中線性方程組的系數(shù)矩陣不是相容次序矩陣且該矩陣的Jacobi迭代是收斂的(ρ(J)=0.707)，可以看到在某一定范圍內(nèi)2PPJ迭代依然是收斂的，并且從表2的第三行可以看出當(dāng)τ，ω適當(dāng)取值時(shí)，2PPJ迭代的收斂速度明顯比Jacobi迭代的收斂速度要快很多，從而又從另一方面進(jìn)一步說明了2PPJ迭代法的優(yōu)越性.