三角分解法.ppt

2 三角分解法 /* Matrix Factorization */, 高斯消元法的矩阵形式 /* Matrix Form of G.E. */：,Step 1:,2 Matrix Factorization Matrix Form of G.E.,单位下三角阵 /* unitary lower-triangular matrix */,A 的 LU 分解 /* LU factorization */,Hey hasnt GE given me enough headache? Why do I have to know its matrix form?!,When you have to solve the system for different with a fixed A.,Could you be more specific, please?,Factorize A first, then for every you only have to solve two simple triangular systems and .,2 Matrix Factorization Matrix Form of G.E.,证明：由1中定理可知，LU 分解存在。下面证明唯一性。,若不唯一，则可设 A = L1U1 = L2U2 ，推出,Upper-triangular,Lower-triangular With diagonal entries 1,注： L 为一般下三角阵而 U 为单位上三角阵的分解称为Crout 分解。 实际上只要考虑 A* 的 LU 分解，即 ，则 即是 A 的 Crout 分解。,2 Matrix Factorization Doolittle, 道立特分解法 /* Doolittle Factorization */： LU 分解的紧凑格式 /* compact form */,反复计算, 很浪费哦 ,2 Matrix Factorization Doolittle,固定 i : 对 j = i, i+1, , n 有,lii = 1,a,将 i ，j 对换，对 j = i, i+1, , n 有,b,一般采用列主元 法增强稳定性。但注意 也必须做相应的 行交换。,例： 求解(A,b)=,解:,第1步分解: 设 A = L U,所以,第2步: 先由 L y = b 求解 y,第3步: 再由 U x = y 求解 x,2 Matrix Factorization Tridiagonal System, 追赶法解三对角方程组 /* Crout Reduction for Tridiagonal Linear System */,Step 1: 对 A 作Crout 分解,直接比较等式两边的元素，可得到计算公式。,Step 2: 追即解 ：,Step 3: 赶即解 ：,与G.E.类似，一旦 i = 0 则算法中断，故并非任何 三对角阵都可以用此方法分解。,2 Matrix Factorization Tridiagonal System,Hey, what does diagonally dominant mean?,It means that the diagonal entries of the matrix are very LARGE.,Well, how large is LARGE?,They satisfy the following inequality:,