嚴(yán)格對(duì)角占優(yōu)Z-矩陣的多級(jí)預(yù)條件AOR迭代法

薛秋芳，肖燕婷，魏 峰

西安理工大學(xué) 理學(xué)院 應(yīng)用數(shù)學(xué)系，西安 710054

1 引言

科學(xué)計(jì)算中的很多問題最后都?xì)w結(jié)為求解線性方程組：

這里，A∈Rn×n是非奇異矩陣；x,b∈Rn，x是未知向量，b是給定的向量。這類方程組一般采用迭代法求解。如果令 A=M-N,其中 M,N∈Rn×n且 M 非奇異，則基本的迭代格式為：

這里，c=M-1b,T=M-1N是迭代矩陣，其譜半徑不僅決定了該迭代法是否收斂，還決定了迭代的收斂速度。盡管某些迭代法可求解方程組（1），但很多時(shí)候，由于緩慢的收斂速度，求解效率往往很低。

為了改善迭代法的收斂性，研究者們提出了預(yù)條件技術(shù)[1-18]，即將原方程組（1）轉(zhuǎn)化為預(yù)條件形式：

其中，P為非奇異矩陣，被稱為預(yù)條件子。該方程組的基本迭代格式為：

其中，PA=MP-NP,且MP非奇異。迭代法（4）被稱為預(yù)條件迭代法。

不同的分裂PA=MP-NP可以得到不同的預(yù)條件方法，如預(yù)條件SOR迭代法、預(yù)條件Gauss-Seidel迭代法等。

文獻(xiàn)[1]和[2]分別提出了如下兩個(gè)經(jīng)典的預(yù)條件子：

他們研究了預(yù)條件Gauss-Seidel迭代法的收斂性。不久之后，文獻(xiàn)[3]探討了帶有預(yù)條件子P?的預(yù)條件SOR迭代法的收斂情況。

關(guān)于文獻(xiàn)[1-2]的進(jìn)一步研究和推廣可參考文獻(xiàn)[4-5]。另外，Evans等人在文獻(xiàn)[6]中提出了預(yù)條件子：

并分析了相應(yīng)的預(yù)條件AOR迭代法的收斂性，證明了對(duì)不可約L-矩陣，預(yù)條件迭代法優(yōu)于標(biāo)準(zhǔn)迭代法。

受以上預(yù)條件子的啟發(fā)，本文提出一類新預(yù)條件子，以上提到的預(yù)條件子均為其特殊情況。本文將該預(yù)條件子應(yīng)用于AOR迭代法，從而將上面的預(yù)條件方法推廣到更一般的情況。

不失一般性，設(shè)A=I-L-U ，其中I是n×n單位陣，-L和-U分別是矩陣A的嚴(yán)格下三角和嚴(yán)格上三角矩陣。令：

則AOR迭代矩陣為：

其中，ω,γ∈[0,2),(ω≠0)是松弛因子（參見文獻(xiàn)[19]）。顯然，當(dāng) (ω,γ)分別取 (ω,ω)、(1,1)和 (1,0)時(shí)，可分別得到SOR迭代矩陣、Gauss-Seidel迭代矩陣和Jacobi迭代矩陣。

下面給出新預(yù)條件子。

設(shè)i∈S={1,2,…,n-1},定義 A的一類預(yù)條件子P(i)為：

這里0≤αj≤1,j=1,2,…,n-i，且存在 j使得

對(duì)應(yīng)于該預(yù)條件子的方程組為：

其中：

若令 D(i)、-L(i)和-U(i)分別為 P(i)A的對(duì)角嚴(yán)格下三角和嚴(yán)格上三角矩陣，則P(i)A=D(i)-L(i)-U(i)。假設(shè) D(i)-L(i)非奇異，則預(yù)條件方程組（7）的AOR迭代矩陣為：

這里ω,γ∈[0,2),(ω≠0)是松弛因子。

若對(duì)任意的 j=1,2,…,n-i,αj=0 ，則式（6）中定義的預(yù)條件子 P(i)是n階單位陣，因而式（9）中的 Lγ,ω(i)即為標(biāo)準(zhǔn)AOR迭代矩陣。

本文給出了嚴(yán)格對(duì)角占優(yōu)Z-矩陣的預(yù)條件AOR迭代法（帶有預(yù)條件子P(i),i∈S，簡(jiǎn)記為PAOR）收斂性分析，并提出了多級(jí)預(yù)條件AOR迭代法（簡(jiǎn)記MPAOR），詳細(xì)研究了這些方法的收斂性。數(shù)值算例驗(yàn)證了相關(guān)結(jié)論，這些預(yù)條件子的確提高了原迭代的收斂速度。

2 定義及引理

本文令I(lǐng)表示單位矩陣，ρ(A)表示矩陣A的譜半徑。對(duì)向量x∈Rn，令x≥0(x＞0)表示x是非負(fù)的（正的），即x的每個(gè)分量都是非負(fù)的（正的）。對(duì)向量x,y∈Rn，令 x≥y(x＞y)表示 x-y≥0(x-y＞0)。對(duì)矩陣也有類似的約定。

定義1矩陣A=(aij)∈Rn×n被稱為：

（1）Z-矩陣，如果對(duì)任意的 i≠j,aij≤0。

（2）L-矩陣，如果 A是Z-矩陣且對(duì)任意的i=1,2,…,n,aii＞0。

（3）M-矩陣，如果 A=s I-B,其中 B≥0且ρ(B)≤s。

顯然，嚴(yán)格對(duì)角占優(yōu)的L-矩陣A一定是非奇異M-矩陣，因此A-1≥0。

定義2設(shè)A是實(shí)方陣，稱分裂A=M-N為：

（1）正規(guī)的，如果M-1≥0且N≥0。

（2）弱正規(guī)的（第一型弱非負(fù)的），如果 M-1≥0且M-1N≥0。

（3）第二型弱非負(fù)的，如果M-1≥0且NM-1≥0。

一般地，正規(guī)分裂?兩種類型的弱非負(fù)分裂。反之，則不對(duì)。

引理1[7]設(shè)A是滿足A-1≥0的非奇異矩陣。

（1）如果A=M-N是弱非負(fù)分裂（第一型或第二型），那么 ρ(M-1N)＜1。

（2）如果A=M-N是第二型弱非負(fù)分裂，那么存在向量x≥0且x≠0使得M-1Nx=ρ(M-1N)x且Ax≥0,同時(shí)Nx≥0且Nx≠0。

引理2[8]設(shè) A1,A2∈Rn×n,Ai=Mi-Ni,i=1,2是非負(fù)分裂。如果Perron向量x2≥0且x2≠0（對(duì)應(yīng)于ρ(T2)的向量 x2）滿足 T1x2≤T2x2，那么 ρ(T1)≤ρ(T2)，其中Ti=Mi-1Ni,i=1,2。

引理3[20]設(shè)A∈Rn×n是非負(fù)矩陣，那么：

（1）ρ(A)是A的一個(gè)特征值，如果A是不可約的，那么 ρ(A)＞0。

（2）對(duì)特征值ρ(A)存在相應(yīng)的特征向量 x≥0，且x≠0，被稱為Perron向量，如果矩陣 A不可約，那么x＞0。

引理4[20-21]設(shè)A是非負(fù)矩陣。

（1）如果存在向量 x≥0且 x≠0，使得αx≤Ax,那么α≤ρ(A)。

（2）如果A不可約，并且存在向量x≥0且x≠0使得αx≤Ax≤βx,且等號(hào)不成立，那么α＜ρ(A)＜β且x＞0。

（3）α＞ρ(A)當(dāng)且僅當(dāng)αI-A非奇異且(αI-A)-1≥0。

3 預(yù)條件AOR方法的收斂性分析

下面分兩部分對(duì)預(yù)條件AOR迭代法的收斂性展開具體討論。

3.1 嚴(yán)格對(duì)角占優(yōu)Z-矩陣的PAOR迭代法

引理5若A=(ajk)∈Rn×n是對(duì)角線元素為1的不可約嚴(yán)格對(duì)角占優(yōu)Z-矩陣，則當(dāng)αj∈[0,1),j=1,2,…,n-i時(shí)，P(i)A,i∈S也是不可約嚴(yán)格對(duì)角占優(yōu)Z-矩陣。

證明首先證明P(i)A,i∈S是嚴(yán)格對(duì)角占優(yōu)Z-矩陣。令 B=P(i)A=(bjk)∈Rn×n，則對(duì)任意的 j=1,2,…,n-i,k=1,2,…,n且而。因而 P(i)A是L-矩陣，且由和aj,i+j≤0可知：

進(jìn)而P(i)A是嚴(yán)格對(duì)角占優(yōu)Z-矩陣。

下面證明P(i)A,i∈S不可約。顯然：

因此，若 ujk≠0，則對(duì) j=1,2,…,n-i，αj∈[0,1)，fjk≠0；若 ljk≠0,則由 (S(i)L)L≥0可知 ejk≠0,再由(S(i)L)U≥0和S(i)U 的非負(fù)性，容易得到當(dāng)αj∈[0,1),j=1,2,…,n-i時(shí)，P(i)A是不可約的。

由引理5，分裂（10）是正規(guī)的，從而由引理1（1）可知，該分裂是收斂的。

定理1設(shè)A是對(duì)角線元素均為1的嚴(yán)格對(duì)角占優(yōu)Z-矩陣，Lγ,ω和 Lγ,ω(i)(i∈S)分別是由式（5）和（9）定義的矩陣A的AOR和預(yù)條件AOR迭代矩陣，且0≤γ≤ω≤1(ω≠0),則對(duì)任意的αj∈[0,1],j=1,2,…,n-i，均有：

ρ(Lγ,ω(i))≤ρ(Lγ,ω)＜1

證明因?yàn)锳=(I-γL)/ω-[(1-ω)I+(ω-γ)L+ωU]/ω是正規(guī)分裂，所以由引理1知 ρ(Lγ,ω)＜1 ，且在向量x≥0(x≠0)，使得 Lγ,ωx=ρ(Lγ,ω)x 并且 Ax≥0。因此：

P(i)Ax=(I+S(i))Ax=Ax+S(i)Ax≥Ax≥0

由S(i)L≥0可知：

M(i)=[I-(S(i)L)D-γ(L+(S(i)L)L)]/ω≤(I-γL)/ω又(I-γL)-1≥0且(M(i))-1≥0，故(M(i))-1≥ω(I-γL)-1,因而：

從而，由 (M(i))-1N(i)≥0 及引理2可知 ρ(Lγ,ω(i))≤ρ(Lγ,ω)＜1 。

注1（1）定理1表明當(dāng)0≤γ≤ω≤1(ω≠0)時(shí)，嚴(yán)格對(duì)角占優(yōu)Z-矩陣的預(yù)條件AOR迭代法是收斂的，且無需條件 ρ(Lγ,ω)＜1 ，對(duì)任意的 i∈S ，均有 ρ(Lγ,ω(i))≤ρ(Lγ,ω)＜1 成立。

（2）在定理1中，選擇特殊的ω和γ即可得到，當(dāng)A為嚴(yán)格對(duì)角占優(yōu)Z-矩陣時(shí)，對(duì)任意的i∈S均有ρ(Lω(i))≤ρ(Lω)＜1，ρ(G(i))≤ρ(G)＜1 且 ρ(J(i))≤ρ(J)＜1 ，這里 Lω、G 、J和 Lω(i)、G(i)、J(i)分別為 A的SOR、Gauss-Seidel和Jacobi迭代矩陣以及相應(yīng)的預(yù)條件迭代矩陣。

定理2設(shè)A是對(duì)角元素為1的不可約嚴(yán)格對(duì)角占優(yōu)L-矩陣，Lγ,ω和 Lγ,ω(i)(i∈S)分別是由式（5）和（9）定義的矩陣 A的AOR和預(yù)條件AOR迭代矩陣，且0≤γ≤ω≤1(ω≠0,γ≠1)，則對(duì)任意的 αj∈[0,1),j=1,2,…,n-i且 αj不全為0，均有 ρ(Lγ,ω(i))＜ρ(Lγ,ω)＜1 。

證明由式（5）和引理4（3）可知下面的等式成立：

其中T≥0。因?yàn)锳不可約，所以當(dāng)0≤γ≤ω≤1(ω≠0,γ≠1)時(shí)，(1-ω)I+ω(1-γ)L+ωU 也不可約。又T≥0，容易得到 Lγ,ω不可約。

由引理5知當(dāng)αj∈[0,1),j=1,2,…,n-i時(shí)，P(i)A是不可約嚴(yán)格對(duì)角占優(yōu)L-矩陣，因而 M(i)非奇異，Lγ,ω(i)是定義好的，與上面類似可證Lγ,ω(i)不可約。

由引理1的證明過程可知，存在向量x≥0且x≠0使得 (M(i))-1N(i)x≤ρ(Lγ,ω)x（見式（12））。從而，由 αj不全為 0，j=1,2,…,n-i及引理 4（2）可得 ρ(Lγ,ω(i))＜ρ(Lγ,ω)＜1 。

由定理2，類似的結(jié)論對(duì)SOR和Jacobi迭代法也成立，這里不再列出。

3.2 嚴(yán)格對(duì)角占優(yōu)Z-矩陣的MPAOR迭代法

本節(jié)討論多級(jí)預(yù)條件AOR方法。

顯然，可將預(yù)條件子P(i),i=1,2,…,n-1,逐步應(yīng)用于方程組。對(duì)任意的i∈S，令U(i)=P(i)…P(1)，用U(i)左乘以方程組（1）可得：

該方程組等價(jià)于（1）。因而方程組（1）的多級(jí)預(yù)條件AOR迭代法，即方程組（13）的AOR迭代法可由如下的迭代格式定義：

為了方便，記Q(i)=[D(i)]-1，且對(duì)任意的i=2,3,…,n-1,B(i)=P(i)B(i-1)Q(i),而 B(1)=P(1)AQ(1),則式（13）可轉(zhuǎn)化為如下等價(jià)形式：

將AOR迭代法應(yīng)用于方程組：

基于引理5和定理1、定理2的分析，容易得到關(guān)于多級(jí)預(yù)條件AOR迭代法的如下結(jié)論。

定理3設(shè)A是對(duì)角線元素均為1的嚴(yán)格對(duì)角占優(yōu)Z-矩陣，Lγ,ω和分別是矩陣 A的AOR和多級(jí)預(yù)條件AOR迭代矩陣，且0≤γ≤ω≤1(ω≠0)，則對(duì)任意的αj∈[0,1],j=1,2,…,n-i,均有：

證明由引理5可知，對(duì)任意的i∈S,U(i)A均為嚴(yán)格對(duì)角占優(yōu)Z-矩陣。因?yàn)榉匠探MU(n-1)Ax=U(n-1)b可以通過對(duì)Ax=b依次左乘P(i),i=2,3,…,n-1得到，所以由定理1知，對(duì)任意的 i=1,2,…,n-1均有其中,故：

注2（1）定理3表明對(duì)任意的 j=1,2,…,n-i，當(dāng)αj∈[0,1]時(shí)，嚴(yán)格對(duì)角占優(yōu)Z-矩陣的多級(jí)預(yù)條件子能夠逐步加快AOR迭代法的收斂速度。

（2）在定理3中選擇特殊的參數(shù)可得類似的結(jié)論對(duì)SOR、Gauss-Seidel和Jacobi迭代法也同樣成立。

定理4設(shè)A是對(duì)角元素為1的不可約嚴(yán)格對(duì)角占優(yōu)Z-矩陣，Lγ,ω和分別是 A 的AOR和多級(jí)預(yù)條件AOR迭代矩陣，且0≤γ≤ω≤1(ω≠0,γ≠1)，則對(duì)任意的 αj∈[0,1),j=1,2,…,n-i且 αj不全為0，均有：

4 數(shù)值算例

考慮具有Dirichlet邊界條件的二維對(duì)流擴(kuò)散方程：

其中，Ω=(0,1)×(0,1);ξ和σ是常數(shù)；?Ω為Ω的邊界；是給定的函數(shù)。令步長(zhǎng)為使用五點(diǎn)差分格式將方程（14）離散化，得到系數(shù)矩陣：

表1 AOR及預(yù)條件AOR迭代法的迭代次數(shù)、CPU運(yùn)行時(shí)間、譜半徑及誤差等

圖1 （預(yù)條件）AOR迭代矩陣譜半徑曲線

這里n=N2,T是N×N 是三對(duì)角矩陣，即T=tridiag(η1,μ0,μ1),其中：

顯然當(dāng)ξ、ζ和σ取不同值時(shí)，會(huì)得到不同矩陣。

令初始向量為零向量，迭代終止條件為：

其中ε=h2/5，而b是使得線性方程組的精確解為(1,1,…,1)T∈Rn的向量。

在此方程組中，令ξ=ζ=σ=0,并分別應(yīng)用AOR迭代法、預(yù)條件AOR迭代法（PAOR）及多級(jí)預(yù)條件AOR迭代法（MPAOR）求解。在表1中，令ρ表示相應(yīng)迭代矩陣的譜半徑。對(duì)任意的 j,α=αj=0.5,ω=0.9,γ=0.7。

以下實(shí)驗(yàn)均使用MATLAB程序完成。

由表1可見，無論是迭代次數(shù)、求解速度，還是譜半徑，PAOR方法明顯優(yōu)于AOR迭代法，而MPAOR迭代法則是這三種方法中收斂最快的方法。該例表明，相比標(biāo)準(zhǔn)的AOR迭代法，預(yù)條件AOR迭代法較大地加快了方程的求解速度，而多級(jí)預(yù)條件AOR迭代法則可進(jìn)一步提高預(yù)條件方法的收斂速度。

圖2（預(yù)條件）SOR迭代矩陣譜半徑曲線

圖1 和圖2分別是相應(yīng)的AOR和SOR迭代法的譜半徑曲線。圖1給出了當(dāng)γ=0.01,ω∈(0.01,1)時(shí)，AOR、PAOR和MPAOR迭代法的譜半徑曲線。圖2給出了當(dāng)ω∈(0.01,1)時(shí)，SOR、PSOR和MPSOR迭代法的譜半徑曲線。

由圖1可見，文中迭代法譜半徑由小到大的排列順序依次為MPAOR、PAOR和AOR，由圖2可見，類似的結(jié)果對(duì)相應(yīng)的（預(yù)條件）SOR迭代法也成立。