数值分析第五章线性方程组直接解法.ppt

* 线性方程组的病态矩阵 考虑线性方程组 Ax=b，如果 A 或 b 的微小变化会导致解的巨大变化，则称此线性方程组是病态的，并称矩阵 A 是病态的，反之则是良态的。 病态矩阵 例： 10000? * 理论分析 理论分析： 设 又 (1)由于右端项的扰动而引起的解的变化 (2)由于系数矩阵的扰动而引起的解的变化 设 Ax = b 的条件数 矩阵A 的条件数 * 矩阵条件数 定义：设 A 非奇异，则称 为 A 的条件数。 矩阵的条件数 定理：考虑线性方程组 Ax=b，设 A 是精确的，b 有微小的变化 ?b，此时的解为 x + ?x ，则 矩阵条件数 定理：考虑线性方程组 Ax=b，设 b 是精确的，A 有微小的变化 ?A，此时的解为 x + ?x ，则 当 ?A 充分小时，不等式右端约为 * 矩阵条件数 条件数与范数有关，常用的有无穷范数和2-范数 Cond(A)2 称为谱条件数，当 A 对称时有 * 条件数性质 条件数的性质： (1) Cond(A) ? 1 (2) Cond(cA) = Cond(A)，其中 c 为非零常数 (3) 当 A 是正交矩阵时，Cond2(A) = 1 (4) Cond2(PA) = Cond2(AP)=Cond2(A)， 其中 P 为正交矩阵 * 举例 例： 计算 Cond(A)? 和 Cond(A)2 解： Cond(A)?=||A-1|| ? ||A|| ? ? 4?104 Cond(A)2=?max / ?min ? 4?104 A 对称，且 * 举例 例：计算 Cond(Hk)? 其中 H 为 Hilbert 矩阵 解： k=1 时， Cond(H1)?=1 k=2 时， Cond(H2)?=27 k=3 时， Cond(H3)?=748 Cond(H4)?=28375 Cond(H10)?=3.5?1013 * Ax = b ( i = n , …, 1 ) ( i = 1, …, n ) 两次回代过程求出方程组的解： 运算量: n2 加LU分解 总运算量： LU分解求解线性方程组 * 解： 例 用LU分解求线性方程组Ax=b的解，其中 令A = LU，由LU分解可得 回代：解Ly = b得：y =[2, 8, 18, 24]T 解Ux = y得：x =[-1, 1, -1, 1]T LU分解求解线性方程组 * 对称正定矩阵的Cholesky 分解 设A为对称矩阵,且顺序主子式不为零，做LU分解 * 若A为对称正定矩阵,则 对称正定矩阵的Cholesky 分解 * 对称正定矩阵的三角分解－－Cholesky 分解 定理：设 A 是对称矩阵，若 A 的所有顺序主子式都不为 0，则 A 可唯一分解为 其中 L 为单位下三角阵，D 为对角矩阵 A = LDLT 定理：（Cholesky分解）若 A 对称正定，则 A 可唯一分解为 其中 L 为下三角实矩阵，且对角元素都大于 0 A = LLT 对称正定矩阵的Cholesky 分解 * 计算 Cholesky 分解 Cholesky 分解的计算 直接比较等式两边的元素 计算公式 * Cholesky 分解算法 for j = 1 to n end i = j +1, …, n 算法 ：(Cholesky 分解 ) 运算量:n3/6 +n2/2 +n /3 * Cholesky 分解算法 例 对矩阵 作Cholesky分解 解 * 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 * 例 利用改进平方根法求解方程组 解： 改进的平方根法 * 求得 解线性方程组 改进的平方根