线性方程组的迭代法及程序实现.docx
《线性方程组的迭代法及程序实现.docx》由会员分享，可在线阅读，更多相关《线性方程组的迭代法及程序实现.docx（18页珍藏版）》请在冰点文库上搜索。
线性方程组的迭代法及程序实现
线性方程组的迭代法及程序实现
学校代码:
11517学号:
200810111217HENANINSTITUTEOFENGINEERING毕业论文
题目线性方程组的迭代法及程序实现
学生姓名
专业班级
学号
系（部）数理科学系
指导教师职称
完成时间2012年5月20日河南工程学院
毕业设计（论文）任务书
题目:
线性方程组的迭代法及程序实现专业:
信息与计算科学学号:
姓名一、主要内容:
通过本课题的研究,学会如何运用有限元方法来解决线性代数方程组问题,特别是Gaussie-Seidel迭代法和Jacobi迭代法来求解线性方程组。
进一步学会迭代方法的数学思想,并对程序代码进行解析与改进,这对于我们以后学习和研究实际问题具有重要的意义。
本课题运用所学的数学专业知识来研究,有助于我们进一步掌握大学数学方面的知识,特别是迭代方法。
通过这个课题的研究,我进一步掌握了迭代方法的思想,以及程序的解析与改进,对于今后类似实际问题的解决具有重要的意义。
二、基本要求:
学会编写规范论文,独立自主完成。
运用所学知识发现问题并分析、解决。
3.通过对相关资料的收集、整理,最终形成一篇具有自己观点的学术论文,以期能对线性方程组迭代法的研究发展有一定的实践指导意义。
4.在毕业论文工作中强化英语、计算机应用能力。
完成期限:
2012年月指导教师签名:
专业负责人签名:
年月日
目录
中文摘要…………………………………………………………………………Ⅰ英文摘要…………………………………………………………………………Ⅱ
1综述1
2经典迭代法概述32.1Jacobi迭代法32.2Gauss?
Seidel迭代法42.3SOR（successiveoverrelaxation）迭代法42.4SSOR迭代法52.5收敛性分析52.6数值试验6
3matlab实现的两个例题83.1例1迭代法的收敛速度83.2例2SOR迭代法松弛因子的选取12致谢16参考文献17附录19
线性方程组的迭代法及程序实现
摘要线性代数方程组的迭代方法是一种极限方法是解大型稀疏矩阵方程组的有效方法。
它的基本思想是用某种极限过程去逐步逼近线性方程组的精确解,是一种逐步逼近的方法。
迭代法将n阶线性方程组变形为某种迭代公式。
对于任意给定的迭代初始值,由某一迭代格式便可生成一向量序列,我们的目的是求解方程组的解,因此我们会希望向量序列的极限逼近方程组的解。
本文首先介绍了求解大型线性方程组的主要迭代算法,对一些经典迭代法Jacobi方法、Gauss?
Seidel方法、SOR方法和SSOR方法进行了详细的讨论,其次着重讨论了经典迭代法的收敛性,详细总结并给出了各种迭代方法的收敛性定理,并通过举例及其Matlab程序实现进一步阐述了迭代法的收敛性。
关键字线性方程组/Jacobi迭代法/Gauss-Seidel方法/SOR方法/收敛性
Iterativemethodandprocedures
forimplementation
ofthelinearequations
ABSTRACTTheiterativemethodoflinearalgebraicequationsisanextrememethodisaneffectivemethodforthesolutionoflargesparsematrixequations.Thebasicideaistoacertainlimitprocesstograduallyapproachtheexactsolutionoflinearequations,astep-by-stepapproximationmethod.Theiterativemethodwillbeiterativeformulaforadeformationofnlinearequations.Foranygiveniterationoftheinitialvalue,byaniterativeschemecangenerateavectorsequence,ouraimisthesolutiontosolvingtheequations,sowewillwanttolimitapproximationthesolutionofequationsofvectorsequences.Thispaperfirstintroducesthemainiterativealgorithmforsolvinglargelinearequations,adetaileddiscussionofsomeclassicaliterativemethodJacobimethod,Gauss-Seidelmethod,SORandSSORmethods,followedfocusedontheclassicaliterativeconvergenceofthemethod,summarizedindetailandgivesavarietyofiterativemethodsconvergencetheorem,andfurtherelaboratedbyexampleandMatlabprogramiterativemethods.
KEYWORDSlinearequations,Jacobiiterativemethod,Gauss-Seidelmethod,theSORmethod,convergence
1综述
在科学研究和大型工程设计中出现了越来越多的数学问题,而这些问题往往需要求数值解。
在进行数值求解时,经离散后,常常归结为求解行如Axb的大型线性方程组。
20世纪50年代至70年代,由于电子计算机的发展,人们开始考虑和研究在计算机上用迭代法求线性方程组Axb的近似解,用某种极限过程去逐渐逼近精确解,并发现了许多非常有效的迭代方法。
迭代法是按照某种规则构造一个向量序列{x},使其极限向量x是Axb的精确解。
因此,对迭代法来说一般有下面几个问题:
（1）如何构造迭代序列?
（2）构造的迭代序列是否收敛?
在什么情况下收敛?
（3）如果收敛,收敛的速度如何?
我们应该给予量的刻划,用以比较各种迭代法收敛的快慢。
（4）因为计算总是有限次的,所以总要讨论近似解的误差估计和迭代过程的中端处理问题,这又和舍入误差的分析有关。
迭代法具有需要计算机存储单元少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点。
例如Jacobi方法、Gauss-Seidel方法、SOR方法、SSOR方法,这几张迭代方法是最常用的一阶线性定常迭代法。
大量偏微分方程的离散形式是大规模线性代数方程组,其数值计算是科学工程计算的核心,占有绝大部分的总体运算时间,解大规模稀疏线性方程组的Krylov子空间方法显示出与众不同的有效性。
当矩阵是对称正定时,常用的方法是具有短递推的共轭度方法CG。
系数矩阵不对称时,常用的方法中有完全正交化方法（FOM）和广义最小参量方法（GMRES）。
还有很多迭代方法正在被人们发现和研究,新的有效的方法层出不穷,其中基于大型稀疏非Bermitian的正定阵的系数矩阵的Bermitian和Skew-Bermitian分裂的BSS方法,IBSS方法等具有非常好的实用性。
但没有一种算法是通用的,对于具体问题必须根据所得到的线性方程组和算法的特点进行选择。
MATLAB是Mathworks公司的产品,MATLAB的产生是与数学计算紧密联系在一起的,其基本数据结构是矩阵,它的表达式与数学工程计算中使用的形式十分相似,便于用户学习和使用.系统包括5个部分:
MATLAB语言、MATLAB工作环境、MATLAB图形处理系统、MATLAB数学函数库和MATLAB应用程序接口.其主要功能包括:
数值计算;符号计算;数据分析和可视化;文字处理;Simulink动态仿真.在数值计算中,线性方程组的求解是一个很重要的问题.用MATLAB来求解线性方程组,有几种方法,非常简单,通过对一些矩阵和函数的操作可以轻松地得到线性方程组的解,不需要使用者掌握任何程序设计语言,对迭代法只需编写简单的程序
2经典迭代法概述
20世纪50年代至70年代,人们开始考虑和研究用迭代法求解线性方程组（2-1）
的近似解,发展了许多有效的方法,其中有Jacobi方法、Gauss-Seidel方法、SOR方法、SSOR方法,这几种迭代方法均属一阶线性定常迭代法,即若系数矩阵A的一个分裂:
;M为可逆矩阵,线性方程组（2-1）化为:
;
得到迭代方法的一般公式:
（2-2）
其中:
。
2.1Jacobi迭代法
若D为A的对角素构成的对角矩阵,且对角线元素全不为零。
系数矩阵A的一个分解:
AD-E+F;这里D为A的对角矩阵,E为严格下三角阵,F为严格上三角阵。
其中:
Jacobi迭代的矩阵形式为:
（2-3）
2-3式中:
;,称为Jacobi迭代矩阵。
其计算公式为:
（2-4）
2.2Gauss?
Seidel迭代法
对于非奇异方程组,若D为A的对角素构成的对角矩阵,且对角线元素全不为零;系数矩阵A的一个分解:
2-5
Gauss?
Seidel迭代矩阵形式为2-6
其计算公式为:
（2-7）
2.3SOR（successiveoverrelaxation）迭代法
对于非奇异方程组,若D为A的对角素构成的对角矩阵,且对角线元素全不为零;系数矩阵A的一个分解:
（2-8）
这里D为A的对角素构成的对角矩阵,E为严格下三角形,F为严格上三角形。
SOR迭代法的矩阵形式为:
（2-9）
计算公式为:
（2-10）
式中:
为实数,称为松弛因子,02。
2.4SSOR迭代法
SSOR（symmetricsuccessiveoverrelaxation）迭代法的矩阵形式为:
2-11
SSOR迭代矩阵为:
（2-12）
计算公式分为以下两步:
先按自然次序（i1,2,…,n）用向前的SOR法逐点计算。
2-13
然后按相反的次序（in,n-1,…,1）用向后的SOR方法逐点计算。
2-14
2.5收敛性分析
综合上面前三种迭代格式,它们可以统一表示为下面形式:
（2-15）
对Jacobi方法来说,,;
对Gauss-Seidel方法来说,,;
对SOR方法来说,,。
定理1:
简单迭代法（2-15）收敛的充分必要条件是迭代矩阵B的谱半径.
定理2:
若迭代矩阵B的范数,则迭代公式（2-15）收敛,且有误差估计式（2-16）（2-17）
定理3:
设对于方程组,若系数矩阵A是严格对角占优矩阵,则Jacobi迭代法和Gauss-Seidel迭代法都收敛。
定理4:
设A为n阶非奇异方阵,则的解总能通过Gauss-Seidel方法得到。
定理5:
设是二阶矩阵,,且,则有:
（1）方程组若用J方法与G-S方法解之,敛散性相同;
（2）方程组若发散,总可以通过交换两行的方法得到解（当时）。
定理6:
若系数矩阵A对称正定,则G-S迭代公式收敛。
定理7:
若系数矩阵A对称正定,且也为对称正定阵,则Jacobi迭代收敛。
定理8:
若系数矩阵A为对称正定阵,则当时,SOR迭代法收敛。
定理9:
若系数矩阵A为严格对角占优阵,则当时,SOR迭代法收敛。
定理10:
若系数矩阵A为是正定的,则当时,SSOR迭代法收敛。
简单迭代法的比较:
一般情况下,J方法与G-S方法比较并无优劣。
收敛情况与速度均不一定。
但是,具有相容次序的矩阵,在相同精确要求下,G-S法比J方法快一倍,而SOR法的收敛速度可提高一个数量级。
2.6数值试验
下面通过一个数值实例来比较Jacobi方法、Gauss-Seidel方法、SOR方法的收敛速度。
数值实验:
我们取一个系数为64阶的线性方程组:
AXb。
其中:
精确解:
X（111…11）;取X（000…00）;精度为:
0.0001。
执行c语言程序interatormethod.c见附录得到result.txt文件。
从中可以得到三种方法的迭代性能对比如
表2-1
MethodITCPUTime/msInfo
Jacobi183.000008.19628
Gauss-Seidel102.000001.68024几乎比Jacobi速度快一倍
SOR
with1.0102.000001.68024退化成G-S迭代
SOR
with61.000005.47552是SOR迭代达到最快
SOR
with1.5173.000002.09836的取值对于SOR迭代的收敛速度影响很大
3matlab实现的两个例题
3.1例1迭代法的收敛速度
用迭代法分别对n20,n200解方程组Axb,其中
（1）选取不同的初值和不同的右端向量b,给定迭代误差,用两种迭代法计算,观测得到的迭代向量并分析计算结果给出结论;
（2）取定初值和右端向量b,给定迭代误差,将A的主对角元成倍放大,其余元素不变,用Jacobi迭代法计算多次,比较收敛速度,分析计算结果并给出结论。
原理解析:
运用了Jacobi迭代,Gauss-Seidel迭代
1）Jacobi迭代算法:
取初始点,精度要求ε,最大迭代次数N,置;
由（3-1）
计算出;
若,则停算,输出作为方程组的近似解;
若kN,则停算,输出迭代失败信息;否则置,转步2。
2）Gauss-Seidel迭代算法:
（3-2）
3.若,则停算,输出x作为方程组的近似解;
4.若kN,则停算,输出迭代失败信息;否则置x,kk+1,转步骤2。
解:
（1）打开matlab软件,新建一个M文件,编写程序（见附录二）,运行程序,记录结果;
（2）把程序中onesn,1改为eyen,1,运行程序,记录结果;
（3）把程序中Ai,im改为Ai,i2*m,注释掉majacobiA,b;后面的部分,运行程序,记录结果;
（4）仿照（3）再把主对角元成倍放大,运行程序,记录结果。
运行结果为:
（1）对于n20时:
n20
Columns1through124.0000-0.3333-0.2000000000000-0.33334.0000-0.3333-0.200000000000-0.2000-0.33334.0000-0.3333-0.200000000000-0.2000-0.33334.0000-0.3333-0.200000000000-0.2000-0.33334.0000-0.3333-0.200000000000-0.2000-0.33334.0000-0.3333-0.200000000000-0.2000-0.33334.0000-0.3333-0.200000000000-0.2000-0.33334.0000-0.3333-0.200000000000-0.2000-0.33334.0000-0.3333-0.200000000000-0.2000-0.33334.0000-0.3333-0.200000000000-0.2000-0.33334.0000-0.3333000000000-0.2000-0.33334.00000000000000-0.2000-0.333300000000000-0.2000000000000000000000000000000000000000000000000000000000000000000000000000
Columns13through2000000000000000000000000000000000000000000000000000000000000000000000000000000000-0.20000000000
-0.3333-0.20000000004.0000-0.3333-0.200000000-0.33334.0000-0.3333-0.20000000
-0.2000-0.33334.0000-0.3333-0.20000000-0.2000-0.33334.0000-0.3333-0.200000
00-0.2000-0.33334.0000-0.3333-0.20000
000-0.2000-0.33334.0000-0.3333-0.2000
0000-0.2000-0.33334.0000-0.333300000-0.2000-0.33334.0000
k11
x11.0000……1.0000//有20个1.0000
k8
x21.0000……1.0000//有20个1.0000
ans3.3039e-007
（2）当n200时:
A由于阶数太大省略;
k11
x11.0000
……1.0000//有200个1.0000
k8
x21.0000
……1.0000//有200个1.0000
ans1.1368e-006
（2）k4
x11.0000……1.0000（20阶）
k4
x21.0000……1.0000（20阶）
ans4.8999e-008
结果分析:
比较结果可知,选取不同的初值和不同的右端向量b,所求得的结果也会不同,Jacobi迭代和Seidel迭代的误差也会随之改变,说明初值对结果有影响,由迭代误差可知Seidel迭代优于Jacobi迭代。
再比较结果,由k6与k5可知,主对角元越大,Jacobi迭代收敛越快。
3.2例2SOR迭代法松弛因子的选取
（1）给定迭代误差,选取不同的超松弛因子,从1.00到2.00,观察不同的松弛因子对解得影响。
然后利用雅可比迭代求的的解与它们比较;
（2）给定迭代误差,选取不同的低松弛因子,从1.00到2.00,观察不同的松弛因子对解得影响。
然后利用雅可比迭代求的的解与它们比较。
原理解析:
（1）逐次超松弛迭代法是Gauss-Seidel迭代法的加速。
Gauss-Seidel迭代格式为:
（3-3）
（2）SOR迭代格式为（3-4）
其中,叫做松弛因子,当1时叫超松弛,当10时叫低松弛。
1是Gauss-Seidel迭代法;
（3）SOR迭代法的算法:
输入矩阵A,向量b,初始点,精确度,最大迭代次数N,松弛因子的选取;进行迭代;判断迭代的情况。
解:
（1）数据准备:
A12*eye200,200;
fori1:
199Ai,i+1-2;Ai+1,i-2;
end
forj1:
198Aj,j+21;Aj+2,j1;
end
b5*ones200,1;
（2）给定迭代误差1e-6,取1.00,1.10,1.20,1.30,1.40,1.50,1.60,1.70,1.80,1.90,
1.91,1.92,1.95,1.97,1.98,1.99,2.00,代入xmasorA,b,,x20majacobiA,b
并利用normx-x20分别分析与雅可比迭代求的解的误差;
3给定迭代误差1e-6,取0.02,0.03,0.040.10,0.20,0.30,0.40,0.50,0.60,0.70,0.80,
0.90,0.97.0.98,0.99,代入xmasorA,b,,majacobiA,b并利用分别分析与雅可比迭代求的解的误差。
运行结果为:
表3-11的情况
k
1.0089.7346e-007
1.10109.6821e-007
1.20121.0307e-006
1.30161.0200e-006
1.40201.1434e-006
1.50261.2691e-006
1.60361.2272e-006
1.70511.4364e-006
1.80831.4657e-006
1.901771.7205e-006
1.911981.7542e-006
1.922242.2548e-006
1.953211.5060e-006
1.974711.8146e-006
1.98500
1.99500
表3-21的情况
k
0.00
0.02500
0.033863.8618e-004
0.042972.8217e-004
0.101261.0286e-004
0.20644.0889e-005
0.30422.1010e-005
0,40301.4555e-005
0.50238.1655e-006
0.60185.0040e-006
0.70143.7920e-006
0.80112.3675e-006
0.9091.0772e-006
0.9789.7786e-007
0.9889.7481e-007
0.9989.7361e-007
结果分析:
（1）由表1-1可以看出,在其它条件不变的情况下,改变的值,会改变解得值,且越接近于1,误差越小,越接近于2,误差越大,而且当的值越大,它的迭代次数越大,就本例而言,当为1.98时,就因迭代次数过大,跳出程序;
（2）由表1-2可以看出,在其它条件不变的情况下,改变的值,会改变解得值,且越接近于1,误差越小,越接近于0,误差越大,且迭代次数也越大,就本例而言,当为0.02时,就因迭代次数过大,跳出程序,且不能取值为0;
（3）综上
（1）
（2）所述,的取值范围为02,且越接近1,误差值越小,迭代次数也越小。
致谢
毕业设计是对我们知识能力的一次全面考核,也是对我们科学研究基本功的训练,培养我们综合运用所学知识独立的分析问题和解决问题的能力,为以后撰写专业学术论文和工作打下良好基础。
本次设计能够顺利完成,首先要感谢我的母校?
?
河南工程学院。
是她为我们提供了学习知识的土壤,使我们在这里茁壮成长,其次要感谢赵恒军老师在设计工程中给予我的悉心指导,她认真负责的态度,严谨的治学精神和深厚的理论水平都是我受益匪浅。
她无论在理论上还是实践中,都给予我很大的帮助,感谢她耐心的辅导,谨向赵老师致以真诚的谢意!
在今后的人生道路上,我一定谨遵恩师的教诲,发挥自己的潜能。
同时,同学们的热心帮助也使我获益菲浅,没有他们我不会取得如此大的进步,在此一并感谢!
最后要感谢相关资料的编著者和给予我们支持的社会各界人士,感谢您们为我提供一个良好的环境,使这次设计圆满完成。
由于知识有限,论文还有很多欠缺之处,请各位审阅老师指正,多提宝贵意见,特此感谢!
参考文献
[1]陈桂秀,方程求解中迭代法的使用[N],青海师范大学学报自然科学版,2009年第1期.
[2]曹志浩.数值线性代数[M].复旦大学出版社,1996
[3]G.E.福赛斯,C.B.莫勒.线性代数方程组的计算机解法[M],徐树荣译.科学出版社,1976[4
升级会员 