解线性方程组的矩阵三角分解法.pptVIP

* 第五章解线性方程组的直接方法 计算方法 —— 矩阵三角分解法 * 本讲内容 一般线性方程组 LU 分解与 PLU 分解 对称正定线性方程组 平方根法－－Cholesky 分解 对角占优三对角线性方程组 追赶法 * LU 分解 将一个矩阵分解成结构简单的三角形矩阵的乘积 矩阵的三角分解 矩阵的 LU(Doolittle) 分解 矩阵的 LDR 分解 克洛脱 (Crout) 分解 * 计算 LU 分解 利用矩阵乘法直接计算 LU 分解 L ? U = A ?比较等式两边的第一行得： u1j = a1j 比较等式两边的第一列得： ?比较等式两边的第二行得： 比较等式两边的第二列得： ( j = 1,…, n ) ( i = 2,…, n ) ( j = 2,…, n ) ( i = 3,…, n ) U 的第一行 L 的第一列 U 的第二行 L 的第二列 * 计算 LU 分解 第 k 步：此时 U 的前 k-1 行和 L 的前 k-1 列已经求出 直到第 n 步，便可求出矩阵 L 和 U 的所有元素。 比较等式两边的第 k 行得： ( j = k, …, n ) 比较等式两边的第 k 列得： ( i = k+1, …, n ) * LU 分解算法 算法 ：(LU 分解 ) for k = 1 to n end j = k, …, n i = k+1, …, n Matlab程序参见：ex51.m 乘除法运算量：(n3 - n)/3 为了节省存储空间，通常用 A 的绝对下三角部分来存放 L (对角线元素无需存储)，用 A 的上三角部分来存放 U * PLU 分解 矩阵的 PLU 分解 for k = 1 to n end i = k, k+1, …, n j = 1, 2, …, n i = k+1, …, n j = k+1, …, n Matlab程序：上机练习 * Cholesky 分解 对称正定矩阵的三角分解－－Cholesky 分解 定理：设 A 是对称矩阵，若 A 的所有顺序主子式都不为 0，则 A 可唯一分解为 其中 L 为单位下三角阵，D 为对角矩阵 A = LDLT 定理：（Cholesky分解）若 A 对称正定，则 A 可唯一分解为 其中 L 为下三角实矩阵，且对角元素都大于 0 A = LLT * 计算 Cholesky 分解 Cholesky 分解的计算 直接比较等式两边的元素 计算公式 * Cholesky 分解算法 for j = 1 to n end i = j +1, …, n 算法 ：(Cholesky 分解 ) * 平方根法 A 对称正定 算法 ：(解对称正定线性方程组的平方根法 ) 计算 A 的 Cholesky 分解 解方程：Ly = b 和 LTx = y i = 2, 3, …, n i = n-1, …, 2, 1 * 改进的 Cholesky 分解 计算公式 改进的 Cholesky 分解 * 改进的 Cholesky 分解 for j = 1 to n end i = j +1, …, n 算法 ：(改进的 Cholesky 分解 ) 优点：避免开方运算 * 改进的平方根法 A 对称正定 算法 ：(解对称正定线性方程组的改进的平方根法 ) 计算 改进的 Cholesky 分解 解方程：Ly = b 和 DLTx = y i = 2, 3, …, n i = n-1, …, 2, 1 * 追赶法 对角占优的三对角矩阵的 LU 分解 计算公式 i = 2, 3, …, n-1 * 追赶法 A 三对角矩阵（对角占优） 算法 ：(追赶法 ) i = 2, 3, …, n i = n-1, …, 2, 1 i = 2, 3, …, n-1 运算量：5n-4 2n – 3 次 2n 次 n – 1 次