一類改進(jìn)的高斯-賽德爾迭代法的比較性定理

黃湧輝

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

一類改進(jìn)的高斯-賽德爾迭代法的比較性定理

黃湧輝

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

討論了改進(jìn)的高斯-賽德爾迭代法的收斂性.若系數(shù)矩陣為非奇異不可約M-矩陣，則該預(yù)條件下高斯-賽德爾迭代法收斂的快慢取決于原高斯-賽德爾迭代法譜半徑的大小.同樣，在該預(yù)條件下高斯-賽德爾迭代法的譜半徑大小與其他高斯-賽德爾迭代法的譜半徑大小有關(guān).

譜半徑；預(yù)條件迭代法；非奇異不可約M-矩陣；收斂速度；高斯-賽德爾迭代法

考慮線性方程組

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

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

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

為討論方便，當(dāng)A可逆時，通過初等變換把A的對角元都化簡為1，因此

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

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

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

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

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

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

用Pα左乘線性方程組（1）的兩邊，得

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

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

1 預(yù)備知識

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

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

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

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

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

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

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

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

2 主要結(jié)論

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

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

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

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

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

定理2 若線性方程組（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β，對于任意 αi∈有下列結(jié)論成立：

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

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

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

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

3 數(shù)值例子

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

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

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

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

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

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

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

表2 αi, β i (i = 2,3,4)取不同的值時， ρ(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]宋永忠.線性方程組迭代解法[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àn)橛嬎銛?shù)學(xué).