51高斯消去法解析.pptxVIP

第五章 线性方程组的直接解法331324线性方程组的直接解法 第五章 线性方程组的直接解法 高斯消去法 矩阵三角分解法向量范数和矩阵范数误差分析 在科学研究和工程技术中所提出的计算问题中，线性方程组的求解问题是基本的，常见的，很多问题如插值函数，最小二乘数据拟合，构造求解微分方程的差分格式等，都包含了解线性方程组问题，因此，线性方程组的解法在数值计算中占有较重要的地位。 线性方程组的概念 设n阶线性方程组： 其矩阵形式为：Ax=b(5-2)其中： 如果线性方程组Ax = b的系数行列式不为零，即det(A) ? 0，则该方程组有唯一解。 求解Ax = b，曾经学过高斯（Gauss）消元法，克莱姆（Cramer）法则，矩阵变换法等，但已远远满足不了实际运算的需要，主要体现两个方面：一是运算的快速和准确，其次是方程组的个数增大时的计算问题。如何建立能在计算机上可以实现的有效而实用的解法，具有极其重要的意义，我们也曾指出过，Cramer法则在理论上是绝对正确的，但当n较大时，在实际计算中却不能用。线性方程组的概念（续） 解线性方程组的数值方法大致分为两类： 直接法：指假设计算过程中不产生含入误差，经过有 限步四则运算可求得方程组准确解的方法。2.迭代法：从给定的方程组的一个近似值出发，构造某种算法逐步将其准确化，一般不能在有限步内得到准确解。 这一章介绍计算机上常用的直接法，它们都是以Gauss消元法为基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。 请注意：由于在计算中某些数据实际上只能用有限位小 数，即不可避免地存在着舍入误差的影响，因 而即使是准确解法，也只能求到近似解。 直接法在求解中小型线性方程组（≤100个），特别是系数矩阵为稠密型时，是常用的、非常好的方法。 线性方程组的数值解法否是是知识结构框图迭代法全主元消去法列主元消去法Gauss消去法AX=b直接法LU分解法高斯（Gauss）消元法第1节 高斯（Gauss）消去法高斯（Gauss）消去法一、高斯消去法 高斯消元法是一个古老的直接法,由它改进得到的选主元的消元法,是目前计算机上常用于求低阶稠密矩阵方程组的有效方法,其特点就是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题举 例，下例说明其基本思想: 例1解线性方程组： 解：消去x1，进行第一次消元：首先找乘数，以-12乘第一个方程加到第二个方程，以18乘第一个方程加到第三个方程上可得同解方程组： 例1（续）再消一次元得： 二次消元后将方程化为倒三角形式，然后进行回代容易解出： x3 = 3, x2 = 2, x1 = 1。 上述Gauss消元法的基本思想是：先逐次消去变量，将方程组化成同解的上三角形方程组，此过程称为消元过程。然后按方程相反顺序求解上三角形方程组，得到原方程组的解，此过程称为回代过程。 我们的目的，是要总结归纳出一般情况下的n阶线性方程组的消元公式和回代求解公式，从而得到求解n阶线性方程组的能顺利在计算机上实现的行之有效的算法。 目标高斯（Gauss）消去法上三角方程组的一般形式是： 高斯（Gauss）消去法称消元过程，逐次计算出 称回代过程。高斯（Gauss）消去法对n阶线性方程组转化为等价的(同解)的三角方程组.Gauss 消去法计算过程分析Gauss 消去法计算过程分析相当于第i个方程减第一个方程×数→新的第i方程—同解！第一方程不动！ 高斯（Gauss）消去法 上述消元过程除第一个方程不变以外, 第2—第 n 个方程全消去了变量 ?1，而系数 和常数项全得到新值：高斯（Gauss）消去法高斯（Gauss）消去法高斯（Gauss）消去法高斯（Gauss）消去法高斯（Gauss）消去法第n-1步消去过程后，得到等价三角方程组。高斯（Gauss）消去法高斯（Gauss）消去法消去过程算法高斯（Gauss）消去法回代过程算法例2举 例举 例举 例二、Gauss消元法的计算量 由于在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。 由消元法步骤知，第k次消元需作n?k次除法，作(n ? k)(n ? k + 1)次乘法，故消元过程中乘除法运算量为： 所以Gauss 消去法的乘除法总运算量为： Gauss 消元法的乘除法总运算量为： 方程组阶数3102050Gauss消元法运算量17430306044150Cramer法则运算量513592512109.7×10207.6×1067Gauss法与Cramer法则的计算量比较 与我们曾经介绍的Cramer法则的乘除法总运算量 (n2?1)n!+n 相比，由下表可知：当阶数越高时，Gauss消元法所需乘