一類(lèi)改進(jìn)的高斯-賽德?tīng)柕ǖ谋容^性定理

黃湧輝

（華南師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，廣東 廣州 510631）

一類(lèi)改進(jìn)的高斯-賽德?tīng)柕ǖ谋容^性定理

黃湧輝

（華南師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，廣東 廣州 510631）

討論了改進(jìn)的高斯-賽德?tīng)柕ǖ氖諗啃?若系數(shù)矩陣為非奇異不可約M-矩陣，則該預(yù)條件下高斯-賽德?tīng)柕ㄊ諗康目炻Q于原高斯-賽德?tīng)柕ㄗV半徑的大小.同樣，在該預(yù)條件下高斯-賽德?tīng)柕ǖ淖V半徑大小與其他高斯-賽德?tīng)柕ǖ淖V半徑大小有關(guān).

譜半徑；預(yù)條件迭代法；非奇異不可約M-矩陣；收斂速度；高斯-賽德?tīng)柕?/p>

考慮線(xiàn)性方程組

其中稱(chēng) M-1N為方程（1）的迭代矩陣，迭代格式（2）是否收斂取決于迭代矩陣 M-1N.

一般地，對(duì)線(xiàn)性方程組（1）的系數(shù)矩陣A做如下的分裂

其中D為非奇異對(duì)角矩陣、L為嚴(yán)格下三角矩陣、U為嚴(yán)格上三角矩陣.

為討論方便，當(dāng)A可逆時(shí)，通過(guò)初等變換把A的對(duì)角元都化簡(jiǎn)為1，因此

對(duì)于形如式（3）的系數(shù)矩陣，Gauss-Seidel迭代法的迭代矩陣為： G =(I -L )-1U.雖然迭代法是求解線(xiàn)性方程組的主要方法，但是當(dāng)系數(shù)矩陣的條件數(shù)較大時(shí)，系數(shù)矩陣對(duì)于求解線(xiàn)性方程組是病態(tài)的，此時(shí)迭代法會(huì)出現(xiàn)不收斂和收斂速度慢的情況；對(duì)于迭代法收斂速度慢的問(wèn)題，采用適當(dāng)?shù)念A(yù)處理技術(shù)，可以使系數(shù)矩陣的特征值分布更加集中，降低矩陣的條件數(shù)，改良矩陣的病態(tài)特性.

線(xiàn)性方程組（1）兩端左乘可逆矩陣 P ∈Rn×n，使方程組等價(jià)地轉(zhuǎn)換為預(yù)條件的方程組

通常稱(chēng)可逆矩陣P為預(yù)處理矩陣（或預(yù)處理因子），則與式（2）對(duì)應(yīng)的基本迭代形式為：

其中 PA = PM -PN是PA的分裂，且PM是可逆的.

本文主要考慮：對(duì)于線(xiàn)性方程組（1），如何選取預(yù)處理矩陣P，使得用Gauss-Seidel迭代法解經(jīng)過(guò)預(yù)處理后的方程組（4）有更快的收斂速度.

考慮用一類(lèi)新的預(yù)處理方法解線(xiàn)性方程組（1），取

用Pα左乘線(xiàn)性方程組（1）的兩邊，得

其中Dα、Lα、Uα分別為Aα的主對(duì)角元，下三角元和上三角元.

此時(shí)，預(yù)條件Gauss-Seidel迭代法的迭代矩陣為

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

定義1[2]33設(shè)則稱(chēng) Zn×n的矩陣A為Z-矩陣；如果A是Z-矩陣，滿(mǎn)足A=sI-B，B≥0，實(shí)數(shù)s＞0且譜半徑 ρ(B)≤ s ，稱(chēng)A是M-矩陣.特別地，當(dāng) ρ(B)＜s 時(shí)，稱(chēng)A為非奇異M-矩陣.

定義2[2]1設(shè)n階方陣A≥0，如果存在一個(gè)置換矩陣使得其中B、 D是分別是k、l階方陣（k≥1、l≥1），則稱(chēng)A是可約矩陣，否則稱(chēng)A是不可約矩陣.

定義3[3]37設(shè)A是n階方陣，A有分裂A=M-N，其中M為非奇異矩陣，若 ρ(M-1N )＜1，則稱(chēng)這個(gè)分裂是收斂的；又若M是非奇異的M-矩陣且N≥0，則稱(chēng)這個(gè)分裂為M-分裂.

引理1[4]232若矩陣A是不可約的，A=M-N為矩陣A的一個(gè)M-分裂，則存在一個(gè)向量x＞0，使得M-1Nx =ρ(M-1N) x成立.

引理2[2]4設(shè)A是n階不可約非負(fù)矩陣，則有：

i）若存在x≥0，x≠0滿(mǎn)足 Ax ≥αx，則 ρ(A)≥a ；

ii）若存在x≥0，x≠0滿(mǎn)足Ax≤βx，則ρ(A)≤β.

引理3[4]231設(shè)A是Z-矩陣，則A是一個(gè)非奇異M-矩陣的充要條件是是一個(gè)非奇異M-矩陣，其中

2 主要結(jié)論

定理1 若線(xiàn)性方程組（1）的系數(shù)矩陣A是非奇異不可約M-矩陣，用G表示系數(shù)矩陣A的Gauss-Seidel迭代法的迭代矩陣，Gα表示經(jīng)預(yù)條件 Pα=I +Sα后的Gauss-Seidel迭代法的迭代矩陣，對(duì)任意有下列結(jié)論成立：

1）當(dāng)0 ＜ ρ(G)＜1時(shí)， ρ(Gα) ≤ρ(G)；

2）當(dāng) ρ(G)=1時(shí)， ρ(Gα) =ρ(G)；

3）當(dāng) ρ(G)＞1時(shí)， ρ(Gα) ≥ρ(G).

證明 由于系數(shù)矩陣A是非奇異不可約M-矩陣，且 A =（ I- L） -U為矩陣A的一個(gè)M-分裂，G =(I -L )-1U，則由引理1知，存在一個(gè)正向量x，使得 Gx =ρ(G) x，由引理3知是一個(gè)非奇異M-矩陣.

定理2 若線(xiàn)性方程組（1）的系數(shù)矩陣A是非奇異不可約M-矩陣，設(shè)γ≤β，其中γ = (γ1, γ2,… ,γn)， β =（β1, β2,…,βn） 且 γi∈ ［0,1］、 βi∈ ［0,1］,? i= 2,3,… ,n ，即 ?i = 2,3,…,n,γi≤βi，分別用Pγ=I+Sγ和Pβ=I +Sβ預(yù)處理矩陣A后得到Gauss-Seidel迭代矩陣分別為Gγ和Gβ，對(duì)于任意 αi∈有下列結(jié)論成立：

1）當(dāng)0 ＜ρ(Gγ)＜1時(shí)，ρ(Gβ) ≤ρ(Gγ)；

2） ρ(Gγ)=1時(shí)， ρ(Gβ) =ρ(Gγ)；

3）當(dāng) ρ(Gγ)＞1時(shí)， ρ(Gβ) ≥ρ(Gγ).

證明 由于系數(shù)矩陣A是非奇異不可約M-矩陣，由引理3得： Aα=(I +Sα)A也是非奇異不可約M-矩陣，由于則Aα=Dα-Lα-Uα為矩陣Aα的一個(gè)M-分裂則由引理1知，存在一個(gè)正向量x，使得令由定理1知：

3 數(shù)值例子

以上分析表明：在一定條件下預(yù)條件能夠加快Gauss-Seidel迭代法的收斂速度.下面舉例說(shuō)明該預(yù)條件的優(yōu)越性.

3.1 預(yù)條件 Pα =I +Sα加快Gauss-Seidel迭代法的收斂速度

為了方便計(jì)算，取 α2=α3=α4. αi(i = 2,3,4)取不同的值時(shí)， ρ(G)與 ρ(Gα)的比較如表1所示.

表1 αi( i = 2,3,4)取不同的值時(shí)，ρ(G)與 ρ(G α )的數(shù)值

ρ(G)的是 ρ(Gα)的一個(gè)特例，因?yàn)?G =(I -L )-1U本身是不含參數(shù) αi(i = 2,3,4)，它不會(huì)受到參數(shù)αi(i = 2,3,4)的影響，當(dāng) αi(i = 2,3,4)=0.1~0.9時(shí)，ρ(G)= 0.6347，且ρ(G ) ＞ρ(Gα).即預(yù)條件 Pα= I+Sα能夠加快Gauss-Seidel迭代法的收斂速度.

3.2 預(yù)條件下Gauss-Seidel迭代法的譜半徑是單調(diào)下降的

為了方便計(jì)算，取 β2=β3=β4.用Pα=I+Sα和Pβ=I +Sβ預(yù)處理矩陣A后得到Gauss-Seidel迭代矩陣分別為Gα和Gβ. αi、 βi(i = 2,3,4)取不同的值時(shí)， ρ(Gα)、 ρ(Gβ)的比較如表2所示.

表2 αi, β i (i = 2,3,4)取不同的值時(shí)， ρ(G α )與 ρ(Gβ )的數(shù)值

由表2，當(dāng)β＞α有 ρ(Gβ) ＜ρ(Gα)，即預(yù)條件下Gauss-Seidel迭代法的譜半徑單調(diào)下降.

[1]KOHNO T,KOTAKEMORI H,NIKI H.Improving modified iterative methods for Z-matrices[J].Liner Algebra and Its Application,1997,267:113-123.

[2]黃廷祝，楊傳勝.特殊矩陣分析及應(yīng)用[M].北京：科學(xué)出版社，2007:1-33.

[3]宋永忠.線(xiàn)性方程組迭代解法[M].南京：南京師范大學(xué)出版社，1992:37.

[4]LI Wen,SUN Weiwei.Modified Gauss-Seidel type methods and Jacobi type methods[J].Linear Algebra and Its Application,2000,317:227-240.

A New Comparison Theorem for the Preconditioned Gauss-Seidel Iterative Method

HUANG Yong-hui
(School of Mathematical Sciences,South China Normal University,Guangzhou 510631,China)

In this paper,the convergence analysis for a new preconditioned Gauss-Seidel iterative method wasdiscussed.Ifthe coefficientmatrix isa nonsingularirreducibleM-matrix,the convergence rate of this iterative method depends on the spectral radius of the original Gauss-Seidel method.Likewise,the spectral radius of the preconditioned Gauss-Seidel iterative method also depends on one of the preconditioned Gauss-Seidel methods.Finally,some numerical examples are given to explain our theoretical results.

spectral radius;preconditioned iterative method;nonsingular irreducibleM-matrix; convergence rate;Gauss-Seidel iterative

?

O241.6

A

1006-7302（2011）03-0019-04

2011-02-08

黃湧輝（1989—），男，廣東揭陽(yáng)人，研究方向?yàn)橛?jì)算數(shù)學(xué).