廣義Gauss-Seidel迭代法的預(yù)測(cè)-校正方法

伊馬木·麥麥提 阿布都熱西提·阿布都外力 娜扎開提·阿迪力

(新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，新疆 烏魯木齊 830046)

1 引 言

考慮線性方程組

Ax=b,

(1.1)

其中A是n×n的非奇異矩陣，b是n維向量.

將系數(shù)矩陣A進(jìn)行分裂為A=D-L-U，其中D是對(duì)角矩陣，L是下三角矩陣，U是上三角矩陣.則經(jīng)典的Gauss-Seidel迭代法為

x(k+1)=(D-L)-1Ux(k)+(D-L)-1b，

k=1,2,3,…,

(1.2)

對(duì)部分線性方程組而言，用經(jīng)典Gauss-Seidel迭代求解，斂速度不理想，為了解決該問題，本文推出了廣義Gauss-Seidel(簡(jiǎn)稱為廣義G-S)迭代法和它的預(yù)測(cè)-校正方法.

2 廣義G-S迭代法

將系數(shù)矩陣A進(jìn)行分裂為A=Dm-Lm-Um，其中Dm是帶狀對(duì)角矩陣，帶寬為2m+1,Dm的各元素是

(2.1)

其中m=0,1,2,…,(n-1)/2，Lm與Um是矩陣A-Dm的嚴(yán)格上下部分，Dm,Lm,Um分別為

Dm=

如果取矩陣Dm-Lm作為迭代矩陣(Dm-Lm)-1Um，則得到文獻(xiàn)[1]中的廣義G-S迭代方法.迭代公式是

x(k+1)=(Dm-Lm)-1Umx(k)+(Dm-Lm)-1b，

k=0,1,2,….

(2.2)

若分裂矩陣中取矩陣Dm-Um作為迭代矩陣(Dm-Um)-1Lm，則推出的迭代方法是

x(k+1)=(Dm-Um)-1Lmx(k)+(Dm-Um)-1b，

k=0,1,2,….

(2.3)

當(dāng)m=0時(shí)式(2.2)與(2.3)表示的是正，反方向的經(jīng)典G-S迭代法，計(jì)算公式分別為

(2.4)

(2.5)

3 廣義Gauss-Seidel迭代法的預(yù)測(cè)-校正方法

為了改進(jìn)廣義G-S迭代法的收斂速度,將兩種廣義G-S迭代方法相匹配，生成廣義G-S迭代法的預(yù)測(cè)-校正方法：

(3.1)

本方法先用(2.2)的廣義G-S迭代法預(yù)測(cè)y(k+1)的值， 然后用(2.3)的廣義G-S迭代法校正x(k+1). 當(dāng)m=0時(shí)，預(yù)測(cè)公式和校正公式的分量形式分別為

(3.2)

4 收斂性分析

迭代法的收斂性依賴于迭代矩陣，設(shè)迭代矩陣為G,則迭代法收斂的充分必要條件是ρ(G)<1(其中ρ是迭代矩陣的譜半徑)，充分條件是‖G‖<1(其中‖‖表示為任意范數(shù)).下面給出了一些比較容易驗(yàn)證的充分條件.

引理1[3]若M=(Mij)和N=(Nij)都是n×n的矩陣，并且M是嚴(yán)格對(duì)角占優(yōu)矩陣，則矩陣M-1N的特征值滿足

(4.1)

定理1如果A為嚴(yán)格對(duì)角占優(yōu)矩陣，則新廣G-S迭代法是收斂.

證明將嚴(yán)格對(duì)角矩陣A分裂為A=M+N，其中M=Dm+Um,N=Lm并且M是嚴(yán)格對(duì)角占優(yōu)矩陣.從上述的引理可得

其中

(4.2)

我們先證:ρ=maxρi<1, 因?yàn)锳是嚴(yán)格對(duì)角占優(yōu)矩陣，所以滿足

(4.3)

由式(4.3)可以推到

(4.4)

由不等式(4.4)可得ρ(M-1N)<ρ<1.據(jù)代法收斂的充分必要條件，新廣義G-S迭代法是收斂.

定理2[2]如果A為不可約弱對(duì)角占優(yōu)矩陣,則新的廣義G-S迭代法是收斂.

定義設(shè)A=(aij),B=(bij)是n×n的矩陣，如果aij與bij滿足aij≤bij(aij≤bij)，則矩陣A與B 的關(guān)系表示為A≤B(A

定理3[4]設(shè)矩陣A=(aij)，B=(bij)若A≤B，bij≤0，且A是M-矩陣，則B也是M-矩陣.

定理4[4,5]若A∈Zn×n，則以下命題相互等價(jià)(其中0是零矩陣)：

(1)A為非奇異M-矩陣；

(2)A是非奇異，且A-1≥0;

(3)存在A的一種分裂A=P-Q(正則分裂),使得P-1≥0，Q≥0,且ρ(P-1Q)<1;

定理5如果A是M-矩陣，則新廣義G-S迭代法是收斂.

證明設(shè)矩陣A分裂為A=P-Q,其中P=Dm-Um，Q=Lm.

因?yàn)锳是M矩陣，顯然，P≥A，Q>0，由定理3可知分裂矩陣P也是M-矩陣.

又因?yàn)镻是M-矩陣，根據(jù)定理4的命題(2)，(3)可知P是非奇異，P-1≥0，且ρ(P-1Q)<1，所以迭代矩陣的譜半徑滿足條件：ρ(P-1Q)<1，若系數(shù)矩陣A為M-矩陣，則新廣義G-S迭代法是收斂.

定理6廣義G-S預(yù)測(cè)-校正法收斂的充要條件是ρ(G正·G反)<1,收斂的充分條件是‖G正·G反‖<1.

證明用預(yù)測(cè)-校正公式(3.1)很容易推到:

x(k+1)= (Dm-Um)-1Lm(Dm-Lm)-1Umx(k)+

(Dm-Um)-1Lm(Dm-Lm)-1b+

(Dm-Lm)-1b.

(4.5)

由迭代式(4.5)可知預(yù)測(cè)-校正方法的迭代矩陣為G=(Dm-Um)-1Lm(Dm-Lm)-1Um，

根據(jù)矩陣的運(yùn)算性質(zhì)，可得迭代矩陣G剛好為兩種迭代矩陣的乘積，即G=G正·G反，因此預(yù)測(cè)-校正方法收斂的充要條件是：ρ(G正·G反)<1,收斂的充分條件是：‖G正·G反‖<1.

由上面所述的一些定理可知，如果系數(shù)矩陣是對(duì)角占優(yōu)矩陣，不可約弱對(duì)角占優(yōu)矩陣，M-矩陣等情況下解線性方程程組的廣義G-S預(yù)測(cè)-校正法是收斂的.

5 數(shù)值實(shí)驗(yàn)

為了比較迭代法的收斂速度，下面給了數(shù)值例子，根據(jù)其結(jié)果，說明這些方法的優(yōu)缺點(diǎn).

例1[5]設(shè)線性方程組(1.1)中A，b值分別為

此線性方程組的精確解是x*=(1,1,…,1)T,迭代初始向量是x(0)=(0,0,…,0)T.

表1 當(dāng)m=0時(shí)各種迭代法的迭代次數(shù)(經(jīng)典G-S法)

表2 當(dāng)m=1時(shí)各種迭代法的迭代次數(shù)

由表(1),(2)可知，廣義G-S迭代法及預(yù)測(cè)-校正方法解線性方程組(1.1)均收斂，而反方法的收斂速度比正方法較快，預(yù)測(cè)-校正算法的收斂速度比兩個(gè)方法都快(即取n相同值時(shí)，達(dá)到同樣精度所需迭代次數(shù)較少).當(dāng)參數(shù)m取不同值時(shí)，三種迭代方法的迭代效果也不相同，m的值越大三種迭代格式的收斂速度越快，迭代次數(shù)越少.

6 結(jié) 語

以上介紹了基于Gauss-Seidel迭代法的三種廣義迭代方法.并在理論和數(shù)值計(jì)算方面證明了本文中的迭代法是有效的.若三種迭代法均收斂，則正反廣義Gauss-Seidel迭代的收斂速度基本相同，預(yù)測(cè)-校正方法的收斂速度要比這兩種廣義迭代法更快一些.本文中迭代法的收斂速度依賴于帶寬因子m,因此m取的值越大收斂速度也是越快.