预条件下Gauss-Seidel迭代法的收敛性 Convergence of Preconditioned Gauss-Seidel Iterative Method

doi:10.12677/PM.2020.1011119

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

PureMathematics理论数学,2020,10(11),1007-1014

PublishedOnlineNovemb er2020inHans.http://www.hanspub.org/journal/pm

https://doi.org/10.12677/pm.2020.1011119

预条件下Gauss-Seidel迭代法的收敛性

黄黄黄江江江玲玲玲

陕西师范大学，数学与信息科学学院，陕西西安

Email:1739124141qq.com

收稿日期：2020年10月13日；录用日期：2020年11月4日；发布日期：2020年11月11日

摘要

假设在线性方程组𝐴𝑥=𝑏的系数矩阵𝐴是非奇异𝑀-阵，通过比较预条件下Gauss-Seidel迭

代法的迭代矩阵的谱半径与经典Gauss-Seidel迭代法的迭代矩阵谱半径大小，得到了预条件

下Gauss-Seidel迭代法的收敛速度要快于经典的Gauss-Seidel迭代法的收敛速度，从而得出该

预条件处理的有效性，最后用一个数值算例验证了该结论。

关键词

非奇异M矩阵，Gauss-Seidel迭代法，谱半径，预条件，收敛性

ConvergenceofPreconditioned

Gauss-SeidelIterativeMethod

JianglingHuang

SchoolofMathematicsandInformationScience,ShaanxiNormalUniversity,Xi’anShaanxi

Email:1739124141qq.com

Received:Oct.13

𝑡ℎ

,2020;accepted:Nov.4

𝑡ℎ

,2020;published:Nov.11

𝑡ℎ

,2020

Abstract

Assumingundertheconditionthatthecoeﬃcient matrix𝐴inlinearequations𝐴𝑥= 𝑏

文章引用:黄江玲.预条件下Gauss-Seidel迭代法的收敛性[J].理论数学,2020,10(11):1007-1014.

DOI:10.12677/pm.2020.1011119

黄江玲

isannonsingular𝑀-matrix,bycomparingthespectralradiusoftheiterativematrix

oftheGauss-Seideliterativemethodunderpreconditionswiththespectralradiusof

theiterativematrixoftheclassicalGauss-Seideliterativemethod,itisobtainedthat

theconvergencespeedoftheGauss-Seideliterativemethodunderpreconditionsis

fasterthanthatoftheclassicalGauss-Seideliterativemethod,andtheeﬀectiveness

ofthepreconditioningisobtained.Finally,anumericalexampleisusedtoverifythe

conclusion.

Keywords

Non-SingularMMatrix,Gauss-SeidelIterativeMethod,SpectralRadius,

Preconditioned,Convergence

○2020byauthor(s)andHansPublishersInc.

This work is licensed undertheCreative Commons Attribution International License (CCBY 4.0).

http://creativecommons.org/licenses/by/4.0/

1.引言

实际生活中的很多问题最后往往会与求解线性方程组对应起来,譬如交通中的网络流问题,最小

二乘法曲线拟合问题,最优化问题,最后往往是一个大型稀疏线性方程组的求解问题.然而迭代法是求

解大型稀疏的一种重要方法,迭代法的研究一直都是国内外的热点问题之一,在实际应用中具有非常

重要的意义[1][2].因此,考虑线性方程组

𝐴𝑥= 𝑏.(1)

为了方便,假设线性方程组的系数矩阵

𝐴= 𝐼−𝐿−𝑈,(2)

其中𝐴是𝑛阶非奇异矩阵,𝐼是𝑛阶单位矩阵, −𝑈是𝐴的严格上三角矩阵,−𝐿是𝐴的严格下三

角矩阵.在文[3]中，求解线性方程组(1)的古典Gauss-Seidel迭代矩阵为

𝐺= (𝐼−𝐿)

−1

𝑈= 𝑀

−1

𝑁.(3)

其中𝑀= 𝐼−𝐿,𝑁= 𝑈.为了加速迭代法的收敛性,常常考虑预处理方法[4],预条件方法是通过寻找

DOI:10.12677/pm.2020.10111191008理论数学

黄江玲

一个有效的非奇异矩阵𝑃,将𝐴𝑥= 𝑏表示为如下形式

𝑃𝐴𝑥= 𝑃𝑏.(4)

对此,近年来很多的学者针对不同的迭代方法提出了不同的预条件[5][6][7][8][9].文[10][11][12]

[13]讨论了预条件下Gauss-Seidel迭代法的收敛性,本文假设线性方程组的系数矩阵为非奇异𝑀−矩

阵.本文考虑预条件𝑃=𝐼+𝑆

𝛼,𝛽

,并在此预条件下讨论Gauss-Seidel迭代法的收敛性,其中𝑆

𝛼,𝛽

矩

阵形式如下

𝑆

𝛼,𝛽

⎛

⎜

⎝

0−𝛼

(𝑎

+𝛽

)−𝛼

(𝑎

+𝛽

)···−𝛼

𝑛−1

(𝑎

1𝑛

+𝛽

𝑛−1

)

000···0

⎞

⎟

⎠

那么在预条件𝑃= 𝐼+𝑆

𝛼,𝛽

,的作用下,

𝐴

𝑠

= (𝐼+𝑆

𝛼,𝛽

)𝐴= (𝐼−𝐸

𝑠

)−𝐿−(𝑈−𝑆

𝛼,𝛽

+𝐹

𝑠

) = 𝐷

𝑠

−𝐿

𝑠

−𝑈

𝑠

= 𝑀

𝑠

−𝑁

𝑠

其中:𝐸

𝑠

,𝐹

𝑠

分别为𝑆

𝛼,𝛽

(𝐿+ 𝑈)的主对角矩阵以及严格上三角矩阵.𝐷

𝑠

=(𝐼−𝐸

𝑠

),𝐿

𝑠

=𝐿,𝑈

𝑠

(𝑈−𝑆

𝛼,𝛽

+𝐹

𝑠

)分别为预条件后𝐴

𝑠

的主对角矩阵,严格下三角矩阵以及严格上三角矩阵.

那么预条件后系数矩阵𝐴

𝑠

所对应的Gauss-Seidel迭代法的迭代矩阵为

𝐺

𝑠

= 𝑀

−1

𝑠

𝑁

𝑠

.(4)

其中𝑀

𝑠

= (𝐷

𝑠

−𝐿

𝑠

),𝑁

𝑠

= 𝑈

𝑠

2.基本定义及引理

定义1[14]若𝐴∈𝑅

𝑛,𝑛

, 𝐴可表示为𝐴= 𝑠𝐼−𝐵, 𝐼为𝑛阶单位阵, 𝐵≥0, 当𝑠≥𝜌(𝐵) 时,称

𝐴为𝑀−阵.特别当𝑠>𝜌(𝐵)时,称𝐴为非奇异𝑀−阵.当𝑠= 𝜌(𝐵) 时,称𝐴为奇异𝑀−阵.

定义2[8]若𝐴∈𝑍

𝑛,𝑛

,𝐴可逆且𝐴

−1

≥0,则称𝐴为非奇异𝑀−阵.

定义3[8]设𝐴为实方阵,若𝑀为非奇异矩阵,则称𝐴=𝑀−𝑁是𝐴的一个分裂,若

𝜌(𝑀

−1

𝑁) <1,则称分裂𝐴= 𝑀−𝑁是收敛的.如果

(1)M分裂,如果𝑀是非奇异M矩阵且𝑁≥0;

(2)正规分裂,如果𝑀

−1

≥0且𝑁≥0;

DOI:10.12677/pm.2020.10111191009理论数学

黄江玲

(3)弱正规分裂,如果𝑀

−1

≥0且𝑀

−1

𝑁≥0.

引理1[14]若𝐴为非负不可约方阵,则

(1)谱半径𝜌(𝐴)为𝐴的非负特征值;

(2)𝐴有与其谱半径𝜌(𝐴)相对应的非负特征向量;

(3)𝐴的任一元素增加时,𝜌(𝐴)不减.

引理2[8]𝐴= 𝑀−𝑁是𝐴的弱正规分裂或者正规分裂,则𝜌(𝑀

−1

) <1的充要条件是𝐴

−1

≥0.

引理3[8]设𝜆∈(0,1],且𝑧∈(−∞,0),𝑄∈(

𝜆−𝑦𝑧

𝑦

,−𝑧)∩(0,−𝑧),那么集合𝑄非空.

引理4[10]设𝐴= 𝑀

−𝑁

= 𝑀

−𝑁

是𝐴的两个弱正规分裂,如果𝐴

−1

≥0,且下列条件成立

之一:

(1)𝑁

≤𝑁

;(2)𝑀

−1

≥𝑀

−1

,𝑁

≥0;(3)𝑀

−1

≥𝑀

−1

,𝑁

≥0;

则有𝜌(𝑀

−1

𝑁

) ≤𝜌(𝑀

−1

𝑁

3.结果与证明

定理假设线性方程组的系数矩阵𝐴是非奇异的𝑀阵,满足当0<𝑎

𝑘+1,1

𝑎

1,𝑘+1

,𝛽

𝑘

∈

(

1−𝑎

1,𝑘+1

𝑎

𝑘+1,1

𝑎

𝑘+1,1

,−𝑎

1,𝑘+1

)∩(0,−𝑎

1,𝑘+1

),𝛼

𝑘

∈(0,1],

𝑛−1



𝑘=1

𝛼

𝑘

≤1,(𝑘= 1,2,···,𝑛−1) 时,则有𝐺,𝐺

𝑠

都

非负.且𝜌(𝑀

−1

𝑠

𝑁

𝑠

) ≤𝜌(𝑀

−1

𝑁) <1.其中𝑀

−1

𝑠

𝑁

𝑠

,𝑀

−1

𝑁分别由(3)与(4)给出.𝜌(𝑀

−1

𝑠

𝑁

𝑠

),𝜌(𝑀

−1

𝑁)

分别是系数矩阵𝐴,𝐴

𝑠

相对的Gauss-Seidel迭代法的迭代矩阵的谱半径.

证明由𝐴是非奇异的𝑀阵以及(3)式有

𝑀

−1

= (𝐼−𝐿)

−1

= [1+𝐿+𝐿

+···+𝐿

𝑛−1

] ≥0,𝑁= 𝑈≥0

𝐺=𝑀

−1

𝑁≥0.得𝐺是非负矩阵,根据定义3,𝐴=𝑀−𝑁为𝐴的正规分裂.现证𝐷

𝑠

≥0,𝐿

𝑠

≥

0,𝐹

𝑠

≥0以及𝐸

𝑠

≥0.因为预条件后系数矩阵𝐴

𝑠

为

𝐴

𝑠

⎛

⎜

⎝

1−

𝑛−1



𝑘=1

𝛼

𝑘

𝑎

𝑘+1,1

(𝑎

1,𝑘+1

+𝛽

𝑘

)···𝑎

1𝑛

−

𝑛−1



𝑘=1

𝛼

𝑘

𝑎

𝑘+1,𝑛

(𝑎

1,𝑘+1

+𝛽

𝑘

)

𝑎

···𝑎

2,𝑛

𝑎

𝑛,1

···1

⎞

⎟

⎠

令𝐷

𝑠

= 𝑑𝑖𝑎𝑔(𝐴

𝑠

) = 𝑑𝑖𝑎𝑔(𝑑

,1,···,1),𝐸

𝑠

= 𝑑𝑖𝑎𝑔(𝑆

𝛼,𝛽

(𝐿+𝑈)) = 𝑑𝑖𝑎𝑔(𝑒

,0,···,0),

其中𝑑

= 1−

𝑛−1



𝑘=1

𝛼

𝑘

𝑎

𝑘+1,1

(𝑎

1,𝑘+1

+𝛽

𝑘

),𝑒

𝑛−1



𝑘=1

𝛼

𝑘

𝑎

𝑘+1,1

(𝑎

1,𝑘+1

+𝛽

𝑘

), 由条件0 <𝑎

𝑘+1,1

𝑎

1,𝑘+1

,𝛽

𝑘

∈

(

1−𝑎

1,𝑘+1

𝑎

𝑘+1,1

𝑎

𝑘+1,1

,−𝑎

1,𝑘+1

)∩(0,−𝑎

1,𝑘+1

),𝛼

𝑘

∈(0,1],

𝑛−1



𝑘=1

𝛼

𝑘

≤1,(𝑘= 1,2,···,𝑛−1),可知

DOI:10.12677/pm.2020.10111191010理论数学

黄江玲

𝑑

= 1−

𝑛−1



𝑘=1

𝛼

𝑘

𝑎

𝑘+1,1

(𝑎

1,𝑘+1

+𝛽

𝑘

) >1−

𝑛−1



𝑘=1

𝛼

𝑘

𝑎

𝑘+1,1

(𝑎

1,𝑘+1

1−𝑎

1,𝑘+1

𝑎

𝑘+1,1

𝑎

𝑘+1,1

)

= 1−

𝑛−1



𝑘=1

(𝛼

𝑘

𝑎

𝑘+1,1

𝑎

1,𝑘+1

+𝛼

𝑘

−𝛼

𝑘

𝑎

𝑘+1,1

𝑎

1,𝑘+1

)

= 1−

𝑛−1



𝑘=1

𝛼

𝑘

≥0

𝑒

𝑛−1



𝑘=1

𝛼

𝑘

𝑎

𝑘+1,1

(𝑎

1,𝑘+1

+𝛽

𝑘

) >

𝑛−1



𝑘=1

𝛼

𝑘

𝑎

𝑘+1,1

(𝑎

1,𝑘+1

1−𝑎

1,𝑘+1

𝑎

𝑘+1,1

𝑎

𝑘+1,1

)

𝑛−1



𝑘=1

(𝛼

𝑘

𝑎

𝑘+1,1

𝑎

1,𝑘+1

+𝛼

𝑘

−𝛼

𝑘

𝑎

𝑘+1,1

𝑎

1,𝑘+1

)

𝑛−1



𝑘=1

𝛼

𝑘

所以𝐷

𝑠

≥0,𝐸

𝑠

>0.又

𝐿

𝑠

= 𝐿=

⎛

⎜

⎝

00···00

−𝑎

0···00

−𝑎

𝑛−1,1

−𝑎

𝑛−1,2

···00

−𝑎

𝑛,1

−𝑎

𝑛,2

···−𝑎

𝑛,𝑛−1

⎞

⎟

⎠

.𝑈

𝑠

⎛

⎜

⎝

0𝑢

···𝑢

1,𝑛−1

𝑢

1𝑛

00···−𝑎

2,𝑛−1

−𝑎

2,𝑛

00···0−𝑎

𝑛−1,𝑛

00···00

⎞

⎟

⎠

其中

𝑢

1𝑗

= −𝑎

1𝑗

𝑛−1



𝑘=1

𝛼

𝑘

𝑎

𝑘+1,𝑗

(𝑎

1,𝑘+

+𝛽

𝑘

) >−𝑎

1𝑗

𝑛−1



𝑘=1

𝛼

𝑘

𝑎

𝑘+1,𝑗

(𝑎

1,𝑘+1

−𝑎

1,𝑘+1

)= −𝑎

1𝑗

≥0

(𝑗= 2,3,···,𝑛),所以𝐿

𝑠

≥0,𝐹

𝑠

≥0,𝑈

𝑠

= (𝑈−𝑆

𝛼,𝛽

+𝐹

𝑠

) ≥0,由(4)知

𝐺

𝑠

= (𝐷

𝑠

−𝐿

𝑠

)

−1

𝑈

𝑠

= [𝐼+𝐷

−1

𝑆

𝐿

𝑠

+(𝐷

−1

𝑠

𝐿

𝑠

)

+···]𝐷

−1

𝑠

𝑈

𝑠

≥0.

因此𝐺和𝐺

𝑠

都是非负矩阵.

因为

𝐴

𝑠

= (𝐼+𝑆

𝛼,𝛽

)𝐴= (𝐼−𝐸

𝑠

)−𝐿−(𝑈−𝑆

𝛼,𝛽

+𝐹

𝑠

) = 𝐷

𝑠

−𝐿

𝑠

−𝑈

𝑠

= 𝑀

𝑠

−𝑁

𝑠

DOI:10.12677/pm.2020.10111191011理论数学

黄江玲

以及上面的证明可知

(𝐼−𝐸

𝑠

)

−1

= (𝐼+𝐸

𝑠

+···) ≥𝐼,𝐿≥0

则有

𝑀

−1

𝑠

= [(𝐼−𝐸

𝑠

)−𝐿]

−1

= [(𝐼−(𝐼−𝐸

𝑠

)

−1

𝐿]

−1

(𝐼−𝐸

𝑠

)

−1

≥(𝐼+𝐿+𝐿

+···) = (𝐼−𝐿)

−1

= 𝑀

−1

≥0.

𝑁

𝑠

= (𝑈−𝑆

𝛼,𝛽

+𝐹

𝑠

) ≥0

令𝑀

= (𝐼+𝑆

𝛼,𝛽

)

−1

𝑀

𝑠

,𝑁

= (𝐼+𝑆

𝛼,𝛽

)

−1

𝑁

𝑠

,那么

𝐴= (𝐼+𝑆

𝛼,𝛽

)

−1

𝐴

𝑠

= (𝐼+𝑆

𝛼,𝛽

)

−1

𝑀

𝑠

−(𝐼+𝑆

𝛼,𝛽

)

−1

𝑁

𝑠

= 𝑀

−𝑁

而𝑀

−1

= 𝑀

−1

𝑠

(𝐼+𝑆

𝛼,𝛽

).所以

𝑀

−1

𝑁

= 𝑀

−1

𝑠

(𝐼+𝑆

𝛼,𝛽

)(𝐼+𝑆

𝛼,𝛽

)

−1

𝑁

𝑠

= 𝑀

−1

𝑠

𝑁

𝑠

≥0.

因此,根据定义3,𝐴= 𝑀−𝑁= 𝑀

−𝑁

均为𝐴的弱正规分裂.

现考虑,

𝑀

−1

−𝑀

−1

= 𝑀

−1

𝑠

(𝐼+𝑆

𝛼,𝛽

)−𝑀

−1

≥𝑀

−1

(𝐼+𝑆

𝛼,𝛽

)−𝑀

−1

= 𝑀

−1

𝑆

𝛼,𝛽

≥0

所以,

𝑀

−1

≥𝑀

−1

,𝑁≥0

由引理4,可知

𝜌(𝑀

−1

𝑁

) ≤𝜌(𝑀

−1

𝑁)

又因为𝐴为非奇异𝑀−矩阵,因此根据引理2

𝐴

−1

≥0,𝜌(𝑀

−1

𝑁) <1

综上,

𝜌(𝑀

−1

𝑠

𝑁

𝑠

) ≤𝜌(𝑀

−1

𝑁) <1

4.数值例子

例1设线性方程组𝐴𝑥= 𝑏的系数矩阵是

𝐴=

⎛

⎜

⎝

1−0.1−0.4−0.3

01−0.3−0.1

−0.3−0.11−0.2

−0.3−0.3−0.11

⎞

⎟

⎠

DOI:10.12677/pm.2020.10111191012理论数学

黄江玲

显然·𝐴是非奇异𝑀−矩阵,通过𝑀𝐴𝑇𝐿𝐴𝐵计算可得,当参数𝛼

𝑘

=𝛽

𝑘

=0,(𝑘=1,2,3)

时,𝜌(𝐺) =0.4396.那么在预条件𝑃=𝐼+𝑆

𝛼,𝛽

的作用下,当𝛼

= 0.95,𝛼

= 0.005,𝛼

= 0.005,𝛽

𝛽

= 𝛽

= 0.01时,𝜌(𝐺

) = 0.4235,可以看出预条件下Gauss-Seidel迭代法的迭代矩阵的谱半径小于

经典的Gauss-Seidel迭代法的迭代矩阵的谱半径,从而说明了该预条件的有效性.当参数𝛼,𝛽取值不

同时，谱半径也不同.

5.结论

从数值算例可知,当线性方程组𝐴𝑥=𝑏的系数矩阵𝐴是非奇异𝑀−阵时,预条件方法可以

改善Gauss-Seidel迭代法的收敛性,当参数𝛼,𝛽取值不同时，谱半径大小也不同,因此如何选择最优

参数,有待进一步研究.

参考文献

[1]陈国良,安虹,陈俊.并行算法实践[M].北京:高等教育出版社,2004.

[2]James, K.R.andRiha,W.(1995)Convergence Criteria forSuccessive over Relaxation. SANM

JournalonNumericalAnalysis,12,13-145.

[3]徐树方,高立,张平文.数值线性代数[M].第二版.北京:北京大学出版社,2013.

[4]Hiiroshi, N.K., Kunenori, H.,Munenori, M., etal.(2004) TheSurvey ofPre-Conditioners Used

forAcceleratingtheRateofConvergenceintheGauss-SeidelMethod.JournalofComputa-

tionalandAppliedMathematics,165,587-600.

https://doi.org/10.1016/j.cam.2003.11.012

[5]雷刚,王慧勤,畅大为. 预条件下2PPJ型方法收敛性的加速[J].江西师范大学学报(自然科学版),

2006,30(1):35-37.

[6]尤晓琳.预条件𝐼+ 𝑆的SSOR迭代法及比较定理[J].河南教育学院学报(自然科学版),2019,

28(3):1-3.

[7]蔡静.一类预处理Jacobi迭代法及其收敛性分析[J].湖州师范学院学报,2019,41(8):122-126.

[8]Behzadi, R. (2019) ANew ClassAOR Preconditioner forL-Matrices. JournalofMathematical

ResearchwithApplications,39,101-110.

[9]Dehghan,M.andHajarian,M.(2014)ModiedAORIterativeMethodstoSolveLinearSystems.

JournalofVibrationandControl,20,661-669.

https://doi.org/10.1177/1077546312466562

[10]庄伟芬,卢琳璋.(𝐼+𝑆𝑚𝑎𝑥)预条件Gauss-Seidel迭代法的进一步探索[J].厦门大学学报(自然

科学版),2004,43(z1):349-352.

[11]高树玲,曾京玲.一类新的预条件Gauss-Seidel迭代法[J].周口师范学院学报,2012,29(2):

9-12.

DOI:10.12677/pm.2020.10111191013理论数学

黄江玲

[12]吴梅君,杨晨.一类新的预条件Gauss-Seidel迭代法[J].高师理科学刊,2018,38(12):17-18.

[13]许云霞,雷学红,李耀堂.H-矩阵的一个新的预条件Gauss-Seidel迭代方法(英文)[J].昆明学院

学报,2008,30(4):3-7.

[14]Li, W. and Sun, W.W. (2000) Modiﬁed Guass-Seidel Type Methods and Jacobi Type Methods

forZ-Matrices.LinearAlgebraandItsApplications,317,227-240.

https://doi.org/10.1016/S0024-3795(00)00140-3

DOI:10.12677/pm.2020.10111191014理论数学