计算方法 解线性方程组的直接法ppt课件.ppt

第8次 线性方程组的直接解法,计算方法(Numerical Analysis),1）高斯消去法2）高斯主元素消去法3）方程组的性态4) 高斯消去法算法构造（编程）,本讲内容,高斯消去法,5.1 引言,在工程技术、自然科学和社会科学中，许多问题最终都可归结为求解线性方程组的数学问题。线性方程组的求解对于实际问题是极其重要的。,解线性方程组的直接法,解线性方程组的直接法,可简记为 Ax=b，其中,( 6.1 ),常见的nxn线性方程组，一般形式为,线性方程组的数值解法一般有两类：直接法：就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是Gauss消去法。迭代法: 就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。(一般有限步内得不到精确解),例子：求解如下的上三角线性方程组：,解：由（4），得,将（4）带入（3），得,将结果代入（2）， 得,将结果代入（1）， 得, 5.2 高斯消去法, 5.2 高斯消去法,5.2.1 高斯消去法的基本思想,解:高斯消去法包括如下的消元和迭代的两个过程。,先用一个简单实例来说明Gauss法的基本思想,例5.1 解线性方程组,（1）消元过程,第1步:将方程乘上(-2)加到方程 上去,将方程 乘上 加到方程 上去,这样就消去了第2、3个方程的 项,于是就得到等价方程组,第2步：将方程 乘上 加到方程 上去，这样就消去了第3个方程的 项，于是就得到等价方程组,这样，消元过程就是把原方程组化为上三角形方程组，其系数矩阵是上三角矩阵。,（2）回代过程,将上述三角形方程组自下而上求解得：,从而求得原方程组的解：,前述的消元过程相当于对原方程组的增广矩阵进行下列行变换,同样可得到与原方程组等价的方程组 ,高斯消去法的基本思想：,这种求解上三角方程组的方法称为回代, 通过一个方程乘或除以某个常数,利用矩阵行的初等变换将原方程组Ax=b系数矩阵化为上三角形矩阵,然后从最后一个方程开始,依次向前代入求出未知变量：,将两个方程相加减,逐步减少方程中的变元数,最终将方程组化成上三角方程组,一般将这一过程称为消元,然后再回代求解。,5.2.3 高斯消去法的适用条件,注2： 设系数矩阵A为非奇异矩阵，则若a11 =0，则可以通过调换行的方法，使得在第一行的第一个元素非0。其它在消元过程中，kk位置的情形类似处理。则高斯消元法可以进行。,注1：设系数矩阵A为非奇异矩阵，直接使用高斯消元法（不进行行的交换）对于某些简单的矩阵可能失败，例如：,证明：上三角形方程组是从原方程组出发，通过逐次进行“一行乘一数加到另一行”而得出的，该变换不改变系数矩阵顺序主子式的值。,因此，需要对上述的高斯算法进行修改，首先应该研究原来的矩阵A在何条件下能够保证,设方程组系数矩阵 ，其顺序主子式,(m =1,2,，n),经变换得到的上三角形方程组的顺序主子式,定义5.1 设矩阵 每一行对角元素的绝对值都大于同行其他元素绝对值之和,则称A为严格对角占优矩阵。, ,上述条件展开以后为：,定理1.1 若方程组 的系数矩阵A为严格对角占优，则用高斯消去法求解时， 全不为0。因此，可以使用高斯消去法求解。,练习：用高斯消去法求解如下的线性方程组,解：增广矩阵为,Home,高斯主元素消去法,使用高斯消去法求解时，在消元过程中可能会出现 的情况，这时消去法将无法进行；,5.3 高斯主元素消去法,即使 ，但它的绝对值很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，将严重影响计算结果的精度。,实际计算时必须避免这类情况的发生。主元素消去法就可弥补这一缺陷。,例4 求解如下的方程组,解法1 使用Gauss消去法求解,其精确解为（舍入到4位有效数字）：,计算解为：,解法2。变换行，避免绝对值小的主元做除数,解为：,这个解比解法1更加接近真实的解。,交换原则：通过方程或变量次序的交换，使在对角线位置上获得绝对值尽可能大的系数作为akk(k)，称这样的akk(k) 为主元素，并称使用主元素的消元法为主元素法根据主元素选取范围分为：列主元素法行主元素法(不讲)全主元素法(不讲),5.3 高斯主元素消去法（续）,5.3.2 列主元素法,列主元素法就是在待消元的所在列中选取主元（选取一列中绝对值最大的元素当主元），经方程的行交换，置主元于对角线位置后进行消元的方法。,例5.4 用列主元素法解下列线性方程组,解：选择-20作为该列的主元素，交换方程(1)和(2)得,m21 =10/-20=-0.5m31=1/-20=-0.05,(5)- m21(4), (6)- m31(4)得,选6为主元素，交换方程（7）与（8），得：,(10)- m32(9) 得 -2.34168x3 = 4.13332 (11),记笔记,计算m32=1/6 =0.16667,保留有主元素的方程,进行回代，得,列选主元素的计算方法与高斯消去法完全一样,不同的是在每步消元之前要按列选出主元,例5.5 用矩阵的初等行变换求解解方程组,解: 用矩阵的初等行变换求解,对增广矩阵 (下面带下划线元素为主元素),矩阵的列主元素计算方法可以用矩阵的初等行变换实现,同学课堂练习：用列主元素法求解线性方程组：,Home,方程组的性态,5.5 方程组的性态,在建立方程组时，其系数往往含有误差（如观测误差或计算误差），即，所要求解的运算是有扰动的方程组，因此需要研究扰动对解的影响。,例5.13 考察方程组,和,上述方程组（1）是方程组（2）在右端项施加了微小的扰动, 但解大不相同.,（1）,（2）,方程组（1）的解：,方程组（2）的解：,这类方程组称为病态的。,定义5.8 A或b的微小变化(又称扰动或摄动)引起方程组Ax=b解的巨大变化，则称方程组为病态方程组，矩阵A称为病态矩阵。否则方程组是良态方程组，矩阵A也是良态矩阵 。,为了定量地刻画方程组“病态”的程度，要对方程组Ax=b进行讨论，考察A（或b）微小误差对解的影响。为此先引入矩阵范数的概念：,矩阵范数的概念：,定义5.9 （矩阵条件数）设A为非奇异矩阵，称,为矩阵A条件数。,常用的条件数有,条件数的性质：,对于任何非奇异矩阵A,都有：,当cond(A)v 1时，则方程组Ax=b是病态的；否则，Ax=b是良态的。,病态方程组(矩阵)的定量描述：,例6.13 线性方程组,的系数矩阵带误差，成为如下方程组,求方程组系数矩阵的条件数, 并说明方程组的性态.,例9 Hilbert矩阵Hn的定义如下,求H3 的条件数。,结论：Hilbert矩阵H3 是病态矩阵；可以证明，当n越大的时候， Hn的 病态越严重。,解：,本次小结,直接法是一种计算量小而精度高的方法。直接法中具有代表性的算法是高斯（Gauss）消去法；克莱姆算法也是一种直接法，但该算法用于高阶方程组时计算量太大而不实用；选主元的算法有很好的数值稳定性。从计算简单出发实际中多选用列主元法；,注意线性方程组有的时候具有病态；线性方程组的病态程度是其本身的固有特性，因此即使用数值稳定的方法求解，也难以克服严重病态导致的解的失真。,Home,高斯消去法算法构造,5.2.2 高斯消去法算法构造(Matlab 编程使用),( 6.3 ),Gauss消去法的消元过程：对( 6.3 )的增广矩阵进行行初等变换。将例6.1中解三阶线性方程组的消去法推广到一般的 阶线性方程组，并记,线性方程组(6.1)用矩阵形式表示为,则高斯消去法的算法构造归纳为：, Gauss消去法的消元过程(由n-1步组成)：,用 乘以第1个方程后加到第 个方程上去,消去第2到第n个方程的未知数 ,得到,第1步 设,记为：,第k步 （k=2, 3, n-1）继续上述消元过程，设第k-1次消元已经完成，得到与原方程组等价的方程组,记为,设 ，计算乘数,用 乘以以上方程组的第k个方程加到第i个方程(i=k+1,n),消去从第k+1个方程到第n个方程中的未知数xk,得到与方程组(6.3)等价的线性方程组,只要 ,消元过程就可以进行下去,直到经过n-1次消元之后，消元过程结束，得到与原方程组等价的上三角形方程组,记为,或者写成,即,(6.7),（2）回代过程：是对上三角方程组（6.7）自下而上逐步回代解方程组计算，即,（3）高斯消去法的计算步骤：,编程, 消元过程; 设,计算:, 回代过程,编程,算法.,上面这一段用于Matlab编程。,Gauss消去法计算量(加法与乘法) n3,作业P176 7,Home,