8 2 Matrix Factorization-Choleski Algorithm: Choleski's Method To factor the symmetric positive definite nxn matrix A into LL, where L is lower triangular Input: the dimension n; entries ai for lsi,jsnofa Output: the entries Li for lsjsiand 1s n of L Step i set HW: p 54 Sep2Forj=2,…,m.set #2,#5,#6 s3F因为A对称,所以只需存半个A,即 [a(n+1)/2]={a1,a21,a2, 其中 Step A[x(-1)2+ Sp6se运算量为O(n6),比普通LU Sp7d分解少一半,但有n次开方。用A=LDL STOP 分解,可省开方时间(p5051§2 Matrix Factorization – Choleski Algorithm: Choleski’s Method To factor the symmetric positive definite nn matrix A into LLT, where L is lower triangular. Input: the dimension n; entries aij for 1 i, j  n of A. Output: the entries l ij for 1 j  i and 1 i  n of L. Step 1 Set ; Step 2 For j = 2, …, n, set ; Step 3 For i = 2, …, n−1, do steps 4 and 5 Step 4 Set ; Step 5 For j = i+1, …, n, set ; Step 6 Set ; Step 7 Output ( l ij for j = 1, …, i and i = 1, …, n ); STOP. 11 a11 l = 1 1 11 l a / l j = j  − = = − 1 1 2 i k ii ii ik l a l ( ) ii i k ji ji jk ik l a  l l l − = = − 1 1  − = = − 1 1 2 n k nn nn nk l a l 因为A 对称，所以只需存半个 A，即 其中 An(n+1)/ 2=  a11, a21, a22 , ..., an1 , ..., ann  a Ai i j ij = ( −1)/ 2 + 运算量为 O(n 3 /6)， 比普通LU 分解少一半，但有 n 次开方。用A = LDLT 分解，可省开方时间(p.50-51)。 HW: p.54 #2, #5, #6