Jacobi method and Gauss-Seidel iterative 源程序(例)
- 格式:doc
- 大小:19.00 KB
- 文档页数:2
Jacobi与Gauss-Seidel迭代的比较及r算法的MATLAB实现胡志成【摘要】探讨比较了Jacobi迭代和Gauss-Seidel迭代,尤其是它们的可并行性.给出了它们在MATLAB中的一个实现.通过算例说明,算法的并行化实现可以大幅度地提升Jacobi迭代的效率.【期刊名称】《高师理科学刊》【年(卷),期】2018(038)003【总页数】4页(P59-61,84)【关键词】Jacobi迭代;Gauss-Seidel迭代;并行性【作者】胡志成【作者单位】南京航空航天大学理学院,江苏南京 210016【正文语种】中文【中图分类】O241.6;G642.0Jacobi迭代和Gauss-Seidel迭代是解线性方程组的2个经典的迭代法,简单又易于实现,是大学计算方法相关课程必讲的知识点.然而教材[1-3]往往只注重理论而轻视算法的程序实现.就这2个迭代法而言,表现为着重讨论迭代法的收敛性和收敛速度,而甚少给出或者仅给出一个粗糙低效的算法实现.至于Jacobi迭代的并行性,探讨的更是少之又少.由于课时的限制,在工科计算方法教学中更是如此.这一方面是由于一般程序语言关于算法的并行化实现并不那么容易,另一方面则是因为在课堂上短时间内举例说明算法并行化实现带来的效率提升较为困难.然而在课堂上适当地给出算法的实现和具体算例,显然有助于学生对算法本身的理解.本文首先回顾了Jacobi迭代和Gauss-Seidel迭代的基本格式和传统比较,然后探讨了它们的可并行性,并给出了在MATLAB中的一个实现.文中给出的算例不仅可以在课堂的短时间内展示结果,也能说明算法的并行化实现可以大幅度地提升Jacobi迭代的效率.设是阶非奇异方阵,为维列向量.若的主对角元,,则线性方程组可以用Jacobi 迭代和Gauss-Seidel迭代求解.其迭代格式分别为若再将表示成,其中:;;,则Jacobi迭代可用矩阵表示为相应地,Gauss-Seidel迭代的矩阵形式为关于Jacobi迭代和Gauss-Seidel迭代的分析和比较,在众多的文献中都有提及[1,4-6],主要归结为:(1)收敛性.当且仅当各自的迭代矩阵(分别是和)的谱半径小于1时,该迭代法收敛.若是严格对角占优阵,则2个迭代法都收敛.但一般地, Jacobi迭代收敛不能保证同一问题的Gauss-Seidel迭代也收敛,反之亦然.(2)收敛速度.当Gauss-Seidel迭代和Jacobi迭代两者都收敛时,多数情况下Gauss-Seidel迭代比Jacobi迭代收敛得更快.对于一些模型问题,Gauss-Seidel迭代的收敛速度甚至是Jacobi迭代的2倍以上[5]58.也就是说,从同一初值出发,为得到满足精度要求的解,Gauss-Seidel迭代所需的步数可能比Jacobi迭代所需步数的一半还要少.(3)每步计算量.由于矩阵的求逆并不那么容易,具体的算法实现多采用分量形式,即式(1)和式(2).比较式(1)和式(2)可知,2个迭代法每步的计算量相等.(4)存储量.Gauss-Seidel迭代只需1个向量来存储或的分量,而Jacobi迭代需要2个向量来分别存储和.比较可知,在传统的算法实现中,Gauss-Seidel迭代比Jacobi迭代往往更具优势.随着多核处理器的迅猛发展,并行计算渐次成为提升计算效率的重要技术手段,因而一个算法的可并行性也成为了衡量其优劣的重要指标[7-9].进一步比较迭代法(1)和(2),易知Jacobi迭代中,各分量的计算是相互独立的,因而具有高度的并行性;而Gauss-Seidel迭代中,各分量是依次顺序计算的,因而本质上是一个串行算法.这就意味着,利用算法的可并行性,如果实现得当,即使收敛速度较慢,Jacobi迭代仍然有可能在更短的时间内得到满足精度要求的数值解.为了加深学生对此的理解,并让学生体会到算法实现,特别是并行化实现的重要性,有必要给出适当的实例和程序实现.MATLAB是一种面向科学与工程计算的数学软件,因其强大的数值计算和图形绘制能力、广泛的工具包支持以及使用的便利性,深受教学和科研工作者的喜爱,是工科大学生需要掌握的重要软件之一[10].借助其灵活的矩阵向量运算,给出Jacobi迭代(1)在MATLAB环境中的一个实现(见算法1)和Gauss-Seidel迭代(2)的一个MATLAB实现(见算法2).可以看到,算法1完全避免了Jacobi迭代各分量之间的for循环,而算法2则无法避免Gauss-Seidel迭代各分量之间的for循环,这是导致2个算法执行效率巨大差异的直接原因.算法1(Jacobi 迭代):function [x,k,res] = Jacobi(A,b,x0,tol,kmax )k = 0; res = 1;while(k <= kmax)& res > tol)x =(b - A * x0 + diag(A).* x0 )./ diag(A);k = k+1;res = max(abs(b - A * x ));x0 = x;end算法2( Gauss-Seidel 迭代):function [x,k,res] = GaussSeidel(A,b,x0,tol,kmax )k = 0;res = 1;x = x0;while (k <= kmax)&(res > tol)for i = 1:length(x)x(i)=(b(i)- A(i,1:end)* x + A(i,i)* x(i))/ A(i,i);endk = k+1;res = max(abs(b - A * x));end以零向量为初值,以残量的无穷范数为收敛准则,考察比较这2个算法求解线性方程组的数值结果,包括迭代步数、每步耗时和总耗时.为了使测试算例具有一定的普遍意义,且能在课堂上较短的时间内展示比较结果.用算法3来随机生成阶线性方程组的系数矩阵.算法3(随机生成一个严格对角占优矩阵):function A = randSDDMatrix(n)nzmax = randi([n*5,round(n*10)],1);i = [randi([1,n],nzmax,1)];j = [randi([1,n],nzmax,1)];s = rand(nzmax,1);A = sparse(i,j,s,n,n);x = randi([1,1e1],n,1)+ sum( abs(A),2);ii = 1:n;A = sparse(ii,ii,x,n,n)+ A;该矩阵是稀疏的,并且是严格对角占优的,可以确保阶数较大时,2个迭代法仍能快速收敛.当然,右端项也是随机生成的.对每一个阶数,都测试100组和,并取其平均数据(见表1).由表1可以看出,虽然Jacobi迭代(1)和Gauss-Seidel迭代(2)的每步计算量相等,但是算法1的每步计算效率显著优于算法2.这最终导致:虽然Jacobi 迭代的总迭代步数是Gauss-Seidel迭代的2倍以上,但是总耗时却远少于Gauss-Seidel迭代.而且随着矩阵阶数增加,在本文的算法实现下,这个优势将进一步扩大.本文比较分析了Jacobi迭代和Gauss-Seidel迭代,强调说明Jacobi迭代是一个高度并行的算法,而Gauss-Seidel迭代则是一个串行算法.因而如果算法实现得当,即使收敛速度更慢的时候,Jacobi迭代仍然可能比Gauss-Seidel迭代更快地给出数值解.在教学实践中,课堂上展示这些MATLAB实现和数值算例,明显地加深了学生对这2个迭代法的理解,也使学生意识到了算法实现的重要性,获得了较好的教学效果.【相关文献】[1] 倪勤,王正盛,刘皞.数值计算方法[M].北京:高等教育出版社,2012[2] 李庆杨,王能超,易大义.数值分析[M].5版.北京:清华大学出版社,2008[3] 李有法,李晓勤.数值计算方法[M].2版.北京:高等教育出版社,2005[4] 杜衡吉,徐昆良.Jacobi和Gauss-Seidel迭代法求解线性方程组的分析及应用[J].曲靖师范学院学报,2011,30(3):46-50[5] 白红梅.Jacobi迭代法与Gauss-Seidel迭代法的收敛性比较分析[J].呼伦贝尔学院学报,2009,17(6):55-58[6] 包丽君.“数值分析”中实践教学的探讨[J].宁波广播电视大学学报,2008,6(2):91-93[7] 徐树方,高立,张平文.数值线性代数[M].北京:北京大学出版社,2000[8] 杨学军.并行计算六十年[J].计算机工程与科学,2012,34(8):1-10[9] 韩建勋.并行计算在矩阵运算中的应用[J].信息与电脑:理论版,2017(5):93-96[10] 韦慧,蒋利华.基于MATLAB的大学工科《计算方法》课程教学方法探讨[J].内江科技,2017(4):72-73。
第三章 逐次逼近法1.1内容提要1、一元迭代法x n+1=φ(x n )收敛条件为:1)映内性x ∈[a,b],φ(x) ∈[a,b] 2)压缩性∣φ(x) -φ(y)∣≤L ∣x-y ∣其中L <1,此时φ为压缩算子,在不断的迭代中,就可以得到最终的不动点集。
由微分中值定理,如果∣φ’∣≤L <1,显然它一定满足压缩性条件。
2、多元迭代法x n+1=φ(x n )收敛条件为:1)映内性x n ∈Ω,φ(x n ) ∈Ω 2)压缩性ρ(▽φ)<1,其中▽φ为x n 处的梯度矩阵,此时φ为压缩算子,在不断的迭代中,就可以得到最终的不动点集。
3、当φ(x )= Bx+f 时,收敛条件为,ρ(B )<1,此时x n+1= Bx n +f ,在不断的迭代中,就可以得到线性方程组的解。
4、线性方程组的迭代解法,先作矩阵变换 U L D A --= Jacobi 迭代公式的矩阵形式 f Bx b D x U L D x n n n +=++=--+111)(Gauss-Seidel 迭代公式的矩阵形式 f Bx b L D Ux L D x n n n +=-+-=--+111)()( 超松弛迭代法公式的矩阵形式f Bx b L D x U D L D x k k k +=-++--=--+ωωωωω111)(])1[()(三种迭代方法当1)(<B ρ时都收敛。
5、线性方程组的迭代解法,如果A 严格对角占优,则Jacob 法和Gauss-Seidel 法都收敛。
6、线性方程组的迭代解法,如果A 不可约对角占优,则Gauss-Seidel 法收敛。
7、Newton 迭代法,单根为二阶收敛 2211'''21lim)(2)(lim---∞→+∞→--=-==--k k k k k k k k x x x x f f c x x ξξαα8、Newton 法迭代时,遇到重根,迭代变成线性收敛,如果知道重数m , )()('1k k k k x f x f m x x -=+仍为二阶收敛 9、弦割法)()())((111--+---=k k k k k k k x f x f x x x f x x 的收敛阶为1.618,分半法的收敛速度为(b-a )/2n-110、Aitken 加速公式11211112)(),(),(+----+-+--+---+---===k k k k k k k k k k k x x x x x x x x x x x ϕϕ1.2 典型例题分析1、证明如果A 严格对角占优,则Jacob 法和Gauss-Seidel 法都收敛。
Jacobi 迭代法与Gauss-Seidel迭代法算法比较目录1 引言 (1)1.1Jacobi迭代法 (2)1.2Gauss-Seidel迭代法 (2)1.3逐次超松弛(SOR)迭代法 (3)2算法分析 (3)3 结论 (5)4 附录程序 (5)参考文献 (8)Jacobi 迭代法与Gauss-Seidel 迭代法比较1 引言解线性方程组的方法分为直接法和迭代法,直接法是在没有舍入误差的假设下,能在预定的运算次数内求得精确解,而迭代法是构造一定的递推格式,产生逼近精确值的序列。
这两种方法各有优缺点,直接法普遍适用,但要求计算机有较大的存储量,迭代法要求的存储量较小,但必须在收敛性得以保证的情况下才能使用。
对于高阶方程组,如一些偏微分方程数值求解中出现的方程组,采用直接法计算代价比较高,迭代法则简单又实用,所以比较受工程人员青睐。
迭代法求解方程组就是构造一个无限的向量序列,使它的极限是方程组的解向量。
即使计算机过程是精确的,迭代法也不能通过有限次算术运算求得方程组的精确解,而只能逐步逼近它。
因此迭代法存在收敛性与精度控制的问题。
迭代法是常用于求解大型稀疏线性方程组(系数矩阵阶数较高且0元素较多),特别是某些偏微分方程离散化后得到的大型稀疏方程组的重要方法。
设n 元线性微分方程组b Ax = (1)的系数矩阵A 非奇异,右端向量0≠b ,因而方程组有唯一的非零解向量。
而对于这种线性方程组的近似解,前辈们发展研究了许多种有效的方法,有Jacobi 迭代法、Gauss —Seidel 迭代法,逐次超松弛迭代法(SOR 法),这几种迭代方法均属一阶线性定常迭代法,即若系数矩阵A 分解成两个矩阵N 和P 的差,即P N A -=;其中N 为可逆矩阵,线性方程组(1)化为:b x P N =-)(b Px Nx +=b N Px N x 11--+=可得到迭代方法的一般公式:d Gx xk k +=+))1(( (2)其中:P N G 1-=,b N d 1-=,对任取一向量)0(x 作为方程组的初始近似解,按递推公式产生一个向量序列)1(x ,)2(x ,...,)k x(,...,当k 足够大时,此序列就可以作为线性方程组的近似解。
Jacobi 迭代法与Gauss-Seidel迭代法算法比较目录1 引言 (1)1.1Jacobi迭代法 (2)1.2Gauss-Seidel迭代法 (2)1.3逐次超松弛(SOR)迭代法 (3)2算法分析 (3)3 结论 (5)4 附录程序 (5)参考文献 (8)Jacobi 迭代法与Gauss-Seidel 迭代法比较1 引言解线性方程组的方法分为直接法和迭代法,直接法是在没有舍入误差的假设下,能在预定的运算次数内求得精确解,而迭代法是构造一定的递推格式,产生逼近精确值的序列。
这两种方法各有优缺点,直接法普遍适用,但要求计算机有较大的存储量,迭代法要求的存储量较小,但必须在收敛性得以保证的情况下才能使用。
对于高阶方程组,如一些偏微分方程数值求解中出现的方程组,采用直接法计算代价比较高,迭代法则简单又实用,所以比较受工程人员青睐。
迭代法求解方程组就是构造一个无限的向量序列,使它的极限是方程组的解向量。
即使计算机过程是精确的,迭代法也不能通过有限次算术运算求得方程组的精确解,而只能逐步逼近它。
因此迭代法存在收敛性与精度控制的问题。
迭代法是常用于求解大型稀疏线性方程组(系数矩阵阶数较高且0元素较多),特别是某些偏微分方程离散化后得到的大型稀疏方程组的重要方法。
设n 元线性微分方程组b Ax = (1)的系数矩阵A 非奇异,右端向量0≠b ,因而方程组有唯一的非零解向量。
而对于这种线性方程组的近似解,前辈们发展研究了许多种有效的方法,有Jacobi 迭代法、Gauss —Seidel 迭代法,逐次超松弛迭代法(SOR 法),这几种迭代方法均属一阶线性定常迭代法,即若系数矩阵A 分解成两个矩阵N 和P 的差,即P N A -=;其中N 为可逆矩阵,线性方程组(1)化为:b x P N =-)(b Px Nx +=b N Px N x 11--+=可得到迭代方法的一般公式:d Gx xk k +=+))1(( (2)其中:P N G 1-=,b N d 1-=,对任取一向量)0(x 作为方程组的初始近似解,按递推公式产生一个向量序列)1(x ,)2(x ,...,)k x(,...,当k 足够大时,此序列就可以作为线性方程组的近似解。
分别用 jacobi 迭代法和 gauss-seidel 迭代法,求解方程组【jacobi 迭代法和 gauss-seidel 迭代法分别应用于方程组的求解】1. 引言在数学领域中,方程组的求解一直是一个重要的课题。
为了解决复杂的线性方程组,人们提出了各种迭代方法,其中 jacobi 迭代法和gauss-seidel 迭代法是两种常见的方法。
本文将探讨这两种迭代方法在求解方程组中的应用。
2. jacobi 迭代法的原理和应用jacobi 迭代法是一种基于逐次逼近的迭代方法。
对于线性方程组AX=B,其中 A 是系数矩阵,X 是未知数向量,B 是已知向量。
我们可以通过以下公式进行逐次逼近:X(k+1) = D^(-1)*(B - (L+U)X(k))其中,D、L、U 分别是 A 的对角线、下三角和上三角矩阵。
jacobi 迭代法的优点在于易于理解和实现,但在收敛速度上较慢,需要进行多次迭代才能得到精确解。
在实际应用中,需要根据实际情况选择合适的迭代次数。
3. gauss-seidel 迭代法的原理和应用与 jacobi 迭代法类似,gauss-seidel 迭代法也是一种基于逐次逼近的迭代方法。
不同之处在于,gauss-seidel 迭代法在计算 X(k+1) 时利用了已经得到的 X(k) 的信息,即:X(k+1)_i = (B_i - Σ(A_ij*X(k+1)_j,j≠i))/A_ii这种方式使得 gauss-seidel 迭代法的收敛速度较快,通常比 jacobi 迭代法更快,尤其是对于对角占优的方程组。
4. 分别用 jacobi 迭代法和 gauss-seidel 迭代法求解方程组为了更具体地说明 jacobi 迭代法和 gauss-seidel 迭代法的应用,我们分别用这两种方法来求解以下方程组:2x1 + x2 = 9x1 + 3x2 = 11我们将该方程组写成矩阵形式 AX=B:|2 1| |x1| |9||1 3| * |x2| = |11|我们根据 jacobi 迭代法和 gauss-seidel 迭代法的原理,依次进行迭代计算,直到满足收敛条件。
浅析Gauss-Seidel 迭代在方程迭代计算中的应用摘要:科学研究与生产实践中许多问题都可归结为方程组的求解,对于方程组的求解,主要有直接法求解和迭代法求解,我们通常用的迭代法有Jacobi,Gauss-Seidel 迭代法。
本文主要针对Gauss-Seidel 迭代法在三类方程组迭代计算中的应用进行研究。
一、Gauss-Seidel 迭代法在求解大型稀疏线性方程组中的应用。
Gauss-Seidel 迭代法充分利用矩阵的稀疏性去解大型稀疏线性代数方程组。
本文通过实际算例验证并分析了它的计算速度和效率。
二、Gauss-Seidel 迭代法在求解H-矩阵线性方程组中的应用。
本文针对系数矩阵 A 为H -矩阵, 为线性方程组 Ax =b 引入了两种形式的预处理矩阵 I +S 和 I +S , 给出了相应的预处理 Gauss-Seidel 方法。
三、异步并行非线性对称Gauss-Seidel 迭代法在求解特殊非线性方程组的应用。
利用非线性方程组的特殊结构,建立了一类并行非线性 Gauss-Siedel 型迭代算法。
关键词:Gauss-Seidel 迭代法,线性方程组,H -矩阵,非线性方程组科学研究与生产实践中许多问题都可归结为线性方程组的求解,高效求解线性方程组成为许多科学与工程计算的核心。
解线性方程组的传统方法是利用高斯消元法或矩阵的三角分解法等直接求解,虽然传统方法具有理论上直接得到真解的优点,但当系数矩阵条件数很大时,存在严重的稳定性问题。
同时,当系数矩阵的非零元结构不规则或带宽较大时,其计算量与存储量也十分地大。
与直接法相比,迭代法只需存储原系数矩阵,对应于预处理的几个辅助矩阵和少量的几个向量,且迭代法中除求解辅助线性方程组外,其余的计算主要是系数矩阵与向量的乘积,从而能充分利用系数矩阵的特性来减少计算量。
而且随着计算机技术的发展,计算机的存储量日益增大,计算速度也迅速提高,线性方程组的迭代求解在科学与工程计算中也起着越来越重要的作用。
求解线性方程组的Jacobi和Gauss-Seidel迭代法的收敛定
理
韩艳丽
【期刊名称】《中国西部科技》
【年(卷),期】2009(008)020
【摘要】本文先描述了迭代法求解线性方程组的基本思想,然后给出三个收敛定理并分别对他们作出解释,最后说明在作题过程中这三个定理如何用和应该注意什么.【总页数】1页(P31)
【作者】韩艳丽
【作者单位】河南理工大学数信学院,河南,焦作,454000
【正文语种】中文
【中图分类】O1
【相关文献】
1.Jacobi与Gauss-Seidel迭代法求解线性方程组收敛性比较与研究 [J], 王育琳;贺迅宇;张尚先
2.Jacobi和Gauss-Seidel迭代法求解线性方程组的分析及应用 [J], 杜衡吉;徐昆良
3.Jacobi迭代法与Gauss-Seidel迭代法的收敛性比较分析 [J], 白红梅
4.弱对角占优矩阵的Jacobi和Gauss-Seidel及SOR迭代法收敛准则 [J], 陈恒新
5.Jacobi和Gauss-Seidel迭代法收敛性的判定 [J], 郭晞娟
因版权原因,仅展示原文概要,查看原文内容请购买。
数值计算方法实验报告(五)班级:地信10801 序号:姓名:一、实验题目:jacobi迭代法和Gauss-Seidel迭代法二、实验学时: 2学时三、实验目的和要求:1.掌握迭代法的基础原理。
2.掌握jacobi迭代法和Gauss-Seidel迭代法的步骤。
3.能用程序语言对jacobi迭代法和Gauss-Seidel迭代法进行编程实现。
四、实验过程代码及结果1、代码:#include<iostream.h>#include<math.h>float x[100],xk[100];float e;int N,M=1000;float a[100][101];void initdata(){cout<<"输入方程阶数:";cin>>N;cout<<"输入误差限e:";cin>>e;cout<<"输入方程系数:"<<endl;for(int i=1;i<=N;i++)for(int j=1;j<=N+1;j++)cin>>a[i][j];cout<<"输入初始解向量x0:"<<endl;for(i=1;i<=N;i++)cin>>xk[i];}void jocobi(){int Nx=0,times=0;while(Nx<N){times++; Nx=0;if(times>=M){cout<<"发散"<<endl; break;}for(int i=1;i<=N;i++){float sum=0;for(int j=1;j<=N;j++)if(i!=j)sum+=xk[j]*a[i][j];x[i]=(a[i][N+1]-sum)/a[i][i];if(fabs(x[i]-xk[i])<e)Nx++;}for(i=1;i<=N;i++)xk[i]=x[i];}cout<<"times="<<times<<endl;for(int i=1;i<=N;i++)cout<<"x["<<i<<"]="<<x[i]<<endl;}void guass_seidel(){int Nx=0,times=0;while(Nx<N){times++;Nx=0;if(times>=M){cout<<"发散"<<endl;break;}for(int i=1;i<=N;i++){float sum1=0;float sum2=0;for( int j=i+1;j<=N;j++){sum1+=xk[j]*a[i][j];}for( j=1;j<=i-1;j++){sum2+=a[i][j]*xk[j];}x[i]=(a[i][N+1]-sum1-sum2)/a[i][i];if(fabs(x[i]-xk[i])<e)Nx++;}for(i=1;i<=N;i++)xk[i]=x[i];}cout<<"times="<<times<<endl;for(int i=1;i<=N;i++)cout<<"x["<<i<<"]="<<x[i]<<endl;}void main(){char ch;initdata();cout<<"请选择解方程的方法:\n";cout<<"A:jocobi B:guass_seidel \n";cin>>ch;if(ch=='A')jocobi();else if(ch=='B')guass_seidel();}2.结果:欢迎您的下载,资料仅供参考!。