一類不可約L－矩陣的預(yù)條件AOR迭代法

山曉東，李 園

(內(nèi)蒙古民族大學(xué)數(shù)學(xué)學(xué)院，內(nèi)蒙古通遼 028043)

近幾年來(lái)在使用AOR迭代方法求解系數(shù)矩陣為稀疏矩陣的線性方程組Ax=b(b為n維向量，A是n階方陣)時(shí)，一般都是通過(guò)預(yù)處理方法進(jìn)行加速AOR迭代法的收斂性.意思就是說(shuō)把線性方程組的兩邊同時(shí)乘以矩陣P(其中P為非奇異方陣)，則原方程變?yōu)镻Ax=Pb.假設(shè)矩陣A=I－L－U為非奇異矩陣(若A奇異矩陣時(shí)，可通過(guò)矩陣不換使成為非奇異矩陣)，其中I為單位矩陣，U為嚴(yán)格上三角矩陣，L為嚴(yán)格下三角矩陣.

本文考慮如下線性方程組:

其中A∈Rn×n為非奇異矩陣，b∈Rn為已知向量，x∈Rn為未知向量，則AOR迭代法的迭代矩陣是:

在1991 年，Gunawardena等［1］提出預(yù)條件為 R=I+S 的 Gauss－Seidel迭代法.Wang等［2］給出了預(yù)條件矩陣為Pαβ=I+Sαβ的預(yù)條件AOR迭代法，其中:

其中:

在本文中給出的預(yù)處理矩陣為P=I+Tαβ，其中:

a1n是A的相應(yīng)位置上的元素，并證明了新的AOR迭代方法的收斂性.

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

為方便起見，本文給出如下記號(hào).設(shè)A=(aij)∈Rn×n為n×n實(shí)矩陣.diag(A)為矩陣A的對(duì)角元素aii(i=1，2，…，n)構(gòu)成的 n×n 對(duì)角矩陣.對(duì)于任意矩陣 A=(aij)，B=(bij)∈Rn×n，稱 A≥B，如果對(duì)所有 i，j=1，2，…，n，成立 aij≥bij.若矩陣 A 的每一個(gè)元素 aij≥0，i，j=1，2，…，n，則稱矩陣矩陣 A 是非負(fù)矩陣，記作 A≥0.稱 AB≥0當(dāng)且僅當(dāng)A≥B.對(duì)于n維向量也有類似的定義.ρ(·)表示矩陣的譜半徑.

線性方程組的求解的重要依據(jù)在于系數(shù)矩陣本身的一些特征，然而這個(gè)特性就是它的特征值，并且這個(gè)特征值就是矩陣的普半徑.

定義 1［4］設(shè)矩陣 A=(ai，j)∈Rn×n，則:

1)若 ai，j≤0，i，j=1，2，…，n，則稱矩陣 A 為 Z－矩陣;

2)若 A∈Z 且 ai，j≥0，i，j=1，2，…，n，則稱 A 為 L－矩陣;

3)若A∈Z為非其異矩陣且A－1≥0，則稱矩陣A為M－矩陣.

定義 2［4］已知 B=(bij)∈Rn×n，A=(aij)∈Rn×n，其中 i，j=1，2，3，…，n，若對(duì)所有的 i，j均有 aij≥bij，則有A≥B.

定義3［5］設(shè)n階方陣 A=(aij)(其中n≥2)，若對(duì)集合W={1，2，3，…，n}的任意兩個(gè)非空子集S和T，有 S∪T=W(其中 S∩T=φ)，都有 i和 j滿足 i∈S，j∈T，使得 aij≠0，則 A是不可約的，反之 A為可約矩陣.

引理1［1］設(shè)A為n×n階非負(fù)不可約矩陣，則:

1)A的譜半徑ρ(A)為A的單位特征值;

2)設(shè)x為ρ(A)的特征向量，且x≥0;

3)對(duì)于A中的任何一個(gè)元素增加時(shí)，ρ(A)也會(huì)隨著增加.

引理 2［1］設(shè) A≥0，則:

1)若存在向量 x≥0 且 x≠0，滿足 Ax≥ax則 ρ(A)≥a.進(jìn)一步地，如果 Ax＞αx，那么 ρ(A)＞a;

2)若存在向量 x≥0，x≠0，滿足 Ax≤βx 則 ρ(A)≤β.進(jìn)一步地說(shuō)，若 Ax＜βx，那么 ρ(A)＜β.

引理4［1］如果矩陣A是一個(gè)L－矩陣，則A是M－矩陣當(dāng)且僅當(dāng)存在一個(gè)正的向量，x＞0使得Ax＞0.

2 預(yù)處理AOR的迭代法以及它的收斂性

預(yù)處理線性方程組是:

則:

其中γ，ω為實(shí)參數(shù).

3 主要結(jié)論

本文的證明需要用到下面的定理:

定理1設(shè)線性方程組(4)和(6)分別是A*和的系數(shù)矩陣，A為L(zhǎng)－矩陣(其中A為不可約)，則方程(5)和方程(7)分別為上述線性方程組的預(yù)處理AOR迭代法的迭代矩陣，如果0≤an1a1n＜α，(α＞1)且β∈不可約.

證明因?yàn)?

定理2 設(shè)線性方程組(4)和(6)的系數(shù)矩陣分別為A*和，A為不可約的L－矩陣，線性方程組(4)和(6)的預(yù)處理AOR迭代法的迭代矩陣分別為，若 aii=0(i=1，2，3，…，n－1)，0≤an1a1n＜α，(α＞1)，

上式等價(jià)于:

則有:

設(shè):

其中 ani=0(i=1，2，…，n)，ai，j=1(i，j=1，2，…，n)，則 Q－U*≥0.

當(dāng) ω+λ≥1，取 β=0，則(1－ω－λ)(Q－U*)=0，結(jié)論依然成立.

根據(jù)上述定理可以推出如下結(jié)論:

當(dāng)ω=γ時(shí)，AOR迭代法就成為SOR迭代法.

推論 1設(shè) A∈Rn×n是非奇異的 L－矩陣，和分別是線性方程組(4)和(6).相應(yīng)的迭代矩陣，且:

則當(dāng) 0≤ω≤0，a1，i=0，(i=2，…，n－1)時(shí)，ρ()≤1.

當(dāng)ω=1，γ=0時(shí)，AOR迭代法即為Jacobi迭代法，則有如下結(jié)論:

4 數(shù)值舉例

設(shè)矩陣A如下:

則AOR迭代法不同參數(shù)的譜半徑如表1.

表1 幾種預(yù)條件AOR迭代法迭代矩陣普半徑比較Tab.1 The comparison of the iterative matrices'spectral radius for some preconditioned iterative methods

由表1，當(dāng)ω和γ取不同值時(shí)，可以看出本文所提出的預(yù)條件AOR迭代法收斂速度更快，這也正好驗(yàn)證了本文的結(jié)論.

［1］Gunawardena A D，Jain S K，Snyder L.Modified iterative methods for consistent linear systems［J］.Linear Algebra Appl，1991，154/156:123－143.

［2］Wang H J，Li Y T.A new preconditioned AOR iterative methods for L－matrices［J］.J Comput Appl Math，2009，229:47－53.

［3］李園，韓海山.新的L－矩陣線性方程組的預(yù)條件AOR迭代法［J］.湖北民族學(xué)院學(xué)報(bào):自然科學(xué)版，2012，30(1):39－44.

［4］Young D M.Iterative Solution of Large Linear Systems［M］.New York:Academic，1971.

［5］Verge R S.Matrix Iterative Analysis［M］.New York:Springer，1962.

［6］郭鵬飛，韓海山，勿仁圖雅.求解線性互補(bǔ)問(wèn)題的預(yù)處理AOR方法［J］.內(nèi)蒙古民族大學(xué)學(xué)報(bào):自然科學(xué)版，2012，27(2):145－147.