《高斯消去法》PPT课件.ppt

第7章 解线性方程组的直接法,1 引言,常见的两种方程组（按系数矩阵的阶n）：,1、低阶稠密矩阵：,2、高阶稀疏矩阵（大型稀疏矩阵）,直接法,间接法或称迭代法,直接法：计算过程中没有舍入误差，经过有限步算术运算可,有效方法：,选主元消去法,解法：,求得方程组的精确解。,三角分解法,解法：,实际中有舍入误差,7.2 高斯消去法,解：,（古老或古典方法）,基本思想方法：,例3 用消去法解方程组,由行初等变换将系数矩阵约化为上三角矩阵；,用回代的方法求解方程组。,（1）消元：,（2）回代求解，得,m个方程，n个未知数的线性方程组的高斯消去法：,若记,（1）第1步(k=1)，,计算公式为：,（m-1)(n-1) 次乘法运算,高斯消去法：,设 ，计算乘数,(m-1)次除法运算,对增广矩阵 施行行初等变换：,（m-1)次乘法运算,记为,（2）第k步（ ）,设已完成上述消元过程第1步，第2步，第k-1步，（设,）得到与原方程组 等价的方程组,其中 元素计算公式为：,计算乘数,第 k步计算：,对 施行行初等变换,使 第k列 以下元素约化为零，,与 前k行元素相同， 左上角 阶阵,为上三角阵。,（m-k)次乘法运算,（m-k）次除法运算,（m-k)(n-k)次乘法运算,即 ，得到与原方程组等价的方程组,（3）继续上述约化过程，,（i） 当m n时，s = n，且设 ，则,（ii）当m = n时， s = n-1,且设 ，则,直到完成第S步计算，得到与原方程组等价的方程组,其中 为上梯形，具有以下三种情况：,(iii)当m n时，s = m-1，且设 ,则,说明：,(1)上述约化过程，可用矩阵变换来叙述，因,由 约化到 ,实际上是由乘数 构成初,与 相乘得到 ，即,等下三角阵,即,为高斯变换，,（上梯形）,条件下存在高斯变换 ，使将A 约化为上梯形。,因此上述约化过程，用矩阵变换来叙述为,（2）元素 称为约化的主元素，且原方程组约化为等价方,由消元过程和回代过程构成了高斯消去法。,程组 过程称为消元过程，,用回代法解（3.9）,（3）若Ax=b,其中 非奇异矩阵，这时 可能为零。,所以A第1列一定存在元素,此时可交换（ ）第1 行与第i1行元素（即 ），,然后进行消元计算。于是 ，且 右下角矩阵为n-1阶,时，可采用上述方法同样处理。,非奇异矩阵。当 时，直接进行消元计算,当,（用高斯变换约化）,结论：,定理6,则存在初等下三角阵 ,使,(上梯形).,(1)如果 ，则通过高斯消去法（不进行,定理7,交换两行的初等变换）将 化为等价的三角方程组。,回代计算：,消元计算：,（2）如果A为非奇异矩阵，则可通过带行交换的高斯消去,Ganss消去法中,注：,则要求在算法中增加一判断框，并要交换两行元素（或者说交换,两个方程）。,法，将 化为等价的三角形方程组（3.12）。,计算量：,回代计算量：,消元计算量(k=1,2,n-1)：,除法：,乘除法：,乘法：,定理8,（2）若,反之亦对。,（1）若 顺序主子式 ，则,（必要性 ）,证明：,用归纳法证明。,当 时， 显然成立，,假设对 时成立，即 ,下证对k 成立，即,由归纳法假设,再由Ganss消去法 ，得,是否是零，可以根据顺序主子式来判断。,反之，若,即定理对k亦成立。,由Ganss消去法知(3.13)成立，则,（2）若,于是,对k= 1,2,n时，(3.13)成,理解高斯消去法并会用该方法解方程组。,本节重点：,立，则,3 高斯消去法,（古老或古典方法）,高斯消去法：,第k步（ ）,设已完成上述消元过程第1步，第2步，第k-1步，（设,）得到与原方程组 等价的方程组,其中 元素计算公式为：,计算乘数,第 k步计算：,对 施行行初等变换,使 第k列 以下元素约化为零，,（m-k)次乘法运算,（m-k）次除法运算,（m-k)(n-k)次乘