LU분해

행렬분해(matrix decomposition)의 의미

• 행렬을 행렬분해 한 상태로 가지고 있으면 여러모로 계산이 편리한 경우가 많다.
• LU분해(LU decomposition)
• QR분해(QR decomposition)
• 특이값 분해(SVD, Singular Value Decomposition)

LU분해

주어진 행렬을 아래의 형태처럼 분할하는 방법이다.

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

LU분해를 하게 되면 Ax = b 의 계산을 다음과 같이 수행할 수 있다.

 

LU분해의 의미

LU분해는 가우스 소거법의 forward elimination을 행렬로 코드화 한 것이다.

• L: 행렬 A를 전방소거하는데 쓰인 replacement와 scaling에 대한 EROs를 기록해 둔 행렬
• U: 행렬 A를 전방소거한 후 남은 upper triangular matrix(상삼각행렬)
• P: 행렬 A를 전방소거하는데 쓰인 interchange에 대한 EROs를 기록해 둔 행렬(옵션)

넘파이나 사이파이에서 LU함수의 리턴값은 다음과 같은 형태를 리턴해준다.

A = P L U

 

LU분해의 활용

• 수치적 안정성: 선형시스템 Ax = b의 해를 역행렬 $A^{-1}$를 이용해 직접 구하는것보다 PLU분해를 이용하는 것이 좀 더 수치적으로 안정적이다.
• b가 자주 업데이트 되는 경우: 선형시스템 Ax = b에서 행렬 A는 고정되있고 b가 자주 변하는 문제가 종종있다. 이런 경우, 행렬 A를 미리 PLU로 분해해 두었다면, b가 업데이트 될때마다 선형시스템의 해 x를 실시간으로 구할 수 있다.