解线性方程组的几种迭代算法

解线性方程组的几种迭代算法

内容摘要:

本文首先总结了分裂法解线性方程组的一些迭代算法,在此基础上分别通过改变系数矩阵A的分裂形式和对SSOR算法的改进提出了两种新的算法,并证明了这两种算法的收敛性.与其它方法相比,通过改变系数矩阵A的分裂形式得到的新算法具有更好的收敛性,改进的SSOR算法有了更快的收敛速度.最后通过数值实例验证了这两种算法在有些情况下确实可以更有效的解决问题.

关键词:

线性方程组 迭代法 算法 收敛速度

Several kinds of solving linear equations

iterative algorithm

Abstract:

In this paper, we firstly summarize some Iterative algorithms of Anti-secession law solution of linear equations. Based on these, two new algorithms are put forward by changing the fission form of coefficient matrix A and improving the algorithm of SSOR, and the convergence of the two algorithms is demonstrated. Compared with other methods, the new algorithm acquired by changing the fission form of coefficient matrix A is possessed of a better convergence. And the improved SSOR algorithm has a faster convergence speed. Finally, some numerical examples verify that the two algorithms can solve problems more effectively in some cases.

Key words:

Linear equations Iteration method algorithm Convergence speed

目录

1.引言 ............................................................................................................... 1 2.迭代法原理 .................................................................................................... 1 3.基本迭代法 .................................................................................................... 2

3.1 Jacobi迭代 .......................................................................................... 2 3.2 Gauss-Seidel迭代法 ........................................................................... 3 3.3 SOR算法 ............................................................................................. 3 3.4 SSOR算法 .......................................................................................... 4 3.5 收敛性分析 .......................................................................................... 4 4.几种新的迭代算法 ......................................................................................... 5

4.1 基于矩阵分裂形式的新迭代算法 .......................................................... 5 4.2 加权－对称超松弛迭代法 .................................................................... 7 5.算法的不足与改进方法 .................................................................................. 9 6.数值实例 ....................................................................................................... 9

6.1渐进收敛速度 ....................................................................................... 9 6.2几种迭代方法的比较 .......................................................................... 10 附录 .................................................................................... 错误！未定义书签。 参考文献 ........................................................................................................ 11

解线性方程组的几种迭代算法

1.引言

在工程技术、自然科学和社会科学中的许多问题最终都可归结为解线性方程组, 因此线性方程组的求解对于解决实际问题是极其重要的.线性方程组的解法有很多种,主要的方法有直接法和迭代法.迭代法就是用某种极限过程去逼近线性方程组精确解的方法,该方法具有对计算机的存贮单元需求少,程序计算简单,原始系数矩阵在计算过程中不变等优点,是求解大型稀疏矩阵方程组的重要方法.

目前,人们已经得到了一些较为成熟的线性方程组的迭代解法,从某种意义上讲它们都可归结为分裂法.但在解决具体问题时我们仍面临着许多问题,如:怎样设计出满足要求的求解算法；如何分析、区别算法的好坏；可否改进现有的算法使其更有效；求解所给问题最好可能的算法会是什么,等等.针对这些问题,很多人都做过了大量的研究.文献[2]对迭代法的原理及一些常用的迭代算法进行了研究.文献[1],[3],[4],[5]给出了一些基本的迭代算法并证明了其收敛性.文献[6],[9],[10],[13],[16]研究了一些特殊方程组的迭代解法.文献[7],[8],[12],[14],[15]都是针对不同的问题对超松弛迭代算法进行了改进.文献[11]主要讨论了迭代法解线性方程组的MATLAB实现.本人在求解线性方程组的问题时,通过对现有迭代算法的改进得到了两种新的算法.本文对这两种算法的收敛性进行了证明,并通过数值实例验证了其在解决某些问题时具有的优势.

2.迭代法原理

设线性代数方程组为

AX?b (1)

常常将系数矩阵A分裂成两个矩阵M和N之差,即

A?M?N (2)

且用迭代

X(k?1)?M?1NX(k)?M?1b (3)

来解线性方程组(1). 将(3)式表示为

X(k?1)?BX(k)?f,k?0,1,? (4)

其中,B?M?1N,f?M?1b,称此迭代方法为分裂法,而将B称为迭代格式(4)的迭代矩阵.

然而迭代法需要解决的首要任务是迭代格式是否收敛的问题,任取初始向量

(0)(0)X(0)??x1(0),x2,?,xn?代入(4)中,计算可得迭代序列X(1),X(2),?X(k?1).若迭代

T序列?X(k?1)?收敛,设?X(K)?的极限为X*,对迭代式(4)两边取极限可得:

1

limX(k?1)?lim?BX(k)?f?

k??k??即X*?BX*?f,X*是方程组(1)的解,此时称迭代法收敛,否则称迭代法发散.

我们有如下的结果:

定理2.1[1] 迭代格式(4)收敛的充分必要条件是迭代矩阵B的谱半径

?(B)?1,而且??B?越小,收敛越快.

定理2.2[1] 若Bp为矩阵B的某范数,则总有Bp???B?.

对于矩阵A的分裂应该说是有很多形式,但并不是所有分裂形式产生的迭代格式都有意义.于是我们有正规分裂的概念:

定义2.1[2]对于实方阵A,若矩阵M和N满足A?M?N,且M?1N?0,N?0则称A?M?N是A的一个正规分裂.

那么正规分裂与其他分裂形式相比到底有什么优势呢?我们有如下定理:

定理2.3[2]若A?M?N为A的正规分裂,且A?1?0,则

??M?1N??1???AN??1??A?1N?

从而??M?1N??1,此时相应的迭代格式(3)必收敛.

如果针对矩阵A给出两种正规分裂,如何来衡量它的好坏呢?

定理2.4[2] 若矩阵有两个正规分裂,设A?M1?N1,A?M2?N2且A?1?0,

?1N1??1. N2?N1?0,N1?0,N1?N2,则有0???M1?1N1????M23.基本迭代法

下面给出常见的几种基本迭代格式.将A??aij?分裂为

A?D?L?U (5)

其中,

?a11?D?????a22?0???0a12?a1n??????a00?a212n?,U????,L???? ?????????????????a?a?0ann?0n,n?1???n1?3.1 Jacobi迭代

取

M?D,N?L?U. (6)

2

则(4)式中迭代矩阵B和右端向量f分别为

B?D?1?L?U?,f?D?1b.

迭代格式(4)的分量形式为

x(k?1)i1?(k)???bi??aijxj?,i?1,2,?n.k?0,1,?. aii?j?i?称它为Jacobi迭代法,该迭代法具有和x(k?1)中分量的计算次序无关,容易并行计算等优点.

3.2 Gauss-Seidel迭代法

取

M?D?L,N?U, (7)

此时(4)式中迭代矩阵B和右端向量f分别为

B??D?L?U,f??D?L?b.

?1?1迭代格式(4)的分量形式为

xi(k?1)?1?(k?1)(k)?b?ax?ax?i?ijj?ijj?,i?1,2,?n.k?0,1,?. aii?j?i?1j?i?1?称它为Gauss-Seidel迭代法.和Jacobi迭代法相比Gauss-Seidel迭代法使用了最新

已经计算的分量. 3.3 SOR算法

取

M?11???D?L,N?M?A??D?U, (8)

此时(4)式中迭代矩阵B和右端向量f分别为

B??D??L??1??1???D??U?,fi?1(k?1)jn???D??L?b.

?1迭代格式(4)的分量形式为

x(k?1)i??1???x(k)i??bi??aijxaii?j?1?1???(k)?ax?ijj?,i?1,2,?n.k?0,1,?

j?i?1?其中,?称为松弛因子(总假定是实数).迭代格式的矩阵形式为:

(k)X(k?1)??D??L????1???D??U??X???D??L?b

?1称它为对应于松弛因子?的逐次超松弛迭代法(Successive Over Relaxation,

简称SOR).它可以看成Gauss-Seidel迭代法与原向量的组合,但使用了最新已经

3

计算的分量.也就是把xi即:

(k?1)取为Gauss-Seidel迭代法中xi(k)与xi(k?1)的某个平均值,

(k?1)xi??1???xi(k)??xi(k?1)?x(k)i???x(k?1)i?x(k)i?

当??1时,它就是Gauss-Seidel迭代法.因此希望选取合适的?使得它比Gauss-Seidel迭代法具有更快的收敛速度. 3.4 SSOR算法

SOR迭代格式还可以写为

(k)?D??L?X(k?1)????1???D??U??X??b,k?0,1,?

将上式L和U的位置互换就得到一个新的迭代格式,具体表示为:

1(k?)?(k)2??1??D??UX??b?????D??L?X?? ?1??D??L?X(k?1)???1???D??U?X(k?2)??b,k?0,1,????若消去X1(k?)2,就得到迭代格式(4),其中

?1?1?1B??D??U?D?D??L??1??D??LD????????1???D??U??,f???2????D??U?D?D??L??1?1

称为对称逐次超松弛迭代法(Symmetric Successive Over Relaxation,简称SSOR). 对一类椭圆微分方程离散后得到的线性方程组,Young[3]给出了最佳松弛因子,即为

??21?1??2?B?

其中B是Jacobi迭代法中的迭代矩阵.在实际问题中最佳松弛因子是很难计算的,但一般都在(0,2)之间. 3.5收敛性分析

定义3.1[3] 若实矩阵A??aij?nn,满足

j?1,j?i?nnaij?aii,?i?1,2,?n?

或

i?1,i?j?aij?ajj,?j?1,2,?n?

则称A为严格对角占优矩阵；若满足

4

j?1,j?i?nnaij?aii,?i?1,2,?n?

或

i?1,i?j?aij?ajj,(j?1,2,?n)

且上述不等式至少有一个严格成立,则称A为弱严格对角占优矩阵.

定义3.2[3] 设A为n阶矩阵,n?2.若存在n阶排列矩阵P,使得

?APTAP??11?0A12?? A22?其中A11为r阶矩阵,1?r?n,则称A是可约的,否则称A不可约.

定理3.1[3] 若A为n阶严格对角占优矩阵或不可约的弱严格对角占优矩阵,则对任意的初始值x(0),(1)式中的Jacobi迭代法、Gauss-Seidel迭代法和关于

0???1的SOR迭代法均收敛.

定理3.2 [4] 对所有?均成立不等式

??BSOR????1

当?是实数时,SOR方法收敛的一个必要条件是0???2.

定理3.3[4] 如果系数矩阵A是Hermite矩阵,则SOR方法收敛的充要条件是:A正定和0???2.

4.几种新的迭代算法

4.1 基于矩阵分裂形式的新迭代算法

上述几种基本迭代方法都是通过对线性方程组(1)的系数矩阵A进行分裂得到的,不同之处在于A分裂成A?M?N的形式时,M和N的取值不同.由(3),(4)可知此种格式下的迭代矩阵B?M?1N?E?M?1A,所以当M是A一个很好的近似时,Bp就会很小.再由定理2.1和定理2.2可知此时得到的迭代法收敛速度也更快.另一方面,我们构造的迭代格式为Mx(k?1)?Nx(k)?b,k?0,1?,由于每一次迭代都要解一个方程组,所以我们也要求非退化的矩阵M的形式比较简单,如对角矩阵、下三角矩阵等.

比较Jacobi迭代、Gauss-Seidel迭代及SOR算法中M的取值,我们可以看到M的形式都为对角矩阵或下三角矩阵,并且随着M越近似等于A,所得到的迭代方法的收敛速度也越快.满足上述两个条件,对M取不同于这三种算法中M取值的形式,我们可以得到下述新的算法.

4.1.1 算法的建立 取

5

M?D??L,N??1???L?U.0???1, (9)

作为A?M?N的一个新分裂,在此分裂的基础上可得到一个新的迭代公式

x(k?1)?B?x(k)?f?,k?0,1,? (10)

其中,B???D??L??1??1???L?U?,f???D??L??1b,0???1.显然,当??0时

就是Jacobi迭代法；当??1时就是Gauss-Seidel迭代法.

4.1.2 收敛性分析

引理1[3] A可约的充要条件为存在非空子集J??1,2,?n?,使得

aij?0,i?J,j?J.

引理2[3] 若A为n阶严格对角占优矩阵或不可约的弱严格对角占优矩阵,则A是非退化的.

定理4.1 若A为n阶严格对角占优矩阵或不可约的弱严格对角占优矩阵,则对任意的初始值x(0),当0???1时,(10)式表示的迭代格式收敛.

证明:(10)式的迭代矩阵为

B???D??L??1??1???L?U?

?1我们有

det??E?B???det?E??D??L??1??1???L?U???

?det??D??L???det???D??L????1???L?U??其中?为B?的特征值.若A?D?L?U为严格对角占优矩阵,则D??L也为严格对角占优矩阵；若A?D?L?U为不可约的弱对角占优矩阵,则D??L也为不可

约的弱对角占优矩阵.由引理2,我们有

det?D??L?所以

??1??0

?det??E?B???0?det??D??L????1???L?U??0

?令

H???D??L????1???L?U???D???????1?L?U

a12a13a23???????1?an3?a11????????1?a21????????????1?an1?

?a22???????1?an2a1n???a2n???????ann???6

下面证明??1,用反证法.

假设??1,由0???1可知A和H的对应元素一定同时为0或非0.由引理1知,A不可约推出H也不可约.

下面比较?和?????1的大小. ①当??1时,

???????1???????1??1???????1??1????1??1????0

②当???1时,?1???1?0,

???????1????????1??????????1????1?????1????1??1???1??1?0由①、②知:当??1,0???1时,???????1.所以有:A为弱对角占优矩阵时,H也是弱对角占优矩阵；A为严格对角占优矩阵时,H也是严格对角占优矩阵.再由引理2,可以得到H为非退化的矩阵.从而,det?H??0.进而,det??E?B???0.这与?是B?的特征值矛盾,所以??1.进一步可得到

????B???1,我们就证明了(10)式表示的迭代格式收敛.

4.2 加权－对称超松弛迭代法

■

4.2.1 算法的建立

考虑SOR算法和4.1给出的新迭代算法,其实质都是给矩阵A分裂以后的因子一个权重后得到的,目的是使得迭代格式(4)的收敛速度尽可能快.按照这种思想,如果在SOR和SSOR迭代中引入一个参数?,就可以得到迭代格式

X(k?1)???BSORX(k)?fSOR???1????BSSORX(k)?fSSOR?,??[0,1] (11)

其中,BSOR,BSSOR分别为SOR迭代和SSOR迭代算法的迭代矩阵.此时的迭代矩阵B??BSOR??1???BSSOR.显然,当??0时,该算法即为SSOR迭代；当??1时,即为SOR迭代.

7

若迭代格式(11)收敛到某个向量X*,则有

X*???BSORX*?fSOR???1????BSSORX*?fSSOR?,??[0,1]

所以不管?在[0,1]内如何取值,当迭代格式(11)收敛时,它必定是原来方程

X?BX?f的解.选取适当的B,根据(4)式的定义,这样的解也是方程(1)的解.显

然我们可以选择一个较好的?,使得迭代格式(11)收敛的尽可能快.

已知SOR迭代的核心部分为:

fori?1:1:nx(k?1)i??1???x(k)i??bi??aijxaii?j?1??i?1(k?1)j?(k)? ax?ijj?j?i?1?nendSSOR迭代的核心部分为:

fori?1:1:nxendfori?n:?1:1xend将SOR迭代和SSOR迭代生成的向量进行加权平均,可得到改进的SSOR迭代算法,其核心部分为:

(k?1)i(k?1)i??1???x(k)i??bi??aijxaii?j?1??i?1(k?1)j?(k)?ax?ijj?j?i?1?n

(k)i??1???x??bi??aijxaii?j?1??i?1(k?1)j?(k)?ax?ijj?j?i?1?nfori?1:1:nx(k?1)i??1???x(k)i??bi??aijxaii?j?1??i?1(k?1)j?(k)?ax?ijj?j?i?1?nendfori?n:?1:1i?1n?(k?1)??(k)(k?1)?xi??1???xi??bi??aijxj??aijx(jk)?

aii?j?1j?i?1?endfori?1:1:nxiend其中,?为权重,可以取[0,1]之间的任意实数,在此称之为加权－超松弛迭代法.

4.2.2 收敛性分析

8

(k?1)?i(k?1)??xi(k?1)??1???x

定理4.2 加权－超松弛迭代算法,满足迭代关系式(4),其迭代矩阵

B??BSOR??1???BSSOR.

其中,

BSOR??D??L????1???D??U??

?1BSSOR??D??U?D?D??L????1???D??L??D???1???D??U??

?1?1?1且(11)对任意的初始向量都收敛的充要条件为??B??1.

证明:由4.2.1中的分析知该定理结论显然成立. ■

5.算法的不足与改进方法

上述两种算法本质上都是添加了一个加权因子,不同之处在于一个是对分裂

后的矩阵添加的,而另一个是对迭代矩阵添加的.增加了加权因子之后,如何对其取值才最合理就变成了一个亟需解决的问题.像SOR算法中很难确定?的值一样,我们很难找到一种通用的方法来确定所增加的加权因子的值.在下面的数值实例中,为了验证算法的优越性,我们可以让加权因子?遍取[0,1]中的某些值,通过MATLAB编程搜索出迭代次数最少时?的取值.但是在解决实际问题时如果仍这样做,不但不能减少迭代的总次数,反而是增加了计算机的工作量和解决问题所需要的时间.

下面提供一种解决实际问题时加权因子?值的确定方法:(1)给定某个迭代次数n,搜索出迭代n次后解的精度最小的那个?的值；（2）用（1）中?的值作为加权因子的值求解线性方程组的指定精度的解.

6.数值实例

6.1渐进收敛速度

为方便比较和表述用不同的迭代方法解线性方程组时的收敛速度,我们引入下述定义.

定义6.1[5]称

Rk?B???lnB为迭代法X(k)?BX(k?1)?f的平均收敛率.

1kk

此处定义的是平均压缩率的对数值(再取负号),它依赖于所选择的范数和迭代次数,使用起来非常不便.由于

limBk??1kk???B?

则再给出下面的定义:

定义6.2[5]称

R?B???ln??B?

为迭代法的渐进收敛速度,简称迭代法的收敛速度.

9

6.2几种迭代方法的比较

下面我们用不同的迭代方法求解n元线性方程组Ax?b,其中

?4?1??3??????14?1???2??,b????. A??????????14?1???2???3??14?????方程的精确解为x*??1,1,?,1?.取n?10,初始向量x(0)为零向量.下表给出了几种迭代方法达到不同精度时所需的迭代次数.(程序见附录)

表1 不同的迭代算法达到某一精度时所需迭代次数的比较 T算法 参数值 迭代次数 精度 21 Jacobi迭代法 \\ 13 Gauss-Seidel迭代法 \\ ??1.2 15 SOR算法 1?10?6 ??1.2 8 SSOR算法 ??0.89 13 4.1中的算法 ??1.2,r?0.02 7 4.2中的算法 27 Jacobi迭代法 \\ 17 Gauss-Seidel迭代法 \\ ??1.2 17 SOR算法 1?10?8 ??1.2 10 SSOR算法 ??0.96 16 4.1中的算法 ??1.2,r?0.13 8 4.2中的算法 由上表可以看到,若合理的选取参数值,解系数矩阵为三对角矩阵的线性方程组时,4.2中提供的方法收敛速度最快.根据6.2的定义,我们算出精度为1?10?8时各种迭代算法的渐进收敛速度,见表2. (程序见附录)

表2 精度为1?10时各种迭代算法的渐进收敛速度

?8算法 Jacobi迭代法 Gauss-Seidel迭代法 SOR算法 SSOR算法 4.1中的算法 4.2中的算法 渐进收敛速度 0.7345 1.4690 1.6094 1.9171 1.3595 2.0020 结合表1与表2,我们可以看到:当迭代结果的精度达到1?10?8时,表1显示的Jacobi迭代法、Gauss-Seidel迭代法、SOR算法、SSOR算法和对称－超松弛迭代算法所需的迭代次数逐渐减少,4.2中给出的方法是收敛最快的,这与表2中

10

给出的其渐进收敛速度逐渐变大的结果一致.我们还可以看到,用4.1中的算法进行计算所需的迭代次数较SSOR方法的迭代次数多,但由定义6.2计算出的其渐进收敛速度却较小,这说明用该定义意义下的范数去度量4.1中的算法的收敛速度,并不是一个好的度量方式.

考虑方程组

?101??x1??5???????-110x??7???2??? ?12?3??x???17????3???其精确解为?2,?5,3?.求出各种迭代方法的迭代矩阵B对应的谱半径??B?,可以看到只有Jacobi迭代法和4.1中的算法是收敛的,其他方法均发散.下面我们比

较Jacobi迭代法和4.1中的算法在达到指定精度时的收敛次数,见表3.(程序见附录)

表3 两种迭代法达到指定精度所需迭代次数的比较

T参数 迭代次数/次 Jacobi迭代法 4.1中的算法 Jacobi迭代法 4.1中的算法 0.86 212 15 10-5 \\ 0.84 253 19 10-6 \\ 0.85 293 21 10-7 \\ 0.86 333 22 10-8 \\ 0.87 374 24 10-9 \\ 我们可以看到4.1中给出的方法解该方程组的收敛速度远远大于Jacobi迭代法. 精度 参考文献

[1] 张韵华,奚梅成,陈效群,数值计算方法与算法[M].北京:科学出版社,2009: 130-140.

[2] 邵新慧,大型线性方程组的迭代解法[J].东北大学博士学论文,2009. [3] 李大明,数值线性代数[M].北京:清华大学出版社,2010:177-192.

[4] 余德浩,汤华中.微分方程数值解法[M].北京:科学出版社,2004:320-328. [5] 薛毅,数值分析与实验[M].北京:北京工业大学出版社,2005:88-93. [6] 马云,数值分析中的迭代法解线性方程组[J].考试周刊,2010:71-72.

[7] 段班祥,吴教育,朱小平,非线性互补问题的改进超松弛迭代算法[J].江西师范大学学报.2009,33(5):617-621.

[8] 蒋家羚,王勇,最优超松弛因子的一种确定方法及其在裂纹计算中的应用[J].机械强度,2002,24(1):133-135.

[9] 郑亚敏,迭代法解线性方程组的收敛性比较[J].江西科学.2009.10: 659-661.

[10] 谢刚,不定线性方程组的一种迭代算法[J].科学技术与工程.2007.第7卷,第14期.

[11] 张步林,线性代数方程组迭代解法的MATLAB实现[J].成都纺织高等专科

11

学校学报,2008.10:45-47.

[12] 李春光,徐成贤,确定SOR最佳松弛因子的一个实用算法[J].计算力学学报.2002.8:299-302.

[13] 曾闽丽,加权-对称超松弛算法[J].莆田学院院报,2008.4,第15卷,第2期. [14] 周荣富,蔡治亚,关于超松弛迭代法收敛的一个判别准则[J].1991.6.第6卷.第2期.

[15] 唐永建,向隆万,最佳双松弛因子迭代法的存在条件[J].上海电力学院学报,第17卷,第1期.

[16] 高虹霓,曹泽阳,一种新的非线性方程求根迭代法[J].空军工程大学学报,2002.4.第3卷,第2期.

12

本文来源：https://www.bwwdw.com/article/ge67.html