선형대수 - (3) LU 분할

가우스 소거법과 선형 결합

가우스 소거법에서 일정 계수를 곱해주고 특정 행을 빼는 행위는,
선형변환으로 표현할 수 있고, 이 선형변환은 행렬로 표현될 수 있다.

다음과 같은 연립방정식이 표현된 행렬이 있다.
$\begin{bmatrix} 2 \quad 1 \quad 1 \\ 4 \quad -6 \quad 0 \\ -2 \quad 7 \quad 2 \end{bmatrix}$

가우스 소거법의 첫번째 단계를 진행하면,
첫번째 행에 계수를 곱해 두번째 행에서 빼주는 것이다: (2) - 2 * (1)
이를 진행하면 다음과 같은 행렬이 나온다:
$\begin{bmatrix} 2 \quad 1 \quad 1 \\ 0 \quad -8 \quad 2 \\ -2 \quad 7 \quad 2 \end{bmatrix}$

이는 선형변환, 즉 다른 행렬로 표현될 수 있다.
다음은 이를 선형변환을 표현하는 행렬과 곱해주는 것을 표현한다:
$ \begin{bmatrix} 1 \quad 0 \quad 0 \\ -2 \quad 1 \quad 0 \\ 0 \quad 0 \quad 1 \end{bmatrix} \begin{bmatrix} 2 \quad 1 \quad 1 \\ 4 \quad -6 \quad 0 \\ -2 \quad 7 \quad 2 \end{bmatrix} = \begin{bmatrix} 2 \quad 1 \quad 1 \\ 0 \quad -8 \quad 2 \\ -2 \quad 7 \quad 2 \end{bmatrix} $

행렬을 잘 살펴보면, 첫번째 행렬이 선형변환을 표현해 주고 있다.
첫번째 행과 세번째 행은 변화가 없으니 I와 같은 형태가 된다.
즉, 앞의 두 행렬을 곱하면 마지막이 나오도록 선형변환을 한것이다.

마지막 줄의 변화는 다음과 같다: (3) - -1 * (1)
그리고 이를 선형변환으로 표현하면 다음과 같다:
$ \begin{bmatrix} 1 \quad 0 \quad 0 \\ 0 \quad 1 \quad 0 \\ 1 \quad 0 \quad 1 \end{bmatrix} \begin{bmatrix} 2 \quad 1 \quad 1 \\ 4 \quad -6 \quad 0 \\ -2 \quad 7 \quad 2 \end{bmatrix} = \begin{bmatrix} 2 \quad 1 \quad 1 \\ 4 \quad -6 \quad 0 \\ -2 \quad 7 \quad 2 \end{bmatrix} $

자세히 보면 첫번째와 두번째 식은 상관이 없기 때문에 I와 같은 것을 볼 수 있다.
이를 표기하는 방법은 다음과 같다:
첫번째 변환은 행렬 A에 2와 1번줄을 사용해 Elementary (E) 행렬을 곱해주었기 때문에 $E_{21}A$ 가 된다.
두번째 변환은 3과 1번줄을 사용해 곱해주었기 때문에 $E_{31} E_{21} A$가 된다.
이를 적용한 결과는 가우스 소거법을 적용한 다음과 같은 행렬이 된다.
$\begin{bmatrix} 2 \quad 1 \quad 1 \\ 0 \quad -8 \quad 2 \\ 0 \quad 8 \quad 3 \end{bmatrix}$

Elementary Matrix란?

위의 예제에서 $E_{21}$을 조금 일반화 시켜보겠다.
$\begin{bmatrix} 1 \quad 0 \quad 0 \\ -l_{21} \quad 1 \quad 0 \\ 0 \quad 0 \quad 1 \end{bmatrix}$

따라서 위의 $E_{21}$은,
(2) - $l_{21}$ * (1) = (2)'
을 하는 Operation이 된다.

LU분할

위의 에제에서 A에서 소거를 끝낸 U값을 구한다고 해보자.
이는 다음과 같은 Operation으로 표현될 수 있다.
$E_{32} E_{31} E_{21} A = U$

$ \begin{bmatrix} 1 \quad 0 \quad 0 \\ 0 \quad 1 \quad 0 \\ 0 \quad -l_{32} \quad 1 \end{bmatrix} \begin{bmatrix} 1 \quad 0 \quad 0 \\ 0 \quad 1 \quad 0 \\ -l_{31} \quad 0 \quad 1 \end{bmatrix} \begin{bmatrix} 1 \quad 0 \quad 0 \\ -l_{21} \quad 1 \quad 0 \\ 0 \quad 0 \quad 1 \end{bmatrix} A $

그리고 반대로 U에서 다시 A를 구하는 방법은 다음과 같다.
A = $E_{21}^{-1} E_{31}^{-1} E_{22}^{-1} U$

$ A = \begin{bmatrix} 1 \quad 0 \quad 0 \\ l_{21} \quad 1 \quad 0 \\ 0 \quad 0 \quad 1 \end{bmatrix} \begin{bmatrix} 1 \quad 0 \quad 0 \\ 0 \quad 1 \quad 0 \\ l_{31} \quad 0 \quad 1 \end{bmatrix} \begin{bmatrix} 1 \quad 0 \quad 0 \\ 0 \quad 1 \quad 0 \\ 0 \quad l_{32} \quad 1 \end{bmatrix} U $

이 때 두번쨰 수식에서 inverse들을 모두 곱하면 다음과 같은 행렬이 나온다.
$\begin{bmatrix} 1 \quad 0 \quad 0 \\ l_{21} \quad 1 \quad 0 \\ l_{31} \quad l_{32} \quad 1 \end{bmatrix}$
이 행렬을 Lower Trianglular Matrix라고 해서 L이라고 부른다.

Ax = b 라는 연립 방정식이 있을 때,
A = L U 두개의 삼각행렬로 분리할 수 있다

따라서 행렬 A는 L과 U로 위와 같이 분할될 수 있고,
이를 LU분할이라고 한다.
(LU factorization / LU decomposition)

LU 분할의 의미

Ax = b에서 A를 행렬이 아니라, 하나의 시스템이라고 생각해 보자.

이 시스템은 u, v, w를 통해 b값들을 구하는 시스템이다.
그리고 행렬에서의 계수들, 즉 u, v, w에 곱해지는 수들은 시스템의 중요한 매개변수들이다.
시스템을 정의해주는 이 중요한 계수들을 알아내는 방법이 LU분할인 것이다.

또한 L이나 U와 같은 삼각행렬은 기본 행렬에 비해 연산이 쉽다.
예를 들면, inverse나 determinant등을 구하기가 용이하다.
따라서 LU분할을 하면 기존 행렬보다 여러가지 계산이 용이해 진다.

한가지 기억할 점은, 행렬 A에 대해 LU분할이 된다면, L과 U는 Unique한 값이 된다.
함수의 영역에서 Unique하다는 의미는, 각각의 x값들에 대해
각기 다른 y값이 있다는 의미이다.

이는 위의 시스템 A가 다음과 같이 L U로 나눠졌을 때도 같은 값을 내야한다는 의미이다.

대각 행렬 (Diagonal Matrix)

Upper Triangle U는 또 다음과 같이 분해될 수 있다.
$ U = \begin{bmatrix} d_1 \quad u_{12} \;\;\;\; u_{13} \quad ... \quad u_{1n} \\ d_2 \quad \quad \quad \\ \quad \quad\quad d_3 \quad \quad \\ \quad \quad\quad \quad\quad ... \quad \\ \quad \quad\quad \quad \quad\quad\quad\quad d_n \end{bmatrix} $

$ = \begin{bmatrix} d_1 \quad \quad \quad \quad \\ \quad d_2 \quad \quad \quad \\ \quad \quad d_3 \quad \quad \\ \quad \quad \quad ... \quad \\ \quad \quad \quad \quad d_n \end{bmatrix} \begin{bmatrix} 1 \quad \frac{u_{12}}{d_1} \quad \frac{u_{13}}{d_1} \quad ... \quad \frac{u_{1n}}{d_1} \\ \quad 1 \quad \quad \quad \\ \quad \quad\quad 1 \quad \quad \\ \quad \quad\quad \;\;\quad\quad ... \quad \\ \quad \quad\quad \quad \quad\quad\quad\quad 1 \end{bmatrix} $
(위수식 내의 행렬의 공백은 0을 의미한다)
위의 식에서 대각선에 해당하는 값들만 있는 행렬을 Diagonal Matrix, D라고 표현하고,
따라서 U는 다시 U = DU 로 표현될 수 있다.
그리고 A는 A = LDU로 표현될 수도 있다.

대각행렬의 특징중 하나는, 제곱을 했을 때, 가운데 값들만 제곱값이 된다.
$ D = \begin{bmatrix} d_1^n \quad \quad \quad \quad \\ \quad d_2^n\quad \quad \quad \\ \quad \quad d_3^n \quad \quad \\ \quad \quad \quad ... \quad \\ \quad \quad \quad \quad d_m^n \end{bmatrix} $

Row Exchange (Pivoting)

가우스 소거법에서 Pivot에 해당하는 값이 0이 될 때,
Pivoting을 통해 식의 순서를 바꿔주는 것이다.
이 변환 작업 역시 행렬로 표현이 가능한데, 이를 Permutation이라고 부른다.

앞의 예제를 그대로 이용해 보겠다.
$\begin{bmatrix} 2 \quad 1 \quad 1 \\ 4 \quad -6 \quad 0 \\ -2 \quad 7 \quad 2 \end{bmatrix}$

위의 행렬의 2번 줄과 1번줄을 바꾸는 작업은 다음과 같다:
$ \begin{bmatrix} 0 \quad 1 \quad 0 \\ 1 \quad 0 \quad 0 \\ 0 \quad 0 \quad 1 \end{bmatrix} \begin{bmatrix} 2 \quad 1 \quad 1 \\ 4 \quad -6 \quad 0 \\ -2 \quad 7 \quad 2 \end{bmatrix}$

이를 표기법으로 표기하면 2번줄과 1번줄을 바꾸는 작업이기 때문에 다음과 같다: $P_{21}$

Permutation

위의 변환 행렬을 정의하면 다음과 같다:
Identity 행렬과 같은 행들로 이뤄져있고, 숫자 1이 모든 행과 모든 열에 하나씩만 존재하다

$P_{31} = \begin{bmatrix} 0 \quad 0 \quad 1 \\ 0 \quad 1 \quad 0 \\ 1 \quad 0 \quad 0 \end{bmatrix}$

Permutation을 여러번 적용할 때는, 먼저 Permutation 행렬들을 곱해준 뒤,
변환을 적용할 행렬에 적용해도 된다.
그리고 Permutation 행렬들은, 교환법칙을 성립하지 않는다.
이는 즉 $P_{32}P_{21} \neq P_{21}P_{32}$ 라는 의미이다.

Permutation 행렬의 Inverse를 구하면 신기하게도, Transpose와 같은 결과가 나온다.
$P^{-1} = P^{T}$

마지막으로 가우스 소거법을 모두 행렬로 표현하게 되면 다음과 같이 표현이 가능하다.
A = P^TLU