《高斯消去法解析》由会员分享，可在线阅读，更多相关《高斯消去法解析（38页珍藏版）》请在金锄头文库上搜索。
1、第五章 线性方程组的直接解法,第五章 线性方程组的直接解法,线性方程组的直接解法,高斯消去法,矩阵三角分解法,向量范数和矩阵范数,误差分析,线性方程组的概念,在科学研究和工程技术中所提出的计算问题中，线性 方程组的求解问题是基本的，常见的，很多问题如插值函 数，最小二乘数据拟合，构造求解微分方程的差分格式等 ，都包含了解线性方程组问题，因此，线性方程组的解法 在数值计算中占有较重要的地位。,设n阶线性方程组：,其矩阵形式为：,Ax=b (5-2),其中：,求解Ax = b，曾经学过高斯（Gauss）消元法，克莱姆（Cramer）法则，矩阵变换法等，但已远 远满足不了实际运算的需要，主要体现两个
2、方面：一是运算的快速和准确，其次是方程组的个数增大时的计算问题。如何建立能在计算机上可以实现的有效而实用的解法，具有极其重要的意义，我们也曾指出过，Cramer法则在理论上是绝对正确的，但当n较大时，在实际计算中却不能用。,线性方程组的概念（续）,如果线性方程组Ax = b的系数行列式不为零，即det(A) 0，则该方程组有唯一解。,线性方程组的数值解法,解线性方程组的数值方法大致分为两类：,请注意：由于在计算中某些数据实际上只能用有限位小 数，即不可避免地存在着舍入误差的影响，因 而即使是准确解法，也只能求到近似解。 直接法在求解中小型线性方程组（100个），特别是系数矩阵为稠密型时，是常用
3、的、非常好的方法。,直接法：指假设计算过程中不产生含入误差，经过有 限步四则运算可求得方程组准确解的方法。,2. 迭代法：从给定的方程组的一个近似值出发，构造某种算法逐步将其准确化，一般不能在有限步内得到准确解。,这一章介绍计算机上常用的直接法，它们都是以Gauss消元法为基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。,AX=b,直接法,迭代法,列主元 消去法,Gauss 消去法,全主元 消去法,LU分解法,知识结构框图,第1节 高斯（Gauss）消去法,高斯（Gauss）消元法,高斯消元法是一个古老的直接法,由它改进得到的选主元的消元法,是目前计算机上常用于求低阶稠密矩阵方程组
4、的有效方法,其特点就是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题,高斯（Gauss）消去法,一、高斯消去法,，下例说明其基本思想:,例1,解线性方程组：,解：消去x1，进行第一次消元：首先找乘数，以 -12乘第一个方程加到第二个方程，以18乘第一个方程加到第三个方程上可得同解方程组：,举 例,例1（续）,上述Gauss消元法的基本思想是：先逐次消去变量，将方程组化成同解的上三角形方程组，此过程称为消元过 程。然后按方程相反顺序求解上三角形方程组，得到原 方程组的解，此过程称为回代过程。,再消一次元得：,二次消元后将方程化为 倒三角形式，然后进行 回代容易解出： x3 = 3,
5、 x2 = 2, x1 = 1。,我们的目的，是要总结归纳出一般情况下的n阶线性方程 组的消元公式和回代求解公式，从而得到求解n阶线性方 程组的能顺利在计算机上实现的行之有效的算法。,上三角方程组的一般形式是：,目标,高斯（Gauss）消去法,高斯（Gauss）消去法,对n阶线性方程组,转化为等价的(同解)的三角方程组.,称消元过程，逐次计算出 称回代过程。,高斯（Gauss）消去法,相当于第i个方程减第一个方程数新的第i方程同解！第一方程不动！,Gauss 消去法计算过程分析,Gauss 消去法计算过程分析,上述消元过程除第一个方程不变以外, 第2第 n 个方程全消去了变量 1，而系数 和常
6、数项全得到新值：,高斯（Gauss）消去法,高斯（Gauss）消去法,高斯（Gauss）消去法,高斯（Gauss）消去法,高斯（Gauss）消去法,第n-1步消去过程后，得到等价三角方程组。,高斯（Gauss）消去法,高斯（Gauss）消去法,消去过程算法,高斯（Gauss）消去法,回代过程算法,高斯（Gauss）消去法,例2,举 例,举 例,举 例,二、Gauss消元法的计算量,由于在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。 由消元法步骤知，第k次消元需作nk次除法，作 (n k)(n k + 1)次乘法，故消元过程中乘除法运算量为：,所以Gauss 消去
7、法的 乘除法总运算量为：,Gauss法与Cramer法则的计算量比较,Gauss 消元法的乘 除法总运算量为：,与我们曾经介绍的Cramer法则的乘除法总运算量 (n21)n!+n 相比，由下表可知：当阶数越高时，Gauss消 元法所需乘除法次数比Cramer法则要少得多：,Gauss 消元法的优缺点：,但其计算过程中，要求akk(k)（称为主元素）均不为零，因而适用范围小，只适用于从1到n 1阶顺序主子式均不为零的矩阵A，计算实践还表明，Gauss消元法的数值稳定性差，当出现小主元素时，会严重影响计算结果的精度，甚至导出错误的结果。,Gauss消元法简单易行。,三、高斯消去法实现的条件,四、
8、主元素法,4.1 引入主元素的必要性 对线性方程组AX = b，若其系数行列式 det(A) 0，则该方程组有唯一 解，但是这一条件 不能保证所有主元素都不等于零，只要某一主元 素等于零，就不能用Gauss消元法求解该方程组， 即使所有主元素不等于零，但 某一主元素的绝对 值很小时，Gauss消元法也是不适用的。如下例：,例3,例2（续1）,解：为减小误差，计算过程中保留3位有效数字。 按Gauss消元法步骤：,第一次消元后得同解方程组：,第二次消元后得同解方程组,回代得解，x3 = 2.02，x2 = 2.40，x1 = 5.80。 容易验证，方程组（1）的准确解为： x1 = 2.60，
9、x2 = 1.00，x3 = 2.0。,显然两种结果相差很大。,若在解方程组前，先交换方程的次序， 如将（1）交换一行与二行改写成如下所示：,再用Gauss消元法，顺序消元后得同解方程组：,回代得解：x3 = 2.00，x2 = 1.00，x1 = 2.60 与准确解相同。,例3（续2）,例3两种解法的误差分析,在例3中，对(1)的方程进行顺序消元时， 主元a(1)11=0.50，a(2)22=0.100都比较小，以它们作 除数就增长了舍入误差,而导致计算结果不准确。,产生上述现象的原因在于舍入误差，当|a(k)kk| 很小时，进行第k次消元，要用|a(k)kk|作除数，这 样就可能增大舍入误
10、差造成溢出停机，或者导致 错误的结果。,为了在计算过程中，抑制舍入误差的增长， 应尽量避免小主元的出现。如例3的第二种解法, 通过交换方程次序，选取绝对值大的元素作主元 基于这种思想而导出主元素法。,4.2 列主元素法,为简便起见，对方 程组（5-1），用 其增 广矩阵：,表示，并直接在增广 矩阵上进行运算。,列主元素法的具体步骤如下：,列主元素法,如此经过n1步，增广矩阵（5-3）被化成上三角形，然后由回代过程求解。 在上述过程中，主元是按列选取的，故称为列主元法。例3中的第二种解法就是按列主元法进行的。,4.3 全主元素法,经过nk次消元后，得到与方程组（5-1）同解的上三角形方程组，再由回代过程求解。,主元素法举例,例4,计算过程保留三位小数。,1. 用高斯消元法解方程组,2. 用列主元素法解方程组：,作 业,
