[인공지능 수학 - 미적분]3강 : LU분해
LU 분해(LU decomposition): 가우스 소거법을 행렬로 표현
가우스 소거법을 프로그래밍적으로 지원하는 알고리즘이 존재한다.
numpy의 가우스 소거법은 LU분해라는 방식으로 제공된다.
LU분해는 지금까지 배운 가우스 소거법을 알고리즘의 형태가 아닌 행렬의 결과물로 표현하는 방식이다.
행렬분해(matrix decomposition)의 의미
인수분해를 생각해보자.
$12 = 3 * 4$
숫자의 인수분해는 주어진 숫자를 여러 숫자의 곱으로 분해하여 표현하는 것이다.
인수분해는 다음과 같은 경우에 쓰인다.
- 분수의 약분
- 두 수의 최대공약수 구하기
- 두 수의 최소공배수 구하기
즉, 주어진 숫자를 인수분해 한 상태로 가지고 있으면 여러모로 계산이 편한 경우가 많다.
이 아이디어를 행렬에 도입한게 행렬분해이다.
다음은 대표적인 행렬분해이다. - LU 분해(LU decomposition)
- QR 분해(QR decomposition)
- 특이값 분해(SVD, Singular Value decomposition)
LU분해는 가우스 소거법을 행렬의 형태로 나타낸 것이다. 우선 LU분해부터 배워보자.
LU decomposition(LU 분해)
LU 분해는 주어진 행렬을 아래의 형태를 가지는 두 행렬의 곱으로 나누는 행렬분해이다.
$A = LU$는 다음과 같이 표현할 수 있다.
$
\begin{bmatrix}
\alpha & \alpha & \alpha\cr
\alpha & \alpha & \alpha\cr
\alpha & \alpha & \alpha
\end{bmatrix}
=
\begin{bmatrix}
\alpha & 0 & 0\cr
\alpha & \alpha & 0\cr
\alpha & \alpha & \alpha
\end{bmatrix}
*
\begin{bmatrix}
\alpha & \alpha & \alpha\cr
0 & \alpha & \alpha\cr
0 & 0 & \alpha
\end{bmatrix}
$
- 행렬 L : lower triangular matrix(하삼각행렬)
- 행렬 U : upper triangular matrix(상삼각행렬)
주이진 행렬 A가 LU 분해되어 있으면 어떤 장점이 있을까?
LU 분해를 이용해 $Ax = b$문제를 아래와 같이 나타내면
$Ax = b$ -> $(LU)x = b$ -> $L(Ux) = b$ -> $Ly = b$ (단, $Ux = y$)
선형시스템을 다음과 같이 두 단계로 간단히 해결할 수 있음을 알 수 있다. 1. y를 구하는 단계, 2. x를 구하는 단계
- Forward-substitution(전방대치법): y구하기
$Ly = b$
$ \begin{bmatrix} \alpha & 0 & 0\cr \alpha & \alpha & 0\cr \alpha & \alpha & \alpha \end{bmatrix} * \begin{bmatrix} y_1\cr …\cr y_n \end{bmatrix} = \begin{bmatrix} \alpha\cr \alpha\cr \alpha \end{bmatrix} $ - Back-substitution(후방대치법): 1번을 통해 구한 y를 이용해 x구하기
$Ux = y$
$ \begin{bmatrix} \alpha & \alpha & \alpha\cr 0 & \alpha & \alpha\cr 0 & 0 & \alpha \end{bmatrix} * \begin{bmatrix} x_1\cr …\cr x_n \end{bmatrix} = \begin{bmatrix} y_1\cr …\cr y_n \end{bmatrix} $
LU decomposition(LU 분해)의 의미
LU 분해는 가우스 소거법의 forward elimination(전방소거법)을 행렬로 코드화 한 것이다.
- L : 행렬 A를 전방소거하는데 쓰인 replacement와 scaling에 대한 EROs를 기록해 둔 행렬
- U : 행렬 A를 전방소거한 후 남은 upper triangular matrix(상삼각행렬)
- P : 행렬 A를 전방소거하는데 쓰인 interchange에 대한 EROs를 기록해 둔 행렬(옵션)
그래서 사실 LU분해라고 하면, A = PLU 가 리턴이 된다.
여기서는 LU 분해를 유도하는 수학적인 내용은 다루지 않지만, LU 분해가 가우스 소거법의 forward elimination(전방소거법)와 의미가 거의 같다는 점을 기억!
LU decomposition(LU 분해)의 활용
LU 분해는 다음의 이유로 활용된다.
- 수치적 안정성 : 선형시스템 $Ax = b$의 해를 역행렬 $A^{-1}$를 이용해 직접 구하는 것 보다 PLU 분해를 이용하는 것이 좀 더 수치적으로 안정적이다.
- b가 자주 업데이트 되는 경우 : 선형시스템 $Ax = b$에서 행렬 A는 고정되어 있고 b가 자주 변하는 문제가 종종 있다. 이런 경우, 행렬 A를 미리 PLU로 분해해 둔다면, b가 업데이트될 때마다 선형시스템의 해 x를 실시간으로 구할 수 있습니다. 공학적으로는 위의 두가지 이유 중 두번째 이유로 인해 LU분해를 이용하는 경우가 굉장히 많다.