LU분해(LU_Decomposition)란

1. 정의

---

- LU 분해란 행렬을 하삼각행렬(Lower triangular matrix) 과 상삼각행렬(Upper triangular matrix)의 곱으로 분해시키는 기술이다. 때때로 행교환행렬인 P 를 추가하여 분해 시키기도 하기 때문에, PLU 분해라고도 한다. 

좌측의 하삼각행렬과 우측의 상삼각행렬의 곱으로 표현.

 

 

 

2. 장점

---

- LU 분해가 된다는 것은 알았지만, 왜 쓰이는지 알아보자. LU 분해는 선형시스템 (Ax = B) 와 같은 형태의 꼴의 문제를 간단히 풀 수 있다는 장점이 존재한다.

라는 행렬이 존재하게 되고 A 를 LU분해 하여 A = LU라고 표시하게 된다면,

(LU)X = B 가 되게 되고,

Ux를 y 로 치환해주게 된다면,

Ly = B 라는 형태의 꼴로 새롭게 변형된다. 자 그러면 아니, 행렬을 더 만들어 줘놓고, 왜 이런거 쓰냐..  라는 말이 있을텐데, 여기서 LU 는 모두 삼각행렬의 꼴이기 때문에, 좀 더 쉽게 만족하는 행렬을 구해줄 수 가 있다. 전의 포스팅인 가우스 소거법에서도 

https://guru.tistory.com/54

가우스 소거법 (Gauss_Elimination)

보았듯이. 삼각행렬로 표현된 행렬은 후방대치법(back_substitution) 으로 쉽게 해를 찾을 수 있다. 이를 그림으로 표현하자면. 다음과 같다.

첫번째로, Ly = B 를 만족시키는 y를 구해주자.

그림에서 보다시피 전방 대치법을 활용하여, y1,y2,y3/.. 차례대로 구해나가면 된다.

두번째로, Ux 를 y로 치환했으니 , 최종 x를 구해주면 된다.

후방 대치법(Back_substitution) 이므로, Xn, Xn-1, Xn-2 같이 뒤에서 부터 차례대로 구해주면, 최종 x 가 나오게된다.

 

 

 

 

3. 어떻게 분해하는가?

---

행렬 A를 가우스 소거를 통하여 Upper triangular form 즉 상삼각행렬로 만들게 된다면,

요러한 형태의 꼴의 행렬이 완성될 것이다. Ep ~ E1 은 기본행렬로써, 기본행연산(-행교환, 상수곱셈, 행의 배수를 다른행 더하기) 으로 이루어진 행렬이다. 따라서 Ep ~ E1 은 모두 역행렬을 가지게 되고,

라는 꼴의 식이 성립하게 된다. 여기서 Lower triangular form 의 행렬은  

이 되게 된다. 그럼 예제로 살펴보자. (여기서 왜 Ep~E1의 역행렬이 L 꼴이 되냐 하실수 있는데, A를 모조리 위로 쓸어올리기 위해서 Ep~E1을 곱해줬으면, 그 역행렬은 모조리 쓸어내리는 역활을 한다 생각하면 편할 것이다.)

 

먼저 다음과 같이 주어진 A가 있다고 하자.

그렇다면, 요 친구와 함께 짝지을 행렬로, I 가 있는데,

얘를 옆에다가 놔줄 건데, A에다가 위에서 봤듯이 Ep ~ E1 을 곱해서 Upper triangular form으로 만들거고, I는 그 반대의 역행렬을 해줘서 lower triangular form 을 만들 것이다. 다음은 이 과정을 계산하는 과정이다.

 

위의 첫 행만 살펴보게 되면, A에 E1 을 곱해주어 A(2,1)이 0 이 되었고, E1의 역행렬과 I 의 곱으로 I(2,1) 이 2가 되었다.

이를 식으로 살펴보면,

먼저 A 와 I 를 정의해준 후, E 는 아까 말한 기본 행 행렬이고,

여기서 E.dot(A) 그리고 E의 역행렬.dot(A)를 해주면, 위와 같이 A(2,1)=0, I(2,1)=2가 나오는 걸 볼 수 있다.

나머지도 마찬가지고 진행해주게 되면,

의 꼴이 나오게 된다.

 

 

 

 

 

4. Numpy 에서의 LU분해

---

scipy 의 scipy.linalg 에서 import lu를 통해 불러 올 수 있다,

permutaion_I 의 값을 default = False 로 가지게 되는데(False 면 행교환을 진행), 이는 위에서 봤듯이 행교환을 하는지 안하는지를 말해주는 Feature 이다.

아까 봤던 행렬

요 친구로 LU분해를 시켜보자.

 

행교환이 이루어져 P가 return 되었으며, 역으로 계산해보면 PA = LU 로 잘 분해 된 것을 확인 가능하다.

 

 

-참고.

1. David C.Lay 의 Linear algebra and its application
2. 프로그래머스 인공지능 스쿨 (선형대수)
3. ko.wikipedia.org/wiki/LU분해