§2三角分解法/ Matrix Factorization >高斯消元法的矩阵形式/Matiⅸ x Form of ge.*: Step 1: m=1/au(auto) in bi 记L1= ,则L[Ab (2) m○ Step n-1 Ln1Ln2…L1Ab 44/其中 k
§2 三角分解法 /* Matrix Factorization */ ➢ 高斯消元法的矩阵形式 /* Matrix Form of G.E. */： Step 1: / ( 0) mi1 = ai1 a11 a11 记 L1 = 1 . . . 1 1 1 21 mn m − − ，则 [ ] = (1) (1) 1 L A b (1) 1 (1) 1 (1) 11 a ... a b n (2) A (2) b Step n − 1: = − − ( ) (2) 2 (1) 1 ( ) (2) 2 (2) 2 2 (1) 1 (1) 1 2 (1) 1 1 1 2 1 . . . . . . ... ... ... ... n n n nn n n n n b b b a a a a a a L L L A b 其中 Lk = 1 . . . 1 1 , 1, n k k k m m − − +
记为 k L k+1,k k Factorize A first, then for every b you only have to x 记U solve two simple triangular. systems Ly=b and Ux=y m AHUA /*LU factor- n
= −1 Lk 1 . . . 1 1 , 1, n k k k m m + = − − − − 1 1 1 2 1 1 ... L L Ln 1 1 1 mi, j 记为 L 单位下三角阵 /* unitary lower-triangular matrix */ 记 U = ( ) (2) 2 (2) 22 (1) 1 (1) 12 (1) 11 . . . ... ... ... n nn n n a a a a a a A = LU A 的 LU 分解 /* LU factorization */ Hey hasn’t 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. b Could you be more specific, please? Factorize A first, then for every you only have to solve two simple triangular systems and . b Ly b = Ux y =
定理「若4的所有顺序主子式 t of lead principal submatrices*/ N/均不为0,则A的LU分解唯一(其 中L为单位下三角阵)。 证明:由§1中定理可知,LU分解存在。下面证明唯一性。 若不唯一,则可设A=L1U1=L2U2,推出 U,U2=L,UU2=LL,=IV Lower-triangular Upper-triangular With diagonal entries 1 注:L为一般下三角阵而U为单位上三角阵的分解称为 Crout分解。 实际上只要考虑A*的LU分解,即4=LU,则 A=U*即是A的 Crout分解
定理 若A的所有顺序主子式 /* determinant of leading principal submatrices */ 均不为0，则 A 的 LU 分解唯一（其 中 L 为单位下三角阵）。 证明：由§1中定理可知，LU 分解存在。下面证明唯一性。 若不唯一，则可设 A = L1U1 = L2U2 ，推出 = −1 U1 U2 2 1 1 1 2 2 2 1 L1 L U U L L − − − = Upper-triangular Lower-triangular With diagonal entries 1 = I ✓ 注： L 为一般下三角阵而 U 为单位上三角阵的分解称为 Crout 分解。 实际上只要考虑 A* 的 LU 分解，即 ，则 即是 A 的 Crout 分解。 A LU ~ ~ * = * ~ * ~ A=U L
>道立特分解法/ Doolittle factorization*: LU分解的紧凑格式/ compact form 较法直接导出L和U的计算公式 很浪费哦 11 n min(i,j) →a1=∑l1
➢ 道立特分解法 /* Doolittle Factorization */： —— LU 分解的紧凑格式 /* compact form */ 反复计算, 很浪费哦 …… 通过比较法直接导出L 和 U 的计算公式。 思 路 = nn n n nn n n u u u l l a a a a . . . . . . ... ... ... 1 ... . . . 1 1 ... . . . . . . . . . . . . ... 1 1 1 1 2 1 1 1 1 1 = min( , ) 1 i j k i k uk j = l ai j
a=∑l 固定i: 对j n有an=∑l+ →:= a-∑l(a k=1 将i,j对换,对j=i计1,…, 般采用列主元 法增强稳定性。但注意 →ln=(an-∑l1ku)/u b也必须做相应的 k=1 行交换。 Algorithm: Doolittle Factorization Step 1: uy=alii i1=a1/u;( n Step 2: compute(aand(b fori=2,., n-1; Step 3 L…= L
= = min( , ) 1 i j k i j i k uk j a l 固定 i : 对 j = i, i+1, …, n 有 kj ij i k aij = l iku + u − = 1 1 l ii = 1 kj i k ui j ai j l i ku − = = − 1 1 a 将 i ，j 对换，对 j = i, i+1, …, n 有 ki ji ii i k a ji = l jku + l u − = 1 1 i i i k l j i (a j i l j kuk i)/ u 1 1 − = = − b Algorithm: Doolittle Factorization Step 1: u1j = a1j ; l j1 = aj1 / u11; ( j = 1, …, n ) Step 2: compute and for i = 2, …, n−1; Step 3: a b − = = − 1 1 n k nn nn nkukn u a l 一般采用列主元 法增强稳定性。但注意 也必须做相应的 行交换。 b