三章求解线方程组的数值解法省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢您,第三章 求解线性方程组数值解法,泰山学院信息科学技术系,第1页,解线性方程组两类方法:,直接法:经过有限次运算后可求得方程组准确解方法(不计舍入误差!),迭代法：从解某个近似值出发，经过结构一个无穷序列去迫近准确解方法(普通有限步内得不到准确解),第2页,3.1,解线性方程组直接法,一、高斯消去法,思绪,首先将方程组,Ax=b,化为上三角方程组,，,此过程称为,消去过程,，再求解上三角方程组，此过程称为,回代过程,.,3.1.1,高斯消去法和选主元高斯消去法,第3页,将增广矩阵,第,i,行,+,l,i,1,第1行,，得到：,消去过程：,第一步,：,设 ，计算因子,其中,第4页,第,k,步：,设 ，计算因子,且计算,共进行,n,1,步，得到,第5页,定理：,若,A,全部,次序主子式,均不为0，则高斯消去法能次序进行消元，得到唯一解。,回代过程：,第6页,二、,选主元消去法,为防止这种情况发生,可经过交换方程次序，选取,绝对值大元素作主元.基于这种思想导出了主元素法,在高斯消去法消去过程中可能出现 情况，这时,高斯消去法将无法进行；即使主原因 但很小，,其作除数，也会造成其它元素数量级严重增加和舍,误差扩散,第7页,列主元消去法,在第,k,步消元前，在系数矩阵第,k,列对角线以下元素中找出绝对值最大元。,若,pk，,交换第,k,个与第,p,个方程后，再继续消去计算.,这种方法称为,列主元,Gauss,消去法。,列主元,Gauss,消去法确保了,l,ik,1,(i=k+1,k+2,，n).,第8页,全主元消去法,在第,k,步消去前，在系数矩阵右下角,n-k+1,阶主子阵中，,选绝对值最大元素作为主元素,。,(1),If,p,k,then,交换第,k,行与第,p,行;,If,q,k,then,交换第,k,列与第,q,列;,(2),消元,注,：,列交换改变了,x,i,次序，须统计,交换次序,，解完后再换回来。,第9页,运算量,（,Amount of Computation）,（1）,用克莱姆,（,Cramer）,法则求解,n,阶线性方程组,每个行列式由,n!,项相加，而每项包含了,n,个因子相乘，乘法运算次数为(,n-1)n!,次.,仅考虑乘(除)法运算,计算解向量包含计算,n+1,个行列式和,n,次除法运算,乘(除)法运算次数,N=(n+1)(n-1)n!+n,.,第10页,（2）,高斯消去法,:,在第1个消去步，计算,l,i1,(i=2,3，n)，,有,n-1,次除法运算.使,a,ij,(1),变为,a,ij,(2),以及使,b,i,(1),变为,b,i,(2),有,n(n-1),次乘法运算和,n(n-1),次加(减)法运算.,在第,k,个消去步，有,n-k,次除法运算、(,n-k+1)(n-k),次,乘法运算和相同加(减)法运算.,首先统计乘法运算总次数.将每个消去步乘法运算次数相加，有,n(n-1)+(n-1)(n-2)+3.2+2.1=n(n-1)(n+1)/3,加(减)法运算次数总计也为,n(n-1)(n+1)/3.,除法运算总次数为,n+(n-1)+1=n(n-1)/2,第11页,回代过程计算,除法运算次数为,n,次.乘法运算和加法运算总次数都为,n+(n-1)+1=n(n-1)/2,次,Gauss,消去法,除法运算次数为:,n(n-1)/2+n=n(n+1)/2，,乘法运算次数为:,n(n-1)(n+1)/3+n(n-1)/2=n(n-1)(2n+5)/6，,加(减)法运算次数为:,n(n-1)(2n+5)/6,通常也说,Gauss,消去法运算次数与,n,3,同阶，记为,O(n,3,),第12页,全主远消去法,:,比 高斯消去法多出 比较，确保稳定，但费时,。,列主元消去法,:,比 高斯消去法只多出 比较，略省时。,第13页,2.1.2,三角分解法,高斯消元法矩阵形式,每一步消去过程相当于左乘初等变换矩阵,L,k,第14页,第15页,A,LU,分解,(,LU,factorization),第16页,定理2.1.4：,若,A,全部次序主子式 均不为0，则,A,LU,分解唯一（其中,L,为,单位,下三角阵）。,证实：由,1,中定理可知，,LU,分解存在。下面证实唯一性。,若不唯一，则可设,A,=,L,1,U,1,=,L,2,U,2,，,推出,上三角矩阵,对角线上为1下三角矩阵,注,：（1）,L,为单位下三角阵而,U,为,普通,上三角阵分解称为,Doolittle,分解,（2）L,为普通下三角阵而,U,为,单位,上三角阵分解称为,Crout,分解,。,第17页,Doolittle,分解法,：,经过比较法直接导出,L,和,U,计算公式。,思绪,第18页,普通计算公式,计算量与,Gauss,消去法同.,第19页,LU,分解求解线性方程组,第20页,第21页,2.1.4,求解正定方程组,Cholesky,方法,回顾：,对称正定阵,A,几个主要性质,（1）,A,1,亦对称正定，且,a,ii,0,（2）,A,次序主子阵,A,k,亦对称正定,（3）,A,特征值,i,0,（4）,A,全部次序主子式,det(,A,k,),0,第22页,定理2.1.6 设矩阵,A,对称正定，则存在唯一对角元全为正下三角阵,G,使得,AGG,T,计算格式为,第23页,2.1.5 求解三对角方程组追赶法,定理：,若,A,为,对角占优,三对角阵，且满足,则方程组有唯一,LU,分解。,第24页,直接比较等式两边元素，可得到计算公式（,p.66）,第二步,:,追,即解 ：,第三步,:,赶,即解 ：,第一步,:对,A,作,Crout,分解,第25页,