8. LU 분해 (LU Decomposition)

LU 분해^{LU Decomposition}

LU 분해는, $m\times m$행렬을 같은 크기의 상삼각행렬 U와, 하삼각행렬 L로 분해하는 것을 말한다.
LU 분해는 행렬의 기본 연산 중, 행 교환 없이 행사다리꼴행렬로 변환 가능한 행렬에 대해 수행할 수 있다.

LU 분해 방법은, 예제를 직접 분해하며 배워보자.

$$A = \begin{bmatrix} 2&1&1\\
4&-6&0\\
-2&7&2\end{bmatrix} $$

위 행렬 $A$를 $LU$분해 할 것이다. 항등행렬 $I$를 준비해놓고, 우리가 수행한 연산을 계속 기록해주기만 하면 된다.

$$ I=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}A = \begin{bmatrix}2&1&1\\
4&-6&0\\
-2&7&2 \end{bmatrix}$$ 

$$ R_2 -= 2\times R_1$$

위 과정에 따라, 항등행렬의 2행 1열에 2를 넣어준다.

$$ \begin{bmatrix}1&0&0\\2&1&0\\0&0&1\end{bmatrix} \begin{bmatrix}2&1&1\\
0&-8&-2\\
-2&7&2 \end{bmatrix}$$ 

$$ R_3 -= (-1) \times R_1$$

$$ \begin{bmatrix}1&0&0\\2&1&0\\-1&0&1\end{bmatrix} \begin{bmatrix}2&1&1\\
0&-8&-2\\
0&8&3 \end{bmatrix}$$ 

$$ R_3 -= (-1)\times R_2$$

$$ \begin{bmatrix}1&0&0\\2&1&0\\-1&-1&1\end{bmatrix} \begin{bmatrix}2&1&1\\
0&-8&-2\\
0&0&1 \end{bmatrix}$$ 

$$ L=\begin{bmatrix}1&0&0\\2&1&0\\-1&-1&1\end{bmatrix} U=\begin{bmatrix}2&1&1\\
0&-8&-2\\
0&0&1 \end{bmatrix}$$ 

LU 행렬을 이용한 선형 시스템 풀이

우리는 지금까지 선형 시스템을 $Ax=b$ 꼴로 나타내었다. 이를 $A$의 LU 분해를 통해 쉽게 풀 수 있다.

1. $Ax=b$를 $LUx=b$로 변환한다.
2. 새로운 벡터 $y=Ux$를 정의하고, $LUx=b$를 $Ly=b$로 정의한다.
3. $Ly=b$를 푼다. 이때, $L$이 하삼각 행렬이므로 대입법을 이용해 쉽게 $y$를 구할 수 있다.
4. $Ux=y$에 $y$를 대입해 다시 쉽게 $x$를 구한다.

예시

아까 위에서 분해한 $A$를 다시 들고 와보자.

$$A = \begin{bmatrix} 2&1&1\\
4&-6&0\\
-2&7&2\end{bmatrix} $$

$$Ax = \begin{bmatrix}7\\-8\\18\end{bmatrix}$$

$LUx=b$꼴로 나타내면,

$$ \begin{bmatrix}1&0&0\\ 2&1&0 \\ -1&-1&1 \end{bmatrix}
\begin{bmatrix}2&1&1\\ 0&-8&-2\\ 0&0&1 \end{bmatrix}
\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix} = \begin{bmatrix}7\\-8\\18\end{bmatrix}$$

$y=Ux$를 정의하고, $Ly=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}7\\-8\\18\end{bmatrix}$$

$$y = \begin{bmatrix} 7\\-22\\3\end{bmatrix} $$

$y=Ux$를 풀면,

$$ \begin{bmatrix}2&1&1\\ 0&-8&-2\\ 0&0&1 \end{bmatrix} \begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}= \begin{bmatrix} 7\\-22\\3\end{bmatrix} $$

$$x = \begin{bmatrix} 1\\2\\3 \end{bmatrix} $$