,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,线性方程组迭代解法,Iterative Techniques,for Solving Linear Systems,线性方程组迭代解法,1,(2.1),迭代法：不是用有限步运算求精确解，通过迭代产生近似解逼近精确解。,Jacobi,迭代,Gauss-Seidel,迭代,思路：构造一个向量序列,X,(n),，使其收敛在某个极限向量,X*,，而,X*,就是,(2.1),式的准确解。,如何构造迭代序列,X,(n),?,X,(n),在什么条件下,收敛?,收敛速率如何?,误差估计.,(2.1)迭代法：不是用有限步运算求精确解，通过迭代产生近似,2,3.1,向量和矩阵的范数,Norms of Vectors and Matrices,数值分析中,经常要用向量和矩阵,为了应用的需要(误差分析),引入衡量向量和矩阵大小的度量,范数,.,对于实数,x,R,我们定义了绝对值,满足,|x|0,非负性,|,x|=|,|x|,齐次性,|x+y|x|+|y|,三角不等式,类似地,定义向量范数,3.1 向量和矩阵的范数Norms of Vectors,3,Def3.1,在实,n,维线性空间,R,n,中定义一个映射,它使任意,X,R,n,有一个非负实数与之对应,记为,|,X,|,且该映射满足:,正定性,任意,XR,n,|X|,0,if and only if X=0,时,|X|,=0,齐次性,任意,XR,n,R,有,|,X,|,=,|,|,|,X,|,三角不等式,任意,X,Y,R,n,有,|X+Y|,|X|,+,|Y|,则称该映射在,R,n,中定义了一个向量范数.,注:,R,n,中的范数不唯一.,常用的范数有三种:设,X=(x,1,x,2,x,n,),T,R,n,.,则,Def3.1 在实n维线性空间Rn中定义一个映射,它使任意,4,注:,(1),用范数的定义可验证上述皆为向量范数,(2),p=1,2,|X|,p,即为,|X|,1,|X|,2,.,(3),任意,xR,n,:,注:(1)用范数的定义可验证上述皆为向量范数,5,定理,3.2,设|,|,和|,|,是,R,n,上任意两种范数，则存在正常数,C1,和,C2，,使得对一切,X,R,n,有,C1,|,X,|,|,X,|,C2,|,X,|,注:,R,n,中范数的等价性表明,虽范数值不同,但考虑到向量序列收敛性时,却有明显的一致性.,定理3.2 设|和|是Rn上任意两种范,6,Def3.3,R,n,中,X(x,1,x,2,x,n,),T,和,Y(y,1,y,2,y,n,),T,则有,有解,(x,1,x,2,x,3,),T,(1,1,1),T,，用Gauss消去法得到近似解,Def3.3 Rn中X(x1,x2,xn)T和Y,7,Def3.4,R,n,中的向量序列,X,(k),即,X,0,X,1,X,K,其中,X,K,(x,1,(k),x,2,(k),x,n,(k),),T,.若对任意,i（i=1,2,n）,都有,注：向量序列收敛实际上是按分量收敛（数列收敛）,利用向量范数，也可以说明向量序列收敛的概念。,定理,3.5,向量序列,X,(k),依分量收敛于,X*,的充要条件是,则向量,X*(x,1,*,x,2,*,x,n,*,),T,称为,X,(k),的极限，记做,Def3.4 Rn中的向量序列X(k),即X0,X1,8,矩阵的范数,类似于向量范数，给出矩阵范数的定义。,Def3.6,在线性空间,R,n,n,中定义一个映射，使任意,A,R,n,n,对应一个非负实数，记做,|,A,|,.如果该映射满足：,1.,正定性,：,（4.是矩阵乘法的需要，而1.2.3.为向量范数的推广。）,2.,齐次性,：,3.,三角不等性,：,4.,相容性,：,在R,n,n,中可定义多种范数。,例1,A=(a,ij,),n,n,R,n,n,称为,frobenius,范数,矩阵的范数 类似于向量范数，给出矩阵范数的定义。De,9,3.2,常用的迭代格式,简单迭代法（,Jacobi,迭代）,(3.1),设有方程组,用矩阵表示,(3.1),其中,A,是,系数矩阵,，非奇异，,X,是解向量，,B,是,右端项,。,3.2 常用的迭代格式 简单迭代法（Jacobi 迭代）(3,10,(3.2),(3.3),(3.2)(3.3),11,若令,则有,B=D,-1,(D-A)=I-D,-1,A,G=D,-1,B,方程,(3.3),可记为,X=BX+G,若令则有,12,方程,(3.3),可记为,X=BX+G,选取初始向量,X,0,(x,1,0,x,2,0,x,n,0,),T,，代入方程,(3.3),右端，可得到一个新向量，记为,X,1,(x,1,1,x,2,1,x,n,1,),T,，一直进行下去，迭代格式,X,(n+1),=BX,(n),+G n=0,1,2,以上过程产生向量序列,X,(k),若收敛于,X*,，则有,X*=BX*+G,(I-B)X*=G=D,-1,B,AX*=B,即,X*,是方程,(3.1),的解,(3.4),方程(3.3)可记为以上过程产生向量序列X(k),若收,13,计算方法3_线性方程组迭代解法课件,14,k,0,1,2,3,10,x,1,k,0.0000,0.6000,1.0473,0.9326,1.0001,x,2,k,0.0000,2.2727,1.7159,2.053,1.9998,x,3,k,0.0000,-1.1000,-0.8052,-1.0493,-0.9998,x,4,k,0.0000,1.8750,0.8852,1.1309,0.9998,唯一解,X(1,2,-1,1),T,k012310 x1k0.00000.60001.04730.,15,Gauss-seidel,迭代法,简单迭代法用,X,(k),计算,X,(k+1),时,需要同时保留,X,(k),和,X,(k+1),(3.5),Gauss-seidel迭代法 简单迭代法用X(k)计算X(,16,若令,则,(3.5),式可写成,X,(k+1),=LX,(k+1),+UX,(k),+G k=0,1,2,也可记为,X,(k+1),=(I-L),-1,UX,(k),+(I-L),-1,G,称,(I-L),-1,U,为,Seidel,迭代法的迭代矩阵,(3.6),(3.7),若令则(3.5)式可写成(3.6)(3.7),17,计算方法3_线性方程组迭代解法课件,18,例3.4 用Seidel迭代法求解方程组,解,：,取初始向量,要求,时迭代终止。,Seidel迭代格式为,例3.4 用Seidel迭代法求解方程组解：取初始向量,19,计算结果可列表如下,注意：未必Seidel方法一定比Jacobi方法好。,计算结果可列表如下 注意：未必Seidel方法一定比Jac,20,松弛法,松弛法可认为是,Seidel,法的加速,Seidel,法,X,(k+1),=LX,(k+1),+UX,(k),+G k=0,1,2,令,X=X,(k+1),X,(k),=LX,(k+1),+UX,(k),+G X,(k),X,(k+1),=,X,(k),X,松弛法思想,X,(k+1),=,X,(k),X,松弛法 松弛法可认为是Seidel法的加速Seidel法,21,松弛法,X,(k+1),=(1-)X,(k),(LX,(k+1),+UX,(k),+G),k=0,1,2,其中，,称为松弛因子，当,1,时叫超松弛，当,1,时叫低松弛,也可记为,X,(k+1),=(I-L),-1,(1-)I+U)X,(k),+(I-L),-1,G,称,(I-L),-1,(1-)I+U),为松弛法的迭代矩阵,(3.8),(3.9),(3.10),松弛法也可记为(3.8)(3.9)(3.10),22,计算方法3_线性方程组迭代解法课件,23,唯一解,X(3,4,-5),T,唯一解X(3,4,-5)T,24,k,0,1,2,3,7,x,1,k,1,5.250000,3.1406250,3.0878906,3.0134110,x,2,k,1,3.812500,3.8828125,3.9267578,3.9888241,x,3,k,1,-5.046875,-5.0292969,-5.0183105,-5.0027940,Seidel,法,k,0,1,2,3,7,x,1,k,1,6.312500,2.6223145,3.1333027,3.0000498,x,2,k,1,3.5195313,3.9585266,4.0102646,4.0002586,x,3,k,1,-6.6501465,-4.6004238,-5.0966863,-5.0003486,SOR,法,=1.25,k01237x1k15.2500003.14062503.0,25,3.3,迭代法的收敛性和误差估计,定理,3.10,对任何初始向量X,(0),和常数项f,由迭代格式,X,(k+1),=MX,(k),+f k=0,1,2,产生的解向量序列X,(k),收敛且与初值无关的充要条件是,(M)1,(M)是矩阵M的谱半径,3.3 迭代法的收敛性和误差估计 定理3.10 对任何初始向,26,计算方法3_线性方程组迭代解法课件,27,k,0,1,2,3,x,1,k,0,11,-69,-499,x,2,k,0,-14,81,-374,x,3,k,0,-3,66,-429,k0123x1k011-69-499x2k0-1481-37,28,3.4,判别收敛的几个常用条件,Jacobi,方法的收敛性,3.4 判别收敛的几个常用条件Jacobi方法的收敛性,29,迭代法,(3.5),的收敛性,迭代法(3.5)的收敛性,30,SOR方法的收敛性,(1)SOR方法对任意 都收敛的必要条件是：,(2)若系数矩阵A对称正定，则 时SOR方法,求解 对任意 收敛；,(3)若系数矩阵A按行（或按列）严格对角占优，,则 时SOR方法对任意 收敛。,最佳松弛因子 选取问题。,SOR方法的收敛性(1)SOR方法对任意 都收敛的必要,31,3.5,收敛速率,3.5 收敛速率,32,