预条件下含参数的JOR迭代法敛散性分析

王慧勤，雷 刚

（宝鸡文理学院数学系，陕西宝鸡721013）

预条件下含参数的JOR迭代法敛散性分析

王慧勤，雷 刚

（宝鸡文理学院数学系，陕西宝鸡721013）

对于JOR迭代法求解线性方程组Ax＝b，运用了预条件加速JOR迭代法的收敛性，在预条件后引入参数α，给出更一般的预条件下含参数形式的JOR迭代方法.证明了这类方法能够加速JOR迭代法的收敛性，找到了参数的最佳取值，并且用数值算例加以验证.

JOR迭代法；收敛性；预条件；谱半径

在有限元分析以及差分方程的数值求解过程中，大型线性方程组的求解几乎决定了整个数值求解的快慢，随着计算机的快速发展与应用，对大型线性方程组的求解大都采用迭代法求解，那么对迭代法是否收敛以及迭代法的收敛速度的研究就成为近年来关注的热点［1－3］.基本的迭代法有Jacobi，Gauss－Seidel迭代法，在此基础上发展了JOR，SOR，AOR等迭代法，各种迭代法互有优缺点，为改变迭代法的收敛性或加速迭代法的收敛速度，预条件方法已经成为一类基本的改善收敛性的方法.

1 预备知识

运用预条件方法解大型线性方程组Ax＝b（其中A＝（aij）n×n∈Rn×n；x，b∈Rn）就是引入一个非奇异矩阵［1］P∈Rn×n，使原方程变为

结合矩阵变换，为讨论方便，假设A＝I－L－U为非奇异矩阵（当A为奇异矩阵时，可通过矩阵变换为低阶的非奇异矩阵），I是单位矩阵，－L和－U分别是由矩阵A的严格下三角部分和严格上三角部分组成的矩阵.雅可比超松弛法（简称JOR法）就是在Jacobi迭代法的基础上引入参数ω，将Ax＝b的系数矩阵A分解为（当ω＝1时即为Jacobi迭代法），相应的迭代形式为

迭代矩阵为

在文献［1］预条件P＝（I＋C）作用下，

其中：CL＝0；CU＝D1＋L1＋U1；C的矩阵形式为

a21，a31，…，an1分别是系数矩阵A对应位置上的元素.那么预条件后JOR迭代法的迭代矩阵为

易知当α＝1时，TJCα＝TJC，即为一般的预条件JOR方法.本文讨论预条件对JOR迭代法收敛性的影响，并找到在能加速收敛性的条件下寻找参数α的最优取值.

2 定义和引理

定义1［4］记n阶实方阵A＝（aij）所组成的集合为Rn，n，记Rn，n的子集Zn，n为

当矩阵A∈Zn，n，并且aii＞0（∀i）成立时，称矩阵A为L－矩阵.

定义2［5－6］如果矩阵A能表示为A＝sI－B，I为n阶的单位矩阵，B≥0，当s≥ρ（B）时，称A为M－矩阵，特别当s＞ρ（B）时，称A为非奇异的M－矩阵；当s＝ρ（B）时，称A为奇异M－矩阵.其中ρ（B）为B的谱半径.

定义3［5－6］设方阵A＝（aij）∈Rn×n，如果存在排列矩阵P，使得

其中：F和H是方阵，0是零矩阵.则称A为可约矩阵；否则称A为不可约矩阵.

引理1［4］（Perron－Frobenius定理） 如果矩阵A为n阶非负方阵，那么就有：

（1）A有非负特征值等于其谱半径ρ（A）；

（2）A有与ρ（A）相对应的非负特征向量；

（3）A的任一元素增加时，ρ（A）不减.

引理2［6］设A为非负矩阵，则：

（1）若αx≤Ax对某一个非负向量x且x≠0成立，那么就有α≤ρ（A）.

（2）若Ax≤βx对某一个正向量x成立，那么就有ρ（A）≤β；如果A不可约且有0≠αx≤Ax≤βx，αx≠Ax，Ax≠βx对某一个非负向量x成立，则α＜ρ（A）＜β.

引理3［7］设矩阵A－1≥0，满足A＝~M－~N＝M－N是弱正规的分裂.如果M－1≤~M－1，且N≥0那么就有ρ（~M－1~N）≤ρ（M－1N）.

3 结果与证明

JOR迭代法的收敛性通常用谱半径是否小于1来判定，如果谱半径小于1，那么迭代法就收敛，否则迭代法就发散.而且谱半径越小，迭代法的收敛速度就越快.

定理1 对线性方程组Ax＝b，TJ和TJCα分别是由（3）和（5）式给出的JOR迭代法的迭代矩阵，如果矩阵A＝I－L－U是严格对角占优的L－矩阵，满足0＜ai1a1i≤1，i＝2，3，…，n，0＜ω≤1，那么当0≤α≤时，就有：

（1）当ρ（TJ）＞1时，ρ（TJCα）≥ρ（TJ）；

（2）当ρ（TJ）＝1时，ρ（TJCα）＝ρ（TJ）；

（3）当ρ（TJ）＜1时，ρ（TJCα）≤ρ（TJ）.

证明在含参数的分裂形式下，（I－αD1）是对角矩阵，结合当0＜ai1a1i≤1，i＝2，3，…，n时，有可知（I－αD1）≥0，从而（I－αD1）－1≥0.

同理易知TJ也是一个不可约的非负矩阵，利用Perron－Frobenius定理知存在一个正向量x＝（x1，x2，…，xn）T，满足TJx＝ρ（TJ）x，即

对（6）式两边同时左乘矩阵C，利用CL＝0可以得到ωCUx＝［（λ－1）C＋ωC）］x.结合矩阵比较定理，考虑

如果令r＝（I－αD1）－1（αD1＋C）x，由D1和C的取值以及（I－αD1）－1≥0可得r＞0.利用文献［4］的结论可得：

定理2 对线性方程组Ax＝b，TJC和TJCα分别是由（4）和（5）式给出的JOR迭代法的迭代矩阵，如果矩阵A＝I－L－U是严格对角占优的L－矩阵，满足0＜ai1a1i≤1，i＝2，3，…，n，0＜ω≤1，那么当1≤α≤，就有ρ（TJCα）≤ρ（TJC）≤ρ（TJ）＜1.

证明由其中MJC＝（I－D1），NJC＝（I－D1）－ωPA，利用定理1的证明有MJC＝（I－D1）－1≥0，从L和C的构造可得LC≥0，结合0＜ω≤1，有

再比较MJCα和MJC，结合条件有（I－αD1）≤（I－D1），所以可得，按照引理有ρ（TJCα）≤ρ（TJC），综合文献［6，8］以及定理1中α＝1时的情形就有ρ（TJCα）≤ρ（TJC）≤ρ（TJ）＜1.定理3 对线性方程组Ax＝b，TJ和TJCα分别是由（3）式和（5）式给出的JOR迭代法的迭代矩阵，如果矩阵A＝I－L－U是严格对角占优的L矩阵，且0＜ai1a1i≤1，i＝2，3，…，n，0＜ω≤1，当αi满足1≤那么当α1＜α2时，就有：

（1）当ρ（TJ）＜1时，ρ（TJCα2）≤ρ（TJCα1）；

（2）当ρ（TJ）≥1时，ρ（TJCα2）≥ρ（TJCα1）.

证明由定理2的证明知，TJCα是非负矩阵，结合Perron－Frobenius定理可知其谱半径是它的某个特征值，且有该特征值对应的非负向量x＝（x1，x2，…，xn）T满足TJCαx＝ρ（TJCα）x.那么当αi满足1≤且α1＜α2时，有（I－α1D1）≥（I－α2D1），结合其为对角矩阵，所以有（I－α1D1）－1≤（I－α2D1）－1.利用定理2考虑

也就是

当ρ（TJ）＜1，且α1＜α2时，上述不等式右端小于零，从而ρ（TJCα2）≤ρ（TJCα1）；

当ρ（TJ）≥1，α1＜α2时，考虑

所以，当ρ（T）＝λ≥1时，上述不等式右端大于或等于零，即ρ（TJCα2）≥ρ（TJCα1）.

注从定理3的证明可以看出，当线性方程组Ax＝b的JOR迭代法收敛时，随着参数α的增大，ρ（TJCα）在减小，所以当，这种预条件后含参数分裂形式的JOR迭代法的谱半径达到最小.

4 数值例子

如果线性方程组Ax＝b的系数矩阵

那么通过计算可知，以A为线性方程组的系数矩阵，对不同的松弛因子ω，JOR迭代法在预条件前后的谱半径比较如表1.

从表1可以看出，随着松弛因子ω的增大，JOR迭代法的谱半径逐渐减小.在预条件因子P＝（I＋C）的作用下，相应的预条件后的JOR迭代法的谱半径都能减小，从而可知预条件方法能加快JOR迭代法的收敛性.

在引入参数α改变预条件后JOR迭代法的分裂形式，当取定一个确定的松弛因子ω时，随着参数α的变化，可以发现改进分裂形式后的JOR迭代法的收敛速度要优于一般的预条件方法.

从表2可知，不论松弛因子ω＝0.6或者ω＝0.8，当参数α＝1时，改进分裂形式的JOR迭代法的谱半径都等于一般预条件后的JOR迭代法的谱半径，符合分裂的情况.随着参数α的增大，新分裂形式下的迭代法的谱半径都在减小，具体的取ω＝0.6，随着参数α的一直增大，改进分裂形式的JOR迭代法的谱半径随α的变化情况如图1所示.

从图1可以看出，随着参数α的增大，谱半径ρ（TJCα）逐渐减小，但是当参数，谱半径ρ（TJCα）突然增大，并且不再收敛，这符合定理3的结论.

5 结论

从理论证明和数值分析可以看出，不但预条件方法能够加速JOR迭代法的收敛性，而且在预条件后引入参数改进矩阵的分裂形式也能加速迭代法的收敛性，同时随着参数取值的不同可以更好地加速JOR迭代法的收敛性.这些可以给在有限元等问题中涉及的大型线性方程组的迭代求解提供新的理论依据.

［1］ JAE HEON YUN.Compaison results of the preconditioned AOR methods for L－matrices［J］.Applied Mathematics and Computation，2011，218：3399－3413.

［2］ QINGBING LIU，GUOLING CHEN，JING CAI.Convergence analysis of the preconditioned Gauss－Seidel method for H－matrices［J］.Computers and Mathematics with Applications，2008，56：2048－2053.

［3］ HIROSHI NIKI，KYOUJI HARADA，MUNENORI MORIMOTO，et al.The survey of preconditioners used for accelerating the rate of convergence in the Gauss－Seidel method［J］.Journal of Computational and Applied Mathematics，2004，165：587－600.

［4］ DAVID M YONG.Iterative solution of large linear systems［M］.New York：Academic Press，1971：26－49.

［5］ RICHARD S VARGA.Matrix iterative analysis［M］.Heidelberg：Spring－Verlag，2000：60－80.

［6］ 张谋成，黎稳.非负矩阵论［M］.广州：广东高等教育出版社，1995：71－93.

［7］ ZHUAN－DE WANG，TING－ZHU HUANG.Comparison result between Jacobi and other iterative methods［J］.Journal of Computational and Applied Mathematics，2004，169：45－51.

［8］ XUE－ZHONG WANG，TING－ZHU HUANG，YING－DING FU.Comparison results on preconditioned SOR－type iterative method for Z－matrices linear systems［J］.Journal of Computational and Applied Mathematics，2007，206：726－732.

Convergence and diverge analysis of the JOR iterative method with parameter in preconditioned

WANG Hui－qin，LEI Gang

（Department of Mathematics，Baoji University of Arts and Sciences，Baoji 721013，China）

For the JOR iteration method to solving the linear system Ax＝b，this paper apply the preconditioner to accelerate convergence of the JOR iteration method，and give a more generally preconditioned JOR iteration method by leading into parameterα.It prove that the rate of convergence of this method is faster than normal JOR iteration method，then have found the parameter optimal numerical.Last the results are verified by numerical example.

the JOR iteration method；convergence；precondition；spectral radius

O 241.6 ［学科代码］ 110·6150 ［

］ A

（责任编辑：陶理）

1000－1832（2015）01－0043－05

10.16163／j.cnki.22－1123／n.2015.01.009

2013－10－12

国家自然科学基金资助项目（11371031）；陕西省教育厅计划项目（14JK1052）；陕西省自然科学基础研究计划项目

（2013JM1001）.

王慧勤（1979—），女，硕士，讲师，主要从事数值计算与数据挖掘研究；雷刚（1977—），男，硕士，副教授，主要从事数值计算与并行分析研究.