5.1高斯消去法解析ppt课件

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