科学计算与数学建模第6章 回归问题-线性方程组求解的迭代法-6.3 迭代法的构造与基本迭代方法-2017-02.pptx

1、6.3 迭代法的构造与基本迭代法,6.3.1线性方程组一般迭代公式的构造,为非奇异矩阵，。,nn,设方程组 Axb，其中 A aij ,T,12n,b (b ,b ,b ),将 A分裂为 AMN，则方程 Ax b 等价于 Mx Nx b 若 M 是非奇异阵，则得 x M1Nx M1b ，从而得迭代公式 x(k1) M 1Nx( k ) M 1b ,(k 0,1,) 记 M1N B 、M1b f，于是得到一般迭代公式,xk 1Bxk f k 0,1, 2,6.3.2Jacobi迭代法,对方程组 Ax b，设 det(A) 0,aii 0(i 1,2,n)，将A改写成：,11,21,22,31,3

2、2,0,2n,n1,n2,a,n,n1,0,a, ,a0,A,aa0,a, , ,n , ,0a12a13a1n 0aa,23 , DLU,an1,n ,aaa0,若取 M =D，则 NMALU ，从而 Ax b 化为,Dx (LU)x b,x D1(L U)x D1b,J,x(k 1)Bx(k ),f,记,、,，于是,，从而得迭代公式,1,f Db,J,1,B D (LU),J,x B x f,其中,称为Jacobi迭代矩阵。,J,这就是Jacobi迭代公式，这种迭代方法称为Jacobi迭代法， 1,B D (LU),0,00 ,0,T,x1,x2,xn,取初值 x,则Jacobi迭代的分量

3、形式为,，,1,T,k ,k ,k k ,，记 x,x,x2,xn,n,k,k,i,i,ijj,i,ijj,ijj,axk ,xk 1,j i +1,j 1 j i,1 b,1 b,aii , ,aii ,ax,i1 j 1,n ax, i 1, 2, n ; k 0,1, 2,亦即为,1,1,122,133,2,2,211,213,1nn,2nn,n,n,n11,n 22,x( k ),x( k ),x( k ) ),a11,x,x( k ),x( k ),x( k ) ),a22,x( k ),x( k ),x( k ) ),ann,( k 1),nn1n1,x( k 1),1(b(a,a

4、, ,1(b -(a,a, ,x( k 1),1(b(a,a,a,a,a,a11 x1 a12 x2 ,a21 x1 a22 x2 ,an1 x1 an 2 x2,a1n xnb1 a2n xnb2 ,ann xnbn,11,122,11,1,1331nn,221 12132nn,nn,a,x1(b (a,x,1(b -(a,2 ,xaxax ),xaxax ),a22 ,xn a(bn (an1 x1 an2 x2 ann1 xn1 ),Jacobi迭代分量形式,例6.3.1,用Jacobi迭代法求下面线性方程组，,其精确解是 x* (1, 2, 1,1)T 。,2,6,10 x1 x2 2

5、x3,x1 11x2 x3 x4 25,2x1 x2 10 x3 x4 11 ,3xx3 8x4 15,解将 ,12,3,2,134,4,23,10,11 1 10,x1 (6 x2 x ),x,1 (25 x x3x ),转化为等价方程组 , x 3,(11 2 x1 x2 x4 ), ,1 (15 3xx ),x 8,1,2,134,3,124,4,23,1 10,11,10,8,x,(k1),(6 x (k) 2x (k) ) 23, ,x(k1),1 (25 x(k) x(k) 3x(k) ), 得Jacobi迭代公式,x(k1),1 (112x(k) x(k) x(k) ),x(k1

6、),1 (15 3x(k) x(k) ),取初始向量,x(0) (0,0,0,0)T,经10次迭代得近似解为 x(10) (1.0001,1.9998,0.9998,0.9998)T,误差为：,x* x(10),0.0002,6.3.3Gauss-Seidel迭代法,若取 M =D-L，则 N MAU，从而 Ax b化为 (D L)x Ux bx (D L)1Ux (D L)1b,G,x(k 1),Bx(k ),f,记,、,，从而得迭代公式,f (D L)b,G,11,B(DL)U,G,，于是 x Bx f,迭代法，其中,称为Gauss-Seidel迭代矩阵。,G,这就是Gauss-Seide

7、l迭代公式，这种迭代方法称为Gauss-Seidel 1,B(DL)U,0,00 ,0,T,x1,x2,xn,取初值 x,则Jacobi迭代的分量形式为,，,1,T,k ,k k ,k ,，记 x,x,x2,xn,亦即为,i,b,n,k,j i1,k1,xi,1 ,aii ,aij x j ，（i 1,2,n;k 0,1,2,）,k1,i1 ijj j1,ax,Gauss-Seidel迭代分量形式,1,11221331nn,22112132nn,n,nn11n22,a11,x(k ) ),a22,ann,x(k1),x(k1),x(k1) ),nn1n1, ,2 ,x(k1),1(b(ax(k

8、1) a,1(b(ax(k ) ax(k ) ax(k ) ),1(b -(ax(k1) ax(k ) a,x(k1) a,将Gauss-Seidel迭代法， 简记为：G-S迭代法。,当计算出,就冲掉旧的分量,。,G-S迭代法与Jacobi迭代法一样每迭代一次只需计算 一次矩阵与向量的乘法，但G-S迭代法比Jacobi迭代法有一个 明显的优点，那就是仅需一组工作单元来保存向量 x(k )（或,向量 x(k1）),j,x,(k1),(k ) j,x,以看作是Jacobi迭代法的一个修正。,由G-S迭代公式可看出在x(k) x(k1) 的一步迭代中，计算分量x(k 1) 时,i 1) 。因此，G-

9、S迭代法可,利用了已计算出来的新分量 xj,(k1),( j 1, 2,i ,例6.3.2,用G-S迭代法求例6.3.1相同的线性方程组。,2,6,10 x1 x2 2x3,x1 11x2 x3 x4 25,2x1 x2 10 x3 x4 11 ,3xx3 8x4 15,解将 ,12,3,2,134,3,124,10,11,10,1,x1 (6 x2 x ),x,1 (25 x x3x ),转化为等价方程组 ,x,1 (11 2 x xx ),x4,(15 3x2 x3 ) 8,1,34,21,3124,3,42,1 10,11,10,8,x,(k1),(6 x (k) 2x (k) ) 23

10、,x(k1) 1 (25x(k1) x(k) 3x(k) ), 得G-S迭代公式,x(k1) 1 (112x(k1) x(k2) x(k) ),x(k1) 1 (153x(k1) x(k2) ),取初始向量 x(0) (0,0,0,0)T, 经5次迭代得近似解为,误差为： x* x(5),0.0001,x51.0001,2.0000,1.0000,1.0000T,从此例可见， G-S迭代法比Jacobi迭代法收敛快， 但这个结论对Ax=b的矩阵满足某些条件才是对的，例如,123,2,3,x1 2x2 2x3 1,线性方程组 xxx1 ,1,用Jacobi迭代法收敛 而G-S迭代法却发散。,事实

11、上，,G,1,1,202,102 ,2 10002 1,B DLU1 1,001 1 0,0001 0 0,23 0,1 210,00,00,2 ,210,(BG ) 2 1,1,J,1,2x2xx1 0,1 ,22 022 0 0,B DLU ,1,1 1,1,0 ,0 ,122,22,特征方程: 3 0,J,(B ) 0 1,2 特征方程:(2)2 0,6.3.4Jacobi迭代与G-S迭代法的收敛性,根据线性方程组迭代法收敛的基本定理，Jacobi迭代与 G-S迭代法的收敛性定理。 定理6.3.1 解方程组Ax=b 的Jacobi迭代与G-S迭代法收敛的 充分必要条 件分别是 (BJ )

12、 1与 BG( ) 1，BJ 与 BG 是Jacobi迭代 矩阵与G-S矩阵。,定义6.3.1 （对角占优矩阵）设,即 A 的每一行对角元素绝对值严格大,于同行其他元素绝对值之和，则称 A 为严格对角占优矩阵。,A (aij )nn,n,j 1 j i,0(i 1 n，),若 aiiaij,n,0(i 1 n) 且至少有一个不等式严格成立，,若 aiiaij,j 1 j i 则称 A 为弱对角占优矩阵。 定义6.3.2（可约与不可约矩阵）设A (aij )nn 当 n 2 时，如果存在 n 阶排列矩阵 P 使,PT,A1 1A1 2 AP ,0,A22 ,11,成立。其中 A,为 r 阶子矩阵

13、， A22 为 n-r 阶,子矩阵(1r n)，则称矩阵 A 为可约的。若不存在排列矩阵 P 使上式成立，则称 A 为不可约矩阵。 当A 为可约矩阵，则 Ax=b 可经过若干行列重排化为两个 低阶方程组求解。,定理6.3.2（对角占优定理）若 A (aij )nn 为严格对角占 优矩阵或为不可约弱对角占优矩阵，则 A 是非奇异阵。,其中为 r 维向量。于是，方程 Ax=b 化为：,y ,d ,事实上，由 Ax=b 化为：PT AP(PT x) PTb，设 y PT x ,1T , P b ,1 ,y2 d2 ,y1 , d1,A11 y1 A12 y2 d1 A22 y2 d2 定理6.3.3

14、 若 A Rnn 为严格对角占优矩阵或为不可约对角占优 矩阵，则对任意的初始向量 x(0) 方程组 Ax=b 的Jacobi迭代法和 G-S迭代法均收敛。且G-S迭代法比Jacobi迭代法收敛速度快。,线性方程组迭代法的收敛与否与方程组中方程的排列 顺序有关，如线性方程组,123,1.25x1-3.69x2 12.37x3 0.58,-10.01x1 9.05x2 0.12x3 1.43 ,1.22x -4.33x2.67x3.22,无法直接判断Jacobi迭代法和G-S迭代法的收敛性，但如果将,方程组中方程的次序调换为 -10.01x1 9.05x2 0.12x3 1.43 1.22x1-4.33x2 2.67x3 3.22,1.25x1-3.69x2 12.37x3 0.58,则方程组的系数矩阵 A 是严格对角占优矩阵，因此用Jacobi迭 代法和G-S迭代法求解该方程组均收敛。,？,如何对G-S迭代法进行改进使其收敛速度更快？,6.3 迭代法的构造与