LU Decomposition

1. LU Decomposition이란?

 NxN 인 square matrix $ \mathbf{A}$가 있다. 이 matrix를 쪼갤 수 있는 방법은 매우 많다. 예를 들어 Cholesky decomposition을 통하여 $\mathbf{LL^{T}}$ 형식으로 lower triangle과 그 transpose로 쪼갤 수 있다. LU decomposition은 square matrix를 lower triangle과 upper triangle 두 부분으로 나누는 기법을 말한다.

$ \mathbf{A = LU} $

 예를 들어 $\mathbf{A}$라는 matrix가 3x3이라고 하면 이 matrix를 다음과 같이 나눌 수 있다.

$
\left( \begin{array}{ccc}  l_{1,1} & 0 & 0 \\ l_{2,1} & l_{2,2} & 0 \\ l_{3,1} & l_{3,2} & l_{3,3} \end{array} \right)
\left( \begin{array}{ccc}  u_{1,1} & u_{1,2} & u_{1,3} \\ 0 & u_{2,2} & u_{2,3} \\ 0 & 0 & u_{3,3} \end{array} \right)  =
\left( \begin{array}{ccc}  a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,1} & a_{3,2} & a_{3,3} \end{array} \right) $

 이 matrix를 풀어보면 다음과 같이 쓸 수 있다.

$
\left( \begin{array}{ccc} l_{1,1}u_{1,1} & l_{1,1}u_{1,2} & l_{1,1}u_{1,3} \\
l_{2,1}u_{1,1} & l_{2,1}u_{1,2} + l_{2,2}u_{2,2} & l_{2,1}u_{1,3} + l_{2,2}u_{2,3} \\
l_{3,1}u_{1,1} & l_{3,1}u_{1,2} + l_{3,2}u_{2,2} & l_{3,1}u_{1,3} + l_{3,2}u_{2,3} + l_{3,3}u_{3,3} \end{array} \right)  =
\left( \begin{array}{ccc}  a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,1} & a_{3,2} & a_{3,3} \end{array} \right) $

이렇게 보면 찾아야 하는 값은 $ 3 \times 3 + 3$개인데 식은 $3\times 3$개만 있는 상황이 된다. 즉 답이 하나가 아닐 수 있다는 의미이다. 이 때 자주 쓰이는 알고리듬이 'Crout's Method' 이다. 실제 내용이나 구현 방법은 링크 또는 Numerical Recipe라는 책을 찾아보면 자세히 나와있다.
 구현에 따라 $ \mathbf{A=LU}$가 아니라 $\mathbf{PA=LU}$의 형식으로 답을 구하는데 여기서 $\mathbf{P}$는 permutation matrix이고, orthogonal이므로 $\mathbf{A=P^{T}LU}$로 다시 역산할 수 있다.

2. 어디에 쓰는가. 

 LU Decomposition을 사용하면 $\mathbf{Ax=b}$ 형태의 linear system을 쉽게 풀 수가 있다. 일반적으로 이런 식을 풀기 위해 Gauss-Jordan Elimination을 사용한다. LU Decomposition으로 푸는 방식은 다음과 같다.

$ \mathbf{ Ax=(LU)x=L(Ux)=b} $

와 같이 식을 쓰게 되면 우선

$ \mathbf{ Ly=b }$ 

에서 $\mathbf{y}$를 Forward substitution방식으로 풀고,

$ \mathbf{Ux=y}$

식을 backward substitution으로 풀 수 있다.