LU 분할

Gaussian Elimination Review

지난 포스팅에서 1차 연립방정식을 가우스 소거법을 사용하여 해를 구해보았다.

1차 연립방정식의 계수로 이루어진 A라는 행렬에 대해서, 적절한 다른 행렬의 곱하기로 변형해보자.

다음 과정은 가우스 소거법과 다를게 없다.

과정에서 볼 수 있듯이 $E_{21}, E_{31}, E_{32}$에 해당하는 것이 적절한 다른 행렬, 즉 Elementary Matrix라고 한다. Elementary Matrix들과 A와 곱을 통해 Upper triangular matrix인 U를 구할 수 있게 되었다. \(\begin{aligned} E_{21}E_{31}E_{32}A\ =\ U \end{aligned}\) 그럼 A라는 행렬을 구하기 위해서 $E_{21}E_{31}E_{32}$에 inverse를 취해보자 \(\begin{aligned} A\ =\ E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U \end{aligned}\)

그럼 놀랍게도 Elementary Matrix들의 inverse에 해당하는 행렬은 Lower triangular matrix가 되고, A라는 행렬은 L과 U의 곱으로 구할 수 있다.

이를 LU decomposition이라고 한다.