[선형대수] 3강. LU 분할

1. 가우스 소거법 행렬로 풀기

앞에서 배운 가우스 소거법을 행렬의 곱으로 바꾸는 작업을 해보자.

우선 가우스 소거법의 단계를 정리해본다.

1. (1)을 이용해 (2)의 u를 제거
2. (1)을 이용해 (3)의 u를 제거
3. (2)를 이용해 (3)의 v를 제거

순서를 따라 해본다.

1. (1)을 이용해 (2)의 u를 제거
   $\begin{bmatrix}E_{21}\end{bmatrix}\begin{bmatrix}2&1&1\\ 4&-6&0 \\ -2&7&2\end{bmatrix}=\begin{bmatrix} 2 & 1 & 1 \\ 0 & -8 & -2 \\ -2 & 7 & 2\end{bmatrix}$
   제거해야할 u는 (2)에 있으므로 (1), (3)은 변하지 않는다. 그러므로 $E_{21}$의 첫 번째와 세 번째 행은 Identity Matrix이다.
   (2)의 u의 계수인 4를 지우기 위해 (1)에 -2를 곱하고 (2)와 더해야 한다. 그러므로 두 번째 행은 (-2, 1, 0)이 된다.
   $E_{21} = \begin{bmatrix}1&0&0\\ -2&1&0 \\ 0&0&1\end{bmatrix}$
   $E_{21}$은 1번 식을 이용해 2번 식을 바꾸는 행렬이다.

2. (1)을 이용해 (3)의 u를 제거
   앞에서 했던 것과 똑같다.
   $\begin{bmatrix}E_{31}\end{bmatrix}\begin{bmatrix}2&1&1\\ 4&-6&0 \\ -2&7&2\end{bmatrix}=\begin{bmatrix} 2 & 1 & 1 \\ 4&-6&0 \\ 0&8&3\end{bmatrix}$
   제거해야할 u는 (3)에 있으므로 (1), (2)는 변하지 않는다.그러므로 $E_{31}$의 첫 번째와 두 번째 행은 Identity Matrix이다.
   (3)의 u의 계수인 -2를 지우기 위해 (1)과 (3)를 더해야 한다. 그러므로 두 번째 행은 (1, 0, 1)이 된다.
   $E_{31} = \begin{bmatrix}1&0&0\\ 0&1&0 \\ 1&0&1\end{bmatrix}$

3. (2)를 이용해 (3)의 v를 제거
   앞에서 했던 것과 똑같다. 이 단계는 이미 (2), (3)이 수행된 후다. 그래서 2, 3 행의 바뀌었다.
   $\begin{bmatrix}E_{32}\end{bmatrix}\begin{bmatrix}2&1&1\\ 0 & -8 & -2 \\ 0&8&3\end{bmatrix}=\begin{bmatrix} 2 & 1 & 1 \\ 0 & -8 & -2 \\ 0&0&1\end{bmatrix}$
   제거해야할 v는 (3)에 있으므로 (1), (2)는 변하지 않는다.그러므로 $E_{32}$의 첫 번째와 두 번째 행은 Identity Matrix이다.
   (3)의 u의 계수인 8를 지우기 위해 (2)과 (3)를 더해야 한다. 그러므로 두 번째 행은 (0, 1, 1)이 된다.
   $E_{32} = \begin{bmatrix}1&0&0\\ 0&1&0 \\ 0&1&1\end{bmatrix}$

정리

$$\begin{bmatrix}E_{32}\end{bmatrix}\begin{bmatrix}E_{31}\end{bmatrix}\begin{bmatrix}E_{21}\end{bmatrix}\begin{bmatrix}2&1&1\\ 4&-6&0 \\ -2&7&2\end{bmatrix}=\begin{bmatrix} 2 & 1 & 1 \\ 0 & -8 & -2 \\ 0 & 0 & 1 \end{bmatrix}$$

연립 방정식에서 계수를 추출한 행렬에서 가우스 소거를 하기 위한 행렬 $E_{21}$, $E_{31}$, $E_{32}$를 곱하면, U(Upper Triangular Matrix)가 나온다.

Elementary Matrix in Gauss Elimination

$$E_{21}=\begin{bmatrix}1&0&0\\ -l_{21}&1&0 \\ 0&0&1\end{bmatrix}=(2)-l_{21}(1)$$

$E_{21}$의 의미: $(2)$에서 $l_{21}(1)$을 빼서 $(2)'$를 만들었다.

$\Rightarrow (2)-l_{21}(1)=(2)'$

$\Rightarrow (2)=(2)'+l_{21}(1)$

 

즉, $E_{21}A=A'$이므로 $E_{21}^{-1}A'=A$이며, 이것은 가우스 소거의 역과정이다.(U에서 처음의 식을 만듦)

또한, $E_{21}^{-1}=\begin{bmatrix}1&0&0\\ l_{21}&1&0 \\ 0&0&1\end{bmatrix}$이다.($l_{21}$의 부호만 바뀜) 그럼 결국 $A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U$를 구할 수 있다.

 

$A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U$

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

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

 

여기에 있는 $\begin{bmatrix}1&0&0\\ l_{21}&1&0 \\ l_{31}&l_{32}&1\end{bmatrix}$도 삼각행렬이다.(Lower Triangular Matrix)

$=LU$

 

Matrix A를 LU로 표현하는 것을 LU분할이라고 한다.

LU분할을 하면 그냥 A로 두는 것보다 계산하기 훨씬 편해진다고 한다.(특히 하드웨어 설계를 할 때 많이 쓰인다고 함)

 

ex1)

$L=\begin{bmatrix}1&0&0\\ 3&1&0 \\ 2&4&1\end{bmatrix}$은 다음과 같은 정보를 함축하고 있다.

1. $(2)-3(1)$
2. $(3)-2(1)$
3. $(3)-4(2)$

L행렬 안에 이 정보를 함축하고 있다. (가우스 소거가 어떤 과정을 거치는지 나타냄)

 

ex2)

$A=\begin{bmatrix}1&2\\ 3&8 \end{bmatrix}\Rightarrow U=\begin{bmatrix}1&2\\ 0&2 \end{bmatrix}, L=\begin{bmatrix}1&0\\ 3&1 \end{bmatrix}$

 

ex3)

$A=\begin{bmatrix}1&0&0\\ l_{21}&1&0 \\ l_{31}&l_{32}&1\end{bmatrix}$일 때, $A=L$이다. 즉, $A=LI$이고, 이 때 $U=I$다.

 

ex4)

$U=\begin{bmatrix}d_1&U_{12}&U_{13}\\ 0&d_2&U_{23} \\ 0&0&d_3\end{bmatrix}$

$=\begin{bmatrix}d_1&0&0\\ 0&d_2&0 \\ 0&0&d_3\end{bmatrix}\begin{bmatrix}1&\frac {U_{12}} {d_1}&\frac {U_{13}} {d_1}\\ 0&1&\frac {U_{23}} {d_2} \\ 0&0&1\end{bmatrix}$

$=DU$

 

d로 이루어진 Matrix를 Diagnal Matrix라고 한다.

정리

$A=LU=LDU$

D는 계산하기 편하다.

• LU분할은 unique하다.
• Pivoting도 Matrix로 표현 가능하다.(Permutation Matrix)

Pivoting의 예)

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

 

왼쪽에 있는 행렬을 $P_{21}$이라고 표현하며, 첫 번째 행과 두 번째 행을 바꾼다. 이 Matrix는 특정 행과 열에 1이 단 하나만 있는 것이 특징이다.