迭代法求解线性方程组的研究.doc

迭代法求解线性方程组的研究 【摘要】:本文总结了解线性方程组的三个迭代法，Jacobi迭代法，Gauss-seidel迭代法，SOR迭代法，并且介绍了现代数值计算软件MATLAB在这方面的应用，即分别给出三个迭代法的数值实验。 【关键字】:Jacobi迭代法 Gauss-seidel迭代法 SOR迭代法 数值实验一 引言迭代法是用某种极限过程去逐步逼近线性方程组精确解的方法，它是解高阶稀疏方程组的重要方法。迭代法的基本思想是用逐次逼近的方法求解线性方程组。设有方程组 将其转化为等价的，便于迭代的形式 (这种转化总能实现，如令),并由此构造迭代公式 式中B称为迭代矩阵，f称为迭代向量。对任意的初始向量，由式可求得向量序列，若，则就是方程或方程的解。此时迭代公式是收敛的，否则称为发散的。构造的迭代公式是否收敛，取决于迭代矩阵B的性质。本文介绍三种解线性方程组的最主要的三种迭代法：Jacobi迭代法，Gauss-Seidel迭代法和SOR迭代法。本文结构如下：第二部分介绍Jacobi迭代法及其数值实验，第三部分介绍Gauss-Seidel迭代法及其数值实验，第四部分介绍SOR迭代法及其数值实验，第五部分总结。二 雅克比（Jacobi）迭代法1. 雅克比迭代法的格式设有方程组 矩阵形式为,设系数矩阵A为非奇异矩阵，且从式中第i个方程中解出x，得其等价形式 取初始向量，对式应用迭代法，可建立相应的迭代公式： 也可记为矩阵形式： 若将系数矩阵A分解为A=D-L-U，式中 ， ， 。则方程Ax=b变为 得 于是 于是式中中的 。式和式分别称为雅克比迭代法的分量形式和矩阵形式，分量形式用于编程计算，矩阵型式用于讨论迭代法的收敛性。2. 雅克比迭代法的程序 雅克比迭代法的MATLAB函数文件 aguijacobi.m如下。 Function x= aguijacobi(a,b) %a为系数矩阵，b为右端向量，为初始向量（默认为零向量） %e为精度（默认为1e-6）,n为最大迭代次数（默认为100） x为返回解向量。 n=length(b)； N=100; e=1e-6; x0=zeros(n,1); x=x0; x0=x+2*e; k=0; d=diag(diag,0); 1=-tril(a,-1); u=-triu(a,1); while norm(x0-x,inf)e&ka=10 -1 2;-1 10 -2;-1 -1 5 a= 10 -1 2 -1 10 -2 -1 -1 5 b=72;83;42 b= 72 83 42 x= aguijacobi(a,b) 计算结果为： k=1 7.20000000000000 8.30000000000000 8.40000000000000 k=2 9.710000000000000 10.70000000000000 11.50000000000000 k=16 10.99999968449670 11.99999968449670 12.99999962583317 x= 10.99999968449670 11.99999968449670 12.99999962583317.三高斯赛德尔（Gauss-Seidel）迭代法1. 高斯赛德尔迭代法的格式。 雅克比迭代法的优点是公式简单，迭代矩阵容易计算。在每一步迭代时，用的全部分量求出的全部分量，因此称为同步迭代法，计算时需保留两个近似解和。 但在雅克比迭代过程中，对已经计算出的信息未能充分利用，即在计算第i个分量时，已经计算出的最新分量没有被利用。从直观上看，在收敛的前提下，这些新的分量应比旧的分量更好，更精确一些。因此，如果每计算出一个新的分量便立即用它取代对应的旧分量进行迭代，可能收敛的速度更快，并且只需要储存一个近似解向量即可。据此思想可构造高斯赛德尔（Gauss-Seidel）迭代法，其迭代公式为 （i=1,2,n）也可以写成矩阵形式 仍将系数矩阵A分解为 则方程组变为 得 将最新分量代替为旧分量，得 即 于是有 所以 因为高斯赛德尔迭代法比雅克比迭代法收敛快，这个结论在多数情况下是成立的，但也有相反的情况，即高斯赛德尔迭代法比雅克比迭代法收敛慢，甚至还有雅克比迭代法收敛，高斯赛德尔迭代法发散的情形。2. 高斯赛德尔迭代法的程序 高斯赛德尔迭代法在MATLAB的函数文件 agui_GS.m 如下 Function x= agui_GS(a,b) %a为系数矩阵，b为右端向量，x0为初始向量（默认为零向量） %e为精度（默认为1e-6）,N为最大迭代次数（默认为100），x为返回解向量 n=length(b); N=100; e=1e-6; x0=zeros(n,1); x=x0; x0=x+2*e; k=0; a1=tril(a); a2=inv（a1）; while norm(x0-x,inf)e&ka=10 -1 2;-1 10 -2;-1 -1 5 a= 10 -1 2 -1 10 -2 -1 -1 5 b=72;83;42 b= 72 83 42 x=agui_GS(a,b). 计算结果为： k=1 7.20000000000000 9.02000000000000 11.64400000000000 k=2 10.43080000000000 11.67188000000000 12.82053600000000 k=3 10.99999996545653 11.99999997883050 12.99999998885741 x= 10.99999996545653 11.99999997883050 12.99999998885741三 超松弛（SOR）迭代法1. 超松弛迭代法的格式超松弛迭代法（Successive Over Relaxation Method,SOR方法）是高斯赛德尔迭代法的一种改进，是解大型稀疏方程组的有效方法之一。设已知第k次迭代向量，及第k+1次迭代向量的前i-1个分量，（j=1,2,i-1）,现在研究如何求向量的第i个分量。 首先，有高斯赛德尔迭代法求出一个值，记为 （i=1,2,n）再将第k次迭代向量的第i个分量与进行加权平均，得，即： 于是的SOR迭代公式 (i=1,2,n) 或 （i=1,2,n） 当=1时，式即为高斯赛德尔迭代法；当01时，式称为超松弛方法，可以用来提高收敛速度。将式写成矩阵的形式，得： 即 于是得SOR迭代的矩阵表示 式中 2. SOR迭代法的程序 SOR迭代法的MATLAB函数文件 agui_SOR.m 如下 function x= agui_SOR(a,b,omg) %a为系数矩阵，b为右端向量，x0为初始向量（默认为零向量） %e为精度（默认为1e-6）,N为最大迭代次数（默认为100） %omg为松弛因子，x为返回解向量。 n=length(b); N=100; e=1e-6; x0=x+2*e; k=0; L=tril(a,-1); U=triu(a,1); While norm(x0-x,inf)e&ka=4 -2 -4;-2 17 10;-4 10 9 a= 4 -2 4 -2 17 10 -4 10 9 b=10;3;7 b= 10 3 -7 取松弛因子为1.46，得 x= agui_SOR(a,b,1.46) k=1 3.65000000000000 0.88458823529412 -0.2021980392157 k=2 2.32166909803922 0.42309393550173 -0.22243214861566 k=20 1.99999799028435 1.00000077908772 -1.00000253133178 k=21 1.99999779745884 1.00000143726811 -1.00000259636013 x= 1.99999779745884 1.00000143726811 -1.00000259636013 取松弛因子为1.即用高斯赛德尔迭代法则需迭代90次，得 x= agui_SOR(a,b,1.0) k=1 2.50000000000000 0.47058823529412 -0.18954248366013 k=2 2.49466017343757 0.64588531811546 -0.38669027637825 k=90 2.00000553192680 0.99999608340497 -0.99999318959361 x= 2.00000553192680 0.99999608340497 -0.99999318959361四 总结以上几种解线性方程组的迭代法主要用于解高阶稀疏矩阵方程组，其特点是：占用内存少，程序设计简单，原始系数矩阵在计算过程中始终不变。但存在收敛性和收敛速度的问题。Jacobi迭代法也称简单迭代法，其基本思想是从方程组的第i个方程求出，并建立相应的迭代公式求出，Gauss-Seidel迭代法在Jacobi迭代法的基础上进行了改进，再求时，用已求出的新值代替旧值，因此也称异步迭代法。在二者都收敛时，Gauss-Seidel迭代法的收敛速度较快，所以，应用比较广泛。SOR迭代法的松弛因子选择的恰当，收敛速度更快，对一些特殊的方程组，选择松弛因子已有成熟的公式和经验，因此，SOR迭代法应用也比较广泛。参考文献【1】 陈国章.使用计算方法应急手册.【M】.天津：天津科学技术出版社，1994.【2】 李乃成，邓建中.数值计算方法.【M】.西安：西安交通大学出版社，2002【3】李庆扬，王能超，易大义. 数值分析（第4版）.【M】. 北京：清华大学出版社，2001.【4】李庆扬.数值分析基础教程.【M】.北京：高等教育出版社,2001.【5】王沫然. MATLAB 5.x与计算方法.【M】.北京：清华大学出版社，2000.【6】Shoichiro Nakamura 著.梁恒，刘晓艳等译.科学计算引论基于MATLAB的数值分析【M】.北京：电子工业出版社，2002.【7】王能超.数值分析简明教程（第2版）.【M】.北京：高等教育出版社，2003.【8】金聪，熊盛武.数值分析.【M】.武汉：武汉理工大学出版社，2003.【9】魏毅强，张建国，张洪斌等.数值计算方法.【M】.北京：高等教育出版社，2004.【10】高培旺.计算方法典型例题与习题.【M】.长沙：国防科技大学出版社，2003.【11】封建湖，聂玉峰，王振海.数值分析（第4版）导教导学导考.【M】.西安：西北工业大学出版社，2003.【12】吴筑筑.计算方法.【M】.北京：清华大学出版社、北京交通大学出版社，2004.【13】严蔚敏，吴伟民数据结构(C语言版) 【M】北京：清华大学出版社,1997【14】Richard L. Burden，J. Douglas Faires. Numerical Analysis （Seventh Edition）.【M】.Thomson Learning，Inc，2001.【15】Pascal Sebah and Xavier Gourdon,Newtons Method And High Order Iterations【A】.Numbers, Constant and Computation.2001Solution Of Linear Equations Of Iteration With The ExperimentalAbstract: This summary understanding of linear equations three iteration, jacobi iteration, gauss - seidel iteration,