稀疏线性方程组求解的逐次超松弛迭代法

第24卷　第4期

2006年10月

沈阳师范大学学报(自然科学版)

Journal of S henyang Norm al U niversity (N atural Science )

V ol 124, N o. 4Oct. 2006

文章编号:1673-5862(2006) 04-0407-04

稀疏线性方程组求解的逐次超松弛迭代法

王诗然

(沈阳电力勘测设计院工程部, 辽宁沈阳　110005)

摘　　　要:针对稀疏线性方程组求解问题, 在论述迭代法离散化处理基础上, 以二维热传导方

程为例, 导出了热传导方程离散化后线性方程组, 用超松弛(SOR ) 迭代法对产生的稀疏线性方程组进行迭代法求解, 并分析了收敛性和收敛速度・将超松弛迭代算法在计算机上实现, 得出了一组与精确解较接近的数值解, 验证了逐次超松弛(SOR ) 迭代法的精确性・关　键　词:稀疏线性方程组; 离散化; 逐次超松弛迭代法中图分类号:TP 391　　　文献标识码:A

1　迭代法的产生背景

, 以至使人们不能在允许

, , 客观上要求用新的方法来解决大维数方程组的求解问题・

, 在解题时, 要对原方程组矩阵作一根本的变换, 从而可能使条件数变坏, 也可能破坏了变换前后方程组的等价性, 以及丧失使原方程组的对称性等・探求新的有效的解题方法依然是迫切的任务・通过对GS 法进行改进, 从而产生了逐次超松弛(SOR ) 迭代法・

在求解过程中由于线性方程组的系数矩阵维数较大, 采用计算机编写算法来求解, 从而实现了对解析模型的计算机数值逼近的计算方法・本论文以逐次超松弛迭代法为主要的求解方法・

2　二维热传导方程的离散化过程

2. 1　向后差分格式

二维热传导方程

2

22+=a +f (x , y , t ) , 00)

9t 9x 29y 2u (x , y , 0) =φ(x )

u (0, y , t ) =u (l , y , t ) , u (x , 0, t ) =u (x , l , t )

取步长h =l/N ,

τ=T/M , 用两族平行线x =x j =jh , y =y k =kh , 将求解域划分成矩形网格, 网点为

(x j , x k

, t n ) (t n =n τ) , r =

u -u n +1

n

2h

u j +1-2u j , k +u j -1, +u j +1, k -2u j , k +u j -1, k +u j +1, k -2u j , k +

u j -1, k +

n

n

n

n

n

n

n +1

n

+1

n +1

n +1

n +1

n +1

2

τ

n +1n

n

2=2

h

u j , k +1-2u j , k +u

j , k

n

+1

n +1

n +1n +1n +1

+τf

n +1

j , k

n

u j , k -u j , k =r

u j , k +1-2u j , k +u j , k -u j , k +1-2u j , k +u j , k -1

n

n -1

n

n

n

n

n +1

+2τf j , k +2τf j , k

n

即

u j , k -u j , k =r

n

n -1

(1+4r ) u j , k -ru j -1, k -ru j +1, k -ru j , k +1-ru j , k -1=u j , k +2τf j , k

由此可得线性方程组

收稿日期:2006206220

作者简介:王诗然(1982-) , 女, 辽宁新宾人, 沈阳电力勘测设计院助理工程师・

408

沈阳师范大学学报(自然科学版) 　　　　　　　　　　　　　　第24卷

(1+4r ) I -S

-r I

-r I (1+4r ) I -S

U

1

k k

U 1

U 2

k -1k -1

+τf 1+τf 2

f

f

O O

-r I

U 2

O -r I

(1+4r ) I -

…

U k

…

U N

k -1

+τf f

010O

O O 1

1T

, U i =(u i 1, u i 2, …, u iN ) , I 为单位矩阵・

k

k

k

k

其中, S =

1

3　热传导问题离散化后线性方程组的迭代法

3. 1　逐次超松弛迭代法

在很多情况下, 由于J 法和GS 法收敛速度较低, 所以需要对GS 法进行改进・假设计算k +1个近似解x (k +1) 时, 分量x 1

x i

(k +1)

(k +1)

i -1

, x 2

(k +1)

, , …, x i -

(k +1)

1

GS 法那样计算

b i -=

6

i (k )

a j x j

-

n

j x j

i (再用某个参数ω作加权平均, () k 1) (k ) (k ) (k +1) (k ) x (1ω) x i =x i +ω( x i -x i ) 或整理成

i -1

x i

(k +1)

=(1-ω) x i

(k )

b i -+

6

a ij x

(k +1)

j

-

6

n

a ij x j

(k )

a ii

　i =1, 2, …

, n ・

这称为逐次超松弛迭代法, 简记SOR 方法, 其中ω称松弛因子・当ω=1时就是GS 法・3. 2　逐次超松弛迭代法的收敛性判别

1) 收敛性判别条件

SOR 迭代法收敛的充分必要条件是ρ(λω)

ω的关系, 再讨论SOR 方法收敛的条件・

定理1　(Kahan ) 对任意的A ∈R n ×n , 设其对角元皆非零, 则对所有实数ω, 有

ρ(λω) ≥ω-1推论:如果解Ax =b 的SOR 方法收敛, 则有ω-1

定理2　(Ostrowski 2Reich ) 设A ∈R n ×n

, A 对称正定, 且0

2) 收敛速度的估计

SOR 迭代法的迭代矩阵λ因此, 需要找到ω与ω有关, 当选取不同的ω时, 其迭代速度也有所不同・

最优的松弛因子ωb , 使对应ωb 的SOR 方法收敛最快・

定理3　设A ∈R n ×n , A =D -L -U 为L U 分解・如果存在排列矩阵P , 使

PA P

T

=

D 1M 2

M 1D 其中, D 1, D 2为对角方阵, 则称A 是22循环的・此外, 若当α≠0时, 矩阵

-1-1-1

αD L +αD U

的特征值都和α无关, 则称A 是相容次序矩阵・

定理4　设A ∈R n ×n , A 有非零的对角元, 且是22循环和相容次序的・又设B =D -1(L +U ) 是方程组Ax =b 的Jacobi 迭代的迭代矩阵, 且B 2的所有特征值均在[0, 1) 上・记μ=ρ(B ) 及

ωb =

1+(1-μ2)

2

第4期　　　　　　　　　　　王诗然:稀疏线性方程组求解的逐次超松弛迭代法409

则方程组的SOR 方法迭代矩阵的谱半径ρ(λω) 满足

ρ(λω) =

ω-1,

ρ(λωb ) =min ρ(λω) ω

0≤≤2

224

2

,

0

ωb ≤ω≤2

且当0

lim ωω

→b -0

(λ)

ωω=-∞d

3. 3　二维热传导方程离散化后的线性方程组的超松弛迭代法

1) 理论解法

同上面解一维热传导方程相似, 解二维热传导问题需得出下列计算公式:

(1) (2)

x 1=ω[b 1-(1+2r ) u 1+ru 1](1+2r )

x i =ω[b i -(1+2r ) u 1

(i )

+r (u 1

i -1

+u 1) ](1+2r ) (1r )

i +1

x n =ω[b n -(1+2r ) u 1

(n -1)

+1

(n -2)

2) 收敛性判别

关于SOR ・3) ωb , 若提高该迭代法的收敛速度, ωb 即可・3. 4　以方程

2

2=D x +D +f (x , y , t ) , 　0≤x , y ≤π, t >0y 9t 9x 29y 2u (x , y , 0) =sin x sin y , 　0≤x ≤π

u (0, y , t ) =u (l , y , t ) =0, u (x , 0, t ) =u (x , l , y ) =0D x =D y =0101, f (x , y , t ) =Q =10

) 分为50等份, 用特殊算法进行计算, 得为例进行精确解计算・在方程中

到各个点在不同时间t (以t =014s 为例) 内所对应的精确值如下(只列举典型部分) :

2. 879083; 3. 799029; 4. 018457; 4. 068228; 4. 090255; 4. 108895; 4. 126805; 4. 144134;

4. 265669; 4. 255839; 4. 244982; 4. 233140; 4. 220358; 4. 206684; 4. 192171; 4. 176871; 4. 160840; 4. 144134; 4. 126805; 4. 108895; 4. 090255; 4. 068228; 4. 018457; 3. 799029・3. 5　二维热传导方程离散化后线性方程组超松迭代法的数值解

以上述热传导方程为例, 其离散化后线性方程组的逐次超松弛迭代法算法的计算机编程略, 其运算结果与精确解的比较如表1所示(只列举典型部分) ・

表1　运算结果比较

t 值

x 值

精确解

2. 091059

2. 0910594. 0902554. 0902556. 0823486. 0823488. 0495508. 049550

数值解

2. 0949552. 0949554. 0908124. 0908126. 0713666. 0713668. 0202718. 020271

误　差

0. 0038960. 0038960. 0005570. 0005570. 0109820. 0109820. 0292790. 029279

0. 20. 20. 40. 40. 60. 60. 80. 8(0. 314159,0. 314159) (0. 314159,2. 827431) (0. 314159,0. 314

159) (0. 314159,2. 827431) (0. 314159,0. 314159) (0. 314159,2. 827431) (0. 314159,0. 314159) (0. 314159,2. 827431)

410

沈阳师范大学学报(自然科学版) 　　　　　　　　　　　　　　第24

卷

4　结　　论

1) 逐次超松弛迭代法与Jacobi 迭代法,Seidel 迭代法相比, 收敛速度较快・

2) 由逐次超松弛迭代法求出的方程组的数值解与该方程组的精确解十分接近, 可见二维热传导方

程离散化后线性方程组的逐次超松弛迭代法的精确性较高・

3) 逐次超松弛迭代法可以广泛地应用于实际・该算法不仅可以用来求解热传导问题, 还可以用来求解与热传导问题相类似的高阶稀疏线性方程组・这样可以大大减少计算量和计算机的内存储量, 从而提高计算效率・参考文献:

[1][2][3][4][5][6][7][8][9][10]

杨华军・数学物理方法与计算机仿真[M ]・北京:电子工业出版社, 2005・

FERZIGER J H , PERIC M. Com putational methods for fluid dynamics[M ].Berlin :S pringer , 1996. 陶文铨・计算热传学的近代进展[M ]・北京:科学出版社, 2000・马正飞, 殷　翔・数学计算方法与软件的工程应用[M ]・北京:化学工业出版社, 2002朱志强・应用计算流体力学[M ]・北京:北京航空航天大学出版社, ・

N I M J , TAO W Q , WAN G S J. Stability analysis for ].Numerical Heat Transfer , Part B , 1999,35(3) :3692388.

NANN ELL I F , SUCCI S. The lattic Boltzmann ].J Statist Phys , 1996,68(3/4) :4012

407.

彭恒武, 徐锡中・[]:, 1998:1542159・

PERN G unsteady flows simulations :alternativestrategies for a volume 2averaged J Methods Fluids[C].1989,9:3412362. 关　治, ・数值分析[M ]・北京:清华大学出版社, 1990:4142415,428・

Successive Over R elaxation Iteration Method to Find

the Solution of Sparsity Linear Equation System

W A N G S hi 2ran

(Engineering Department , Liaoning Electric Power Survey and Design Institute , Shenyang 110005, China )

Abstract :Aiming at the problem of finding the solution of s parsity linear equation systeem , on the basis of discussing the

dispersed handling for iteration method , and taking two 2dimensional heat conduction equation as example , the work educes the linear equation system , finds the solution with SOR iteration method , and anal yzes the convergence performance and convergence speed. It realizes SOR iteration method on the com puter , gets a set of numerical solution approximated to the accurate solution , and vaalidates the accuracy of SOR iteration method.

K ey w ords :sparsity linear equation system ; dispersed ; successive over relaxation iteration method

第24卷　第4期

2006年10月

沈阳师范大学学报(自然科学版)

Journal of S henyang Norm al U niversity (N atural Science )

V ol 124, N o. 4Oct. 2006

文章编号:1673-5862(2006) 04-0407-04

稀疏线性方程组求解的逐次超松弛迭代法

王诗然

(沈阳电力勘测设计院工程部, 辽宁沈阳　110005)

摘　　　要:针对稀疏线性方程组求解问题, 在论述迭代法离散化处理基础上, 以二维热传导方

程为例, 导出了热传导方程离散化后线性方程组, 用超松弛(SOR ) 迭代法对产生的稀疏线性方程组进行迭代法求解, 并分析了收敛性和收敛速度・将超松弛迭代算法在计算机上实现, 得出了一组与精确解较接近的数值解, 验证了逐次超松弛(SOR ) 迭代法的精确性・关　键　词:稀疏线性方程组; 离散化; 逐次超松弛迭代法中图分类号:TP 391　　　文献标识码:A

1　迭代法的产生背景

, 以至使人们不能在允许

, , 客观上要求用新的方法来解决大维数方程组的求解问题・

, 在解题时, 要对原方程组矩阵作一根本的变换, 从而可能使条件数变坏, 也可能破坏了变换前后方程组的等价性, 以及丧失使原方程组的对称性等・探求新的有效的解题方法依然是迫切的任务・通过对GS 法进行改进, 从而产生了逐次超松弛(SOR ) 迭代法・

在求解过程中由于线性方程组的系数矩阵维数较大, 采用计算机编写算法来求解, 从而实现了对解析模型的计算机数值逼近的计算方法・本论文以逐次超松弛迭代法为主要的求解方法・

2　二维热传导方程的离散化过程

2. 1　向后差分格式

二维热传导方程

2

22+=a +f (x , y , t ) , 00)

9t 9x 29y 2u (x , y , 0) =φ(x )

u (0, y , t ) =u (l , y , t ) , u (x , 0, t ) =u (x , l , t )

取步长h =l/N ,

τ=T/M , 用两族平行线x =x j =jh , y =y k =kh , 将求解域划分成矩形网格, 网点为

(x j , x k

, t n ) (t n =n τ) , r =

u -u n +1

n

2h

u j +1-2u j , k +u j -1, +u j +1, k -2u j , k +u j -1, k +u j +1, k -2u j , k +

u j -1, k +

n

n

n

n

n

n

n +1

n

+1

n +1

n +1

n +1

n +1

2

τ

n +1n

n

2=2

h

u j , k +1-2u j , k +u

j , k

n

+1

n +1

n +1n +1n +1

+τf

n +1

j , k

n

u j , k -u j , k =r

u j , k +1-2u j , k +u j , k -u j , k +1-2u j , k +u j , k -1

n

n -1

n

n

n

n

n +1

+2τf j , k +2τf j , k

n

即

u j , k -u j , k =r

n

n -1

(1+4r ) u j , k -ru j -1, k -ru j +1, k -ru j , k +1-ru j , k -1=u j , k +2τf j , k

由此可得线性方程组

收稿日期:2006206220

作者简介:王诗然(1982-) , 女, 辽宁新宾人, 沈阳电力勘测设计院助理工程师・

408

沈阳师范大学学报(自然科学版) 　　　　　　　　　　　　　　第24卷

(1+4r ) I -S

-r I

-r I (1+4r ) I -S

U

1

k k

U 1

U 2

k -1k -1

+τf 1+τf 2

f

f

O O

-r I

U 2

O -r I

(1+4r ) I -

…

U k

…

U N

k -1

+τf f

010O

O O 1

1T

, U i =(u i 1, u i 2, …, u iN ) , I 为单位矩阵・

k

k

k

k

其中, S =

1

3　热传导问题离散化后线性方程组的迭代法

3. 1　逐次超松弛迭代法

在很多情况下, 由于J 法和GS 法收敛速度较低, 所以需要对GS 法进行改进・假设计算k +1个近似解x (k +1) 时, 分量x 1

x i

(k +1)

(k +1)

i -1

, x 2

(k +1)

, , …, x i -

(k +1)

1

GS 法那样计算

b i -=

6

i (k )

a j x j

-

n

j x j

i (再用某个参数ω作加权平均, () k 1) (k ) (k ) (k +1) (k ) x (1ω) x i =x i +ω( x i -x i ) 或整理成

i -1

x i

(k +1)

=(1-ω) x i

(k )

b i -+

6

a ij x

(k +1)

j

-

6

n

a ij x j

(k )

a ii

　i =1, 2, …

, n ・

这称为逐次超松弛迭代法, 简记SOR 方法, 其中ω称松弛因子・当ω=1时就是GS 法・3. 2　逐次超松弛迭代法的收敛性判别

1) 收敛性判别条件

SOR 迭代法收敛的充分必要条件是ρ(λω)

ω的关系, 再讨论SOR 方法收敛的条件・

定理1　(Kahan ) 对任意的A ∈R n ×n , 设其对角元皆非零, 则对所有实数ω, 有

ρ(λω) ≥ω-1推论:如果解Ax =b 的SOR 方法收敛, 则有ω-1

定理2　(Ostrowski 2Reich ) 设A ∈R n ×n

, A 对称正定, 且0

2) 收敛速度的估计

SOR 迭代法的迭代矩阵λ因此, 需要找到ω与ω有关, 当选取不同的ω时, 其迭代速度也有所不同・

最优的松弛因子ωb , 使对应ωb 的SOR 方法收敛最快・

定理3　设A ∈R n ×n , A =D -L -U 为L U 分解・如果存在排列矩阵P , 使

PA P

T

=

D 1M 2

M 1D 其中, D 1, D 2为对角方阵, 则称A 是22循环的・此外, 若当α≠0时, 矩阵

-1-1-1

αD L +αD U

的特征值都和α无关, 则称A 是相容次序矩阵・

定理4　设A ∈R n ×n , A 有非零的对角元, 且是22循环和相容次序的・又设B =D -1(L +U ) 是方程组Ax =b 的Jacobi 迭代的迭代矩阵, 且B 2的所有特征值均在[0, 1) 上・记μ=ρ(B ) 及

ωb =

1+(1-μ2)

2

第4期　　　　　　　　　　　王诗然:稀疏线性方程组求解的逐次超松弛迭代法409

则方程组的SOR 方法迭代矩阵的谱半径ρ(λω) 满足

ρ(λω) =

ω-1,

ρ(λωb ) =min ρ(λω) ω

0≤≤2

224

2

,

0

ωb ≤ω≤2

且当0

lim ωω

→b -0

(λ)

ωω=-∞d

3. 3　二维热传导方程离散化后的线性方程组的超松弛迭代法

1) 理论解法

同上面解一维热传导方程相似, 解二维热传导问题需得出下列计算公式:

(1) (2)

x 1=ω[b 1-(1+2r ) u 1+ru 1](1+2r )

x i =ω[b i -(1+2r ) u 1

(i )

+r (u 1

i -1

+u 1) ](1+2r ) (1r )

i +1

x n =ω[b n -(1+2r ) u 1

(n -1)

+1

(n -2)

2) 收敛性判别

关于SOR ・3) ωb , 若提高该迭代法的收敛速度, ωb 即可・3. 4　以方程

2

2=D x +D +f (x , y , t ) , 　0≤x , y ≤π, t >0y 9t 9x 29y 2u (x , y , 0) =sin x sin y , 　0≤x ≤π

u (0, y , t ) =u (l , y , t ) =0, u (x , 0, t ) =u (x , l , y ) =0D x =D y =0101, f (x , y , t ) =Q =10

) 分为50等份, 用特殊算法进行计算, 得为例进行精确解计算・在方程中

到各个点在不同时间t (以t =014s 为例) 内所对应的精确值如下(只列举典型部分) :

2. 879083; 3. 799029; 4. 018457; 4. 068228; 4. 090255; 4. 108895; 4. 126805; 4. 144134;

4. 265669; 4. 255839; 4. 244982; 4. 233140; 4. 220358; 4. 206684; 4. 192171; 4. 176871; 4. 160840; 4. 144134; 4. 126805; 4. 108895; 4. 090255; 4. 068228; 4. 018457; 3. 799029・3. 5　二维热传导方程离散化后线性方程组超松迭代法的数值解

以上述热传导方程为例, 其离散化后线性方程组的逐次超松弛迭代法算法的计算机编程略, 其运算结果与精确解的比较如表1所示(只列举典型部分) ・

表1　运算结果比较

t 值

x 值

精确解

2. 091059

2. 0910594. 0902554. 0902556. 0823486. 0823488. 0495508. 049550

数值解

2. 0949552. 0949554. 0908124. 0908126. 0713666. 0713668. 0202718. 020271

误　差

0. 0038960. 0038960. 0005570. 0005570. 0109820. 0109820. 0292790. 029279

0. 20. 20. 40. 40. 60. 60. 80. 8(0. 314159,0. 314159) (0. 314159,2. 827431) (0. 314159,0. 314

159) (0. 314159,2. 827431) (0. 314159,0. 314159) (0. 314159,2. 827431) (0. 314159,0. 314159) (0. 314159,2. 827431)

410

沈阳师范大学学报(自然科学版) 　　　　　　　　　　　　　　第24

卷

4　结　　论

1) 逐次超松弛迭代法与Jacobi 迭代法,Seidel 迭代法相比, 收敛速度较快・

2) 由逐次超松弛迭代法求出的方程组的数值解与该方程组的精确解十分接近, 可见二维热传导方

程离散化后线性方程组的逐次超松弛迭代法的精确性较高・

3) 逐次超松弛迭代法可以广泛地应用于实际・该算法不仅可以用来求解热传导问题, 还可以用来求解与热传导问题相类似的高阶稀疏线性方程组・这样可以大大减少计算量和计算机的内存储量, 从而提高计算效率・参考文献:

[1][2][3][4][5][6][7][8][9][10]

杨华军・数学物理方法与计算机仿真[M ]・北京:电子工业出版社, 2005・

FERZIGER J H , PERIC M. Com putational methods for fluid dynamics[M ].Berlin :S pringer , 1996. 陶文铨・计算热传学的近代进展[M ]・北京:科学出版社, 2000・马正飞, 殷　翔・数学计算方法与软件的工程应用[M ]・北京:化学工业出版社, 2002朱志强・应用计算流体力学[M ]・北京:北京航空航天大学出版社, ・

N I M J , TAO W Q , WAN G S J. Stability analysis for ].Numerical Heat Transfer , Part B , 1999,35(3) :3692388.

NANN ELL I F , SUCCI S. The lattic Boltzmann ].J Statist Phys , 1996,68(3/4) :4012

407.

彭恒武, 徐锡中・[]:, 1998:1542159・

PERN G unsteady flows simulations :alternativestrategies for a volume 2averaged J Methods Fluids[C].1989,9:3412362. 关　治, ・数值分析[M ]・北京:清华大学出版社, 1990:4142415,428・

Successive Over R elaxation Iteration Method to Find

the Solution of Sparsity Linear Equation System

W A N G S hi 2ran

(Engineering Department , Liaoning Electric Power Survey and Design Institute , Shenyang 110005, China )

Abstract :Aiming at the problem of finding the solution of s parsity linear equation systeem , on the basis of discussing the

dispersed handling for iteration method , and taking two 2dimensional heat conduction equation as example , the work educes the linear equation system , finds the solution with SOR iteration method , and anal yzes the convergence performance and convergence speed. It realizes SOR iteration method on the com puter , gets a set of numerical solution approximated to the accurate solution , and vaalidates the accuracy of SOR iteration method.

K ey w ords :sparsity linear equation system ; dispersed ; successive over relaxation iteration method