LU 분해

행렬분해 matrix decomposition

 

인수분해는 다음과 같은 경우 쓰인다.

- 분수의 약분

- 두 수의 최대공약수 구하기

- 두 수의 최소공배수 구하기

 

주어진 숫자를 인수분해 한 상태로 두면 계산에 쓰기 좋다.

 

행렬분해도 인수분해와 마찬가지로, 행렬을 분해된 상태로 두어 계산에 쓰기 좋게 만든다.

 

행렬분해

- LU 분해 LU decomposition

- QR 분해 QR decomposition

- 특이값 분해 SVD, Singular Value Decomposition

 

LU분해

가우스 소거법의 전방소거법을 행렬로 코드화 한 것

 

L - lower triangular matrix 하삼각행렬

U - upper triangular matrix 상삼각행렬

 

하삼각과 상삼각을 제외한 부분이 모두 0으로 되어있는 행렬을 의미한다.

 

주어진 행렬 A를 두 행렬의 곱으로 나누는 행렬 분해

A = LU ( P - permutation matrix L을 만들기 위해 행을 바꿨다면 기록)

LU=A

Ax = b

(LU)x = b

L(Ux) = b

Ly = b

Ux = y

 

여기서 두 단계의 계산이 가능하다.

- 전방대치법 Forward - substitution y값 구하기

- 후방대치법 Back - substitution x값 구하기

 

전방대치법은 y를 구한다. Ax = b 에서 L(Ux) = b, Ly =b 식에서 y를 구할 수 있다.후방대치법은 x를 구한다.Ax = b 에서 Ux = y에서 이전에 y를 구했기 때문에 x를 구할 수 있다.

 

LU 분해를 사용하는 이유- 수치적 안정성, 역행렬을 사용하는 것보다 PLU 분해를 사용하는 것이 수치적으로 안정적이다.- b가 자주 업데이트 되는 경우, Ax = b에서 b가 종종 변하는 문제일 경우에 A를 미리  PLU로 분해한다면 시간소모를 줄일 수 있다.