ch_线性方程组求解.PPTVIP

? 克兰姆(Cramer)法则： 运算量(乘除)： ?高斯消元法(Gauss)： 运算量(乘除) Gauss: 3060次； Cramer: * 解线性方程组的直接法 AX = b （3.1） §1 高斯消去法 1．三角形方程组的解法 （3.2） （3.3） 2．高斯消去法 消元公式 回代公式 列主元消去法计算步骤： 1、输入矩阵阶数n，增广矩阵 A(n,n+1); 2、对于 (1) 按列选主元：选取 l 使 (2) 如果 ，交换 A(n,n+1) 的第k行与底l 行元素 (3) 消元计算 ： 3、回代计算 4．无回代过程的主元消去法 算法： 第一步：选主元，在第一列中选绝对值最大的元素，设第k行为主元行， 将主元行换至第一行，将第一个方程中x1的系数变为1，并从 其余n – 1个方程中消去x1。 第二步：在第二列后n – 1个元素中选主元，将第二个方程中x2的 系数变为1，并从其它n – 1个方程中消去x2。 第k步：在第k列后n – k个元素中选主元，换行，将第k个方程xk的系数 变为1，从其它n - 1个方程中消去变量xk， ………… 消元公式为： 对k = 1, 2, …, 按上述步骤进行到第n步后，方程组变为： 即为所求的解 5．无回代消去法的应用 （1）解线性方程组系 设要解的线性方程组系为： AX = b1, AX = b2, … AX = bm 上述方程组系可以写为 AX = B = (b1, …, bm) 因此 X = A-1B 即为线性方程组系的解。 在计算机上只需要增加几组右端常数项的存贮单元， 其结构和解一个方程组时一样。 行 系数 右端 （2）求逆矩阵 设A = (aij)n?n是非奇矩阵，?A? ? 0，且令 由于 AA-1 = AX = I 因此，求A-1的问题相当于解下列线性方程组 相当于（1）中m = n, B = I 的情形。 （3）求行列式的值 用高斯消去法将 ?A?化成 ? 高斯消元法的矩阵形式: Step 1: §2 矩阵的三角分解及其在解方程组中的应用 记 L1 = L1－1 = 记 于是 Step n ? 1: Lk = 其中 记为 L 记 U = 定理1：（矩阵的三角分解）设A为n ? n实矩阵，如果 解AX = b用高斯消去法能够完成（限制不进行行的交 换，即 ），则矩阵A可分解 为单位下三角矩阵L与上三角知阵U的乘积。 A = LU 且这种分解是唯一的。 ? 杜立特分解法 /* Doolittle Factorization */： —— LU 分解的紧凑格式 通过比较法直接导出L 和 U 的计算公式。 思路 直接三角分解法解AX = b的计算公式 对于r = 2, 3, …, n计算 （2）计算U的第r行元素 （3）计算L的第r 列元素 (r ? n) (1) (4) (5) §4 平方根法 1．矩阵的LDR分解 定理3：如果n阶矩阵A的所有顺序主子式均不等于零， 则矩阵A存在唯一的分解式A = LDR其中L和R分别是 n阶单位下三角阵和单位上三角阵，D是n阶对角元素 的不为零的对角阵，上述分解也称为A的LDR分解。 2．平方根法 如果A为对称正定矩阵，则存在一个实的非奇异 下三角矩阵，使A=LLT ，且当限定的对角元素为正时， 这种分解是唯一的。 定理4：（对称正定矩阵的三角分解） 将对称 正定阵 A 做 LU 分解 U = uij = u11 uij / uii 1 1 1 u22 unn 记为 A 对称 即 记 D1/2 = 则 仍是下三角阵 定理 设矩阵A对称正定，则存在非奇异下三角阵 使得 。若限定 L 对角元为正，则分解唯一。 注： 对于对称正定阵 A ，从 可知对任意k ? i 有 。即 L 的元素不会增大，误差可控，不需选主元。 用平方根法解线性代数方程组的算法 （1）对矩阵A进行Cholesky分解，即A=LLT，由矩阵乘法： 对于 i = 1, 2,…, n 计算 （2）求解下三角形方程组 （3）求解LTX = y §5 向量和矩阵的范数 1．向量的范数 定义1：设X ? R n，??Ｘ?? 表示定义在Rn上的一个实值函数， 称之为X的范数