ch4-线性代数方程组的迭代解法省名师优质课赛课获奖课件市赛课一等奖课件.ppt

,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢您,Tel：,86613747,E-mail：,lss,讲课:68,学分：4,第1页,在第二章中我们知道，凡是迭代法都有,一个收敛问题，有时某种方法对一类方程组迭代收敛，而对另一类方程组进行迭代时就会发散。一个收敛迭代法不但含有程序设计简单，适于自动计算，而且较直接法更少计算量就可取得满意解。所以，迭代法亦是求解线性方程组，尤其是求解含有大型稀疏矩阵线性方程组主要方法之一。,第四章 解线性方程组迭代法,第2页,4.2 迭代法基本思想,迭代法基本思想是将线性方程组转化为便于迭代等价方程组，对任选一组初始值,，按某种计算规则，不停地,对所得到值进行修正，最终取得满足精度要求方程组近似解,。,第3页,设 非奇异，则线性方程组,有惟一解 ，经过变换结构出一个等价同解方程组,将上式改写成迭代式,选定初始向量 ,重复不停地使用迭代式逐步迫近方程组准确解,直到满足精度要求为止。这种方法称为迭代法,第4页,假如,存在极限,则称迭代法是收敛，不然就是发散。,收敛时，在迭代公式,中当 时，,则,故 是方程组 解。,对于给定方程组能够结构各种迭代公式。,并非全部收敛,第5页,例4.1 用迭代法求解线性方程组,解 结构方程组等价方程组,据此建立迭代公式,取,计算得,迭代解离准确解 越来越远迭代不收敛,第6页,4.3 雅可比（,Jacobi）,迭代法,4.3.1雅可比迭代法算法结构,例4.2 用雅可比迭代法求解方程组,解：从方程组三个方程中分离出 和,建立迭代公式,第7页,取初始向量,进行迭代,能够逐步得出一个近似解序列：,（,k=1,2,）,直到求得近似解能到达预先要求精度，,则迭代过程终止，以最终得到近似解作为线,性方程组解。,当迭代到第10次有,计算结果表明，此迭代过程收敛于方程组精,确解,x,*,=(3,2,1),T,。,第8页,考查普通方程组，将,n,元线性方程组,写成,若 ,分离出变量,据此建立迭代公式,上式称为解方程组,Jacobi,迭代公式。,第9页,4.3.,2,雅可比迭代法矩阵表示,设方程组 系数矩阵,A,非奇异，且主对,角元素 ，则可将,A,分裂成,记作,A=L+D+U,第10页,则 等价于,即,因为,，,则,这么便得到一个迭代公式,令,则有,（,k=0,1,2）,称为雅可比迭代公式,B,称为雅可比迭代矩阵,第11页,其中,在例4.2中,由迭代公式写出雅可比迭代矩阵为,第12页,雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际计算中，要用雅可比迭代法公式分量形式。即,(,k=0,1,2,),第13页,4.3.3,雅可比迭代法算法实现,第14页,4.4 高斯-塞德尔（,Gauss-Seidel）,迭代法,4.4.1 高斯-塞德尔迭代法基本思想,在,Jacobi,迭代法中，每次迭代只用到前一次迭代值，若每次迭代充分利用当前最新迭代值，即在求 时用新分量,代替旧分量,就得到高斯-赛德尔迭代法。其迭代法格式为：,(,i,=1,2,n,k,=0,1,2,),第15页,例,4.3,用,Gauss,Seidel,迭代格式解方程组,准确要求为,=0.005,解,Gauss,Seidel,迭代格式为,取初始迭代向量 ,迭代结果为：,x,*,第16页,4.4.2,GaussSeidel,迭代法矩阵表示,将,A,分裂成,A=L+D+U,，,则 等价于,(,L+D+U),x,=b,于是,则高斯塞德尔迭代过程,因为 ,所以,则高斯-塞德尔迭代形式为：,故,令,第17页,4.4.3 高斯塞德尔迭代算法实现,高斯-塞德尔迭代算法计算步骤与流程图与雅可比迭代法大致相同，只是一旦求出变元,某个新值 后,就改用新值 替换老值,进行这一步剩下计算。,高斯-塞德尔迭代算法,程序实现,(见附录,A A-7,用高斯塞德尔迭代法求解线,性方程组,）,第18页,4,.5,超松弛迭代法（,SOR,方法）,使用迭代法困难在于难以预计其计算,量。有时迭代过程即使收敛，但因为收敛速,度迟缓，使计算量变得很大而失去使用价值,。所以，迭代过程加速含有主要意义。逐,次超松弛迭代（,Successive Over relaxatic Method，,简称,SOR,方法）法，能够看作是带参数高斯塞德尔迭代法，实质上是高斯-塞德尔迭代一个加速方法。,第19页,4.5.1超松弛迭代法基本思想,超松弛迭代法目标是为了提升迭代法收敛速度，在高斯塞德尔迭代公式基础上作一些修改。这种方法是将前一步结果 与高斯-塞德尔迭代方法迭代值 适当加权平均，期望取得更加好近似值 。是解大型稀疏矩阵方程组有效方法之一，有着广泛应用。,其详细计算公式以下：,用高斯塞德尔迭代法定义辅助量。,第20页,把 取为 与 加权平均，即,合并表示为：,式中系数,称为,松弛因子,，当,=1,时，便为高斯,-,塞德尔迭代法。为了确保迭代过程收敛，要求,0,2,。,当,0,1,时，低松弛法；当,1,2,时称为超松弛法。但通常统称为超松弛法,(,SOR),。,第21页,4.5.2 超松弛迭代法矩阵表示,设线性方程组 系数矩阵,A,非奇异,且主对角元素 ,则将,A,分裂成,A=L+D+U,则超松弛迭代公式用矩阵表示为,或,故,显然对任何一个,值,(,D+L),非奇异,(因为假设,)于是超松弛迭代公式为,令,则超松弛迭代,公式可写成,第22页,例,4.4,用,SOR,法求解线性方程组,取,=1.46，,要求,解：,SOR,迭代公式,k=0,1,2,，,初值,该方程组准确解,只需迭代20次便可到达精度要求,假如取,=1(,即高斯塞德尔迭代法)和同一初,值 ,要到达一样精度,需要迭代110次,第23页,4.6 迭代法收敛性,我们知道,对于给定方程组能够结构成简单迭代公式、雅可比迭代公式、高斯-塞德尔迭代公式和超松弛迭代公式，但并非一定收敛。现在分析它们收敛性。,对于方程组,经过等价变换结构出等价方程组,在什么条件下迭代序列 收敛？先引入,以下定理,第24页,定理,4.1,对给定方阵,G,若 ,则,为非奇异矩阵,且,证:用反证法,若 为奇异矩阵,则存在非零向,量,x,使 ,即有,由相容性条件得,因为 ,两端消去 ,有 ,与已知条件,矛盾,假设不成立,命题得证。,又因为,有,即,将,G,分别取成,G,和,-,G,，,再取范数,又已知 ，有,第25页,定理4.2 迭代公式 收敛,充分必要条件是迭代矩阵,G,谱半径,证:必要性 设迭代公式收敛,当,k,时,则在迭代公式两端同时取极限得,记 ,则 收敛于0(零向量),且有,于是,因为 能够是任意向量,故 收敛于0当且仅,当 收敛于零矩阵，即当 时,于是,所以必有,第26页,充分性:设 ,则必存在正数,使,则存在某种范数,使 ,则 ,所以,即 。故 收敛于 0,收敛于,由此定理可知，不论是雅可比迭代法、高斯,塞德尔迭代法还是超松弛迭代法，它们收敛,充要条件是其迭代矩阵谱半径 。,实际上,在例4.1中,迭代矩阵,G=，,其特征多项式为,特征值为-2，-3，,所以迭代发散,第27页,定理4.3(迭代法收敛充分条件),若迭代矩阵,G,一个范数 ,则迭代公式,收敛,且有误差预计式,且有误差预计式,及,证:矩阵谱半径不超出矩阵任一个范数,已知 ,所以 ,依据定理4.2可知迭代公式收敛,第28页,又因为 ,则,det(I-G)0,I-G,为非奇异矩阵,故,xGxd,有惟一解 ,即,与迭代过程 相比较,有,两边取范数,第29页,由迭代格式，有,两边取范数，代入上式，得,证毕,由定理知，当 时，其值越小，迭代收敛越快，在程序设计中通惯用相邻两次迭代,（,为给定精度要求）作为,控制迭代结束条件,第30页,例4.5 已知线性方程组,考查用,Jacobi,迭代和,G-S,迭代求解时收敛性,解:雅可比迭代矩阵,故,Jacobi,迭代收敛,第31页,将系数矩阵分解,则高斯-塞德尔迭代矩阵,故高斯塞德尔迭代收敛。,第32页,定理4.4 设,n,阶方阵 为对角占优阵,则,非奇异,证:因,A,为对角占优阵,其主对角元素绝对值大,于同行其它元素绝对值之和,且主对角元素,全不为0,故对角阵 为非奇异。,作矩阵,第33页,利用对角占优知,由定理,4.1,知 非奇异,从而,A,非奇异,证毕,系数矩阵为对角占优阵线性方程组称作对角,占优方程组,。,第34页,定理4.5 对角占优线性方程组 雅可比,迭代公式和高斯-赛德尔迭代公式均收敛。,证:雅可比迭代公式迭代矩阵为,由定理4.4知,这时 ,再由,定理4.3知迭代收敛,再考查高斯-赛德尔迭代公式迭代矩阵,令 ，则有,即,写出分量形式有,第35页,设,而,由上式得,由此整理得,利用对角占优条件知上式右端小于1,(假如右端大于1,则得出与对角占优条件矛盾结果)故有,据定理4.3知,G-S,收敛,第36页,例,4.6,设求解线性方程组 雅可比迭代,求证当 1时,对应高斯-塞德尔迭代收敛,证:因为,B,是雅可比迭代迭代矩阵,故有,又 1,故有,则,系数矩阵 为对角占优阵,故,G-S,迭代收敛,第37页,例,4.7,设 ,证实,求解方程组,Jacobi,迭代与,G-S,迭代同时收敛或发散,证:雅可比迭代矩阵,其谱半径,第38页,例,4.7,设 ,证实,求解方程组,Jacobi,迭代与,G-S,迭代同时收敛或发散,证:,G-S,迭代矩阵,其谱半径,显然,和 同时小于、等于或大于1,因而,Jacobi,迭代法与,G-S,迭代法含有相同收敛性,第39页,例,4.8,设求解线性方程组,雅可比迭代,x,(k+1),=B x,(k),+f k=0,1,求证当,B,1,时,对应,G-S,迭代收敛,证 这里以,B,为例,B,1,类似,因为,B,是,雅可比迭代,迭代矩阵，故有,Ax=b,系数矩阵按行严格对角占优,故,高斯-塞德尔迭代收敛,第40页,例,4.9,考查用,雅可比迭代法和,高斯-塞德尔迭代,法解线性方程组,Ax=b,收敛性，其中,解：先计算迭代矩阵,第41页,求特征值,雅可比矩阵,(,B)=0 1,用高斯-塞德尔迭代,法求解时，迭代过程发散,高斯-塞德尔迭代矩阵,求特征值,第43页,Ax=b,系数矩阵按行严格对角占优,故,高斯-塞德尔迭代收敛,例4.10 设有迭代格式,X,(k+1),=B X,(k),+g (k=0,1,2）,其中,B=I-A,假如,A,和,B,特征值全为正数，,试证：该迭代格式收敛。,分析:依据,A，B,和单位矩阵,I,之间特征值关系导出,()1,从而说明迭代格式收敛。,证:因为,B=I-A,故,(B)=(I)-(A)=1-(A),(A)+(B)=1,因为已知,(A),和(,B),全为正数，故,0,(B)1,从而,(,B),1,所以该迭代格式收敛。,第44页,当初,a1,时,Jacobi,矩阵,G,J,1,对初值,x,(0),均收敛,例4.11 设 方程组,写出解方程组,Jacobi,迭代公式和迭代矩阵,并讨论迭代收敛条件。,写出解方程组,Gauss-Seidel,迭代矩阵,并讨,论迭代收敛条件。,解,Jacobi,迭代公式和,Jacobi,矩阵分别为,第45页,例4.11设,方程组,写出解方程组,Gauss-Seidel,迭代矩阵，并讨论,迭代收敛条件。,解,Gauss-Seidel,矩阵为,当初,a1,时,Gauss-Seidel,矩阵,G,s,1,所以对任意初值,x,(0),均收敛。,也可用矩阵谱半径,p(G,S,)1,来讨论,第46页,解：先计算迭代矩阵,例4.12 讨论用,雅可比迭代法和,高斯-塞德尔迭代,法解线性方程组,Ax=b,收敛性。,第47页,求特征值,雅可比矩阵,(,B)=1,用,雅可比迭代法求解时，迭代过程不收敛,1,=-1，,2,3,=1/2,第48页,求特征值,高斯-塞德尔迭代矩阵,(,G,1,)=0.3536 1,用,高斯-塞德尔迭代,法求解时，迭代过程收敛,1,=0,第49页,求解,AX=b,当,取何,值时迭代收敛？,解:所给迭代公式迭代矩阵为,例4.13 给定线性方程组,AX=b,用迭代公式,X,(K+1),=X,(K),+,(b-A,X,(K),)(k=0,1,）,第50页,即,2,-(2-5,),+1-5,+4,2,=0,2,-(2-5,),+(1-,)(1-4,)=0,-(1-,),-(1-4,),=0,1,=1-,2,=1-4,(,B)=max|1-,|,|1-4,|1,取,0,1/2,迭代收敛,第51页,例4.14 设求解线性方程组,Ax=b,简单迭代法,x,(k+1),=Bx,(k),+g (k=0,1,2,),收敛,求证:对0,1,迭代法,x,(k+1),=(1-,),I+,B,x,(k),+,g (k=0,1,2,),收敛。,证:设,C=(1-,),I+,B,(C),和,(B),分别为,C,和,B,特征值，则显然,(C),=(1-,),+,(B),因为,0,1,(C),是1和,(B),加权平均,且由迭代法,x,(k+1),=Bx,(k),+g (k=0,1,2,),收敛知|,(B),|1,故|,(C),|1,从而(,C)1,即,x,(k+1),=(1-,),I+,B,x,(k),+,g (k=0,1,2,),收敛,k=0,1,第52页,本章小结,本章介绍了解线性方程组 迭代法,一些基本理论和详细方法。迭代法是一个逐次逼,近方法，即对任意给定初始近似解向量，按,照某种方法逐步生成近似解序列，使解序列极,限为方程组解。注意到在使用迭代法,解方程组时，其迭代矩阵,B,和迭代向量,f,在计算过,程中一直不变,迭代法含有循环计算公式,方法,简单，程序实现方便，它优点是能充分利用系,数稀疏性,适宜解大型稀疏系数矩阵方程组。,第53页,迭代法不存在误差累积问题。使用迭代法,关键问题是其收敛性与收敛速度，收敛性与迭代,初值选取无关，这是比普通非线性方程求根,优越之处。在实际计算中，判断一个迭代格式收,敛性较麻烦，因为求迭代谱半径时需要求特征,值，当矩阵阶数较大时，特征值不易求出，通,常采取矩阵任一个范数都小于1或对角占优来判,断收敛性。有时也可边计算边观察其收敛性。如,何加紧迭代过程收敛速度是一个很主要问题,，实用中更多采取,SOR,法，选择适当松驰因子,有赖于实际经验。我们应针对不一样实际问题,，采取适当数值算法。,第54页,本章作业,4.1 4.12,第55页,