线性方程组的迭代解法 消去法.ppt

第五章 线性方程组的迭代解法 6.1 消去法 方程组系数矩阵的分类 低阶稠密矩阵（例如，阶数不超过150） （一般用直接法来求解） 大型稀疏矩阵（即矩阵阶数高且零元素较多） （一般用迭代法来求解） 消去法的基本思想 通过将一个方程乘或除以某个常数，以及将两个 方程相加减这两种手续，逐步减少方程中变元的 数目，最终使每个方程仅含一个变元，从而得出 所求的解. 约当（Jordan)消去法 高斯（Gauss)消去法 约当消去法 方程形态的演变（0） 方程形态的演变（1） 方程形态的演变（1） 方程形态的演变（2） 方程形态的演变（2） 方程形态的演变（k-1） 方程形态的演变（k） 方程形态的演变（k） 方程形态的演变（n） 约当消去法第（1）步 约当消去法第（1）步 约当消去法第（k）步 约当消去法第（k）步 约当消去法的计算量与存储空间 高斯消去法 举例（一） 高斯消去法的基本思想 方程形态的演变（0） 方程形态的演变（1） 方程形态的演变（1） 方程形态的演变（2） 方程形态的演变（2） 方程形态的演变（k-1） 方程形态的演变（k） 方程形态的演变（k） 方程形态的演变（n） 高斯消去法的回代过程 高斯消去法的计算量分析 高斯主元素消去法 由高斯消去法知道，在消元的过程中可能 出现 的情况，这是消去法将无法进 行即使主元素 但很小时，用其作除 数，会导致其他元素数量级的严重增长和 舍入误差的扩散，最后也使得计算解不可 靠。 例2错误算法 例2改进算法 全主元高斯消去法 定理 定理1 定理1 定理1 定理1 例题2 写成向量表示形式 消元（1） 消元（2） 回代 矩阵的三角分解 矩阵的三角分解 矩阵的三角分解 矩阵的三角分解 矩阵的三角分解 矩阵的三角分解 矩阵的三角分解法 将高斯消去法改写为紧凑型时，可以直接 从矩阵A的元素得到计算L,U元素的递推公 式，而不需要任何中间步骤，这就是所谓 直接三角分解法。一旦实现了矩阵A的LU 分解，那么求解Ax=b的问题就等价于求解 两个三角形方程组 分解方式A=LU的唯一性 为保证分解方式A=LU的唯一性，要求将分解阵 L与U中的一个单位化，即令其主对角元素全为1 这里区分两种情况： 如果限定L为单位下三角阵，则称矩阵分解为Doolittle分解 如果限定U为单位上三角阵，这时矩阵分解成为Crout分解 矩阵的三角分解 矩阵的三角分解 直接利用矩阵乘法来计算 LU分解 直接利用矩阵乘法来计算 LU分解 例题1 例题2 例题3 例题4 追赶法 追赶法 追赶法 追赶法 解 解 追 赶 消元第k步的计算量为 (n-k+1)(n-k+1) 回代第k步的计算量为(k-1) 高斯消去法总的乘除运算量为： 第 k 步消元时选 A(k) 中绝对值最大的元素为主元，即 ① 先选取全主元： if ik ? k then 交换第 k 行和第 ik 行； if jk ? k then 交换第 k 列和第 jk 列； ③ 消元 列交换改变了 xi 的顺序，须记录交换次序，解完后再换回来。 全主元高斯消去法具有很好的稳定性，但选全主元比较费时，故在实际计算中很少使用。 定理1 定理2 假设方程组（4）是对角占优的，则（k=1，2，…，n）全不为 0. 假设方程组（4）对称并且是对角占优的，则 （k=1，2，…，n）全是主元素. 假设方程组（4）是对角占优的，则（k=1，2，…，n）全不为 0. 证： 变换以后仍然是对角占优的，以此类推，则命题得证。 用列主元消去法求解下列方程组 增广矩阵 选主元素 交换 消元 选主元素 交换 消元 得到方程 方程组的解 ? 高斯消元法的矩阵形式: Step 1: 记 L1 = L1－1 = 记 于是 Step n ? 1: Lk = 其中 记为 L 记 U = 定理1：（矩阵的三角分解）设A为n ? n实矩阵，如果 解AX = b用高斯消去法能够完成（限制不进行行的交 换，即 ），则矩阵A可分解 为单位下三角矩阵L与上三角知阵U的乘积。 A = LU 且这种分解是唯一的。 于是有： 容易验证： ( k = 1, …, n-1) 记： ，则 其中：L --- 单位下三角矩阵，U --- 上三角矩阵 LU 分解 (杜利脱尔Doolittle分解) ?比较等式两边的第一行得： u1j = a1j 比较等式两边的第一列得： ?比较等式两边的第二行得： 比较等式两边的第二列得： ( j = 1,…, n ) ( i = 2,…, n ) ( j = 2,