线性方程组的迭代解法及收敛分析

河南科技学院

2015届本科毕业论文

论文题目：线性方程组的三种迭代解法

及收敛分析

学生姓名：韦成州

所在院系：数学科学学院

所学专业：信息与计算科学

导师姓名：李巧萍

完成时间： 2015年5月20日

线性方程组的三种迭代解法及收敛分析

摘要

对于线性方程组的迭代解法，本文重点讨论雅可比迭代法，高斯塞德尔迭代法和超松弛迭代法三种迭代解法。主要讨论内容有：首先，写出三种迭代解法的基本思想，基本算法及收敛条件；其次，针对这三种迭代解法进行举例分析，通过MATLAB程序，求得三种迭代法各自的迭代次数、每次迭代的结果及误差；最后，在满足设定精度的情况下，对每个迭代方法所用的迭代次数进行通过分析比较，得出了在选择适当的松弛因子后，三种迭代法的收敛速度：超松弛迭代法＞高斯塞德尔迭代法＞雅可比迭代法，对于方程组Axb，迭代法的收敛性只与系数矩阵A有关，而与右端项b无关。同时，本文又对算法设计，收敛速度的判定等问题提出了改进意见。

关键词： MATLAB,数学模型,迭代解法,收敛,线性方程组

Three kinds of solutions of systems of linear equations iterative

method and convergence analysis

Abstract

For iterative solution of linear equations, this article focuses on the Jacobi iteration method, gauss seidel iteration method and overrelaxation iteration method of three kinds of iterative method.Main discussion: first of all, write down three iterative method, the basic idea of the basic algorithm and convergence condition;Secondly, in view of the three kinds of iterative solution methods for analysis, through the MATLAB program, get three iterative method respective number of iterations, the results of each iteration and error;Finally, in the case of meet the setting precision, for each iteration method to carry through analysis and comparison, the number of iterations used in selecting the appropriate relaxation factor is obtained, the convergence rate of the three types of iterative method: overrelaxation iteration method, gauss seidel iteration method, Jacobi iteration method for the system of equations, the convergence of iterative method is only related to the coefficient matrix, and has nothing to do with the right items.And at the same time, this paper, the algorithm design, and the convergence rate of decision problems, such as improvement opinions are put forward.

Keywords：MATLAB, Mathematical model, Iterative method, Convergence System of linear equations

1引言 .......................................................................................................... 1

2迭代法的基本思想 ................................................................................. 1

3三种迭代法的思想，算法及收敛条件 ................................................. 1

3.1 雅可比迭代法 ............................................................................... 1

3.1.1 雅可比迭代法的思想与算法 .............................................. 1

3.1.2 雅格比迭代法的收敛条件 .................................................. 2

3.2 高斯塞德尔迭代法 ....................................................................... 2

3.2.1 高斯塞德尔迭代法的思想和算法 ...................................... 2

3.2.2 高斯塞德尔迭代法的收敛条件 .......................................... 3

3.3超松弛迭代法 ................................................................................ 3

3.3.1 松弛法思想和算法 .............................................................. 3

3.3.2 超松弛迭代法的收敛条件 .................................................. 4

4数学模型 .................................................................................................. 4

4.1雅可比迭代法求解 ........................................................................ 5

4.2高斯赛德尔方法求解 .................................................................... 7

4.3超松弛迭代法求解 ...................................................................... 10

5小结 ........................................................................................................ 13

致谢 ........................................................................................................... 15

参考文献 ............................................................................................... 15

1引言

在实际生活中，存在着大量求解线性方程组的问题。这些方程组具有数据量大，系数矩阵稀疏，在一定精度保证下，只需要求解近似解等特点。线性方程组的迭代解法特别适合于这类方程组的求解，它具有程序设计简单，需要计算机的贮存单元少等特点，但也有收敛性与收敛速度问题。因此，研究线性方程组的迭代解法及收敛分析对于解决实际问题具有非常重要的作用。

2迭代法的基本思想

将方程组Axb写成等价的形式xMxb，定一个初值向量x0,可以得到迭代公式:

xk1Mxkg,k0,1,

这样构造一个向量序列{xk}，使其极限向量xk是方程组的精确解。

3三种迭代法的思想，算法及收敛条件

3.1 雅可比迭代法

3.1.1 雅可比迭代法的思想与算法

1基本思想：

如果方程组Axb的系数矩阵A(aij)nxn，满足条件aij0(i1,2,...,n)。把A分解成ADLU。其中Ddiag(a11,a22,...ann)，L为主对角线为零的下三角矩阵，U为主对角线为零的上三角矩阵，于是方程组Axb等价于

(DLU)Xb

整理得：

xD1(LU)xD1b

由此可得迭代公式：

x(k)D1(LU)x(k)D1b(k0,1,2,...)

其中x(0)任选，由上式所表示的迭代法就是雅可比迭代法，其中

MjD1(LU)

就是该迭代法的迭代矩阵，其分量式为：

xik1n1kbiaijx

j,i1~n,k0,1,aiij1ji

2基本算法：

步一.取初始向量x[00000]',精度erle6；

步二.计算初始误差，并进入while循环，运算迭代公式

步三.如果误差er小于精度，则输出x，否则，转步二

3.1.2 雅格比迭代法的收敛条件

1.雅可比迭代法收敛的充要条件是该迭代法的迭代矩阵的谱半径(Mj)小于1。

2.若系数矩阵A为对称正定矩阵，且对角元aii0(i1,2,...n),则有雅可比迭代法收敛的充要条件是A及(2DA)都是正定矩阵。

3.若方程组Axb的系数矩阵A是主对角线按行(或按列)严格占优矩阵,即

aijaij,i1,2,...n

i1ijn

则有雅可比迭代法收敛。

3.2 高斯塞德尔迭代法

3.2.1 高斯塞德尔迭代法的思想和算法

1基本思想：

高斯塞德尔迭代法是在雅可比迭代法的基础上得到的迭代算法,主要不同是在计算xi(k1)时,前面的(i1)个值x1(k1),x2(k1),...,xi1(k1)已经算出,用这些新值代

(k)(k)(k)替上次迭代的旧值x1,x2,...,xi1,用矩阵表示为

x(k1)D1Lx(k1)D1Ux(k)D1b(k0,1,2,...)

两边左乘D,整理得

(DL)x(k1)Ux(k)b(k0,1,2,...)

于是可得迭代公式为:

x(k1)(DL)1Ux(k)(DL)1b(k0,1,2,...)

1

其中迭代矩阵MGS为: MGS(DL)U，其分量式为：

k1

xi



00

x0x10,x2,xn

i1n1k1biaijxjaijxjk

aiij1ji1

i1~n,k0,1,2,



2基本算法：

步一.取初始向量x[00000]';精度erle6；

步二.计算初始误差er，并进入while循环，运算迭代公式

x(k1)(DL)1Ux(k)(DL)1b(k0,1,2,...)

步三.如果误差er小于精度，则输出x，否则，转步二 3.2.2 高斯塞德尔迭代法的收敛条件

1高斯塞德尔迭代法收敛的充要条件是该迭代法的迭代矩阵的谱半径

(MGS)小于1

2 若系数矩阵A为对称正定矩阵，且对角元aii0(i1,2,...n),则有高斯塞德尔迭代法收敛的充要条件是A是正定矩阵。

3若方程组Axb的系数矩阵A是主对角线按行(或按列)严格占优矩阵,即

aijaij,i1,2,...n

i1

ijn

则有高斯塞德尔迭代法收敛。 3.3超松弛迭代法 3.3.1 松弛法思想和算法

1基本思想：

超松弛迭代法一种加速收敛的新的迭代算法,与高斯塞德尔迭代法相比,它明显地提高了收敛的速度，具体来说就是采用加权平均的算法，在计算xi(k1)时，用高塞德尔算法得到的xi(k1)与前一步迭代中得到的xi(k)加权平均，即

xi(k1)(1w)xi(k)wxi(k1)，其矩阵形式为:

M(DwL)1[(w1)DwU]

其分量形式为：

(k1)i

x

(k)i





aii

(biaijx

j1

i1

(k1)j

aijx(jk))k0,1,.......

ji

其中w为松弛因子 2基本算法:

步一.输入初始向量xzeros10,1; 步二.重复执行

1) 用迭代格式:塞德尔迭代xi(k

，加权平均:

xi(k1)(1w)xi(k1)wxi(k1)

2) 计算误差er:ersqrtsumxxx.*xxx 3) 直到误差小于所给的精度步三.输出迭代次数count 3.3.2 超松弛迭代法的收敛条件

1超松弛迭代法收敛的充分必要条件是该迭代法的迭代矩阵的谱半径



(MGS)小于1

2超松弛迭代法收敛的必要条件是0w2

3设系数矩阵A对称正定,且0w2,则解线性方程组Axb的超松弛迭代法收敛。

4数学模型

10x1x22x33x44x512x9xx2x3x2712345 2x1x27x33x4x5174x13x25x3x415x512

4.1雅可比迭代法求解

先将Axb转化为等价方程组:

1x110(12x22x33x44x5)

x1(27xx2xx)

1345

29

1x(142x1x23x45x5)3

7

1x412(173x12x23x3x5)

x1124x3x5x4x5123415

由此建立等价的迭代格式:

k11kkkkx(12x2x3x4x)1234510

xk11(27xkxk2xkxk)

1345

29

k11kkkkx3(142x1x23x45x5)

7 

k11kkkkx412(173x12x23x3x5)

xk11124xk3xk5xk4xk

5123415

MATLAB代码为：

function [x,a,count,e]=jacobi(A,b,jd,x)

%A表示系数矩阵,b表示常数项矩阵,jd表示精度(本程序选择精度为1e-6),x表示任选的初始向量(本程序选零向量) xx=inv(A)*b; %求出真实解

er=sqrt(abs(sum(x-xx)));%求出误差(二范数) D=diag([10 9 7 12 15]);%求对角矩阵D dd=inv(D);%求对角矩阵的逆矩阵 L=tril(A,-1);%求下三角矩阵 U=triu(A,1);%求上三角矩阵

M=-dd*(L+U);%求迭代矩阵 g=dd*b;j=1;count=0;k=1;

er=sqrt(sum((x-xx).*(x-xx)));%求误差 while er>=jd %迭代求解 x=M*x+g; for i=1:5

a(j)=x(i);%把每次迭代结果(x的五个分量)保存 j=j+1; end

er=sqrt(sum((x-xx).*(x-xx)));

e(k)=er;%把每次迭代的误差向量保存 k=k+1;

count=count+1;%记录迭代次数 end

在命令窗口中输入：

A=[10 1 2 3 4;1 9 -1 2 -3;2 -1 7 3 -5;3 2 3 12 -1;4 -3 -5 -1 15]; b=[12 -27 14 -17 12]';

jd=1e-6; x=[0 0 0 0 0]'; [x,a,count,e]=jacobi(A,b,jd,x),可以得到: 1.近似解:x=[1.0000 -2.0000 3.0000 -2.0000 1.0000] 2.迭代次数count=75

3.每次迭代结果及误差见表4.1

表4.1 雅可比迭代法中每次迭代结果及误差

由表4.1可知：随着迭代次数的增多，x的各个分量越来越接近真实解，并且误差也在逐渐减小，可以知道，此时雅可比迭代法收敛。 4.2高斯赛德尔方法求解如下:

由高斯塞德尔迭代法与雅可比迭代法的关系,易得高斯塞德尔的迭代公式:

k11kkkkx110(12x22x33x44x5)

xk11(27xk1xk2xkxk)

1345

29

k11k1k1kkx3(142x1x23x45x5)

7

k11k1k1k1kx(173x2x3xx)4123512

xk11124xk13xk15xk14xk1

51234

15

MATLAB代码为:

function [x,a,count,e]=gsshiyan1(A,b,jd,x)

%A表示系数矩阵,b表示常数项矩阵,jd表示精度(本程序选择精度为1e-6）,x表示任选的初始向量(本程序选零向量)

xx=inv(A)*b; %求出真实解

er=sqrt(sum((x-xx).*(x-xx)));%求出误差(二范数) count=0;k=1;j=1;

while er>=jd %迭代求解 for i=1:5

x(i)=-1/A(i,i).*(A(i,1:i-1)*x(1:i-1)+A(i,i+1:5)*x(i+1:5)-b(i)); a(j)=x(i); %把每次迭代结果(x的五个分量)保存 j=j+1; end

er=sqrt(sum((x-xx).*(x-xx)));

e(k)=er;%把每次迭代的误差向量保存 k=k+1;

count=count+1; %记录迭代次数 end

在命令窗口中输入：

A=[10 1 2 3 4;1 9 -1 2 -3;2 -1 7 3 -5;3 2 3 12 -1;4 -3 -5 -1 15]; b=[12 -27 14 -17 12]';

jd=1e-6; x=[0 0 0 0 0]'; x=gs(A,b,jd,x),可以得到: 1.近似解:x=[1.0000 -2.0000 3.0000 -2.0000 1.0000] 2.迭代次数count=44

3.每次迭代结果及误差见表4.2

表4.2 高斯塞德尔迭代法中每次迭代结果及误差

由表4.2可知：随着迭代次数的增多，x的各个分量越来越接近真实解，并且误差也在逐渐减小，可以知道，此时高斯塞德尔迭代法收敛。 4.3超松弛迭代法求解

超松弛迭代法是在雅可比迭代法与高斯塞德尔迭代法基础上得到的加速收敛迭代法,迭代公式为:

wk1kkkkkk

xx(1210xx2x3x4x112345)1



xk1xkw(27xk19xxk2xkxk)

212345

29

wk1k

xx(142x1k1x2k17x33x4k5x5k)33

7

wk1kk1k1k1k

xx(173x2x3xx)44123512

xk1xkw124xk13xk15xk14xk115x

551234515

超松弛迭代法的收敛性与松弛因子有关, 不同的松弛因子使得超松弛迭代

法的迭代次数不同,松弛因子与迭代次数的关系见表4.3

表4.3 松弛因子与迭代次数的关系

由表4.3可知:w=2,迭代次数大于10000次，迭代次数过大，此时也不收敛。

画出松弛因子与迭代次数的关系图像见图4.3

图4.3 松弛因子与迭代次数的关系图像

由图4.3可以看出：

1.不同的松弛因子对超松弛迭代法的收敛速度的影响不同。

2.w=1.3时，迭代次数最少，因此对于该方程组，最佳松弛因子是1.3 选取松弛因子为w=1.3,MATLAB代码为: function [x,a,count,e]=SOR(A,b,jd,x)

%A表示系数矩阵,b表示常数项矩阵,jd表示精度(本程序选择精度为1e-6),x表示任选的初始向量(本程序选零向量)

xx=inv(A)*b; %求出真实解

er=sqrt(sum((x-xx).*(x-xx)));%求出误差(二范数) count=0;w=1.3,k=1;j=1; while er>=jd %迭代求解 for i=1:5

x1(i)=-1/A(i,i).*(A(i,1:i-1)*x(1:i-1)+A(i,i+1:5)*x(i+1:5)-b(i)); %求出高斯塞德尔解

x(i)=(1-w)*x(i)+w*x1(i);%求出超松弛解 a(j)=x(i); %把每次迭代结果(x的五个分量)保存 j=j+1; end

er=sqrt(sum((x-xx).*(x-xx)));

e(k)=er;%把每次迭代的误差向量保存 k=k+1;

count=count+1; %记录迭代次数 if count>10000

disp '迭代次数过大,该迭代法不收敛' break; end end end

在命令窗口中输入：

A=[10 1 2 3 4;1 9 -1 2 -3;2 -1 7 3 -5;3 2 3 12 -1;4 -3 -5 -1 15]; b=[12 -27 14 -17 12]';

jd=1e-6; x=[0 0 0 0 0]'; x=SOR(A,b,jd,x),可以得到: 1.近似解:x=[1.0000 -2.0000 3.0000 -2.0000 1.0000] 2.迭代次数count=15

3.每次迭代结果及误差见表4.4

表4.4 超松弛迭代法中每次迭代结果及误差

由表4.3可知：

1.当0=2时，该迭代法是不收敛的，这与理论分析”0

2.选择不同的w的值，迭代次数是不同的，因此选择适当的w的值，可使迭代速度达到最快。

3.当w=1时，根据SOR的构造方法知，SOR法就是高斯塞德尔迭代法。

5小结

通过以上数据测试可以分析出以下几点：

1. 雅可比迭代法、高斯塞德尔迭代法、超松弛迭代法三种迭代法对应的迭代次数是逐渐减少的，从而可以得到它们的收敛速度上是逐渐增加的。

2. 经过很少次的迭代运算,在满足设定精度情况下,三种迭代法计算得到的近似解与严格计算方程组后的精确解达到了相同，说明三种迭代法的求解精度是高的。

3.由MATLAB计算得，A与2D-A均为对称正定矩阵，有收敛条件知，这三种迭代法均收敛，由上机实验得到的数据知，三种迭代方法均收敛，这与理论分析相一致。

4.由收敛条件知，三种迭代法的收敛性只与迭代矩阵M(或者说系数矩阵A)有关，与右端项无关。

线性方程组的迭代解法除了这三种之外,还有区间迭代,点迭代这样的数值迭代逼近方法,例如,对分法,黄金分隔法,三点抛物线法,牛顿法等。本文主要讨论了常用的三种迭代解法，在时间允许的情况下，还可以从以下方面进行改进：

⑴ 对算法进行优化，尽量少开辟数组空间，及时对数组空间进行释放，重复

利用某些数组空间，从而使系统资源的利用最大化。

⑵ 对收敛速度的判定进行优化，不仅从收敛次数进行比较，还要加入收敛时

间的比较，同时将这三种迭代解法应用于不同阶数的线性方程组。分别得出收敛时间和收敛次数,再进行比较分析，这样可以排除阶数对收敛速度的影响。

致谢

大学四年学习时光已经接近尾声，在此我想对我的母校，我的父母、亲人们，我的老师和同学们表达我由衷的谢意。感谢我的家人对我大学四年学习的默默支持;感谢我的母校河南科技学院给了我在大学四年深造的机会，让我能继续学习和提高;感谢河南科技学院的老师和同学们四年来的关心和鼓励。老师们课堂上的激情洋溢，课堂下的谆谆教诲;同学们在学习中的认真热情，生活上的热心主动，所有这些都让我的四年充满了感动。这次毕业论文设计我得到了很多老师和同学的帮助，其中我的论文指导老师李巧萍老师对我的关心和支持尤为重要。每次遇到难题，我最先做得就是向李巧萍老师寻求帮助，而李巧萍老师每次不管忙或闲，总会抽空来找我面谈，然后一起商量解决的办法。

我做毕业设计的每个阶段，从选题到查阅资料，论文提纲的确定，中期论文的修改，后期论文格式调整等各个环节中都给予了我悉心的指导。这几个月以来，李巧萍老师不仅在学业上给我以精心指导，同时还在思想给我以无微不至的关怀，在此谨向李巧萍老师致以诚挚的谢意和崇高的敬意。

同时，感谢在整个毕业设计期间和我密切合作的同学，和曾经在各个方面给予过我帮助的伙伴们，在此，我再一次真诚向帮助过我的老师和同学便是感谢!

参考文献

[1]于冬梅,藤翠玲.基于线性代数方程组迭代法的比较分析与MATLAB实现[J].中国科技论文在线,123000:1-8.

[2]徐树方,高丽,张平文.数值线性代数(第二版)[M],北京:北京大学出版社,2003.1.

[3]蔡锁章,杨明,雷英杰.数值计算方法[M],北京:国防工业出版社,2011,12. [4]赵慎行.线性方程组Axb几种解法的比较研究[J].科技咨询导报,410205:101. [5]几种线性方程组的解法研究.上海大学土木工程系.200072:1-6. [6]蒋尔雄,赵风光.数值逼近,上海:复旦大学出版社,1996.