嚴格對角占優Z-矩陣的多級預條件AOR迭代法

薛秋芳，肖燕婷，魏 峰

西安理工大學 理學院 應用數學系，西安 710054

1 引言

科學計算中的很多問題最后都歸結為求解線性方程組：

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

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

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

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

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

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

文獻[1]和[2]分別提出了如下兩個經典的預條件子：

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

關于文獻[1-2]的進一步研究和推廣可參考文獻[4-5]。另外，Evans等人在文獻[6]中提出了預條件子：

并分析了相應的預條件AOR迭代法的收斂性，證明了對不可約L-矩陣，預條件迭代法優于標準迭代法。

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

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

則AOR迭代矩陣為：

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

下面給出新預條件子。

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

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

對應于該預條件子的方程組為：

其中：

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

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

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

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

2 定義及引理

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

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

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

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

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

顯然，嚴格對角占優的L-矩陣A一定是非奇異M-矩陣，因此A-1≥0。

定義2設A是實方陣，稱分裂A=M-N為：

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

（2）弱正規的（第一型弱非負的），如果 M-1≥0且M-1N≥0。

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

一般地，正規分裂?兩種類型的弱非負分裂。反之，則不對。

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

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

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

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

引理3[20]設A∈Rn×n是非負矩陣，那么：

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

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

引理4[20-21]設A是非負矩陣。

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

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

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

3 預條件AOR方法的收斂性分析

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

3.1 嚴格對角占優Z-矩陣的PAOR迭代法

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

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

進而P(i)A是嚴格對角占優Z-矩陣。

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

因此，若 ujk≠0，則對 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 的非負性，容易得到當αj∈[0,1),j=1,2,…,n-i時，P(i)A是不可約的。

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

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

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

證明因為A=(I-γL)/ω-[(1-ω)I+(ω-γ)L+ωU]/ω是正規分裂，所以由引理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表明當0≤γ≤ω≤1(ω≠0)時，嚴格對角占優Z-矩陣的預條件AOR迭代法是收斂的，且無需條件 ρ(Lγ,ω)＜1 ，對任意的 i∈S ，均有 ρ(Lγ,ω(i))≤ρ(Lγ,ω)＜1 成立。

（2）在定理1中，選擇特殊的ω和γ即可得到，當A為嚴格對角占優Z-矩陣時，對任意的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迭代矩陣以及相應的預條件迭代矩陣。

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

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

其中T≥0。因為A不可約，所以當0≤γ≤ω≤1(ω≠0,γ≠1)時，(1-ω)I+ω(1-γ)L+ωU 也不可約。又T≥0，容易得到 Lγ,ω不可約。

由引理5知當αj∈[0,1),j=1,2,…,n-i時，P(i)A是不可約嚴格對角占優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，類似的結論對SOR和Jacobi迭代法也成立，這里不再列出。

3.2 嚴格對角占優Z-矩陣的MPAOR迭代法

本節討論多級預條件AOR方法。

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

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

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

將AOR迭代法應用于方程組：

基于引理5和定理1、定理2的分析，容易得到關于多級預條件AOR迭代法的如下結論。

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

證明由引理5可知，對任意的i∈S,U(i)A均為嚴格對角占優Z-矩陣。因為方程組U(n-1)Ax=U(n-1)b可以通過對Ax=b依次左乘P(i),i=2,3,…,n-1得到，所以由定理1知，對任意的 i=1,2,…,n-1均有其中,故：

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

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

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

4 數值算例

考慮具有Dirichlet邊界條件的二維對流擴散方程：

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

表1 AOR及預條件AOR迭代法的迭代次數、CPU運行時間、譜半徑及誤差等

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

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

顯然當ξ、ζ和σ取不同值時，會得到不同矩陣。

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

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

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

以下實驗均使用MATLAB程序完成。

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

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

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

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