《数值方法第三章1 线性方程组课件》由会员分享，可在线阅读，更多相关《数值方法第三章1 线性方程组课件（50页珍藏版）》请在金锄头文库上搜索。
1、第3章 解线性方程组的直接方法,本章要点 高斯消元法、高斯列主元素消去法。 矩阵三角分解法。 迭代法。,3.1 引言 在工程技术、自然科学和社会科学中，经常遇到的许多问题最终都可归结为解线性方程组，如电学中网络问题、用最小二乘法求实验数据的曲线拟合问题，工程中的三次样条函数的插值问题，经济运行中的投入产出问题以及大地测量、机械与建筑结构的设计计算问题等等，都归结为求解线性方程组或非线性方程组的数学问题。因此线性方程组的求解对于实际问题是极其重要的。,3.1 工程实例 火警系统：,如果要求解这个公式，那么，至少n次测量， 形成n个方程,每个节点作用不一致, 需要有加权。,第3章 解线性方程组的直
2、接法,常见的线性方程组是方程个数和未知量个数相同的n阶线性方程组，一般形式为,简记为 Ax=b，其中,( 3.1 ),一般b0, 当系数矩阵A非奇异(即detA0) 时，方程组（3.1）有惟一解。,线性方程组的数值解法一般有两类： 直接法：就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是高斯(Gauss)消去法。 迭代法: 就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。(一般有限步内得不到精确解),3.2 解线性方程组的直接法（高斯消去
3、法）,首先，,克莱姆法则在理论上有着重大意义，但在实际应用中存在很大的困难，在线性代数中，为解决这一困难给出了高斯消元法。,3.2 解线性方程组的直接法（高斯消去法）,3.2.1 高斯消去法的基本思想 先用一个简单实例来说明Gauss法的基本思想 例3.1 解线性方程组, ,解: 该方程组的求解过程实际上是将一个方程乘或除以某个常数,然后将两个方程相加减,逐步减少方程中的未知数,最终使每个方程只含有一个未知数,从而得出所求的解。整个过程分为消元和回代两个部分。,（1）消元过程 第1步:将方程乘上(-2)加到方程 上去,将方程 乘上 加到方程 上去,这样就消去了第2、3个方程的 项,于是就得到等
4、价方程组, ,第2步：将方程 乘上 加到方程 上去，这样就消去了第3个方程的 项，于是就得到等价方程组,这样，消元过程就是把原方程组化为上三角形方程组，其系数矩阵是上三角矩阵。,（2）回代过程 回代过程是将上述三角形方程组自下而上求解，从而求得原方程组的解：,前述的消元过程相当于对原方程组,的增广矩阵进行下列变换( 表示增广矩阵的第 行）,同样可得到与原方程 组等价的方程组 ,由此看出,高斯消去法解方程组基本思想是设法消去方程组的系数矩阵A的主对角线下的元素,而将Ax=b化为等价的上三角形方程组,然后再通过回代过程便可获得方程组的解。换一种说法就是用矩阵行的初等变换将原方程组系数矩阵化为上三角
5、形矩阵,而以上三角形矩阵为系数的方程组的求解比较简单,可以从最后一个方程开始,依次向前代入求出未知变量 。这种求解上三角方程组的方法称为回代, 通过一个方程乘或除以某个常数,以及将两个方程相加减,逐步减少方程中的变元数,最终将方程组化成上三角方程组,一般将这一过程称为消元,然后再回代求解。,通常把按照先消元,后回代两个步骤求解线性方程组的方法称为高斯（Gauss）消去法。,3.2.2 高斯消去法算法构造 我们知道,线性方程组(3.1)用矩阵形式表示为,( 3.3 ),解线性方程组（3.1）的高斯（Gauss）消去法的消元过程就是对( 3.3 )的增广矩阵进行初等行变换。将例3.1中解三阶线性方
6、程组的消去法推广到一般的 阶线性方程组并记 则高斯消去法的算法构造归纳为：, 消元过程,高斯消去法的消元过程由n-1步组成： 第1步 设 ,把(3.3)中的第一列中元素 消为零,令,用 乘以第1个方程后加到第 个方程上去,消去 第2n个方程的未知数 ,得到 即,其中,第k步 （k=2,3,n-1）继续上述消元过程，设第k-1次消元已经完成，得到与原方程组等价的方程组,记为,其中,设 ，计算乘数,用 乘以第k个方后加到第i个到第n个方程中，消去第i个到第n个方程的未知数 ，得到,只要 ,消元过程就可以进行下去,直到经过n-1次消元之后，消元过程结束，得到与原方程组等价的上三角形方程组,记为,或者
7、写成,即,(3.7),（2）回代过程 就是对上三角方程组（3.7）自下而上逐步回代解方程组计算，即,（3）高斯消去法的计算步骤： 消元过程;设 计算, 回代过程,高斯消元算法,FOR k=1 TO n-1 FOR i=k+1 TO n ; FOR j=k+1 TO n; ; Output ,回代算法,FOR i=n TO 1 s=bi; FOR j=i TO n ; ; Output ,选列主元算法,(4) 高斯消去法流程图 (5) Gauss消去法计算量 , 消元计算: aij(k+1)= aij(k)- mik akj(k) (i,j=k+1,k+2, , n) 第一 步计算乘数mi1,
8、mi1=ai1/a11 (i=2,3,n) 需要n-1次除法运算, 计算 aij(2）(i,j=2,3,n) 需要(n-1)2次乘法运算及(n-1)2次加减法运 算,消元过程： 乘： 除： 回代过程： 运算量：,消元过程： 乘：,FOR k=1 TO n-1 FOR i=k+1 TO n ; FOR j=k+1 TO n; ; ,消元过程： 乘： 除： 回代过程： 运算量：,3.2.3 高斯消去法的适用条件,定理3.1 方程组系数矩阵的顺序主子式全不 为零则高斯消去法能实现方程组的 求解。 证明 上三角形方程组是从原方程组出发，通过逐次进行“一行乘一数加到另一行”而得出的，该变换不改变系数矩阵
9、顺序主子式的值。,设方程组系数矩阵 ，其顺序主子式,（m =1,2,，n）,经变换得到的上三角形方程组的顺序主子式,所以能实现高斯消去法求解,（m =1,2,，n）,定义3.1 设矩阵 每一行对角元素的绝对值都大于同行其他元素绝对值之和,则称A为严格对角占优矩阵。,定理3.2 若方程组 的系数矩阵A为严格对角占优，则用高斯消去法求解时， 全不为零。,证:先考察消元过程的第1步,因A为严格对角占 优,故 故 ,又根据高斯消 去公式得 于是,再利用方程组的对角占优性,由上式可进一步得,又由,证明：,故有,当A为严格对角占优时, ,余下的子阵仍是对角占优的，从而又有 。依次类推全不为零。 定理证毕。
10、,一般线性方程组使用高斯消去法求解时，在消元过程中可能会出现 的情况，这时消去法将无法进行；即使 ，但它的绝对值很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，将严重影响计算结果的精度。实际计算时必须避免这类情况的发生。主元素消去法就可弥补这一缺陷。,基本思想：每次消元之前在系数矩阵中按一定的范围选取绝对值最大的元素作为主元素，以便减少舍入误差的影响。 交换原则：通过方程或变量次序的交换，使在对角线位置上获得绝对值尽可能大的系数作为akk(k)，称这样的akk(k) 为主元素，并称使用主元素的消元法为主元素法 根据主元素选取范围分为：列主元素法、行主元素法、全主元素法 列主
11、元素法：在待消元的所在列中选择主元，经方程的变换，置主元素于对角线位置后进行消元的方法。 全主元素：在全体待选系数中选取主元，则得全主元素法。,记笔记,3.2.4 高斯主元素消去法,主元素法的意义,例3.2 用高斯消去法求下列方程组的解,解： 确定乘数 ，再计算系数,假设计算在4位浮点十进值的计算机上求解,则有,这时方程组的实际形式是,由此回代解出 ,但这个解不满足原方程组,解是错误的。这是因为所用的除数太小使得上式在消元过程中“吃掉”了下式，解决这个问题的方法之一就是采用列选主元高斯消元法。即按列选绝对值大的系数作为主元素，则将方程组中的两个方程相交换，原方程组变为,得到消元后的方程组,这时
12、,因而方程组的实际形式是,由此回代解出 ,这个结果是正确的,可见用高斯消去法解方程组时,小主元可能导致计算失败,因为用绝对值很小的数作除数,乘数很大,引起约化中间结果数量级严重增长,再舍入就使得计算结果不可靠了,故避免采用绝对值很小的主元素。以便减少计算过程中舍入误差对计算解的影响。,每一步选绝对值最大的元素为主元素，保证 。,Step k: 选取, If ik k then 交换第 k 行与第 ik 行; If jk k then 交换第 k 列与第 jk 列;, 消元,全主元素法不是按列选主元素，而是在全体待选系数中选取，则得全主元素法。,例3.3 用全主元素法解下列线组,解：选择所有系数
13、中绝对值最大的40作为主元素，交换第一、二行和交换第一、二列使该主元素位于对角线的第一个位置上，得,记笔记,计算m21=-19/40=0.475，m31=4/40=0.1 (5)- m21(4), (6)- m31(4) 消去x2 得,选4.9为主元素,计算m32=-1.525/4.9=-0.31122， (10)- m32(9)消去x2得 1.43366x1=6. 33161 (11),记笔记,保留有主元素的方程,进行回代,3.2.4.1 列主元素法,列主元素法就是在待消元的所在列中选取主元，经方程的行交换，置主元素于对角线位置后进行消元的方法。 即：,在高斯消元第k步之前，做如下的事情：,
14、若,交换 k 行和 j 行,行的交换，不改变方程组的解，同时又有效地克服了高斯消元的缺陷。,例3.4 用列主元素法解下列线性方程组,解：选择-20作为该列的主元素，,计算m21 =10/-20=-0.5 m31=1/-20=-0.05,(5)- m21(4), (6)- m31(4)得,选6为主元素,计算m32=1/6=0.16667， (10)- m32(9) 得 -2.34168x3=4.13332 (11),记笔记,保留有主元素的方程,进行回代,记笔记,列选主元素的计算方法与高斯消去法完全一样,不同的是在每步消元之前要按列选出主元。,例3.5 用矩阵的初等行变换求解解方程组,解: 用矩阵
15、的初等行变换求解,对增广矩阵 (下面带下划线元素为主元素),所以，等价的三角形方程组为：,回代求解，得：,3.2.5 高斯-约当（Jordan）消去法,高斯消去法有消元和回代两个过程，消去的是对角线下方的元素。当对消元过程稍加改变便可使方程组 化为对角阵 。,（3.8）,这时求解就不需要回代了，这种将主元素化为1，并用主元将其所在列的冗余元素全都消为0，即消去对角线上方与下方的元素，这种方法称为高斯-约当消去法，这时等号右端即为方程组的解。,算法核心：, 每步不计算 mik ，而是先将当前主元 akk(k) 变为 1;, 把 akk(k) 所在列的上、下元素全消为0;,计算方法,例3.6 用高斯-约当(Jordan)消去法求方程组的解,解 方程组相应的增广矩阵,列选主元,故得,定理3.4 设A为非奇异矩阵，方程组AX = I的增广矩阵为 C =A I ，如果对C应用高斯-约当消去法化为 I B，则 =B。 例3.7 用高斯-约当（Jordan）消去法求,的逆矩阵,解 C = A I =,
