1. LU 분해(LU factorization)
이번 시간엔 행렬 $A$를 두 개의 삼각 행렬(triangular matrices)의 곱으로 표현하는 방법을 알아볼 겁니다. 다음의 $3 \times 3$ 행렬 $A$를 가우스 소거(Gauss elimination) 해봅시다.
\[A = \begin{pmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{pmatrix}\] \[R_2 \leftarrow R_2 - 2R_1\] \[\begin{pmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ -2 & -3 & 7 \end{pmatrix}\] \[R_3 \leftarrow R_3 + R_1\] \[\begin{pmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ 0 & 1 & 5 \end{pmatrix}\] \[R_3 \leftarrow R_3 - R_2\] \[\begin{pmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ 0 & 0 & 4 \end{pmatrix} = U\]여기서 멈춥니다. 위 행렬은 선행 성분(leading component)을 $1$로 만들어주지 않은 행사다리꼴(row-echelon form)로 상삼각행렬(upper triangular matrices)입니다. 여기까지 행한 기본행연산을 기본행렬(elementary matrices)로 나타내면 다음과 같습니다.
\[E_1 = \begin{pmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \quad E_2 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}, \quad E_3 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1 & 1 \end{pmatrix}\] \[E_3 E_2 E_1 A = U\]기본행렬은 역행렬이 존재하므로 $A$에 대해 정리하면 다음과 같습니다.
\[A = E_1^{-1} E_2^{-1} E_3^{-1} U\] \[E_1^{-1} = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \quad E_2^{-1} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{pmatrix}, \quad E_3^{-1} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}\]기본행렬 $E_i$와 기본행렬의 역행렬 $E_i^{-1}$ 모두 대각 성분이 $1$인 하삼각행렬(lower triangular matrices)입니다. 대각 성분이 모두 $1$인 하삼각행렬끼리의 곱의 결과는 똑같이 대각 성분이 모두 $1$인 하삼각행렬이 됩니다.
\[E_1^{-1} E_2^{-1} E_3^{-1} = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}\] \[= \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}\] \[= \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & 1 & 1 \end{pmatrix} = L\]따라서 다음과 같이 쓸 수 있습니다.
\[A = LU\]$\text{check)}$
\[LU = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ 0 & 0 & 4 \end{pmatrix} = \begin{pmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{pmatrix} = A\]행렬을 하삼각행렬(대각 성분이 모두 $1$)과 상삼각행렬의 곱으로 나타내는 것을 LU 분해(LU factorization or LU decomposition)라고 합니다. LU 분해는 소거 과정에서 행교환이 필요 없는 경우 항상 가능합니다.
2. 산가지로 풀어 보자
2.1 행렬 $A$에서 행렬 $U$까지
사진의 산가지 조작과 아래 표의 행렬을 같은 순서로 보면, 각 조작이 가우스 소거의 어느 단계인지 바로 확인할 수 있습니다.
| 단계 | 산가지에서 하는 연산 | 대응하는 LaTex 행렬 |
|---|---|---|
| 시작 | 주어진 행렬 $A$를 놓는다. | $\begin{pmatrix} 2 & 4 & -2 \ 4 & 9 & -3 \ -2 & -3 & 7 \end{pmatrix}$ |
| 1 | 1행의 $-2$배를 2행에 더한다. | $R_2 \leftarrow R_2 - 2R_1$ $\begin{pmatrix} 2 & 4 & -2 \ 0 & 1 & 1 \ -2 & -3 & 7 \end{pmatrix}$ |
| 2 | 1행을 3행에 더한다. | $R_3 \leftarrow R_3 + R_1$ $\begin{pmatrix} 2 & 4 & -2 \ 0 & 1 & 1 \ 0 & 1 & 5 \end{pmatrix}$ |
| 3 | 2행을 3행에서 뺀다. | $R_3 \leftarrow R_3 - R_2$ $\begin{pmatrix} 2 & 4 & -2 \ 0 & 1 & 1 \ 0 & 0 & 4 \end{pmatrix} = U$ |
행렬 A가 있습니다.
이 상태에서 1행에 2를 곱한 것을 수행할 대상이 되는 2행 오른쪽에 올립니다.
2행 오른쪽에 올린 것에 다시 -1을 곱해 -2배로 만듭니다.
2행에 그 오른쪽에 올려 둔 것을 더하여 줍니다.
-2배는 실수하지 않게 음수 연산을 분리하여 처리합니다.
1행을 그대로 3행 오른쪽에 올립니다.
3행에 그 오른쪽에 둔 것을 더하여 줍니다.
2행을 그대로 3행 오른쪽에 둡니다.
빼서 그대로 상삼각행렬을 만듭니다. 이 경우는 연산이 단순해서 -1배 처리하든, 그대로 뺄셈으로 간주하고 처리하든 무관합니다. 아래에선 -1배 처리하는 예제로 보이겠습니다.
이제 행렬 U가 완성되었습니다.
3. 기본행연산에 대응하는 각 행렬을 만들기
이 경우, 기본행연산을 3번 수행하였으니 만들어야 할 행렬은 3개입니다.
첫 번째 연산은 1행을 -2배 하여 2행에 더하는 스칼라배 후 덧셈이었습니다.
1행의 -2배를 2행 오른쪽에 둡니다.
1행의 -2배를 2행에 더합니다.
행렬 $E_1$입니다.
1행을 그대로 3행 오른쪽에 둡니다.
1행을 그대로 3행에 더합니다.
행렬 $E_2$입니다.
2행의 -1배를 3행 오른쪽에 둡니다.
2행의 -1배를 그대로 3행에 더합니다.
행렬 $E_3$입니다.
4. 역행렬 구하기
좌측에 역행렬을 구할 대상이 될 행렬을 두고, 우측에 단위 행렬을 둡니다.
좌측이 단위 행렬이 될 때까지 기본행연산을 양쪽 행렬에 진행합니다.
4.1 세 개의 행렬에 대한 역행렬
$E_1^{-1}$ 행렬입니다.
$E_2^{-1}$ 행렬입니다.
$E_3^{-1}$ 행렬입니다.
5. 세 개의 역행렬에서 행렬 $L$까지
$E_1^{-1}$을 좌측에 두고 $E_2^{-1}$를 우측에 둡니다.
$E_1^{-1}$에 $E_2^{-1}$를 곱합니다.
$E_1^{-1}$에 $E_2^{-1}$를 곱한 것을 좌측에 두고, $E_3^{-1}$를 우측에 둡니다.
계산 도중 연산이 복잡해지면, 행렬곱에서 (i,j)를 구하기 쉽게 좌측 귀퉁이에 공간을 내어 연산 결과를 펼친 후 더합니다.
이제 맨 오른쪽에 있는 것이 $L$입니다. 여기에 앞에서 구한 $U$를 곱해 원래 행렬 $A$가 되는지 확인합니다.
따라서 연산 결과는 $A = LU$로 정상입니다.
6. 빠른 연산 기술
이제 역행렬을 구하고, $L$을 구하는 원리를 알았으니 빠른 셈을 해 봅시다.
앞서서 단위행렬을 산가지로 둡니다.
앞서서, 상삼각행렬을 구할 때 1행의 2배를 2행에서 뺐습니다.
이것은 -2 스칼라배입니다.
부호를 반전하여 2로 단위 행렬의 (2,1)에 기입합니다.
앞서 1행을 3행에 더하였습니다.
이것은 1 스칼라배입니다.
부호를 반전하여 -1로 단위 행렬의 (3, 1)에 기입합니다.
마찬가지로 2행의 1배를 3행에서 뺐습니다.
이것은 -1 스칼라배입니다.
부호를 반전하여 1로 단위 행렬의 (3, 2)에 기입합니다.
이와 같이 연산하면 산가지를 매우 적게 옮기고도 행렬 L을 구할 수 있습니다.