Matrix Decomposition(1) LU Decomposition

행렬은 여러 개의 수를 포함하고 있으며, 이를 통해 어떤 시스템이나 변환 등을 표현한다. 또한 우리는 행렬로 표현된 식의 해를 찾거나, 행렬식이나 교유값/벡터 등을 구하여 주어진 시스템이나 변환의 특성을 분석하곤 한다. 하지만 때때로 행렬은 너무 많은 수를 포함하고 있어 위와 같은 계산이 쉽지 않거나, 그 특성이 한 눈에 들어오지 않는 경우가 발생한다. 이러한 문제를 해결하기 위해 우리는 주어진 행렬을 다시 여러 개의 행렬로 분할 할 수 있으며, 분할된 행렬을 통해 여러 계산과 분석을 간소화 할 수 있다. 이 글에서는 행렬 연산에 많이 쓰이는 3가지 행렬 분해 방법을 소개하고자 한다.

LU decomposition은 주어진 $m \times n$ 행렬 $\mathbf{A}$를 $\mathbf{A}=\mathbf{L}\mathbf{U}$ 와 같이 $m \times s$ 하삼각행렬 $\mathbf{L}$과 $s \times n$ 상삼각행렬 $\mathbf{U}$로 분해하는 것이다. 하삼각행렬과 상삼각행렬은 다음과 같으며, 보통 $\mathbf{L}$이나 $\mathbf{U}$ 중 하나의 대각 성분은 1로 두기도 한다.

이제 LU decomposition의 과정을 살펴보자. 먼저 $\mathbf{L}$과 $\mathbf{U}$를 다음과 같이 쓰자.

우리의 목표는 $\mathbf{A} = \mathbf{l_1}\mathbf{u_1^T} + \cdots + \mathbf{l_s}\mathbf{u_s^T} = \mathbf{L}\mathbf{U}$의 형태로 만드는 것이다.

먼저 $\mathbf{A} \equiv \mathbf{A}(1) = (a_{ij}(1))$로 두며, 여기서 $\mathbf{A}(1)$은 1번째 step에서의 목표 행렬을 의미하며 1번째 step에서 이 목표 행렬은 처음에 주어진 $\mathbf{A}$와 같지만, 이 후 step에서는 달라진다. $a_{ij}(1)$는 $\mathbf{A}(1)$의 각 원소를 의미한다. 이를 이용하여 우리는 $\mathbf{l_1}, \mathbf{u_1^T}$를 구할 수 있다.

위와 같이 설정하면 다음과 같이 쓸 수 있다.

이 과정을 $\mathbf{A}(2)$에서도 반복하여 $\mathbf{A}(3)$을 구하며, 2번째 step에서의 $\mathbf{l_2}, \mathbf{u_2^T}$는 다음과 같다.

이러한 과정을 $\mathbf{A}(3), \cdots, \mathbf{A}(s)$에 대해서 반복하면 결국 처음 목표했던 $\mathbf{A} = \mathbf{l_1}\mathbf{u_1^T} + \cdots + \mathbf{l_s}\mathbf{u_s^T}$과 같은 형태가 되고, 그 결과를 이용하여 행렬 $\mathbf{L}, \mathbf{U}$를 구할 수 있다.

다만, 위 과정에서 $a_{11}(1), a_{11}(2)$(각 목표 행렬에서 가장 앞에 있는 원소)로 나누는 부분이 있는데 해당 값이 0이라면 문제가 발생한다. 이럴 경우 행렬 $\mathbf{A}$의 행을 서로 치환하여 문제를 해결할 수 있으며, 행의 치환은 다음과 같은 행렬을 곱하는 것으로 볼 수 있다.

위의 예시는 3번째 행과 2번째 행을 서로 바꾸는 것으로 $\mathbf{P}$의 각 행은 하나의 1만 포함하고 있다. 이러한 치환 행렬까지 포함하면 LU decomposition은 다음과 같이 쓸 수 있다.

이렇게 행렬을 미리 LU decomposition 해놓으면 이후의 계산에서 많은 이점을 얻을 수 있다. 예를 들어 행렬식 $det(\mathbf{A})$을 구할때, $det(\mathbf{A})=det(\mathbf{LU})=det(\mathbf{L})det(\mathbf{U})$이며, 삼각행렬의 행렬식은 삼각행렬의 대각성분의 곱이므로 행렬식을 쉽게 구할 수 있다.

또한 삼각행렬으로 표현된 방정식은 위와 같이 쉽게 풀 수 있으므로, $\mathbf{A}\mathbf{x}=\mathbf{b}$를 풀기 위하여, $\mathbf{L}\mathbf{y}=\mathbf{b}, \;\;\; \mathbf{y}=\mathbf{U}\mathbf{x}$를 먼저 풀고, 이후에 $\mathbf{y}=\mathbf{U}\mathbf{x}$를 풀면 간단하게 해결이 가능하다.