[Linear Algebra] 행렬의 LDU 분해

---

삼각행렬의 성질

 

삼각행렬은 하삼삭행렬(lower triangular matrix)와 상삼각행렬(upper triangular matrix)로 나뉜다.

어떤 두 행렬이 하삼각행렬이고 서로 행렬곱 연산이 가능할 때 두 행렬의 곱은 하삼각행렬이다. 또한 만약 하삼각행렬인 행렬이 가역행렬이라면 이 행렬의 역행렬은 하삼각행렬이다. 당연하게도 하삼각행렬과 하삼각행렬을 더하면 하삼각행렬이 나온다. 상삼각행렬 역시 같은 성질을 지닌다. 즉 각 삼각행렬은 덧셈, 곱셈, 역행렬에 대해 닫혀있다.

 

---

LU 분해

 

단위행렬에 기본 행 연산을 했을 때 나오는 기본행렬은 단위행렬, 상삼각행렬, 하삼각행렬, 혹은 치환행렬이다. 치환행렬(permutation matrix)은 단위행렬에서 행을 교환하여 얻은 행렬이다.

가우스-요르단 소거법으로 역행렬을 계산할 때 역행렬을 계산하려는 행렬에 단위행렬을 결합하여 확대행렬로 만들고, 기본 행 연산을 통해 좌측에 위치한 원래 행렬을 단위행렬로 만들어 역행렬을 계산하였다. 이때 기본 행 연산을 하는 것을 기본행렬에 원래 행렬을 곱하는 것으로 볼 수도 있었다. 이를 이용해서 어떤 행렬에 기본 행 연산을 통해 상삼각행렬로 만드는 것을 다음과 같이 나타낼 수 있다. $ U $ 는 상삼각행렬이다.

$$ E_k \cdot E_{k-1} \cdots E_2 \cdot E_1 \cdot A = U $$

기본행렬은 가역행렬이므로 다음과 같이 나타낼 수 있다.

$$ A = E^{-1}_1 \cdot E^{-1}_2 \cdots E^{-1}_k \cdot U $$

기본행렬에 어떤 행렬을 곱해서 나온 행렬을 생각해보기 위해 기본행렬을 다시 확인하면 단위행렬, 상삼각행렬, 하삼각행렬, 치환행렬이었다. 만약 단위행렬과 하삼각행렬만을 곱해서 어떤 행렬을 만든다면 하삼각행렬은 곱셈에 대해 닫혀있기 때문에 그 행렬은 하삼각행렬일 것이다. 하삼각행렬의 역행렬 역시 하삼각행렬이기 때문에 위 식에서 모든 기본행렬 $ E $ 가 치환행렬과 상삼각행렬이 아니라면 기본행렬들의 곱은 하삼각행렬이고, 이를 통해 어떤 행렬 $ A $ 를 하삼각행렬과 상삼각행렬의 곱으로 나타낼 수 있다. 즉 다음이 성립한다. 이때 $ L $ 은 하삼각행렬이고, $ U $ 는 상삼각행렬이다.

$$ A = LU $$

즉 어떠한 행렬을 $ L $ 과 $ U $ 로 분해한 것이고, 이를 LU 분해라 한다. 모든 행렬이 LU 분해가 가능하지는 않다.

역행렬을 계산할 때는 확대행렬을 만든 후 우측에 위치한 단위행렬의 결과값만 확인하면 나름 간편하게 역행렬을 구할 수 있었지만, LU 분해는 그렇게 간편하지는 못하다. 역행렬을 구해야 하기 때문이다. 기본행렬을 모두 구해서 그 행렬들의 역행렬을 구하고, 다시 그 역행렬들을 곱하는 것이 위 방법이었지만, 나름 간단하게 만들어 구할 수도 있다. 먼저 $ E_k \cdot E_{k-1} \cdots E_2 \cdot E_1 = L^* $ 이므로 확대행렬을 만들어 역행렬을 계산할 때와 동일하게 원래 행렬을 상삼각행렬로 만든다. 단 $ R_i \leftrightarrow R_j $ 연산은 사용하지 않아야 한다. 만약 LU 분해가 가능하다면 우측에 하삼각행렬 $ L^* $ 이 만들어졌을 것이다. 즉 $ L^* A = U $ 까지 계산할 수 있다. 이렇게 만들어진 $ L^* $ 는 가역행렬이기 때문에 $ A = (L^*)^{-1} \cdot U $ 이 성립하며, $ (L^*)^{-1} = L $ 역시 성립한다. 즉 역행렬을 구할 때와 유사하게 하삼각행렬을 구한 후 이 하삼각행렬의 역행렬을 구하면 된다.

 

---

LDU 분해

 

만약 LU 분해가 가능해서 어떤 행렬을 상삼각행렬과 하삼각행렬의 곱으로 나타낼 수 있고, 이때의 하삼각행렬의 주대각성분은 모두 1 이며, 상삼각행렬의 주대각성분이 모두 0 이 아니라면 이를 다시 분해할 수 있다.

주대각성분이 모두 0 이 아닌 상삼각행렬에서 주대각성분만 따로 띄어내어 대각행렬로 만드는 것이다. 이때 상삼각행렬은 각 행을 띄어낸 주대각성분으로 나누어주어야 한다.

$$ \begin{bmatrix} u_1 & s & \cdots & t \\ 0 & u_2 & \cdots & r \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_n \end{bmatrix} = \begin{bmatrix} u_1 & 0 & \cdots & 0 \\ 0 & u_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_n \end{bmatrix} \begin{bmatrix} 1 & \dfrac{s}{u_1} & \cdots & \dfrac{t}{u_1} \\ 0 & 1 & \cdots & \dfrac{r}{u_2} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix} = DU $$

조건이 만족한다면 이렇게 상삼각행렬을 대각행렬과 상삼각행렬로 분해할 수 있다. $ D $ 가 대각행렬이고, $ U $ 가 상삼각행렬이다. 이를 이용하여 LU 분해가 끝난 행렬을 다시 하삼각행렬, 대각행렬, 상삼각행렬로 분해할 수있고 이를 LDU 분해라 하며, 이 $ A = LDU $ 는 유일하다. LU 분해는 유일하지 않다.

LDU 분해는 위 방법이 아니더라도 가능하다. 어떤 행렬이 있을 때 결과적으로 LDU 분해가 되었다면 어차피 LDU 분해된 행렬은 유일하기 때문이다.

 

---

참고

 

• 치환행렬이 필요한 경우

만약 처음 행렬을 분해할 때 기본행렬 중에 치환행렬이 있었다면 $ PA = LU $ 혹은 $ PA = LDU $ 로 나타내는 치환행렬 $ P $ 가 유일하게 존재한다. 다르게 말하자면 어떤 행렬이 $ R_i \leftrightarrow R_j $ 연산 없이는 LDU 분해가 불가능하다면 $ PA $ 로 만들어준 후 LDU 분해를 하면 된다.

 

• 대칭행렬인 경우

만약 LDU 분해를 하려는 행렬이 대칭행렬이고, 치환행렬 없이 LDU 분해가 되었다면, 다음이 성립한다.

$$ LDU = A = A^T = (LDU)^T = U^T D^T L^T = U^T D L^T $$

$$ L = U^T \Longrightarrow A = LDL^T $$