[Week2-Day2] LU분해

오준석·2021년 4월 29일
0

LU분해 -> 알고리즘의 형태가 아니라 행렬의 결과물을 표현한 방식

행렬분해 := 인수분해

행렬분해 = 인수분해의 행렬버전

인수분해의 가치

  • 분수의 약분
  • 두 수의 최대공약수 구하기
  • 두 수의 최소공배수 구하기
  • 보안분야에서도 기본적인 알고리즘으로 사용됨

'수'를 인수분해 한 형태로 가지고 있으면 계산이 편한 경우가 많음

LU분해 (LU decomposition)
QR분해 (QR decomposition)
특이값 분해 (SVD, Sigular Value Decomposition) - 차원을 줄일 때 사용됨

LU분해 - Gauss 소거법을 행렬방식으로 적어 놓은 것

L: lower triangular matrix(하삼각행렬)
U: upper triangular matrix(상삼각행렬)

Ax = b
-> (LU)x = b
-> L(Ux) = b - Ux를 y로 치환
-> Ly = b

LU분해의 특징

lower triangular matrix에서는 전방대치법(Forward-substitution)을 통해 y를 구할 수 있다.
upper의 경우는 후방대치법

LU분해는 가우스 소거법의 forward elimination(전방소거법)을 행렬로 코드화
L: 행렬 A를 전방소거하는데 쓰인 replacement와 scaling에 대한 EROs를 기록해 둔 행렬
U: 행렬 A를 전방소거한 후 남은 upper triangular matrix
P: 행렬 A를 전방소거하는데 쓰인 interchange에 대한 EROs를 기록해 둔 행렬 (옵션)

LU분해를 사용하는 이유

Q: A ~> A-1을 통해 해를 구할 수 있는데 왜 LU분해를 해야하나?

수치적 안정성: 선형시스템 Ax = b의 해를 역행렬을 이용해 직접 구하는 것 보다 PLU 분해를 이용하는 것이 수치적으로 안정적임

b가 자주 업데이트되는 경우: 선형시스템 Ax = b에서 행렬 A는 고정되어 있고 b가 자주 변하는 경우, b가 업데이트될 때마다 해를 실시간으로 구할 수 있음

profile
오늘만 사는 개발자

0개의 댓글