[선형대수] LU Decomposition
LU Decomposition은 정사각 행렬 $A$를 상삼각 행렬 $U$와 하삼각 행렬 $L$의 곱으로 분해하는 방법을 의미한다.
\[A=LU \tag{1}\]이때 $L$은 대각 성분이 모두 1인 하삼각 행렬이다.
하나의 행렬 $A$에 대해, 여러 개의 서로 다른 우변 $\mathbf{b}$로 $A\mathbf{x}=\mathbf{b}$를 반복해서 풀 때 효율을 위해 고안된 방법이다.
방정식 $A\mathbf{x}=\mathbf{b}$ 대신 $(LU)\mathbf{x}=\mathbf{b}$를 풀며, 과정은 아래와 같다.
- Forward substitution: $U\mathbf{x}=\mathbf{y}$로 치환해서 $L\mathbf{y}=\mathbf{b}$를 푼다.
- Backward substitution: $U\mathbf{x}=\mathbf{y}$를 푼다.
만약 $\mathbf{b}$가 바뀔 때마다 가우스 소거법을 처음부터 다시 수행한다면 매번 $O(n^3)$의 계산 복잡도가 발생한다.
$A$를 $L$과 $U$로 분해하는 과정도 $O(n^3)$의 계산 복잡도가 발생하지만, $A=LU$로 한 번 분해해두면 이후로는 전진 대입과 후진 대입만으로 각 $\mathbf{b}$를 $O(n^2)$에 풀 수 있다.
기본 행렬과 LU Decomposition
가우스 소거법의 각 연산은 하나의 기본 행렬 (Elementary matrix)을 왼쪽에 곱하는 것과 같다.
LU Decomposition은 이 사실을 그대로 정리한 것에 지나지 않는다.
소거 과정에서 사용하는 연산은 어떤 행의 상수배를 다른 행에 더하는 것이며, 이에 대응하는 기본 행렬을 $E_k$라 하자.
예를 들어 $i$행에 $j$행의 $-m_{ij}$배를 더하는 연산은 단위 행렬의 $(i,j)$ 성분만 $-m_{ij}$로 바꾼 행렬이 된다.
\[E=I-m_{ij}\,\mathbf{e}_i\mathbf{e}_j^\top \tag{2}\]예를 들어, 2번째 행에서 1번째 행을 빼는 연산 $R_2\to R_2-R_1$을 수행하는 행렬은 다음의 기본 행렬로 표현할 수 있다.
\[E=I-\mathbf{e}_i\mathbf{e}_j^\top=\begin{bmatrix}1&0&0\\-1&1&0\\0&0&1\end{bmatrix}\]따라서 $A$에 $R_2\to R_2-R_1$ 연산을 적용하는 것을, 다음과 같이 $E$를 곱하는 것으로 표현할 수 있다.
\[EA=\begin{bmatrix}1&0&0\\-1&1&0\\0&0&1\end{bmatrix}\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}=\begin{bmatrix}1&2&3\\3&3&3\\7&8&9\end{bmatrix}\]
소거를 순서대로 적용해 $A$를 상삼각 행렬 $U$로 만들면 다음과 같이 쓸 수 있다.
\[(E_k\cdots E_2 E_1)A = U \tag{3}\]이제 양변에 소거 연산들의 역을 곱하면 다음과 같이 정리할 수 있다.
\[A = (E_1^{-1}E_2^{-1}\cdots E_k^{-1})U = LU, \;,\quad\text{where } L = E_1^{-1}E_2^{-1}\cdots E_k^{-1} \tag{4}\]즉, $L$은 소거에 사용한 기본 행렬들의 역행렬을 곱한 것이다.
Example: LU Decomposition 수행
\[\begin{bmatrix}\begin{array}{ccc|c}2&4&-2&2\\4&9&-3&8\\-2&-3&7&10\end{array}\end{bmatrix}\]1. 가우스 소거법을 이용해 $U$ 구하기
\[\begin{bmatrix}1&0&0\\0&1&-2\\0&0&1\end{bmatrix}\begin{bmatrix}2&4&-2\\4&9&-3\\-2&-3&7\end{bmatrix}=\begin{bmatrix}2&4&-2\\0&1&1\\-2&-3&7\end{bmatrix}\]
- $R_2\rightarrow R_2-2R_1$
\[\begin{bmatrix}1&0&0\\0&1&0\\1&0&1\end{bmatrix}\begin{bmatrix}2&4&-2\\0&1&1\\-2&-3&7\end{bmatrix}=\begin{bmatrix}2&4&-2\\0&1&1\\0&1&\end{bmatrix}\]
- $R_3\rightarrow R_3+R_1$
\[\begin{bmatrix}1&0&0\\0&1&0\\0&-1&1\end{bmatrix}\begin{bmatrix}2&4&-2\\0&1&1\\0&1&5\end{bmatrix}=\begin{bmatrix}2&4&-2\\0&1&1\\0&0&4\end{bmatrix}=U\]
- $R_3\rightarrow R_3-R_2$
2. 기본 행렬을 이용해 $L$ 구하기
위의 가우스 소거법 과정은 아래와 같이 표현할 수 있다.
\[(E_3E_2E_1)A=U\]$E_i$는 모두 대각 성분이 1인 하삼각 행렬이며,
\[A=(E_3E_2E_1)^{-1}U=(E_1^{-1}E_2^{-1}E_3^{-1})U=LU\] \[L=\begin{bmatrix}1&0&0\\2&1&0\\0&0&1\end{bmatrix}\begin{bmatrix}1&0&0\\0&1&0\\-1&0&1\end{bmatrix}\begin{bmatrix}1&0&0\\0&1&0\\0&-1&1\end{bmatrix}=\begin{bmatrix}1&0&0\\2&1&0\\-1&1&1\end{bmatrix}\]3. $L\mathbf{y}=\mathbf{b}$ 풀기
\[\begin{bmatrix}1&0&0\\2&1&0\\-1&1&1\end{bmatrix}\begin{bmatrix}y_1\\y_2\\y_3\end{bmatrix}=\begin{bmatrix}2\\8\\10\end{bmatrix}~\to~\mathbf{y}=\begin{bmatrix}2\\4\\8\end{bmatrix}\]4. $U\mathbf{x}=\mathbf{y}$ 풀기
\[\begin{bmatrix}2&4&-2\\0&1&1\\0&0&4\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}2\\4\\8\end{bmatrix}~\to~\mathbf{x}=\begin{bmatrix}-1\\2\\2\end{bmatrix}\]
기본 행렬의 성질
기본 행렬의 역행렬은 아래와 같다.
행 교환 행렬의 역행렬은 자기 자신이다.
\[E=\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix} ~\to~ E^{-1}=\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix}\]행 상수배 행렬의 역행렬은 대각 행렬의 역행렬과 같다.
\[E=\begin{bmatrix}1&0&0\\0&3&0\\0&0&1\end{bmatrix} ~\to~ E^{-1}=\begin{bmatrix}1&0&0\\0&\frac{1}{3}&0\\0&0&1\end{bmatrix}\]행 덧셈 행렬의 역행렬은 부호를 바꾸면 된다.
\[E=\begin{bmatrix}1&0&0\\0&1&0\\-2&0&1\end{bmatrix} ~\to~ E^{-1}=\begin{bmatrix}1&0&0\\0&1&0\\2&0&1\end{bmatrix}\]