理学数值分析第六章课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,无忧,PPT,整理发布,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第五章,解线性方程组的数值解法,第五章解线性方程组的数值解法,1,引言,在自然科学和工程技术中,很多问题归结为,解线性方程组,.,例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元方法解常微分方程、偏微分方程边值问题等都导致求解线性方程组，而这些,方程组的系数矩阵大致分为两种,，,一种是低阶稠密矩阵,(,例如，阶数不超过,150).,另,一种是大型稀疏矩阵,(,即矩阵阶数高且零元素较多,).,引言 在自然科学和工程技术中,很多问题归结,2,有的问题的数学模型中虽不直接表现为含线性方程组,但它的数值解法中将问题,“,离散化,”,或,“,线性化,”,为线性方程组,.,因此,线性方程组的求解是数值分析课程中最基本的内容之一,.,关于线性方程组的解法一般有两大类：,有的问题的数学模型中虽不直接表现为含线性方程组,但它,3,但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解,.,本章将阐述这类算法中最基本的和具有代表性的算法就是高斯消元法,以及它的某些变形和应用,.,这类方法是解低阶稠密矩阵方程组及某些大型稀疏矩阵方程组,(,例如，大型带状方程组,),的有效方法,.,1.,直接法,经过有限次的算术运算,可以求得方程组的精确解,(,假定计算过程没有舍入误差,).,如线性代数课程中提到的克莱姆算法就是一种直接法,.,但该法对高阶方程组计算量太大,不是一种实用的算法,.,但实际计算中由于舍入误差的存在和影响，这种方法也只能,4,就是用某种极限过程去逐步逼近方程组精确解的方法,.,迭代法具有计算机的存储单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点，但存在,收敛条件,和,收敛速度,问题,.,迭代法是解大型稀疏矩阵方程组,(,尤其是由微分方程离散后得到的大型方程组,),的重要方法,.,2.,迭代法,就是用某种极限过程去逐步逼近方程组精确解的方,5,5.2,高斯消去法,本节介绍高斯消去法,(,逐次消去法,),及消去法和矩阵三角分解之间的关系,.,虽然高斯消去法是一种古老的求解线性方程组的方法,(,早在公元前,250,年我国就掌握了解方程组的消去法,),，但由它改进、变形得到的选主元素消去法、三角分解法仍然是目前计算机上常用的有效方法,.,我们在中学学过消去法,高斯消去法就是它的标准化的、适合在计算机上自动计算的一种方法,.,5.2 高斯消去法 本节介绍高斯消去法(逐次消去,6,5.2.1,高斯消去法,设有线性方程组,或写成矩阵形式,简记为,Ax,=,b,.,5.2.1 高斯消去法 设有线性方程组或写成,7,如,:,上三角矩阵,所对应的线性方程组,解为,当,m,=,n,时，对,三角形方程组,的解非常容易，如,如: 上三角矩阵所对应的线性方程组解为 当m=,8,下三角矩阵,所对应的线性方程组,计算量（乘除法的主要部分）都为,n,2,/2,.,解为,因此，我们将一般的线性方程组化成等价的三角形方程组来求解,.,下三角矩阵所对应的线性方程组计算量（乘除法的主要部分）都为,9,首先举一个简单的例子来说明消去法的基本思想,.,例,1,用消去法解方程组,解,第,1,步，将方程,(2.2),乘上,-,2,加到方程,(2.4),上去，消去,(2.4),中的未知数,x,1,，得到,第,2,步，将方程,(2.3),加到方程,(2.5),上去，消去,(2.5),中的未知数,x,2,，得到与原方程组等价的三角形方程组,首先举一个简单的例子来说明消去法的基本思想.,10,显然，方程组是,(2.6),是容易求解的，解为,上述过程相当于对方程的,增广阵做初等行变换,其中,r,i,用表示矩阵的第,i,行,.,显然，方程组是(2.6)是容易求解的，解为 上,11,由此看出，用消去法解方程组的,基本思想,是用逐次消去未知数的方法把原方程组,Ax=b,化为与其等价的三角形方程组，而求解三角形方程组可用回代的方法求解,.,换句话说，上述过程就是用初等行变换将原方程组系数矩阵化为简单形式,(,上三角矩阵,),，从而求解原方程组,(2.1),的问题转化为求解简单方程组的问题,.,或者说，对系数矩阵,A,施行一些行变换,(,用一些简单矩阵左乘,A,),将其约化为上三角矩阵,.,这就是,高斯消去法,.,由此看出，用消去法解方程组的基本思想是用逐次,12,下面讨论求解一般线性方程组的高斯消去法,.,由,下面讨论求解一般线性方程组的高斯消去法.由,13,将,(2.1),记为,A,(1),x,=,b,(1),，其中,将(2.1)记为A(1)x=b(1)，其中,14,(1),第,1,步,(,k,=1).,设,a,11,(1),0,，首先计算,乘数,m,i,1,=,a,i,1,(1),/,a,11,(1),(,i,=2,3,m,).,用,-,m,i,1,乘,(2.1),的第一个方程，加到第,i,个,(,i,=2,3,m,),方程上，消去,(2.1),的从第二个方程到第,m,个方程中的未知数,x,1,，得到与,(2.1),等价的方程组,(2.7),(1) 第1步(k=1).,15,简记为,A,(2),x,=,b,(2),，,其中,A,(2),b,(2),的元素计算公式为,(2),第,k,次消元,(,k,=1,2,s,s,=min(,m,-,1,n,),).,设上述第,1,步，,，第,k,-,1,步消元过程计算已经完成，即已计算好与,(2.1),等价的方程组，简记为,A,(,k,),x,=,b,(,k,),，其中,简记为 A(2)x=b(2)，,16,设,a,kk,(,k,),0,，计算,乘数,m,ik,=,a,ik,(,k,),/,a,kk,(,k,),(,i,=,k,+1,m,).,用,-,m,ik,乘,(2.8),的第,k,个方程加到第,i,个,(,i,=,k,+1,m,),方程上，消去从第,k,+1,个方程到第,m,个方程中的未知数,x,k,，得到与,(2.1),等价的方程组,A,(,k,+1),x,=,b,(,k,+1),，,设akk(k)0，计算乘数,17,其中,A,(,k,+1),b,(,k,+1),的元素计算公式为，,显然,A,(,k,+1),中从第,1,行到第,k,行与,A,(,k,),相同,.,(3),继续上述过程，且设,a,ii,(,i,),0,(,i,=1,2,s,),，直到完成第,s,步消元计算,.,最后得到与原方程组等价的简单方程组,A,(,s,+1),x,=,b,(,s,+1),，其中,A,(,s,+1),为上阶梯,.,其中A(k+1), b(k+1)的元素计算公式为，显然A(k,18,特别当,m,=,n,时，,与原方程组等价的简单方程组为,A,(,n,),x,=,b,(,n,),，即,由,(2.1),约化为,(2.10),的过程称为,消元过程,.,如果,A,是非奇异矩阵，且,a,kk,(,k,),0,(,k,=1,2,n,-,1),，求解三角形方程组,(2.10),，得到求解公式,(2.10),的求解过程,(2.11),称为,回代过程,.,特别当m=n时，与原方程组等价的简单方程组为,19,注意：设,Ax,=,b,，其中,A,R,n,n,为非奇异矩阵，如果,a,11,(1),=0,，由于,A,为非奇异矩阵，所以,A,的第,1,列一定有元素不等于零，例如,a,l,1,0,，于是可交换两行元素,(,即,r,1,r,l,),，将,a,l,1,调到,(1,1),位置，然后进行消元计算，这时,A,(2),右下角矩阵为,n,-,1,阶非奇异矩阵，继续这过程，高斯消去法照样可进行计算,.,总结上述讨论即有,注意：设Ax=b，其中ARnn为非奇异矩,20,定理,5,设,Ax,=,b,，其中,A,R,n,n,.,(1),如果,a,kk,(,k,),0,(,k,=1,2,n,),，则可通过高斯消去法将,Ax,=,b,约化为等价的三角形方程组,(2.10),，且计算公式为,(a),消元计算,(,k,=1,2,n,-,1,),定理5 设Ax=b，其中ARnn.,21,(b),回代计算,(2),如果,A,为非奇异矩阵，则可通过高斯消去法,(,及交换两行的初等变换,),将方程组,Ax,=,b,约化为等价的三角形方程组,(2.10).,(b) 回代计算 (2),22,例子,解方程组,解,：消元,回代得,例子 解方程组解：消元回代得,23,5.3,高斯主元素消元法,由高斯消去法知道,在消元过程中可能有,a,kk,(,k,),0,的情况，这时消去法将无法进行；即使主元素,a,kk,(,k,),0,但很小时，用其作除数，会导致其它元素数量级的严重增长和舍入误差的扩散，最后也使得计算解不可靠,.,高斯消去法也称,主元素消去法,(,条件,det,A,0),即,当,a,kk,(,k,),=0,时，高斯消元法,无法进行,；或,|,a,kk,(,k,),|1,时，带来,舍入误差的扩散,。,（小主元）,5.3 高斯主元素消元法 由高斯消去法知,24,5.3.1,列主元素消去法,设方程组,(2.1),的增广矩阵为,首先在,A,的第,1,列中选取绝对值最大的元素作为主元素，例如,5.3.1 列主元素消去法 设方程组(2.1,25,交换,交换,26,消元法的应用,1.,求行列式,高斯,消元法,2.,求逆矩阵,(,用高斯,-,若当消去法,),消元法的应用1. 求行列式 高斯消元法2. 求逆矩阵(用高斯,27,例子,分别用高斯消元法和列主元消元法求矩阵的行列式,.,解：,高,斯,消,元,法,大数“吃掉”了小数！,例子 分别用高斯消元法和列主元消元法求矩阵的行列式.解,28,列,主,元,消,元,法,列,29,5.3.2,高斯,-,若当消去法,高斯,-,若当消去法是高斯消去法的一种变形,.,高斯消去法,是消去对角元素下方的元素,.,如果同时消去对角元素上方和下方的元素，而且将对角元素化为,1,，这种方法就称为,高斯,-,若当,(Gauss-Jordan),消去法,.,设高斯,-,若当消去法已完成,k,-,1,步，于是,Ax=b,化为等价方程组,A,(,k,),x=b,(,k,),，其中增广阵,5.3.2 高斯-若当消去法 高斯-若当消去,30,在第,k,步计算时,(,k,=1,2,n,),考虑将第,k,行上、下的第,k,列元素都进行消元计算化为零，且,a,kk,化为,1.,在第k步计算时(k=1,2,n),考虑将,31,1.,按列选主元素，即确定,i,k,使,2.,换行,(,当,i,k,k,时,),，交换第,k,行与第,i,k,行元素,(,j=k,k+,1,n,),3.,计算乘数,m,ik,=,-,a,ik,/,a,kk,(,i=,1,2,n, ik,),m,kk,=,1/,a,kk,.,(,m,ik,可保存在存放,a,ik,的单元中,).,4.,消元计算,a,ij,a,ij,+m,ik,a,kj,(,i=,1,2,n,且,ik,j=k+,1,n,),b,i,b,i,+m,ik,b,k,(,i=,1,2,n,且,ik,),1. 按列选主元素，即确定ik使,32,5.,计算主行,a,kj,a,kj,m,kk,(,j=k,k+,1,n,),，,b,k,b,k,m,kk,.,上述过程结束后，即当,k=n,时有,显然,x,i,=,b,i,i,=1,2,n,就是,Ax=b,的解,.,5.计算主行上述过程结束后，即当k=n时有显,33,说明用高斯,-,若当消去法虽比高斯消去法略复杂些，但将,A,约化为单位矩阵，,计算解就在常数项位置得到,，因此用不着回代求解，故也称为,无回代的高斯消元法,.,它的计算量大约需要,n,3,/2,次乘除法，要比高斯消去法大，但用高斯,-,若当消去法,求一个矩阵的逆矩阵,还是比较合适的,.,说明用高斯-若当消去法虽比高斯消去法略复杂些,34,定理,9(,高斯,-,若当法求逆矩阵,),设,A,为非奇异矩阵，方程组,AX,=,I,n,的增广矩阵为,C,=(,A,|,I,n,),，如果对,C,应用高斯,-,若当方法化为,(,I,n,|,T,),，则,A,-,1,=,T,.,事实上,求,A,的逆矩阵,A,-,1,即求,n,阶矩阵,X,使,AX,=,I,n,其中,I,n,为单位矩阵，将,X,按列分块,X,=(,x,1,x,2,x,n,),，,I,=(,e,1,e,2,e,n,),，,于是求解,AX,=,I,n,等价于求解,n,个方程组,Ax,j,=,e,j,(,j,=1,2,n,).,我们可用高斯,-,若当方法求解,AX,=,I,n,.,定理9(高斯-若当法求逆矩阵) 设A为非,35,例,4,用高斯,-,若当方法求下列矩阵的逆矩阵,.,解,由分块矩阵,例4 用高斯-若当方法求下列矩阵的逆矩阵.,36,所以得,所以得,37,小节,比较而言,Gauss,顺序消去法条件苛刻,且数值不稳定,; Gauss,全主元消去法工作量偏大，需要比较 个元素及行列交换工作，算法复杂；对于,Gauss-Jordan,消去法形式上比其他消元法简单，且无回代求解，但计算量大,比,Gauss,顺序消去法多 计算量。因此从算法优化的角度考虑，,Gauss,列主元消去法比较好。,小节 比较而言,Gauss顺序消去法条件苛刻,且数值不稳,38,理学数值分析第六章课件,39,5.4,矩阵的三角分解法,我们知道对矩阵进行一次初等变换，就相当于用相应的初等矩阵去左乘原来的矩阵。因此我们这个观点来考察,Gauss,消元法用矩阵乘法来表示，即可得到求解线性方程组的另一种直接法：矩阵的三角分解。,5.4 矩阵的三角分解法 我们知道对矩阵进行一次初,40,5.4.1 Gauss,消元法的矩阵形式,5.4.1 Gauss消元法的矩阵形式,41,理学数值分析第六章课件,42,5.4.2 Doolittle,分解,5.4.2 Doolittle分解,43,理学数值分析第六章课件,44,Doolittle,分解,若矩阵,A,有分解：,A=LU,，其中,L,为单位下三角阵，,U,为上三角阵，则称该分解为,Doolittle,分解，可以证明，当,A,的各阶顺序主子式均不为零时，,Doolittle,分解可以实现并且唯一。,Doolittle分解若矩阵A有分解：A=LU，其中L为单位,45,A,的各阶顺序主子式均不为零，即,A的各阶顺序主子式均不为零，即,46,Doolittle,分解,Doolittle分解,47,Doolittle,分解,Doolittle分解,48,Doolittle,分解,(,看看就可,),Doolittle分解(看看就可),49,Doolittle,分解,Doolittle分解,50,Doolittle,分解,Doolittle分解,51,Doolittle,分解,Doolittle分解,52,例题,例题,53,例题,例题,54,例题,例题,55,例题,例题,56,例题,例题,57,上机,P27,例题,上机P27 例题,58,理学数值分析第六章课件,59,第六章 解线性方程组的迭代方法,6.1,引言,6.2,基本迭代法,6.3,迭代法的收敛性,第六章 解线性方程组的迭代方法6.1 引言,60,例,1,求解方程组,记为,Ax,=,b,，其中,方程组的精确解是,x,*,=(3,2,1),T,.,现将改写为,例1 求解方程组记为Ax=b，其中方程组的,61,或写为,x,=,B,0,x,+,f,，其中,或写为x=B0x+f，其中,62,我们任取初始值，例如取,x,(0),=(0, 0, 0),T,.,将这些值代入,(1.3),式右边,(,若,(1.3),式为等式即求得方程组的解，但一般不满足,),，得到新的值,x,(1),=(,x,1,(1),x,2,(1),x,3,(1),),T,=(3.5, 3, 3),T,，再将,x,(1),分量代入,(1.3),式右边得到,x,(2),，反复利用这个计算程序，得到一向量序列和一般的计算公式,(,迭代公式,),我们任取初始值，例如取x(0)=(0, 0,63,简写为,x,(,k,+1),=,B,0,x,(,k,),+,f,，,其中,k,表示迭代次数,(,k,=0,1,2,).,迭代到第,10,次有,简写为 x(k+1)=,64,从此例看出，由迭代法产生的向量序列,x,(,k,),逐步逼近方程组的精确解是,x,*,=(3,2,1),T,.,即有,对于任何一个方程组,x,=,Bx,+,f,(,由,Ax,=,b,变形得到的等价方程组,),，由迭代法产生的向量序列,x,(,k,),是否一定逐步逼近方程组的解,x,*,呢？回答,是不一定,.,请同学们考虑用迭代法解下述方程组,但,x,(,k,),并不是所有的都收敛到解,x,*,！,从此例看出，由迭代法产生的向量序列x(k)逐步逼近方程组,65,6.2,基本迭代法,其中，,A,=(,a,ij,),R,n,n,为非奇异矩阵，下面研究任何建立,Ax,=,b,的各种迭代法,.,设线性方程组,Ax,=,b,，,(2.1),其中，,M,为可选择的非奇异矩阵，且使,Mx,=,d,容易求解，一般选择,A,的某种近似，称,M,为,分裂矩阵,.,将,A,分裂为,A,=,M,-,N,. (2.2),6.2 基本迭代法其中，A=(aij)Rnn为非奇异,66,于是，求解,Ax,=,b,转化为求解,Mx,=,Nx,+,b,，即求解,可构造一阶定常迭代法,其中,B,=,M,-,1,N,=,M,-,1,(,M,-,A,)=,I,-,M,-,1,A,，,f,=,M,-,1,b,.,称,B,=,I,-,M,-,1,A,为迭代法的,迭代矩阵,，选取,M,矩阵，就得到解,Ax,=,b,的各种迭代法,.,设,a,ii,0,(,i,=1,2,n,),，并将,A,写成三部分,于是，求解Ax=b转化为求解Mx=Nx+b,67,理学数值分析第六章课件,68,即,A=D,-,L,-,U,即A=D-L-U,69,6.2.1,雅可比,(Jacobi),迭代法,设,a,ii,0,(,i,=1,2,n,),，选取,M,为,A,的对角元素部分,即选取,M,=,D,(,对角阵,),，,A,=,D,-,N,，由,(2.3),式得到解方程组,Ax,=,b,的,雅可比,(Jacobi),迭代法,.,又称,简单迭代法,.,其中,B,=,I,-,D,-,1,A,=,D,-,1,(,L,+,U,)=,J,f,=,D,-,1,b,.,称,J,为解,Ax,=,b,的,雅可比迭代法的迭代矩阵,.,6.2.1 雅可比(Jacobi)迭代法 设,70,于是雅可比迭代法可写为,矩阵形式,其,Jacobi,迭代矩阵,为,于是雅可比迭代法可写为矩阵形式其Jacobi迭代矩阵为,71,等,价,方,程,组,其中,a,ii,(,i,),0,(,i,=1,2,n,),即由方程组,Ax,=,b,得到的,等其中 aii(i)0 (i=1,2,n)即由方程,72,建立的雅可比迭代格式为,建立的雅可比迭代格式为,73,于是，解,Ax,=,b,的雅可比迭代法的计算公式为,由,(2.6),式可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法且计算过程中原始矩阵,A,始终不变,.,于是，解Ax=b的雅可比迭代法的计算公式为,74,6.2.2,高斯赛德尔迭代法,在,Jacobi,迭代中，计算,x,i,(,k,+1),(2,i,n,),时,，,使用,x,j,(,k,+1),代替,x,j,(,k,),(1,j,i,-,1),，,即有,建,立,迭,代,格,式,6.2.2 高斯赛德尔迭代法在 Jacobi 迭代中,75,或缩写为,称为,高斯,塞德尔,(Gauss Seidel),迭代法,.,或缩写为称为高斯塞德尔(Gauss Seidel)迭代,76,解,Ax,=,b,的,高斯,塞德尔迭代法的计算公式为,或,解Ax=b的高斯塞德尔迭代法的计算公式为或,77,雅可比迭代法,不使用变量的最新信息计算,x,i,(,k,+1),，而由,高斯,塞德尔迭代公式,(2.8),可知，计算,x,(,k,+1),的第,i,个分量,x,i,(,k,+1),时，利用了已经计算出的最新分量,x,j,(,k,+1),(,j,=1,2,i,-,1),.,可看作,雅可比迭代法,的一种改进,.,由,(2.8),可知，,高斯,塞德尔迭代公式,每迭代一次只需计算一次矩阵与向量的乘法,.,雅可比迭代法不使用变量的最新信息计算xi(,78,例,2,用,高斯,塞德尔迭代法,解例,1,的方程组,(1.2).,解,用,高斯,塞德尔迭代公式：,取,x,(0),=(0, 0, 0),T,.,迭代到第,7,次有,例2 用高斯塞德尔迭代法解例1,79,由此例可知，用,高斯,塞德尔迭代法,，,雅可比迭代法,解线性方程组,(1.2)(,且取,x,(0),=0,),均收敛，而,高斯,塞德尔迭代法,比,雅可比迭代法,收敛较快,(,即取相同的,x,(0),，达到同样精度所需迭代次数较少,),，但这结论只当,A,满足一定条件时才是对的,.,由此例可知，用高斯塞德尔迭代法，雅可比迭,80,例,1,用雅可比迭代法解方程组,解：,Jacobi,迭代格式为,例1 用雅可比迭代法解方程组,81,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,取,x,(0),=,(0,0,0),T,计算,结果,如下：,kx1(k)x2(k)x3(k)10.720.830.842,82,解：,Gauss-Seidel,迭代格式为,例,2,用,GaussSeidel,迭代法解上题,.,解：Gauss-Seidel 迭代格式为,83,取,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,取 x(0)=(0,0,0)T 计算结果如下：kx1(k),84,理学数值分析第六章课件,85,理学数值分析第六章课件,86,理学数值分析第六章课件,87,Jacobi,迭代法的算法,Jacobi迭代法的算法,88,Gauss-Seidel,迭代法的算法,Gauss-Seidel迭代法的算法,89,Thanks!,Thanks!,90,