[선형대수학] LU분해

LU 분해 (LU Decomposition)

---

• 분해는 하나의 행렬을 두개 혹은 3개 이상의 행렬 곱으로 표현한 식

• $A=BC$ : 행렬 A를 B와 C의 곱으로 표현

• 방정식을 푸는 방법
  1) A의 역행렬을 이용
  2) LU분해

• L은 하삼각행렬 (a unit lower triangular matrix)

• U는 사다리꼴 행렬 (echelon form)

• $A=LU → Ax=b → LUx=b → Ux=y(치환) → Ly=b → Ux=y → x$
  위와 같은 단계로 해를 구할 수 있음

LU 구하는 방법

• A가 row replacement만을 사용하여 사다리 꼴(echelon form) 형태로 변환될 수 있다고 가정

• U(echelon form)로 변환하기 위한 행 줄임(row operation) 기본 행렬 E1, ... , Ep 가 존재함
  

• 이 기본 행렬의 역행렬(inverse)이 L이 됨

• A가 (m x n)일 때, L은 (m x m), U는 (m x n)이 되어야 함
  

• 아래 A행렬의 LU를 구해보자

• $a_{11}$을 시작으로 대각선아래를 다 0으로 만들어 사다리꼴 행렬 완성

• 대각선 계수들을 1로 만들어 주는 계산을 하고 나머지는 0으로 채워 삼각행렬 완성

• A가 5개의 행을 갖고 있으므로 L은 4x4가 되어야 함

LU분해를 사용해 해를 구했을 때 장점

---

• 역행렬로 해를 구했을 때 보다 LU분해의 연산량이 1/3배 적음
• A가 sparse(대부분 0으로 채워져 있는 경우)하면 L과 U도 sparse 함
• 하지만 역행렬은 dense(값이 많은 경우)함.
• L과 U를 저장하는 memory와 역행렬 값을 저장하는 memory의 차이가 큰 것
• 공학적인 문제를 풀 때 LU분해는 속도와 메모리적 측면에서 큰 이점이 있음