[精彩]125赵连云-雅可比迭代法与高斯—塞德尔迭代法的比拟

[精彩]125赵连云-雅可比迭代法与高斯—塞德尔迭代法的比拟 雅可比迭代法与高斯—塞德尔迭代法的比较 赵连云(03211085) 包头师范学院数学科学学院 摘要:在求解线性代数方程组的许多实际问题中，尤其在偏微分方程的差分方法与有限方法的求解问题之中，用迭代法去解线形方程组有明显的优点.其中最主要的是雅可比(Jacobi)迭代法和高斯-塞得尔(Gauss-Seidel)迭代法，本文就这两种方法及它们的收敛判别条件作了较系统的归纳 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf ，并给出典型例子加以分析.对具体的求解中，选用那一种方法使解题更快速，更有效有着重要意义. 关键词:Jacobi迭代法; Gauss-Seidel迭代法; 收敛; 比较. 一 预备知识 ，，A,aijn，n定义1 设为n阶矩阵. ?如果 ? n a,a,i,1,2,...n,iiij,ji,ji (13) 即A的每一行对角元素的绝对值都严格大于同行其他元素绝对值之和，则称A为严格对角优势矩阵. ? ?如果 n a,a,i,1,2,...n,iiij,ji,ji 且至少有一个不等式严格成立,则称A为弱对角优势矩阵. 2,101,10，，，， ,,,,13112,1,,,, ,,,,013013，，，，例如是严格对角优势矩阵，是弱对角优势矩阵. ，，A,aijn，n定义2 设是n阶矩阵，如果经过行的互换及相应列的互换可化为AA，，1112 ,,0A，，22, 即存在n阶排列矩阵P,使 AA，，1112TPAP,,,0A22，， A,A1122其中为方阵，则称A是可约的,否则称A为不可约的. 二 具体内容 (一) 雅可比迭代法 设线性方程组 Ax,b (1) a,a,...,a1122nn的系数矩阵A可逆且主对角元素均不为零,令 ，，D,diaga,a,...,a1122nn 并将A分解成 ，，A,A,D，D (2) 从而(1)可写成 ，，Dx,D,Ax，b 令 x,Bx，f11 ,1,1B,I,DA,f,Db11其中. (3) B1以为迭代矩阵的迭代法(公式) 1，，，，k，kx,Bx，f11 (4) 称为雅可比(Jacobi)迭代法(公式),用向量的分量来表示,(4)为 n1，1(k)(k)x,b,ax,,,iiijj,1ja,ii,ji, i,1,2,...n,k,0,1,2,..., (5) T，，，，，，，，0000，，x,x,x,...x12n其中为初始向量. 由此看出,雅可比迭代法公式简单,每迭代一次只需计算一次矩阵和向量的 ，，，，kk，1xx乘法.在电算时需要两组存储单元,以存放及. 例1 用雅可比迭代法求解下列方程组 xxx.10,,2,72,123,xxx.,，10,2,83,123 ,xxx.,,，5,42123, 解 将方程组按雅可比方法写成 ,,01，02，072x.x.x.123,,,01，02，083x.x.x.,213 ,x,0.2x，0.2x，0.84312,, TT，，，，，，，，0000，，，，x,x,x,x,0,0,0,123取初始值按迭代公式 1k，kk，，，，，，,,，，x0.1x0.2x0.72123,,1k，kk，，，，，，,，，x0.1x0.2x0.83,213 ,，，，，，，1k，kkx,0.2x，0.2x，0.84312,, 进行迭代，其计算结果如表1所示 表1 0 1 2 3 4 5 6 7 k ，，k0 0.72 0.971.051.0853 1.0951 1.0983 … x1 1 7 ，，k0 0.83 1.071.151.1853 1.1951 1.1983 … x2 0 71 ，，k0 0.84 1.151.241.2828 1.2941 1.2980 … x3 0 82 (二) 高斯—塞德尔迭代法 ，，kx由雅可比迭代公式可知,在迭代的每一步计算过程中是用的全部分量来 ，，k，1，，k，1xxi计算的所有分量,显然在计算第i个分量时,已经计算出的最新分量，，，，k，1k，1x,...,x1i,1没有被利用，从直观上看,最新计算出的分量可能比旧的分量要 ，，k，1，，k，1xjk，1x好些.因此，对这些最新计算出来的第次近似的分量加以利用,就得到所谓解方程组的高斯—塞德(Gauss-Seidel)迭代法. 把矩阵A分解成 A,D,L,U (6) ，，D,diaga,a,...,a,L,,UA1122nn其中,分别为的主对角元除外的下三角和上三角部分,于是,方程组(1)便可以写成 ，，D,Lx,Ux，b 即 x,Bx，f22 其中 ,1,1，，，，B,D,LU,f,D,Lb22 (7) B2以为迭代矩阵构成的迭代法(公式) 1，，，，k，kx,Bx，f22 (8) 称为高斯—塞德尔迭代法(公式),用 量表示的形式为 i,1n1(k，1)(k，1)(k),,x,b,ax,ax,,iiijjijjj,，11j,ia,ii,i,1,2,？n,k,0,1,2,..., (9) 由此看出,高斯—塞德尔迭代法的一个明显的优点是,在电算时,只需一组存 ，，，，，，，，k，1kk，1kxxxxiiii储单元(计算出后不再使用,所以用冲掉,以便存放近似解. 例2 用高斯——塞德尔迭代法求解例1. TT，，，，，，，，0000，，，，x,x,x,x,0,0,0,123解 取初始值，按迭代公式 k，1kk，，，，，，,x0.1x0.2x0.72,，，123,k，1k，1k，，，，，，x0.1x0.2x0.83,，，,213 ，，，，，，,k，1k，1k，1x0.2x0.2x0.84,，，312, 进行迭代，其计算结果如下表2 表2 0 1 2 3 4 5 6 7 k ，，k0 0.72 1.04308 1.0931.09913 1.09989 1.09999 1.1 x1 13 ，，k0 0.901.16719 1.1951.19947 1.19993 1.19999 1.2 x2 2 72 ，，k0 1.161.28205 1.2971.29972 1.29996 1.3 1.3 x3 44 77 从此例看出,高斯—塞德尔迭代法比雅可比迭代法收敛快(达到同样的精度所需迭代次数少),但这个结论,在一定条件下才是对的,甚至有这样的方程组,雅可比方法收敛，而高斯—塞德尔迭代法却是发散的. (三)迭代收敛的充分条件 定理1 在下列任一条件下,雅可比迭代法(5)收敛. anijB,max,1,1,i1j,aiij,i? ; anij,,1Bmax,11j1i,aiij,i? ; anij,1TI,DA,max,1,,ji,1ajji,j? BB1,2定理2 设分别为雅可比迭代矩阵与高斯—塞德尔迭代矩阵,则 B,B21,, (10) 从而，当 anij,,1Bmax,1,i1j,aiij,i 时，高斯—塞德尔迭代法(8)收敛. BB1,2证明 由的定义,它们可表示成 ,1，，B,DL，U1 ,1,1,1,1，，，，B,D,LU,I,DLDU2 T，，e,1,1,...,1en用表示维向量,则有不等式 Be,Be11, ,1,1B,DL，DU1 这里,记号,?,表示其中矩阵的元素都取绝对值,而不等式是对相应元素来考虑 的,于是 ,,11DUe,B,DLe，，1 ,1，，，，,I,DL,1,BIe1, 容易验证 nn,1,1，，DL,DL,0 ,1,1I,DLI,DL所以,及可逆，且 n,1,1,1,1,1I,DL,I，DL，...，DL，，，， n,1,1,1,1,1，，,I，DL，...DL,I,DL ,1,1，，I,DL,I 从而有 ,1,,11Be,I,DL,DUe，，2 ,1,1,1,,，，，，，,I,DLI,DL,1,BIe1, ,1,1，，,，，,,I,1,BI,I,DLe1, ,Be1, 因此必有 B,B21,, B,1B,112,,因为已知所以.即高斯—塞德尔迭代法收敛. A若矩阵为对称，我们有 A定理3 若矩阵正定,则高斯—塞德尔迭代法收敛. 证明 把实正定对称矩阵A分解为 TA,D,L,L T，，U,LD,则为正定的,迭代矩阵 ,1T，，B,D,LL2 B,x2设是的任一特征值,为相应的特征向量,则 ,1T，，，，D,LLx,,x TD,LA,D,L,L以左乘上式两端,并由有 T，，1,,Lx,,Ax x用向量的共轭转置左乘上式两端,得 ,,TTT，，1,,xLx,,xAx (11) 求上式左右两端的共轭转置,得 ,,,,TT,,1,,xLx,,xAx,,,, , 1,1,,,以和分别乘以上二式然后相加,得 ,,,,,TTT,,,,，，，，1,,1,,xL，Lx,,，,,2,,xAx,,,,,,,, TA,D,L,L由,得 ,,,,,TT,,,,，，，，1,,1,,xD,Ax,,，,,2,,xAx,,,,,,,, 即 ,,22TT，，1,,xLx,1,,,xAx (12) ,,1因为A和D都是正定的,且x不是零向量,所以由(11)式得,而由(12) 21,,,0,1,，，,B,12式得, 即,从而,因而高斯—塞德尔迭代法收敛. 定理4如果A为严格对角优势矩阵或为不可约弱对角优势矩阵,则对任意，，0x,雅可比迭代法(4)与高斯—塞德尔迭代法(8)均为收敛的. 证明 下面我们以A为不可约弱对角优势矩阵为例，证明雅可比迭代法收 敛. ，，,B,1B11要证明雅可比迭代法收敛，只要证,是迭代矩阵. ,1,，，Bdet,I,B,0,11用反证法,设矩阵有某个特征值,使得,则,由 ,1D于A不可约,且具有弱对角优势，所以存在，且 ,1,1，，，，,I,B,,I,I,DA,D,D，A,D1 从而 ，，det,D，A,D,0 ，，,D，A,D另一方面，矩阵与矩阵A的非零元素的位置是完全相同的，所以 ,,1，，,D，A,D也是不可约的,又由于,且A弱对角优势，所以 n ,a,a,a,i,1,2,...n,iiiiij,ji,ji ，，,D，A,D并且至少有一个i使不等号严格成立.因此,矩阵弱对角优势，故 ，，,D，A,D为不可约弱对角优势矩阵.从而 ，，det,D，A,D,0 B1矛盾，故的特征值不能大于等于1，定理得证. 33，，(四)典型例题 1,,44例 设Ax=b 其系数矩阵 ,,33 ,,1 44,,A = 33,,1 ,,44，， 证明:它的Jacobi迭代公式发散，而 Gauss-Seidel迭代公式收敛. 证:矩阵A的Jacobi迭代公式 33，，0,,,,44,,33,1,,B = -(L+U) ,0,D44,,33,,,,0,,44，， 33，，,, ,, 只能用 (,). ,？？BB,1,,,44 ,,3323,,,33,,,,344,,,,,I,B,(),,,,,，,,,,,,,,3344,,,,,, ,,,44，， 27273,,，,0即 , 1632333,,,, ？,,,123442 3,, ()B,,,？max,i21,i,3 所以 其Jacobi迭代公式发散. ,1A的高斯-塞得尔迭代矩阵G = -U ，，D，L 3333，，，，，，00,,,,,,1004444,,,,,,3393,110000,,,,,,，,,,,U ，，D，L441616,,,,,,33000945,,,,,,10,,,,,,,,,,1646464，，，，，， 33，，0,,,,44,,,193,,G=-U0 ,,？，，D，L1616,,945,,0,,6464，， >1 >1 ？GG1, 只能用 ，，,G？ 33，，,,,44,,93,,,,I,G,0,,0 f(,),1616,,945,,,0,,,,6464，， ,0 ,0.633，0.146i ,0.633,0.146i ？,,,123 ,(G),1？ 所以 高斯-塞得尔迭代法收敛. 三 总结 以上给出了雅可比迭代法和高斯,塞得尔迭代法及判断它们收敛的各种方法，通过例题可以看出雅可比迭代法的收敛性和高斯,塞得尔迭代法的收敛性之间没有必然的联系.这些知识让我们对迭代法有了更广泛更深入的了解.特别是在解线性方程组时，怎样选择合适的方法去解题有实际意义. 四 参考文献 1 《数植分析原理》,M, 吴勃英编 科学出版社 2003年8月 2 《数值计算方法和算法》,M, 张韵华等编 科学出版社 2000年1月 3 《计算方法》,M, 姚敬之等编 河海大学出版社 2002年 4 《计算机数值方法》,M, 施吉林等编 高等教育出版社 1999年