2.6 소거와 LU Factorization: A = LU

행렬 $A$에 소거를 진행하면 상부삼각행렬 $U$를 만들 수 있습니다. 이 과정은 소거행렬 $E_{x}$를 이용해 $E_{n}$…$E_{1}A$ = $U$로 쓸 수 있고, 이는 다시 $A$ = $LU$로 표현할 수 있습니다. 여기서 $L$은 하부삼각행렬입니다. 즉, $A$는 $L$과 $U$로 나눌 수 있습니다. 이를 $LU$ Factorization이라고 합니다. 

이번 포스팅은 앞선 시간에 배운 $LU$ factorization($LU$ 분해)에 대해 좀 더 살펴보겠습니다. 여기서 $U$는 소거를 통해 만든 상부삼각행렬이고 $L$은 그 소거행렬($E_{n}$…$E_{1}$)의 역행렬입니다.

 

LU factorization의 원리와 예제

주어진 행렬 $A$에 소거를 하여 상부삼각행렬 $U$를 만든다고 가정하겠습니다.
소거 과정의 각 단계에 대응되는 소거행렬을 $E_{1}$, $E_{2}$, …, $E_{n}$이라 하면, 

모든 소거과정은 다음과 같이 쓸 수 있습니다: 
($E_{n}$…$E_{1}$)$A$ = $U$.

 

여기서 양변에 $E_{1}^{-1}$…$E_{n}^{-1}$를 곱하면  
($E_{1}^{-1}$…$E_{n}^{-1}$)·($E_{n}$…$E_{1}$)$A$ = ($E_{1}^{-1}$…$E_{n}^{-1}$)·$U$이 됩니다.
좌변의 소거행렬과 그 역행렬들의 곱은 단위행렬 $I$가 되므로,
$I$·$A$ = $A$ = ($E_{1}^{-1}$…$E_{n}^{-1}$)·$U$이 됩니다.

 

앞서 우리는 소거행렬의 역행렬이 하부삼각행렬임을 배웠습니다. 
하부삼각행렬들의 곱도 하부삼각행렬이 되므로 괄호 역시 하부삼각행렬입니다.
괄호를 하부삼각행렬 Lower triangular matrix의 알파벳 앞 글자를 따서 쓰면,
$A$ = $LU$가 됩니다.

위 내용은 행 교환(row exchange)이 필요하지 않은 경우임을 주의해야합니다.
소거 과정에서 행 교환이 필요하다면, 교환행렬 $P$를 써서, ($E_{n}$…$E_{1}P$)$A$ = $U$로 쓸 수 있습니다. 

이때 괄호안의 행렬곱은 하부삼각행렬이 아닙니다. 
즉, $A$는 $LU$ 분해되지 않는다. 대신 $PA$는 $LU$ 분해됩니다. 

---

LU factorization 예제

$A$ = $\begin{pmatrix} \begin{array}{rrr} 2 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 2 \end{array} \end{pmatrix}$을 $LU$ 분해해보겠습니다.

$A$를 상부삼각행렬로 만들기 위해서는 피벗 아래 성분들을 0으로 만들어야 합니다.
먼저 $a_{21}$ (2행 1열 성분)을 제거합나다.

이 과정에 대한 소거행렬은 

 

$E_{1}$ = $\begin{pmatrix} \begin{array}{rrr} 1 & 0 & 0 \\ -\frac{1}{2} & 1 & 0 \\ 0 & 0 & 1 \end{array} \end{pmatrix}$이고,

$E_{1}A$ = $\begin{pmatrix} \begin{array}{rrr} 2 & 1 & 0 \\ 0 & \frac{3}{2} & 1 \\ 0 & 1 & 2 \end{array} \end{pmatrix}$이 됩니다. 

다음은 2번 행에 $\frac{2}{3}$을 곱하여 3번 행에 빼주어 $a_{32}$을 제거합니다.

이때 소거행렬은 $E_{2}$ = $\begin{pmatrix} \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -\frac{2}{3} & 1 \end{array} \end{pmatrix}$입니다.

이제 $E_{2}E_{1}A$ = $\begin{pmatrix} \begin{array}{rrr} 2 & 1 & 0 \\ 0 & \frac{3}{2} & 1 \\ 0 & 0 & \frac{4}{3} \end{array} \end{pmatrix}$입니다.

두 소거행렬의 역행렬은 각각 

 

$E_{1}^{-1}$ = $\begin{pmatrix} \begin{array}{rrr} 1 & 0 & 0 \\ \frac{1}{2} & 1 & 0 \\ 0 & 0 & 1 \end{array} \end{pmatrix}$, 

 

$E_{2}^{-1}$ = $\begin{pmatrix} \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & \frac{2}{3} & 1 \end{array} \end{pmatrix}$이므로,

$L$ = $E_{1}^{-1}E_{2}^{-1}$ = $\begin{pmatrix} \begin{array}{rrr} 1 & 0 & 0 \\ \frac{1}{2} & 1 & 0 \\ 0 & \frac{2}{3} & 1 \end{array} \end{pmatrix}$입니다.

즉, $A$ = $\begin{pmatrix} \begin{array}{rrr} 1 & 0 & 0 \\ \frac{1}{2} & 1 & 0 \\ 0 & \frac{2}{3} & 1 \end{array} \end{pmatrix}$$\begin{pmatrix} \begin{array}{rrr} 2 & 1 & 0 \\ 0 & \frac{3}{2} & 1 \\ 0 & 0 & \frac{4}{3} \end{array} \end{pmatrix}$와 

 

같이 $LU$ 분해되었습니다. 

---

LDU 분해

위 예를 보면 $L$의 대각 성분들은 모두 1인 반면, U의 대각 성분들은 모두 1이 아닙니다. 

$U$의 대각 성분들은 피벗으로 보통은 1이 아닙니다. 
$L$과 $U$의 균형을 위해, $U$를 다시 $DU$로 나뉩니다.
여기서 $D$는 대각행렬입니다. 
$D$의 대각 성분들은 원래 $U$의 피벗들입니다.

위 예에서는

 

$U$ = $\begin{pmatrix} \begin{array}{rrr} 2 & 0 & 0 \\ 0 & \frac{3}{2} & 0 \\ 0 & 0 & \frac{4}{3} \end{array} \end{pmatrix}$$\begin{pmatrix} \begin{array}{rrr} 1 & \frac{1}{2} & 0 \\ 0 & 1 & \frac{2}{3} \\ 0 & 0 & 1 \end{array} \end{pmatrix}$입니다.

따라서 

$A$ = $\begin{pmatrix} \begin{array}{rrr} 1 & 0 & 0 \\ \frac{1}{2} & 1 & 0 \\ 0 & \frac{2}{3} & 1 \end{array} \end{pmatrix}$$\begin{pmatrix} \begin{array}{rrr} 2 & 0 & 0 \\ 0 & \frac{3}{2} & 0 \\ 0 & 0 & \frac{4}{3} \end{array} \end{pmatrix}$$\begin{pmatrix} \begin{array}{rrr} 1 & \frac{1}{2} & 0 \\ 0 & 1 & \frac{2}{3} \\ 0 & 0 & 1 \end{array} \end{pmatrix}$

입니다.

---

$L$과 $U$를 이용한 행렬 방정식 $Ax$ = $b$ 풀기

행렬 방정식 $Ax$ = $b$ 는 다음 과정을 통해 풀 수 있습니다:
1. $A$를 $L$과 $U$로 분해하기
2. $Lc$ = $b$를 풀어 $c$를 구한 다음, $Ux$ = $c$를 풀면, 방정식의 해 $x$를 구할 수 있습니다.

 

행렬 방정식 $Ax$ = $b$에 소거를 진행하면 $Ux$ = $c$가 됩니다.
이는 상부삼각형태의 연립방정식과 대응됩니다.
그리고 $A$를 $L$과 $U$로 분해한다면, $Ax$ = $b$은 $LUx$ = $b$이 됩니다.

이것은 다시 $LUx$ = $Lc$ = $b$입니다.
따라서 $Lc$ = $b$에서 $c$를 구하고 나서 $Ux$ = $c$을 풀면 원래 방정식의 해 $x$를 구할 수 있습니다. 

 

다음 연립 방정식 예를 보겠습니다.
$x_{1}$ + 2$x_{2}$ = 5
4$x_{1}$ + 9$x_{2}$ = 21 

이에 대응되는 행렬 방정식 $Ax$ = $b$에서 $A$와 $b$는 $A$ = $\begin{pmatrix} \begin{array}{rr} 1 & 2 \\ 4 & 9 \end{array} \end{pmatrix}$, $b$ = $\begin{pmatrix} \begin{array}{r} 5 \\ 21 \end{array} \end{pmatrix}$입니다.

위 설명대로 $A$를 $L$과 $U$로 분해하겠습니다. 
먼저 $A$를 소거하기 위한 multiplier는 4임을 쉽게 알 수 있습니다.

그래서 소거행렬은 $\begin{pmatrix} \begin{array}{rr} 1 & 0 \\ -4 & 1 \end{array} \end{pmatrix}$이고,

 
$L$은 소거행렬의 역행렬 $\begin{pmatrix} \begin{array}{rr} 1 & 0 \\ 4 & 1 \end{array} \end{pmatrix}$입니다. 

 

또 $U$ = $\begin{pmatrix} \begin{array}{rr} 1 & 2 \\ 0 & 1 \end{array} \end{pmatrix}$를 쉽게 구할 수 있습니다.

다음은 $Lc$ = $b$를 풀겠습니다.

즉, $\begin{pmatrix} \begin{array}{rr} 1 & 0 \\ 4 & 1 \end{array} \end{pmatrix}$$\begin{pmatrix} \begin{array}{r} c_{1} \\ c_{2} \end{array} \end{pmatrix}$ = $\begin{pmatrix} \begin{array}{r} 5 \\ 21 \end{array} \end{pmatrix}$를 풉니다.

여기서 $c_{1}$은 5 임을 바로 알 수 있고, 
$c_{1}$값을 대입하면 $c_{2}$가 1인 것도 쉽게 알 수 있습니다.

따라서, $c$ = $\begin{pmatrix} \begin{array}{r} 5 \\ 1 \end{array} \end{pmatrix}$. 

이제 $Ux$ = $c$를 풀 수 있습니다.

$\begin{pmatrix} \begin{array}{rr} 1 & 2 \\ 0 & 1 \end{array} \end{pmatrix}$$\begin{pmatrix} \begin{array}{r} x_{1} \\ x_{2} \end{array} \end{pmatrix}$= $\begin{pmatrix} \begin{array}{r} 5 \\ 1 \end{array} \end{pmatrix}$.

역시 $x_{2}$ = 1을 바로 계산할 수 있고, 
이 값을 대입하여 $x_{1}$ = 3도 쉽게 계산할 수 있습니다.

따라서 방정식의 해는 $x$ = $\begin{pmatrix} \begin{array}{r} 3 \\ 1 \end{array} \end{pmatrix}$입니다.