2.1高斯消元法ppt课件

第二章解线性方程组的直接解法 高斯消元法解三对解方程组的追赶法方程组的病态问题三角分解法 本章介绍求解n元线性代数方程组的直接解法 并研究舍入误差对解的影响 2 1 这里假定系数行列式不为零 方程组的解存在且唯一 所谓直接法 就是不计舍入误差时 通过有限次算术运算能求得准确解的方法 克莱姆法就是一种直接法 只是方程组阶数较高时它的运算量太大 实际无法使用 线性方程级 2 1 常简写成矩阵形式Ax b其中A x b 2 1高斯消去法2 1 1高斯消去法的基本步骤高斯 Gauss 消去法其实将一般的线性方程组变换为三角形 上三角 方程组求解问题 消元法 只是步骤规范 便于编写计算机程序 中国东汉初年诞生的 九章算术 记载了求解线性代数组的消去法 比国外早1500年 例解方程组解 步骤如下 将第一个方程乘 5 7 分别加于第二 第三方程 消去未知量x1 得同解方程组 将所得方程组的第二方程乘 加到第三方程 消去未知量x2 得同解方程组 这就是上三角方程组 它很容易求解 由第三方程得x3 2 代入第二方程可得x2 5 再代入第一方程得x1 3 一般高斯消去法包括两过程 先把方程组化为同解的上三角形方程组 再按相反顺序求解上三角形方程组 前者称消去或消元过程 后者称回代过程 消去过程实际上是对增广矩阵作行初等变换 如上例可表示为 对一般的n阶方程组 消去过程分n 1步 第一步消去a11下方元素 第二步消去a22下方元 素 第n 1步消去an 1 n 1下方元素 即第k步将第k行的适当倍数加于其后各行 或可说是从k 1 n行减去第k行的适当倍数 使它们的第k列元素变为零 而其余列元素减去第k行对应列元素的倍数 对k 1 n 1 步 做对i k 1 n 行 做令 适当倍数 对j k 1 n 1 列 令 因此 如把增广矩阵变换前后都在计算机上用同一数组A存储 则消去过程可写为 回代过程是解同解的上三角形方程组 回代过程可写为 2 1 2高斯消去法的运算量高斯消去法比起克莱姆法则和约当消去法 主要长处就是运算量较少 用克莱姆法则求解n阶线性方程组 需计算n 1个行列式 每个行列式是n 个乘积之和 而每个乘积是n个元素相乘 因此共需乘法次数 n 1 n n 1 n 1 n 1 当n 20时 n 1 n 1 9 7 1020 要完成这么多次乘法 在每秒做一亿次乘法运算的计算机上 也需30 8万年 因此克莱姆法则在实际计算中不适用 高斯消去法消去过程运算量 消元过程所用乘 除法次数为 对k 1 n 1 步 做对i k 1 n 行 做令 适当倍数 对j k 1 n 1 列 令 回代过程运算量 回代过程求xn需1次除法 求xn 1需1次乘法 1次除法 求需n 1次乘法1次除法 因此共需乘除次数 两过程共需乘除次数 当n 20时 N 3060 显然比克莱姆法则少得多 线性代数教材讲授线性方程组解法时 往往提倡用行初等变换把增广矩阵化为最简形 如上例方程组 多用如下变换 变换结束后时增广矩阵最后一列就是解 不需回代 这种解法称为约当消去法 它容易学习掌握 也容易编写计算机程序 其计算过程可写为 不过这种解法需要乘除次数 比高斯消去法多相当于多高斯消去法约一半的运算量 因此除非方程组的阶数n较小 计算机上不用约当消去法 上面比较了三种解法的乘除次数 一般算法乘除次数与加减次数相差不多 而且计算机上乘除运算比加减运算费时间 所以通常只比较乘除次数 2 1 3选主元消去法高斯消去法的弊端 高斯消去法消去过程中 第k步中求n k个倍数数用到的除数 称为主元 它若为零或接近于零 计算机将 溢出 而停止计算 或产生较大误差 例如方程组 准确到九位小数的解是x1 0 250001875 x2 0 499998749 若在5位计算机上按高斯消去法求解 则有 回代解得x1 0 00000 x2 0 50000 显然严重失真 造成这种结果的原因 就是小主元的出现 用它用除数产生大乘数 数乘大数变大数 大数吃小数产生舍入误差 如3 4 105 399997 106 0 4000 从而有误差 求出x2代回第一个方程时 因10 5x1 2x2 1 10 5x1 2x2 1两式相减得10 5 x1 x1 2 x2 x2 0 可见 x1 x1 200000 x2 x2 表明x1的误差被放大200000倍 x1 自然失真 列主元消去法为了避免出现小主元 在每次消元前进行选主元 即每次消元前先选取所要消元的列中绝对值最大的元素作为主元 然后再消元 具体为 在第k步的第k列的元素中选主元 即在其中找出绝对值最大的元素 然后交换第k行和第p行 继续进行消元过程 交换行相当于改变方程顺序 不会影响原方程组的解 把它应用于上例 有 回代得解 0 5 0 25 接近真解 算法 第一步 求主元apk使得第二步 判断 apk 则输出错误信息并停机 否则转三 第三步 判断若 则交换增广矩阵中第p行与第k行 否则不交换 也可在第k步时 在第k行元素akk ak k 1 akn中选绝对值最大的元素akq 交换k p列 然后继续消去过程 这种消去法称行主元法也可在第k步时 在第k n行及第k n列的所有元素akk ak k 1 akn ak 1k ak 1 k 1 ak 1n ann中选绝对值最大的元素apq 交换k p行和k q列 然后继续消去过程 这种消去法称全主元法 不过交换两列相当于改变未知量顺序 所以需用一数组 专门记录未知量顺序及其变化 并在最后调整解的顺序 使解中n个数与未知量正确对应 三种主元消去法选取绝对值相对最大的元素作主元 保证了倍数c的绝对值不超过1 也有利于控制误差的传播 所以稳定性较好 三种主元法中全主