[TIL] DAY 9 - LU 분해(LU decomposition)

LU 분해 (LU decomposition)

• 주어진 행렬을 아래의 형태를 가지는 두 행렬의 곱으로 나누는 행렬 분해(matrix decomposition)
  • L: lower triangular matrix(하삼각행렬)
  • U: upper triangular matrix(상삼각행렬)
• LU 분해를 이용해 $Ax=b$ 문제를 아래와 같이 나타내면
  • $Ax=b\Rightarrow (LU)x=b\Rightarrow L(Ux)=b$
    $\quad \quad \quad \Rightarrow Ly=b, ($단$, Ux=y)$
• LU 분해는 가우스 소거법의 forward elimination(전방소거법)과 의미가 거의 같음
• LU 분해의 활용 이유
  • 수치적 안정성
    • 선형 시스템 $Ax=b$의 해를 역행렬 $A^{-1}$를 이용하여 구하는 것보다 안정적
  • $b$가 자주 업데이트되는 경우
    • 선형 시스템 $Ax=b$에서 행렬 $A$는 고정되어 있고 $b$가 자주 변하는 경우
      행렬 $A$를 미리 분해해 두면 $b$가 업데이트될 때마다 해 $x$를 실시간으로 구할 수 있음

 

출처: 프로그래머스 스쿨 3강: LU분해