4. LU decomposition

저번 강의에서 우리는 소거를 통해 A행렬이 소거가 완료된 행렬 U로 이동한다는 것을 배웠습니다.

이번 시간에는 두 개의 연산을 진행하는 행렬을 소거해보겠습니다.

 

$AB$의 역행렬을 구해봅시다. 개별적인 두 행렬의 역행렬을 구해야 합니다. 그리고 그 두 역행렬을 곱해야 하는데 곱하는 순서가 있습니다. 바로 역순으로 곱해줘야 합니다.

 

 

$ABB^{-1}A^{-1} = AB(AB)^{-1}$

 

 

 

$A(BB^{-1})A^{-1} = AIA^{-1} = AA^{-1} = I$

 

이렇게 역순으로 곱하게 되면 A와 A의 역행렬을 곱할 수 있게 됩니다. 

 

 

 

LU decomposition

 

LU 분해는 행렬의 가장 기본적인 분해입니다.

• $A = LU$ 여기서 U는 A에 소거를 진행한 결과물입니다.

 

설명을 위해 행렬 A이 존재한다고 하겠습니다. 이 행렬은 good matrix여서 소거법을 진행할 때 행 교환이 필요 없습니다.

이런 행렬을 소거하여 U를 만든다면 A와 U는 어떤 관계에 있을까요?

 

- 이러한 관계를 설명해주기 위해서 두 행렬을 연결 시켜주는 행렬 L을 구할 것입니다.

 

 

우선 행렬 A를 만들어보겠습니다.

 

 

$A = \left[\begin{matrix} 2 &  \\ 8 &   \end{matrix} \right]$

 

 

첫 번째 피벗은 2입니다. 그리고 4를 곱해서 소거를 진행할 수 있게 8을 넣어주겠습니다. 그리고 그다음에는 1을 넣어보겠습니다.

 

 

$A = \left[\begin{matrix} 2 & 1 \\ 8 &   \end{matrix} \right]$

 

 

여기서 $A_{22}$값으로 넣으면 안 되는 숫자는 무엇일까요? 4를 넣을 경우 column vector들이 같은 선상에 존재하게 되기 때문에 역행렬이 존재하지 않게 됩니다.

 

 

$A = \left[\begin{matrix} 2 & 1 \\ 8 &  6  \end{matrix} \right]$

 

 

마지막은 6을 넣어주겠습니다.

 

 

$ \left[\begin{matrix}  &  \\  &   \end{matrix} \right] \left[\begin{matrix} 2 & 1 \\ 8 &  6  \end{matrix} \right] = U $

 

 

이제 E라는 소거 행렬을 넣어주겠습니다. 2행 1열 값을 0으로 만들어 줘야 하기 때문에 이 행렬을 $E_{21}$이라고 부르겠습니다. 

 

 

$ \left[\begin{matrix} 1 & 0 \\ -4 &  1 \end{matrix} \right] \left[\begin{matrix} 2 & 1 \\ 8 &  6  \end{matrix} \right] =  \left[\begin{matrix} 2 & 1 \\ 0 &  3 \end{matrix} \right] $

 

 

다음과 같이 소거를 진행하기 위해서 행렬 $E_{21}$의 원소를 채워 행렬 U를 구했습니다. 이제 LU decomposition을 설명하기 위해서 $A = LU$로 나타내보면 (L은 $E_{21}$의 역행렬입니다.)

 

- $E_{21}A = U$

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

- $IA = E_{21}^{-1}U$

- $A = LU$

 

- 소거행렬의 역행렬이 행렬 L이 된다!

 

 

$  \left[\begin{matrix} 2 & 1 \\ 8 &  6 \end{matrix} \right]  = \left[\begin{matrix} 1 & 0 \\ 4 &  1 \end{matrix} \right] \left[\begin{matrix} 2 & 1 \\ 0 &  3  \end{matrix} \right] $

 

이것이 LU decomposition입니다. 추가적으로 U가 가지고 있는 피벗을 보기 편하게 하기 위해서 한번 더 분해를 하는 LDU decomposition이라는 방법도 존재합니다.

 

 

$  \left [\begin {matrix} 2 & 1 \\ 8 &  6 \end{matrix} \right]  = \left[\begin{matrix} 1 & 0 \\ 4 &  1 \end{matrix} \right] \left[\begin{matrix} 2 & 0 \\ 0 &  3  \end{matrix} \right] \left[\begin{matrix} 1 & \frac 1 2 \\ 0 &  1  \end{matrix} \right] $

 

오른쪽 항의 가운데 생성된 행렬은 U의 1행, 2행을 각행의 피벗으로 나눈 것입니다. (1행은 2로, 2행은 3으로)

 

$$\frac { \left[\begin{matrix} 2 & 1 \end{matrix} \right]} 2 , \frac { \left[\begin{matrix} 0 & 3 \end{matrix} \right]} 3$$

 

 

여기까지는 $2 \times 2$ 행렬이어서 간단했지만 이제 조금 더 복잡한 내용을 배워보기 위해서 $3 \times 3$ 행렬을 예로 들어보겠습니다. $3 \times 3$ 행렬 A가 존재할 때 우선 이 행렬의 원소가 0이 아닌 값으로 채워져 있다고 한다면 소거를 진행해주어야 합니다.

 

위에서 우리가 A와 U의 관계를 나타내 주기 위해서 L이나 E를 사용했습니다. 그런데 L을 사용한 방법과 E를 사용한 방법 중 더 좋은 방법은 L을 사용한 방법입니다. 왜 그럴까요?

 

1. $EA = U$

2. $A = LU$

 

첫 번째는 E를 사용한 방법이고 두 번째는 L을 사용한 방법입니다. 다르게 표현한다면 아래와 같이 나오게 됩니다. $2 \times 2$ 행렬에서는 E 행렬이 한 개라서 괜찮았지만 $3 \times 3$ 행렬에서는 다릅니다. 

 

1. $E_{32} E_{31} E_{21} A = U$ 

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

 

$3 \times 3$ 행렬 A를 가지고 예를 들어보겠습니다.

 

$A = { \left [\begin {matrix} 2 & 1 & 7 \\ 4 & -1 & 16 \\ 0 & -15 & 19 \end {matrix} \right]} $

 

여기서 소거법을 진행해 얻은 $E_{31}, E_{32}, E_{21}$ 중 행렬 $E_{31}$은 단위행렬이어서 무시하고 진행해도 괜찮습니다.  

 

 

 

위 사진에서 알 수 있듯이 행렬 E로 소거된 행렬은 3행 1열 부분에 10이라는 숫자가 생겼습니다. 그 반면에 행렬 L의 경우에는 추가되는 숫자가 없습니다. 여기서 행렬 E를 A에 곱하게 되면 결과적으로 U라는 값이 나오게 되지만 연산중 10이 A의 1번 행에 영향을 미치게 됩니다. 이러한 부분 때문에 방해를 받을 수도 있기 때문에 L이 더 좋은 표현입니다.

 

- 분해를 하는 이유는 어려운 행렬을 단순화 시켜주기 때문에 계산적 이점과 분석적 이점이 존재하기 때문이라고 합니다.

 

 

 

 

요약

 

- 분해는 하나의 행렬을 두 개 이상의 행렬 곱으로 표현한 것, $A = LU$ (A행렬을 두 행렬로 분해함)

- LU decompostion은 소거 전 행렬 $A$와 소거 후 행렬 $U$를 이어주는 행렬$L$을 찾는 방법임

- $EA = U$로 구하는 것보다 $A = LU$로 구하면 오차가 더 적어짐

- $A^{-1}$로 방정식으로 해를 구하는 것보다 LU 분해의 연산량이 $1/3$배 적습니다. 

- $A$가 sparse할 경우 L과 U도 sparse합니다. 하지만 A의 역행렬은 dense합니다. (희소행렬이 아니고 값이 많이 존재함)

 

- 그래서 LU decomposition이 메모리적 측면과 속도에서 큰 이점을 얻습니다.