GPSD迭代法的收斂性定理

陳恒新

（華僑大學(xué)數(shù)學(xué)科學(xué)學(xué)院，福建 泉州 362021）

GPSD迭代法的收斂性定理

陳恒新

（華僑大學(xué)數(shù)學(xué)科學(xué)學(xué)院，福建 泉州 362021）

給出了一些易于檢驗(yàn)的廣義的預(yù)條件同時(shí)置換（GPSD）迭代法的收斂性定理.利用這些定理，能夠較容易地判別解線性方程組Ax=f的GPSD迭代法的收斂性.數(shù)值例子證明，定理具有較好的實(shí)用價(jià)值.

線性方程組；GPSD迭代法；PSD迭代法；收斂性

廣義的預(yù)條件同時(shí)置換（GPSD）迭代法包含了PSD迭代法，而PSD迭代法則包含了Jacobi超松弛迭代法（JOR），對(duì)稱超松弛迭代法（SSOR），預(yù)優(yōu)Jacobi迭代法（PJ）等迭代法［1-3］.文［1］在線性方程組系數(shù)矩陣A為相容次序矩陣及A的Jacobi迭代矩陣的特征值μj均為實(shí)數(shù)且＜1的條件下，證明了PSD迭代法收斂的充分必要性定理.文［2］在線性方程組系數(shù)矩陣A為對(duì)稱正定矩陣或非奇異H-陣的情況下，研究了PSD迭代法的收斂性.本文對(duì)GPSD迭代法做進(jìn)一步的研究，給出了一些易于檢驗(yàn)的GPSD迭代法的收斂性定理.

1 GPSD迭代法

設(shè)A=D-E-F是n×n實(shí)矩陣.其中：D是非奇異對(duì)角陣；E是嚴(yán)格下三角陣；F是嚴(yán)格上三角陣.記L-D-1E，U=D-1F，對(duì)角矩陣Ω=diag（ω1，ω2，…，ωn）；T=diag（τ1，τ2，…，τn），τi≠0，i=1，…，n，則矩陣A的Jacobi迭代矩陣為B=D-1E+D-1F=L+U，且記B=［bi，j］.其中：bi，i=0，i=1，2，…，n.

求解線性代數(shù)方程組

的GPSD迭代法為

其GPSD法迭代矩陣為

當(dāng)取T=τI，Ω=ωI時(shí)，GPSD迭代法便成為PSD迭代法［1］.

為了敘述方便，引入如下記法：

（1）記Jacobi迭代矩陣B=［bi，j］，空集為φ，N1⊕N2=1⊕2=N=｛1，2，…，n｝，且N1∩N2=φ，1∩2=φ.

（4）集合K-L=｛i|i∈K而i?L，對(duì)任一n階方陣G=［gi，j］，|G|=［|gi，j|］.

需要說明的是，文中所取數(shù)集N1，1，N2，2皆非空.

2 非負(fù)矩陣的性質(zhì)

定義1 對(duì)于n×n實(shí)矩陣G，M及N，如果M非奇異，并且有M-1≥0和N≥0，則稱G=M-N為矩陣G的正規(guī)分裂.由文［4］定理3.8，定理3.13可得引理1，2.

引理1 設(shè)n×n矩陣G≥0，則I-G非奇異且（I-G）-1≥0的充要條件是ρ（G）＜1.

引理2 設(shè)G=M-N為矩陣G的正規(guī)分裂，且G-1≥0，則ρ（M-1N）＜1.

引理3［5］若A，B為n階方陣，且|B|≤A，則ρ（B）≤ρ（A）.

3 GPSD迭代法的收斂性定理

定理1 設(shè)線性方程組（1）的系數(shù)矩陣A為非奇異H-矩陣，則當(dāng)

證明 因?yàn)锳為非奇異H-矩陣，則有ρ（|B|）＜1，其中|B|=|L|+|U|.又因?yàn)閁為嚴(yán)格上三角矩陣，Ω=diag（ω1，ω2…，ωn）≥0，所以有ρ（ΩU）=0ρ，（Ω|U|）=0.于是有

同理，因L為嚴(yán)格下三角矩陣，故有

|（I-ΩL）-1|≤（I-Ω|L|）-1.

于是有

現(xiàn)記

由式（3）可知

令

則由式（4），（5）有

（i）當(dāng)0＜τi≤1，i=1，2，…，n時(shí)，因0≤ωi≤τi，i=1，2，…，n，令

由于 I-T=diag（1-τ1，1-τ2，…，1-τn）≥0，T-Ω=diag（τ1-ω1，τ2-ω2，…，τn-ωn）≥0，故可知≥0，則有

因?yàn)閨B|≥0ρ，（|B|）＜1，0＜τi≤1，i=1，2，…，n.

所以，由式（11），（12）并據(jù)引理3可得

即GPSD迭代法收斂.

由式（6），（13）可知

于是，由式（15），（17）并據(jù)引理1可知

（G（2））-1=（I-（2I-T）-1T|B|）-1（2I-T）-1≥0.

再由引理2可得

所以，由式（14），（18）并據(jù)引理3可得

此時(shí)，GPSD迭代法也收斂.證畢.

引理4 對(duì)于任意的i∈N1，j∈N2，若i，j∈N-，則恒成立

ri，j=αi+βj+αβji-αβij＜1.

證明 因?yàn)閕，j∈N-，所以有αi+βi=bi＜1，αj+βj=bj＜1，則有0≤βi＜1-αi和0≤αj＜1-βj.于是有αβji＜（1-αi）（1-βj），從而有

ri，j=αi+βj+αβji-αβij＜1.

注1 因定理2（以及定理3）中N1（或1）可在N-（或-）中任取，所以該定理的應(yīng)用性較廣.

證明 若N1=N-，則N2=N+；若N1≠N-，則N2-N+≠φ.因?yàn)閕∈N1?N-，對(duì)j∈N2-N+，有bj＜1，即j∈N-.由引理4可知，ri，j＜1.

據(jù)此及定理?xiàng)l件，可知對(duì)一切i∈N1，j∈N2，有ri，j=αi+βj+αβji-αβij＜1恒成立.所以可得

又由αi+βi=bi＜1，可得

由式（19），（20）可知，1-βj＞0.因此，βj＜1.

否則，｛i|βi＞0，i∈N1｝≠φ，即βi≡0，i∈N1，則取

即|B1|=H-1|B|H，則ρ（|B1|）=ρ（|B|）.

因此，有ρ（|B|）＜1，即矩陣A為非奇異H-矩陣.所以，由定理1可知，當(dāng)

時(shí)，解方程組（1）的GPSD迭代法（2）收斂.同理，對(duì)列也有如下相應(yīng)定理.

定理3 在線性方程組（1）矩陣A的Jacobi迭代矩陣B中任取一1?-.如果對(duì)i∈1，j∈+，成立，則當(dāng)0＜τi＜，0≤ωi≤τi，i=1，2，…，n時(shí)，解方程組（1）的GPSD迭代法（2）收斂.它隱含PSD（0＜τ＜，0≤ω≤τ），SSOR（0＜ω＜2），JOR（0＜τ＜），PJ（0＜ω≤1）等迭代法收斂.

4 數(shù)值例子

因?yàn)閎1=0.6＜1，b2=1.2＞1，b3=1.125＞1，所以N-=｛1｝，N+=｛2，3｝.現(xiàn)取N1=N-則N2=N+，且有α1=0，β1=0.6；α2=0.7，β2=0.5；α3=0.5，β3=0.625.因?yàn)閷?duì)i∈N1=｛1｝，j∈N+=｛3，4｝，有r1，2=0.5+0.7×0.6=0.92＜1，和r1，3=0.625+0.5×0.6=0.925＜1成立

因?yàn)閎1=0.6＜1，b2=0.95＜1，b3=1.2＞1，b4=1.1＞1，所以N-=｛1，2｝，N+=｛2，3｝.又因=1.45＞1，=0.9＜1，=0.6＜1，=0.9＜1，所以=｛2，3，4｝，+=｛1｝.

若直接取N1=N-，N2=N+，因r2，3=0.45+0.5+07×0.5-0.45×0.5=1.075＞1；若取1=，因=0.5+1.45×0.4=1.08＞1.所以，不能用文中定理判別解該方程組之GPSD法的收斂性.但是，由于文中定理的1（或1），可在-（或-）中任取，所以其應(yīng)用性較廣.如在例2中，可取N1=｛1｝?N-，則N2=｛2，3，4｝，α1=0，β1=0.6；α3=0.6，β3=0.6；α4=0.4，β4=0.7.

于是，對(duì)于i∈N1=｛1｝，j∈N+=｛3，4｝，則有r1，3=0.6+0.6×0.6=0.96＜1和r1，4=0.7+0.4×0.6=0.94＜1成立.

［1］陳恒新.關(guān)于PSD迭代法收斂的充分必要性定理［J］.應(yīng)用數(shù)學(xué)與計(jì)算數(shù)學(xué)學(xué)報(bào)，1999，13（1）：11-20.

［2］劉興平.某些迭代方法的收斂性［J］.數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用，1992，13（1）：58-64.

［3］陳恒新.關(guān)于SSOR迭代法和Jacobi迭代法的斂散性［J］.華僑大學(xué)學(xué)報(bào)：自然科學(xué)版，1993，14（1）：20-26.

［4］瓦格RS.矩陣迭代分析［M］.蔣爾雄，等譯.上海：上?？茖W(xué)技術(shù)出版社，1966：41-130.

［5］胡家贛.線性代數(shù)方程組的迭代解法［M］.北京：科學(xué)出版社，1997：18-19.

Convergence Theorem of GPSD lterative Method

CHEN Heng-xin
（School of Mathematical Sciences，Huaqiao University，Quanzhou 362021，China）

Some convergence theorems of GPSD（generalized preconditioned simultaneous displacement）iterative method are obtained in this paper.The convergence of GPSD iterative method for solving linear equationsAx=fcan be easily discriminated by use of these theorems.Two numericial examples are given，that shows these theorems had a good practical value.

linear equations；GPSD iterative method；PSD iterative method；convergence

O 241.6

A

1000-5013（2010）06-0706-05

（責(zé)任編輯：陳志賢 英文審校：張金順，黃心中）

2009-12-16

陳恒新（1956-），男，副教授，主要從事計(jì)算數(shù)學(xué)的研究.E-mail：chenhx@hqu.edu.cn.

福建省自然科學(xué)基金計(jì)劃資助項(xiàng)目（S0650018）