§2三角分解法 Matrix Factorization >高斯消元法的矩阵形式/ Matrix Form of ge. Step 1: m=a/au(auto b 记L ,则L1[A0b m○ Step n-1: 2其中 LmLm-2.[A 6 1222 (
§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 − − +
$2 Matrix Factorization-Matrix Form of GE 记为 k+1,k k air Factorize A first, then for every you only have to ix*/ 记U solve two simple triangular systems Ly=b and Ux=y m A的’U /*LU factor- n
§2 Matrix Factorization – Matrix Form of G.E. = −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 =
$2 Matrix Factorization-Matrix Form of GE 定理若4的所有顺序主子式eng principal submatrices+均不为0,则A的LU分解唯—(其 中L为单位下三角阵)。 证明:由§1中定理可知,LU分解存在。下面证明唯一性。 若不唯一,则可设A=L1U1=L2U2,推出 L L2 U2U2=LL2=/ Lower-triangular Upper-triangular With diagonal entries 1 注:L为一般下三角阵而U为单位上三角阵的分解称为 Crout分解。 实际上只要考虑A*的LU分解,即4=LU,则 A=U*即是A的 Crout分解
§2 Matrix Factorization – Matrix Form of G.E. 定理 若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
$2 Matrix Factorization-Doolittle >道立特分解法/ Doolittle Factorization: LU分解的紧凑格式/ compact form 思 比较法直接导出L和U的计算公式。 很浪费哦 11 min(i,j) →a ∑l
§2 Matrix Factorization – Doolittle ➢ 道立特分解法 /* 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
=∑1 $2 Matrix Factorization-Doolittle 固定i 对j=;计+1,,n有a=∑l+ur k=1 →=ay-l(a k=1 将i,j对换,对j=,计1, 一般采用列主元 法增强稳定性。但注意 →=(a1-2u)b也必须做应的 k=1 行交换。 Algorithm: Doolittle Factorization Step l:u1i-aijijl JI/U n Step 2: compute(a)and (b fori=2,., n-1; S L…=〖 L
§2 Matrix Factorization – Doolittle = = 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