第2章 线性方程组的迭代法yjs10n

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,科大研究生学位课程,*,第,2,章 解线性方程组的迭代法,n,元线性方程组,（,2.1,）,或,A,x,=,b,思路,与解,f,(,x,)=0,的不动点迭代相似,将,Ax,=,b,等价改写为,x,=,Mx,+,f,建立迭代,x,(,k,+1),=,Mx,(,k,),+,f,从初值,x,(0),出发，得到序列,x,(,k,),.,研究 内容：,如何建立迭代格式？,收敛速度？,向量序列的收敛条件？,误差估计？,（,2.2,）,1,科大研究生学位课程,2.1,迭代法的一般理论,为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对,R,n,(,n,维向量空间,),中的向量或,R,n,x,n,中矩阵的“,大小,”引入一种度量，,向量和矩阵的范数。,在一维数轴上，实轴上任意一点,x,到原点的距离用,|,x,|,表示。而任意两点,x,1,，,x,2,之间距离用,|,x,1,-,x,2,|,表示。,2,科大研究生学位课程,向量和矩阵的范数,而在二维平面上，平面上任意一点,P,(,x,y,),到原点的距离用 表示。而平面上任意两点,P,1,(,x,1,y,1,),P,2,(,x,2,y,2,),的距离用,表示。推广到,n,维空间，则称为向量范数。,3,科大研究生学位课程,2.1.1,向量和矩阵的范数,向量的范数,定义,2.2,设,是向量空间,R,n,上的实值函数,且满足条件,:,(1),非负性,:,对任何向量,x,R,n,x,0,且,x,=0,当,且,仅当,x,=,0,(2),齐次性,:,对任何向量,x,R,n,和实数,x,=|,|,x,(3),三角不等式,:,对任何向量,x,y,R,n,x,+,y,x,+,y,则称,为空间,R,n,上的范数,x,为,向量,x,的,范数,.,4,科大研究生学位课程,记,x,=(,x,1,x,2,x,n,),T,常用的向量,范数有,:,向量的,1-,范数,:,x,1,=|,x,1,|+|,x,2,|+|,x,n,|,向量的,2-,范数,:,x,2,=,向量的,-,范数,:,x,=,例,设向量,x,=(2,-4,3,1),T,求向量,范数,x,p,p=1,2,.,解,由定义,x,1,=10,x,2,=,x,=4.,虽然不同范数的值可能不同，但它们间存在等价关系,.,定理,(,范数的等价性,),对于,R,n,上,的任何两种范数,和,存在正常数,m,M,使得,m,x,x,M,x,x,R,n,5,科大研究生学位课程,常用的三种向量范数满足如下等价关系,x,x,1,n,x,x,R,n,定义,设向量序列,k,=1,2,向量,如果,则称向量序列,x,(k),收敛于向量,x,*,记作,易见,6,科大研究生学位课程,2.,矩阵的范数,定义,2.3,设,是以,n,阶方阵为变量的实值函数,且满足条件,:,(1),非负性,:,A,0,且,A,=0,当且,仅当,A,=,0,(2),齐次性,:,A,=|,|,A,R,(3),三角不等式,:,A+B,A,+,B,(4),相容性,:,AB,A,B,则称,A,为,矩阵,A,的范数,.,记,A,=(,a,ij,),常用的矩阵,范数有,:,矩阵的,1-,范数,:,A,1,也称矩阵的,列范数,.,矩阵的,2-,范数,:,A,2,也称为,谱范数,.,7,科大研究生学位课程,矩阵的,-,范数,:,A,也称为,行范数,.,矩阵的,F,-,范数,:,A,F,例,设矩阵,求矩阵,A,的范数,A,p,p=1,2,F,.,解,A,1,=4,A,=5,A,F,8,科大研究生学位课程,设,是一种向量范数,则定义,称之为由向量范数派生的,矩阵算子范数,.,矩阵的算子范数满足,Ax,A,x,x,R,n,把满足上式的矩阵范数称为,与向量范数,相容,的矩阵范数,.,对于,p=1,2,矩阵范数,A,p,是,由向量范数,x,p,派生的矩阵算子范数,所以,A,p,是与,x,p,相容的矩阵范数,.,但,A,F,不是一种算子范数,却与,x,2,是,相容的,.,设,是一种算子范数,则,9,科大研究生学位课程,矩阵的范数与矩阵的特征值之间也有密切的联系,.,设,是矩阵,A,的特征值,x,是对应的特征向量,则有,Ax,=,x,利用向量和矩阵范数的相容性,则得,|,|,x,=,x,=,Ax,A,x,于是,|,|,A,设,n,阶矩阵,A,的,n,个特征值为,1,2,n,则称,为矩阵,A,的,谱半径,.,对矩阵的任何一种相容范数都有,(,A,),A,另外,0,一种相容范数,使,A,(,A,)+,10,科大研究生学位课程,任何两种矩阵范数也具有等价性,m,A,A,M,A,A,R,nn,矩阵序列的收敛性也定义为,11,科大研究生学位课程,12,科大研究生学位课程,把,n,元线性方程组,（,2.1,）,或,Ax,=,b,改写成等价的方程组,或,x,=,Mx,+,f,2.1.2,迭代格式的构造,（,2.2,）,13,科大研究生学位课程,由此建立方程组的迭代格式,x,(k+1),=,Mx,(k),+,f,k=0,1,2,(2.5),其中,M,称为,迭代矩阵,。,对,任意取定的初始向量,x,(0),由,(2.5),式可逐次算出迭代向量,x,(k),k=1,2,如果向量序列,x,(k),收敛于,x,*,由,(2.5),式可得,x,*,=,Mx,*,+,f,从而,x,*,是方程组,x,=,Mx,+,f,的解,也就是方程组,Ax,=,b,的解,.,对迭代格式,(2.5),定义误差向量,e,(k,),=,x,(k),-,x,*,则迭代法收敛就是,e,(k),0,.,由于,x,(k+1),=,Mx,(k),+,f,k,=0,1,2,x,*,=,Mx,*,+,f,k,=0,1,2,14,科大研究生学位课程,x,(k+1),=,Mx,(k),+,f,k,=0,1,2,x,*,=,Mx,*,+,f,k,=0,1,2,所以,e,(k+1),=,M,e,(k),k,=0,1,2,递推可得,e,(k),=,M,k,e,(0),k,=0,1,2,可见,当,k,时,e,(k),0,M,k,O,.,对任意初始向量,x,(0),迭代法收敛,(,M,)1.,定理,2.4,证,:(,必要性）,若,(,M,)0,使得,(,M,)+1.,则由定理,2.2,M,k,M,k,(,M,)+),k,0.,若,M,k,0,k,(,M,)=(,M,k,),M,k,0,所以,(,M,)1.,15,科大研究生学位课程,若,M,1,则,对任意,x,(0),迭代法收敛,而且,定理,2.5-6,证,由于,x,(k+1),=,Mx,(k),+,f,x,(k,),=,Mx,(k-1),+,f,x,*,=,M,x,*,+,f,所以,x,(k+1),-,x,(k),=,M,(,x,(k),-,x,(k-1),),x,(k+1),x,*,=,M,(,x,(k),x,*,),于是有,x,(k+1),-,x,(k),M,x,(k),-,x,(k-1),x,(k+1),x,*,M,x,(k),x,*,x,(k+1),-,x,(k),=,(,x,(k+1),x,*,)-(,x,(k),x,*,),x,(k),x,*,-,x,(k+1),x,*,(1-,M,),x,(k),x,*,16,科大研究生学位课程,所以,上述定理只是收敛的充分条件,并不必要,如,则,M,1,=1.2,M,=1.3,M,2,=1.09,M,F,=1.17,但,(,M,)=0.81,所以迭代法是收敛的,.,由,(2.10),式可见,M,越小,收敛越快,且当,x,(k),-,x,(k-1),很小时,x,(k),x,*,就,很小,实际上用,x,(k),-,x,(k-1),作为,迭代终止的条件,.,17,科大研究生学位课程,即,若使,x,(k),x,*,只需,可以事先估计达到某一精度需要迭代多少步,.,线性方程组的迭代法主要有,Jocobi,迭代法、,Gauss-Seidel,迭代法和超松弛,(,Sor,),迭代法,.,18,科大研究生学位课程,2.2,雅克比（,Jacobi,）,迭代法,若系数矩阵非奇异，且,(,i,=1,2,n,),，,将方程组,改成,19,科大研究生学位课程,然后写成迭代格式,（,2.11,）,（,2.11,）,式也可以简单地写为,（,2.11,）,20,科大研究生学位课程,写成,矩阵形式,：,A,=,L,U,D,B,Jacobi,迭代阵,(2.12),21,科大研究生学位课程,算法,2.1,（,Jacobi,迭代法）：,程序见,P19,。,22,科大研究生学位课程,2.2.2 Jacobi,迭代法的收敛条件,迭代格式收敛,(,B,)1,。,若,B,1,迭代法收敛,.,定理：若系数矩阵,A,满足下列条件之一，则,Jacobi,迭代收敛。,A,为行对角占优阵,A,为列对角占优阵,A,满足,对于,Jacobi,迭代，我们有一些保证收敛的充分条件,.,引理,若,A,是严格对角占优矩阵,则,det(,A,),0.,证,A,=,D,-,L,-,U,=,D,(,I,-,D,-1,(,L,+,U,)=,因为,A,是严格对角占优矩阵,所以,det(,D,),0,而且,因此,(,B,),B,1,故,=1,不是,B,的特征值,det(,I,-,B,),0.,所以,det(,A,),0.,D,(,I,-,B,),23,科大研究生学位课程,证明：,由条件知，,A,为列对角占优阵，则,A,T,为行对角占优阵，有,证毕,A,为行对角占优阵,A,为列对角占优阵,24,科大研究生学位课程,为了加快收敛速度，同时为了节省计算机的内存，我们作如下的改进：每算出一个分量的近似值，立即用到下一个分量的计算中去，即用迭代格式：,2,.3,高斯,赛得尔,(Gauss-Seidel),迭代法,逐一写出来即为,25,科大研究生学位课程,只存一组向量即可。,写成,矩阵形式,：,B,Gauss-Seidel,迭代阵,2,.3,高斯,赛得尔,(Gauss-Seidel),迭代法,(2.14),(2.16),26,科大研究生学位课程,程序见,P23,。,算法,2.2,（,Gauss-Seidel,迭代法）：,27,科大研究生学位课程,例,用雅可比迭代法解方程组,解：雅,可,比,迭,代,格式为,28,科大研究生学位课程,k,x,1,(,k,),x,2,(,k,),x,3,(,k,),1,0.72,0.83,0.84,2,0.971,1.07,1.15,11,1.099993,1.199993,1.299991,12,1.099998,1.199998,1.299997,取,计算如下,29,科大研究生学位课程,解：,Gauss-Seidel,迭代格式为,例,用,GaussSeidel,迭代法解上题。,30,科大研究生学位课程,取,x,(0),=,(0,0,0),T,计算如下：,k,x,1,(,k,),x,2,(,k,),x,3,(,k,),1,0.72,0.902,1.1644,8,1.099998,1.199999,1.3,31,科大研究生学位课程,2.3.2,收敛条件,我们看一下,Gauss-Seidel,迭代法收敛的充分条件,定理：若,A,满足下列条件之一，则,Seidel,i,迭代收敛。,A,为行或列对角占优阵,A,对称正定阵（证略书上定理,2.9,）,迭代格式收敛,(,B,)1,。,若,B,1,迭代法收敛,.,det(,I,-,B,),=,det(,I,-(,D,-,L,),-1,U,),证明：,=det(,D,-,L,),-1,)det(,D,-,L,)-,U,)=0,所以有,det(,(,D,-,L,)-,U,)=0,32,科大研究生学位课程,若,|,|1,则矩阵,(,D,-,L,)-,U,是,严格对角占优矩阵,这与,det(,(,D,-,L,)-,U,)=0,矛盾,所以,|,|1,于是,(,B,)1.,注：,二种方法都存在,收敛性问题,。,有例子表明：,Gauss-Seidel,法收