LU분해

LU 분해는 주어진 행렬을 아래의 형태를 가지는 두 행렬의 곱으로 나누는 행렬분해

$A = L\;\;\;U$
$\begin{vmatrix}* & * & * \\ * & * & * \\ * & * & *\end{vmatrix}\, = \,\begin{vmatrix}* & 0 & 0 \\ * & * & 0 \\ * & * & *\end{vmatrix}\begin{vmatrix}* & * & * \\ 0 & * & * \\ 0 & 0 & *\end{vmatrix}$

L : lower triangular matrix(하삼각행렬)
U : upper triangular matrix(상삼각행렬)

LU 분해를 이용해 $Ax = b$ 문제를 간단히 해결할 수 있다.
$Ax = b \to (LU)x = b \to L(Ux) = b \to Ly = b, (Ux = y)$

먼저 전방대치법(Forward Substitution)으로 y를 구한다.
$L\;y = b$
$\begin{vmatrix}* & 0 & 0 \\ * & * & 0 \\ * & * & *\end{vmatrix} \begin{vmatrix} y_1 \\ y_2 \\ y_3\end{vmatrix} = \begin{vmatrix}*\\*\\*\end{vmatrix}$

후방대치법(Back Substitution)으로 x를 구한다.
$L\;y = b$
$\begin{vmatrix}* & * & * \\ 0 & * & * \\ 0 & 0 & *\end{vmatrix} \begin{vmatrix} x_1 \\ x_2 \\ x_3\end{vmatrix} = \begin{vmatrix}y_1 \\ y_2 \\ y_3\end{vmatrix}$

LU분해의 장점
$Ax=b$에서 역행렬 $A^{-1}$를 이용해 직접 구하는 것보다 LU 분해를 이용하는 것이 컴퓨터에서 수치적으로 안정적이다.
$b$가 자주 업데이트되는 경우, LU 분해하면 해를 실시간으로 구할 수 있다.