一类不可约L－矩阵的预条件AOR迭代法

山晓东，李 园

(内蒙古民族大学数学学院，内蒙古通辽 028043)

近几年来在使用AOR迭代方法求解系数矩阵为稀疏矩阵的线性方程组Ax=b(b为n维向量，A是n阶方阵)时，一般都是通过预处理方法进行加速AOR迭代法的收敛性.意思就是说把线性方程组的两边同时乘以矩阵P(其中P为非奇异方阵)，则原方程变为PAx=Pb.假设矩阵A=I－L－U为非奇异矩阵(若A奇异矩阵时，可通过矩阵不换使成为非奇异矩阵)，其中I为单位矩阵，U为严格上三角矩阵，L为严格下三角矩阵.

本文考虑如下线性方程组:

其中A∈Rn×n为非奇异矩阵，b∈Rn为已知向量，x∈Rn为未知向量，则AOR迭代法的迭代矩阵是:

在1991 年，Gunawardena等［1］提出预条件为 R=I+S 的 Gauss－Seidel迭代法.Wang等［2］给出了预条件矩阵为Pαβ=I+Sαβ的预条件AOR迭代法，其中:

其中:

在本文中给出的预处理矩阵为P=I+Tαβ，其中:

a1n是A的相应位置上的元素，并证明了新的AOR迭代方法的收敛性.

1 预备知识

为方便起见，本文给出如下记号.设A=(aij)∈Rn×n为n×n实矩阵.diag(A)为矩阵A的对角元素aii(i=1，2，…，n)构成的 n×n 对角矩阵.对于任意矩阵 A=(aij)，B=(bij)∈Rn×n，称 A≥B，如果对所有 i，j=1，2，…，n，成立 aij≥bij.若矩阵 A 的每一个元素 aij≥0，i，j=1，2，…，n，则称矩阵矩阵 A 是非负矩阵，记作 A≥0.称 AB≥0当且仅当A≥B.对于n维向量也有类似的定义.ρ(·)表示矩阵的谱半径.

线性方程组的求解的重要依据在于系数矩阵本身的一些特征，然而这个特性就是它的特征值，并且这个特征值就是矩阵的普半径.

定义 1［4］设矩阵 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，若对所有的 i，j均有 aij≥bij，则有A≥B.

定义3［5］设n阶方阵 A=(aij)(其中n≥2)，若对集合W={1，2，3，…，n}的任意两个非空子集S和T，有 S∪T=W(其中 S∩T=φ)，都有 i和 j满足 i∈S，j∈T，使得 aij≠0，则 A是不可约的，反之 A为可约矩阵.

引理1［1］设A为n×n阶非负不可约矩阵，则:

1)A的谱半径ρ(A)为A的单位特征值;

2)设x为ρ(A)的特征向量，且x≥0;

3)对于A中的任何一个元素增加时，ρ(A)也会随着增加.

引理 2［1］设 A≥0，则:

1)若存在向量 x≥0 且 x≠0，满足 Ax≥ax则 ρ(A)≥a.进一步地，如果 Ax＞αx，那么 ρ(A)＞a;

2)若存在向量 x≥0，x≠0，满足 Ax≤βx 则 ρ(A)≤β.进一步地说，若 Ax＜βx，那么 ρ(A)＜β.

引理4［1］如果矩阵A是一个L－矩阵，则A是M－矩阵当且仅当存在一个正的向量，x＞0使得Ax＞0.

2 预处理AOR的迭代法以及它的收敛性

预处理线性方程组是:

则:

其中γ，ω为实参数.

3 主要结论

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

定理1设线性方程组(4)和(6)分别是A*和的系数矩阵，A为L－矩阵(其中A为不可约)，则方程(5)和方程(7)分别为上述线性方程组的预处理AOR迭代法的迭代矩阵，如果0≤an1a1n＜α，(α＞1)且β∈不可约.

证明因为:

定理2 设线性方程组(4)和(6)的系数矩阵分别为A*和，A为不可约的L－矩阵，线性方程组(4)和(6)的预处理AOR迭代法的迭代矩阵分别为，若 aii=0(i=1，2，3，…，n－1)，0≤an1a1n＜α，(α＞1)，

上式等价于:

则有:

设:

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

当 ω+λ≥1，取 β=0，则(1－ω－λ)(Q－U*)=0，结论依然成立.

根据上述定理可以推出如下结论:

当ω=γ时，AOR迭代法就成为SOR迭代法.

推论 1设 A∈Rn×n是非奇异的 L－矩阵，和分别是线性方程组(4)和(6).相应的迭代矩阵，且:

则当 0≤ω≤0，a1，i=0，(i=2，…，n－1)时，ρ()≤1.

当ω=1，γ=0时，AOR迭代法即为Jacobi迭代法，则有如下结论:

4 数值举例

设矩阵A如下:

则AOR迭代法不同参数的谱半径如表1.

表1 几种预条件AOR迭代法迭代矩阵普半径比较Tab.1 The comparison of the iterative matrices'spectral radius for some preconditioned iterative methods

由表1，当ω和γ取不同值时，可以看出本文所提出的预条件AOR迭代法收敛速度更快，这也正好验证了本文的结论.

［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－矩阵线性方程组的预条件AOR迭代法［J］.湖北民族学院学报:自然科学版，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］郭鹏飞，韩海山，勿仁图雅.求解线性互补问题的预处理AOR方法［J］.内蒙古民族大学学报:自然科学版，2012，27(2):145－147.