[Linear Algebra] Lecture 4, LU Decomposition(LU 분해)

Introduction

이번에 선형대수를 공부하면서 내용을 정리해보았습니다.

강의 영상 : https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/video_galleries/video-lectures/

Video Lectures | Linear Algebra | Mathematics | MIT OpenCourseWare

스터디 github : https://github.com/jwkweon/study-linear-algebra

GitHub - jwkweon/study-linear-algebra

참고한 블로그 :

https://blog.naver.com/PostView.naver?blogId=skkong89&logNo=221390709589&categoryNo=48&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postList&userTopListOpen=true&userTopListCount=30&userTopListManageOpen=false&userTopListCurrentPage=1 

Lecture 4: Factorization into A = LU

https://twlab.tistory.com/12

[Linear Algebra] Lecture 4 LU Decomposition(분해)

(주로 https://twlab.tistory.com/12 블로그의 사진과 내용을 보면서 공부했고 추가로 나머지 블로그를 참고하였습니다.)

(저는 제가 이해하기 쉽게 요약해서 적었으므로 좀더 자세히 공부하고싶다면 위 블로그를 참고하시면 됩니다.)

---

행렬곱셈의 Inverse

LU 분해를 배우기전 행렬곱셈의 Inverse에 대해 공부해보자.

어떤 행렬 A가 있고 행렬 A의 역행렬을 알고 있을 때 다음과 같은 식이 성립함을 배웠다.

$$ A A^{-1} = I = A^{-1} A $$

 

만일, non-singular이고 정방행렬인 A와 B가 있다고 가정하자. 이 두 행렬 AB가 곱한 형태에 어떤 역행렬을 곱하여 단위행렬을 얻고자 하면 어떻게 곱해야 할까? 먼저, 역행렬을 뒤에 곱한다고 하자.

$$ AB \Box \Box = I $$

 

행렬은 순서대로 연산되니 뒤에서 B와 먼저만나니 맨앞에는 B의 역행렬 그 뒤에는 A의 역행렬이 오면 될 것이다.

$$ A B B^{-1} A^{-1} = I $$

$$ BB^{-1} = I, A I  A^{-1} = A A^{-1} = I $$

 

이번에는, 역행렬을 앞에 곱한다고 해보자. 아래와 같이 나오는게 당연할 것이다.

$$ B^{-1} A^{-1} A B = I $$

 

즉, 단위행렬을 만들기 위해서는 역행렬을 곱해줄 때에는 각 행렬의 역행렬이 본래 자신의 행렬과 붙을 수 있게, 원래 행렬 곱셈의 반대 순서로 역행렬을 곱해주면 된다.

따라서,

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

즉, 행렬의 곱의 역행렬을 위와 같이 찾을 수 있다.

---

전치(Transpose)

이번에는 행렬곱셈의 전치에 대해 알아보자.

전치란 Row와 Column이 서로 바뀐다 생각하면된다. 행렬에서 대각선을 중심으로 180도 뒤집는다고 생각하면 된다.

$$ \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} \underset{Transpose}{\Longrightarrow} \begin{bmatrix} a_{11} & a_{21} \\ a_{12} & a_{22} \end{bmatrix} ^T $$

$$ A \quad \quad \quad \quad \quad \quad \quad A^T $$

(참고로 $ I^T = I $ 이다)

 

행렬 곱셈에 Transpose를 적용해보자. 정방행렬인 A와 A의 역행렬을 곱해서 단위 행렬을 만드는 식이 있을 때, 이 식을 Transpose해보자. 어떤 결과가 나올까?

$$ AA^{-1} = I \underset{Transpose}{\Longrightarrow} (AA^{-1} )^T = (I)^T \Rightarrow (A^{-1} )^T (A)^T = I $$

위 결과를 보면 A와 A 역행렬이 곱하는 순서가 반대로 된다.

마지막 줄에서 A의 역행렬의 Transpose는 -> A의 Transpose의 역행렬로 바꿀 수 있다. 아래 식을 보면 된다.

(단, 각각의 단일 행렬에 대해서만 적용된다)

$$ (A^{-1})^T = (A^T)^{-1} $$

즉, (-1)과 (T)가 자리가 바뀌었다.

 

한번, 예로 봐보자.

$$ \underset{R^{T}}{\begin{bmatrix} 1 & 3 \\ 2 & 3 \\ 4 & 1 \end{bmatrix}^T} = \underset{R}{\begin{bmatrix} 1 & 2 & 4 \\ 3 & 3 & 1 \end{bmatrix}} $$

$$ ( 3 \times 2 ) \quad \quad ( 2 \times 3) $$

 

따라서, 전치의 정의를 써보면

$$ ( A^{T} )_{ij} = A_{ji} $$

i : index of row, j : index of column

따라서, 전치를 하면 i, j 두 index가 바뀌게 된다. $ R_{12} $ 가 $ R_{21} $이 된걸 위 예제로 알 수 있다.

---

LU Decomposition(Factorization)

Decomposition(Factorization)이라는 것은 분해라는 뜻이다.

어떤 시스템 혹은 데이터를 표현한 행렬 A를 인수분해 한다는 뜻이다.

행렬 분해(Matrix Decomposition)이란? 선형대수에서 어떤 행렬을 여러 행렬들의 곱으로 표현하는 것을 의미한다.

행렬 분해를 왜 할까? 그 이유는 우리가 중학교 때 배웠던 인수분해를 하는 이유와 같은 맥락이다. 우리는 어떤 방정식을 풀 때 인수분해를 해서 쉽게 방정식의 해를 구한다. 마찬가지로 행렬에서도 적용하면 된다.

즉, 시스템 행렬을 단순화시켜 우리가 쉽게 분석을 할 수 있게 된다.

행렬 분해 방법은 SVD, QRD 등 다양한 방법이 있지만, 가장 기본적인 형태인 LU Decomposition에 대해 알아보자.

 

A=LU 분해 뜻을 해석해보면 어떤 행렬 A가 있을 때 하삼각 행렬(Lower triangular matrix)과 상삼각 행렬(Upper triangluar matrix)의 곱으로 분해하여 나타내는 것을 의미한다. LU는 Lower의 L과 Upper의 U를 따서 붙인 이름이다.

 

지난번(Lecture 2)에서 배운 소거행렬 $ E_{21} $ 을 통해 U행렬을 만드는 과정을 다시 떠올려보자.

$$ \underset{E_{21}}{\begin{bmatrix} 1 & 0 \\ -4 & 1 \end{bmatrix}} \underset{A}{ \begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix}} = \underset{U}{\begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix}} $$

 

여기서 U행렬을 보면 상삼각 행렬이다. 그리고 $E_{21}$ 행렬을 보면 하삼각 행렬이다.

어? 그러면 $E_{21}$을 오른쪽으로 넘기면 A=LU 형태가 될 것이다. 역행렬을 곱해주면 될 것같은 느낌이 오면된다.

$$ \begin{align} (E_{21})^{-1} E_{21} A &= (E_{21})^{-1} U  \\ IA & = (E_{21})^{-1} U \\ A &= LU \end{align}$$

결국, 소거행렬 $E_{21}$의 역행렬이 L행렬인 것이다.

$$ (E_{21})^{-1} = L $$

 

이제 소거행렬의 역행렬만 구하면 된다. $E_{21}$의 역행렬은 -4의 부호만 +로 바꿔주면 된다.

이유는 역행렬을 곱해서 단위행렬을 만들어야 되기 때문에 소거법에서 피벗을 잡고 했던 방법을 잘 떠올려보면 유추가 가능하다.

따라서,

$$ \underset{(E_{21})^{-1} = L}{\begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix}} $$

임을 알 수가 있다.

최종적으로 다음과 같은식이 나온다.

$$ \underset{A}{\begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix}} = \underset{L}{ \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix}} \underset{U}{\begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix}} $$

---

LDU Decomposition

어떤 경우에는 A=LU에서 U의 피벗성분(2, 3)만 따로 떼어내서 행렬을 만들고 싶을 때, 다음과 같이 하면 된다.

첫번째 피벗인 2를 피벗이 속한 $Row_{1}$을 2로 나눠주고 두번째 피벗인 3을 피벗이 속한 $Row_{2}$을 3으로 나눠주면 된다. 그리고 D라는 피벗만 있는 형태의 행렬을 만들어 주면된다.

여기서 D는 Diagonal Matrix의 뜻이며 대각선 방향의 원소만 가지고 있는 대각행렬을 의미한다.

따라서, A=LDU 꼴이며, L은 하삼각행렬 D는 피벗만있는 대각행렬 U는 상삼각행렬이다.

다시한번더 상기하자면 이렇게 A행렬을 분해하는 이유는 계산을 쉽게하려는 이유임을 떠올리자.

---

3x3 행렬

이제 2x2의 2차원을 봤으니 당연히 3x3 행렬도 다뤄보자.

다음과 같은 3x3 정방행렬 A가 있다고 가정해보자. 이때, A행렬을 상삼각행렬을 만들려면 총 피벗이 3개 필요하고 소거행렬도 3개 필요할 것이다. 또한, Row exchange는 필요없는 Very good 행렬로 가정하자. 소거법을 진행해 상삼각행렬을 만드는 식은 다음과 같을 것이다.

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

이제 각 소거행렬의 역행렬을 곱하면 A=LU가 만들어진다.

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

따라서, $E_{21}^{-1} E_{31}^{-1} E_{32} ^{-1} = L $임을 알 수 있다.

우리는 여기서 A와 U간의 연결고리인 L을 소거행렬 역행렬의 곱으로 만들어 낸 것으로도 생각할 수 있고, 맨처음 식에서 소거행렬의 곱도 A와 U의 연결고리라고 할 수 있다.

따라서, 두개의 연결고리가 있는데

$$E_{32} E_{31} E_{21} $$

$$E_{21}^{-1} E_{31}^{-1} E_{32} ^{-1}$$

과연 둘 중 어떤게 더 좋은 형태일까?

결론적으로 말하면 두번째 역행렬 형태가 더 좋은 형태이다.

---

다음과 같이 A행렬이 있다고 해보자.

$$ \underset{A}{\begin{bmatrix} 2 & 1 & 7 \\ 4 & -1 & 16 \\ 0 & -15 & 19 \end{bmatrix}} $$

A행렬을 소거법을 통해 E행렬과 L행렬을 구해서 비교해보자.

$$ \underset{E_{32}}{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -5 & 1 \end{bmatrix}} \underset{E_{31}=I}{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}} \underset{E_{21}}{\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}} = \underset{E}{\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 10 & -5 & 1 \end{bmatrix}} $$ 

$$ \underset{E_{21}^{-1}}{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}} \underset{E_{31}^{-1}=I}{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}} \underset{E_{32}^{-1}}{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 5 & 1 \end{bmatrix}} = \underset{L}{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 5 & 1 \end{bmatrix}} $$

 

먼저, 각 E행렬의곱을 통해 E행렬이 나오는 과정을 봐보자.

$E_{31}$은 단위행렬이기 되었기 때문에 곱셈 과정에서 무시해도 된다.  $E_{32}$의 -5와 $E_{21}$의 -2를 잘봐라. E행렬에 그대로 옮겨지고 그 둘의 곱인 10형태로 사이에 들어 갔다. 만일, 이런 E행렬과 A행렬을 곱하여 U행렬을 만들면 10이라는 큰 숫자가 곱해질 것이다. (참고로 -5와 -2는 소거 과정에서 해당 피벗의 row에 곱해지는 multiplier임을 기억하자)

 

이번에는 각 E행렬의 역행렬곱을 통해 L행렬이 나오는 과정을 봐보자.

마찬가지로 $E_{31}^{-1}$은 단위행렬이기 때문에 무시한다. $E_{21}^{-1}$의 2와 $E_{32}^{-1}$의 5는 그대로 옮겨지고 E행렬과 다르게 L행렬에서는 곱해진 형태가 들어가지 않는다. 즉, 10과 같이 큰 숫자를 만들지 않는다는 것이다.

또한, EA=U와 달리 A=LU에서는 A를 신경쓰지 않고 연산이 가능하다. 결국 A와 U의 연결고리로써는 E보다는 L이 좀 더 낫다는 뜻이다.

 

요약하면 A=LU Decomposition에서(행 교환(row exchanges)가 없는 경우) 소거에 사용되는 multiplier들은 L행렬의 각자 위치에 그대로 들어간다.

---

치환(Permutation)

지금까지는 LU Decomposition에서 행 교환(row exchange)가 없는 경우만 살펴보았다. 행 교환이 필요한 경우는 어떻할까? 바로 Lecture2에서 잠깐 배운 치환행렬을 행 교환이 필요할 경우 곱해주면 된다.

일단, 3x3 정방행렬에서 치환행렬의 종류를 살펴보자. 일단 치환행렬은 Permutation에서 P를 따 P행렬로 부른다.

$$ \underset{I}{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}} \underset{P_{12}}{\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}} \underset{P_{13}}{\begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}} \underset{P_{23}}{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}} \underset{P_{13}P_{23}}{\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}} \underset{P_{12}P_{23}}{\begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}} $$

먼저, $P_{12}$, $P_{13}$, $P_{23}$은 쉽게 유추가 가능하다. $P_{12}$은 $Row_1$과 $Row_2$를 바꿔주는 P행렬이다.

마찬가지로 나머지도 쉽게 이해 가능하다.

$P_{13}P_{23}$도 $Row_2$와 $Row_3$을 바꾼 후 $Row_3$과 $Row_1$을 바꾸면 된다. ($I$행렬을 기준으로 보면됨)

(아무런 변화가 없지만 단위행렬도 치환행렬의 한 종류다)

치환 행렬의 조합의 개수는 n!(factorial)로 계산하면 된다. 3x3행렬일 경우 n=3이므로 3! = 3x2x1 = 6가지의 조합이 나온다.

 

따라서, 치환 행렬은 row를 바꿔주는 역할이다. 그렇다면 다시 원래대로 되돌려 놓으려면 치환 행렬의 역행렬을 곱하면되는데, 치환 행렬의 역행렬은 원래 행렬과 같다.

무슨 의미냐면 치환 행렬 $P_{12}$에서 row1과 row2를 바꿨으면 원래대로 돌릴려면 다시 row1과 row2를 바꿔주면되니 원래 행렬(=$P_{12}$)과 역행렬(=$P_{12}$)이 같을 수 밖에 없다.

이는 치환 행렬 자체가 대각 원소들을 기준으로 좌우가 대칭이기 때문이다. 이런 좌우 대칭인 경우 역행렬은 전치(Transpose)로 구할 수 있다.

또한, $P_{13} P _{23} $은 $P_{12} P_{23} $과 잘보면 전치 관계이므로 역행렬 관계임을 알 수 있다.

 

결론은 우리는 행 교환이 필요한 A=LU Decomposition을 할 때 이러한 치환 행렬을 곱하여 PA=LU와 같은 꼴로 Decomposition을 할 수 있다.

$$ PA = LU $$

여기서 P는 행 교환 연산을 수행하는 치환행렬이고 위 식은 어떤 invertible A에도 적용이 된다.

 

치환행렬은 두가지 속성이 있는데 첫번째는 모든 P행렬은 invertible(역행렬이 존재)하다. 역행렬이 존재하는 단위행렬에서 행만 바꿨으니 당연한 얘기다. 두번째는 P행렬의 역행렬은 Transpose(전치)와 같다.

$$ P^{-1} = P^{T} , \ \ P^{T} P = I  $$

위 식을 잘 기억해두자.

---

결론

이번 강의에서는 어떤 시스템 행렬 A를 L과 U로 분해하는 방법을 배웠다. 여기서 A와 U를 이어주는 L을 정의하고 L과 소거행렬 E와의 관계도 확인했다. 또한 행 교환을 위한 치환행렬에 대해 공부 했고 전치도 공부했다.