04. LU 분해법과 숄레스키 방법(LU Decomposition Method and Cholesky Method)

 

4. 1. LU 분해법과 숄레스키 방법(LU Decomposition Method and Cholesky Method)

 

- LU 분해법(LU Decomposition Method): 행렬 크기가 너무 크면 연산이 오래 걸린다. 연산을 줄이기 위해서 행렬 A를 Upper Triangular Matrix U, Lower Triangular Matrix L을 이용해 A = LU 분해하는 것을 말한다.

 

- Ax = b -> LUx = b (Ux = z) -> Lz = b.

 

 

- LU분해조건(LU Decomposition Condition).

 

 모든 n-square Matrix가 LU Decomposition이 되는 것은 아니다. A는 n² 성분이 있고, L과 U는 각각 n(n+1)/2 성분이 있으므로 n² + n이 된다. 미지수 n이 줄어들어야 해가 존재하기 때문에 다음 조건 중 하나를 만족해야 한다.

 

 1) l₁₁ = l₂₂ = … = l_nn = 1. (두리틀[Doolittle Method])

 

   -> Lower Triangular Matrix 의 Diagonal Element 를 1로 놓는다.

 

 2) u₁₁ = u₂₂ = … = u_nn = 1. (크라우트[Crout Method])

 

  -> Upper Triangular Matrix 의 Diagonal Element 를 1로 놓는다.

 

 3) l₁₁ = u₁₁ , l₂₂ = u₂₂ , … , l_nn = u_nn . (숄레스키[Cholesky Method])

 

  -> 행렬 A가 대칭이고 A = LU로 유일하게 분해되면, U = L^T가 된다.

      따라서, A = LL^T 로 분해되어 저장공간을 줄일 수 있을 뿐 아니라, 연산의 개수도 줄일 수 있다.

 

 

 

- 숄레스키 방법(Cholesky Method).

 

  1) Symmetric Matrix A 가 0이 아닌 벡터에 대하여 x^TAx > 0 이면 양의 정부호(Positive Definite)를 갖는다.

 

  2) Symmetric Matrix A 가 Positive Definite 가지면, A = LL^T 로 분해된다. 역도 성립한다.

 

 

필요 곱셈의 수: 1/6O³ + O(n²) -> Gauss Elimination에 비하여 연산의 수가 1/2로 줄어든다. 또한 행렬 A가 대칭이므로 저장공간도 1/2로 줄어든다.

 

---