[Linalg] LU Decomposition

LU Decomposition

(프로그래머스 2주차 Day2 - LU Decomposition 내용)

행렬의 분해

행렬의 분해는, 행렬을 곱으로 분해하여, 계산한다.

대표적인 행렬 분해의 예시는 다음과 같다.

- LU 분해 (가우스 소거법을 행렬의 형태로 적음)
- QR 분해 (직교 분할과 관련)
- 특이값 분해(SVD)

오늘은 LU 분해에 대해서 알아본다.

LU분해

LU 분해란, 주어진 행렬을 하삼각행렬 * 상삼각 행렬 형태로 쪼개는 것을 말한다.

만일 이것을 했을 경우, 어떤 장점이 있을까?

Ax = b -> (LU)x = b -> L(Ux) = b -> 상삼각이나 하삼각 형태이므로 해를 구하기가 간단해진다.

이 때, LU분해의 과정에서 행끼리 바꿔줘야 하는 경우가 존재한다. 이는 치환행렬을 곱하는 것으로 행을 바꿔줄 수가 있다. ( 하삼각행렬과 상삼각행렬을 맞춰주기 위한 과정)

< 모든 가역 행렬 A에 대해, PA = LU를 만족한다. 이 때, P는 치환 행렬이다>

 

LU 분해를 하는 이유

- 직접적으로 역행렬을 계산하는 대신, LU분해를 통해 계산할 경우 수치적으로 안정적이다.

- b의 값이 자주 바뀔 경우, 선형시스템에서 A를 미리 LU 분해 해두면, 실시간 계산이 가능하다.