[선형대수학 정리] 22. LU 분해, PLU 분해, LDU 분해

1. 배경

 

---

그래픽스 공부에 들어가기 전, 근본 중에서도 근본인 선형대수학을 먼저 파야겠다고 생각했다!
 
Chris Ohk 님의 Game Developer Roadmap 2022를 보고 내가 부족한 부분을 채워나가기로 결심했기 때문이다.
 

https://github.com/utilForever/game-developer-roadmap

.

2. 정리

---

LU분해 (LU decomposition)

 

 

행렬 A를 Lower triangular matrix L과

Upper triangular matrix U의 곱으로 나타내는 것을 의미한다.

 

A=LU 와 같이 변환하면 계산이 쉬워 이와 같은 분해를 진행한다.

---

LU 분해의 예시

 

위와 같이 변수가 세 개인 연립일차방정식을 풀 때

계수부분을 담은 행렬 A를 U 모양으로 만들기 위해 소거를 하게 된다.

 

이때 소거하는 과정을 어떤 행렬이 곱해지는 과정으로 볼 수 있다.

곱해지는 행렬의 모양이 L 모양이고, 첫번째로 구한 이 L 행렬은 L1이라 한다.

 

 

위와 같이 A 행렬을 U 모양으로 바꾸다보면

L2, L3와 같은 행렬들을 찾게 되고 그 결과

 

L3 L2 L1 A = U

 

와 같은 형태로 구할 수 있으니, 이들의 역행렬을 곱해 계산한다.

 

• Lower triangular matrix는 determinant가 대각성분의 곱이므로 0이 아니다.
• Upper triangular matrix도 동일한 성질을 가진다.
• 그러므로 L, U 모양의 행렬 모두 역행렬을 가진다.

L1, L2, L3의 역행렬을 곱한 결과도 L 모양이므로

역행렬을 곱해 좌변에 A만 남기면,  A = LU로의 LU 분해가 완성된다.

 

LU분해의 응용과 LDU 분해 

 

 

LU 분해를 하게 되면 Ax = b를 Ax = LUx = b로 바꿀 수 있고,

Ux = y로 치환하여 총 두번 간단한 행렬식을 풀게 된다.

 

그리고 U의 대각성분만 뽑아 행렬 D를 만들면

U의 대각성분이 모두 1이 되어 계산하기 깔끔해지고

이 경우 A = LDU가 되므로 이를 LDU 분해 (LDU decomposition) 라 한다.

 

PLU 분해

 

 

근데 A = LU 모양으로 분해가 안되는 경우

행들을 서로 바꿔 LU 모양으로 바꿀 수 있도록 하려 한다.

 

이때 행들을 서로 바꿔주는 역할을 행렬 P가 한다고 하고

PA = LU와 같이 분해할 경우 A = P^{-1}LU가 된다.

 

근데 구해본 결과 P는 orthogonal matrix이므로 역행렬이 곧 전치행렬이다.

그리고 구한 전치행렬이 곧 자기 자신과 동일해 A = PLU가 된다.

이를 PLU 분해 (PLU decomposition) 라 한다.