数值分析研究生第四章线性方程组的直接解法一.pptVIP

* 上页 下页 返回 第四章 线性方程组的直接解法（一） 第一节 实际问题的导入 第三节 矩阵的三角分解法 第二节 高斯消去法 第四节 解三对角方程组的追赶法 求解 §1 实际问题的导入 ? Cramer法则：计算量太大. ?线性方程组的系数矩阵可分为： 低阶稠密矩阵——阶数不超过500，零元素很少； 大型稀疏矩阵——阶数高且零元素多. ?解线性方程组的方法： 直接法——系数矩阵是低阶稠密矩阵的线性方程组及某些大型稀疏矩阵的线性方程组； 迭代法——系数矩阵是大型稀疏矩阵的线性方程组. §2 高斯消去法 一、高斯消去法 思路 首先将A化为上三角阵 ，再回代求解. = 消元 记 Step 1：设 ，计算因子 将增广矩阵第 i 行 ? mi1 ? 第1行，得到 其中 Step k：设 ，计算因子 且计算 共进行 ？ 步 n ? 1 回代 定理 若A的所有顺序主子式 均不为0，则高斯消元无需换行即可进行到底，得到唯一解. 注：事实上，只要 A 非奇异，即 A?1 存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解. 二、选主元消去法 例1 单精度解方程组 /* 精确解为 和 */ 8个 8个 用高斯消元法计算： 8个 小主元 可能导致计算失败. ? 全主元消去法 每一步选绝对值最大的元素为主元素，保证 . Step k: ① 选取 ② If ik ? k then 交换第 k 行与第 ik 行; If jk ? k then 交换第 k 列与第 jk 列; ③ 消元. 注：列交换改变了 xi 的顺序，须记录交换次序，解完后再换回来. ? 列主元消去法 省去换列的步骤，每次仅选一列中最大的元. 例2 ? 注：列主元法没有全主元法稳定. 例3 注意：这两个方程组在数学上严格等价. ? ? 标度化列主元消去法 对每一行计算　　　　　 。为省时间，si 只在初始时计算一次. 以后每一步考虑子列 中　 最大的 aik 为主元. 注：稳定性介于列主元法和全主元法之间. 实际应用中直接调用高斯消元法解3阶线性方程组的结果： 结合全主元消去后的结果： ? 高斯-若当消去法 与高斯消元法的主要区别： ? 每步不计算 mik ，而是先将当前主元 akk(k) 变为 1; ? 把 akk(k) 所在列的上、下元素全消为0; ? 运算量 由于计算机中乘除 运算的时间远远超过加减 运算的时间，故估计某种算法的运算量时，往往只估计乘除的次数，而且通常以乘除次数的最高次幂为运算量的数量级. ?高斯消元法: Step k：设 ，计算因子 且计算 共进行n ? 1步 (n ? k) 次 (n ? k)2 次 (n ? k) 次 (n ? k) (n ? k + 2) 次 消元乘除次数： 1 次 (n ? i +1) 次 回代乘除次数： 高斯消元法的总乘除次数为 ，运算量为 级. ?全主元消去法 : 比高斯消元法多出 　 ，保证稳定，但费时. ?列主元消去法 : 比高斯消元法只多出 　 ，略省时，但不保证稳定. ?标度化列主元消去法 : 比高斯消元法多出 　 除法和 ，比列主元法稳定. 但若逐次计算 si(k)，则比全主元法还慢. ?高斯-若当消去法 : 运算量约为 . 故通常只用于求逆矩阵，而不用于解方程组. 求逆矩阵即 . §3 矩阵的三角分解法 ? 高斯消元法的矩阵形式 ： Step 1: 记 L1 = ，则 Step n ? 1: 其中 Lk = 一、矩阵的LU分解 记为 L 单位下三角阵 记 U = 定理 若A的所有顺序主子式 均不为0，则 A 的 LU 分解唯一（其中 L 为单位下三角阵）. 证明：由§1中定理可知，LU 分解存在. 下面证明唯一. 若不唯一，则可设 A = L1U1 = L2U2 ，推出 一般上三角阵 单位下三角阵 ? 注： L 为一般下三角阵而 U 为单位上三角阵的分解称为Crout 分解. 实际上只要考虑 A* 的 LU 分解，即