数值分析讲矩阵的角分解法.pptVIP

作业 教材第45页习题5、6、8 掌握（或者自己实现）Doolittle法和追赶法求解线性方程组的程序 课后阅读：《C数值算法》第二章相关内容 数值分析 朱立永 北京航空航天大学 数学与系统科学学院 Email: numerical_analysis@ Password:beihang 答疑时间：星期四下午2:30－5:30 答疑地点：主216 第四讲矩阵的三角分解法 第二章 线性方程组的解法 In Scientific Computing ↓ Large Linear Systems Ax=b as sub-problems/ as intermediate steps Gauss-Seidel method Jacobi method SOR method Conjugate Gradient method for symmetric systems Gaussian elimination LU factorization Cholesky factorization GMRES GCR Bi-CG CGS Bi-CGSTAB Bi-CGSTAB2 GPBi-CG Bi-CGSTAB(L) 回顾高斯消去法 Gauss消元法的第k步： 从矩阵理论来看，相当于左乘矩阵 指标为k的初等下三角阵 因此，整个Gauss消元法相当于左乘了一个单位下三角阵 所以有 L为单位下三角阵，U为上三角阵 矩阵的直接三角分解(LU分解)对解线性方程组有什么帮助？ 三角方程组，易于求解 1、Doolittle分解 L为单位下三角，U为上三角 比较第1行： 比较第1列： 比较第2行： 比较第2列： 比较第k行： 比较第k列： K-1次 K-1＋1次 分解过程完毕，加上两次反代过程 总运算量为： 存储在矩阵的原来位置，且不影响计算 L为下三角，U为单位上三角 两次反代过程 比较第k列： 比较第k行： 定理2.4 若矩阵A非奇异，则存在置换矩阵Q， 使得QA可以作Doolittle分解 QA=LU 其中L是单位下三角矩阵，U是上三角矩阵。 选主元直接三角分解法 当需选主元时，PA=LU. 设第r-1步已完成,就有 选主元三角分解算法： 求解Ly=Pb及Ux=y的算法： 三对角阵的追赶法（A的前n-1个顺序主子式非零） 在数值求解常微分方程边值问题、热传导方程和建立三次样条函数时，都会要解三对角方程组：AX=b 所以，有计算过程如下： 说明: 稳定性（对角占优）；运算量5n-4次乘除法； 存贮（一维数组）. 平方根法 应用有限元法解结构力学问题时，最后归结为求解线性代数方程组，系数矩阵往往对称正定。平方根法是一种对称正定矩阵的三角分解法，广泛用于求解系数矩阵为对称正定的线性代数方程组。 设A为对称矩阵,且顺序主子式不为零，则 若A为对称正定矩阵,则 解AX=b的平方根法:… 称为平方根法， 因为带了开方运算，因此不常用 Cramer rule Gauss elimination LU factorization Gauss-Jordan elimination Square root /improved square root 追赶法 (n+1)! n3/3 n3/3 n3/2 n3/6 5n-4 Row/column/complete Pivoting Only eliminating elements in a column below the diagonal one No pivoting Directly factorization column pivoting Eliminating elements in a row except for the diagonal element A symmetric and positive definite No pivoting A三对角，弱 对角占优 Summary 直接法内容总结 1：用LU分解（Doolittle）求解线性代数方程组等价于顺序Gauss 消元法：Ax＝b ? LUx＝b ? Ux＝y，Ly＝b； 2：用选主元LU分解（Doolittle）求解线性代数方程组等价于选列主元Gauss消元法：Ax＝b ? LUx＝Qb ? Ux＝y，Ly＝Qb； 3：对上半带宽为s、下半带宽为r的带状矩阵作LU分解，那么L为下半带宽为r的下三角矩阵，U为上半带宽为s的上三角矩阵； 直接法内容总结 4：对上半带宽为s、下半带宽为r的带状矩阵作选主元LU（Doolittle）分解，将破坏L和U的带状性质； 5：对上半带宽为1、下半带宽为1的三对角带状矩阵，可以有快速追赶法； 6：对非对角占