LU 분해 (LU Decomposition)

한 줄 정의: 행렬을 아래삼각행렬과 위삼각행렬의 곱으로 나누는 분해입니다.

쉽게 풀면

정사각행렬을 대각선 아래쪽만 값이 있는 행렬과 위쪽만 값이 있는 행렬의 곱으로 쪼개는 것이 LU 분해입니다. 삼각행렬로 이루어진 연립방정식은 위에서 아래로, 또는 아래에서 위로 차례차례 대입하면 바로 풀리기 때문에 계산이 아주 쉽습니다. 그래서 한 번 분해해 두면 우변만 바뀌는 여러 문제를 빠르게 풀 수 있습니다.

왜 중요한가

같은 계수행렬에 대해 우변이 여러 개인 연립방정식을 반복해서 풀어야 하는 상황이 공학 계산에서 매우 흔한데, LU 분해는 가장 비싼 부분을 한 번만 수행하게 해 줍니다. 행렬식이나 역행렬 계산에도 그대로 활용되어 수치선형대수 라이브러리의 기본 루틴으로 자리 잡았습니다.

논문에서는 이렇게 쓰입니다

"계수행렬을 LU 분해한 뒤 우변만 바꾸어 반복 계산함으로써 전체 연산량을 크게 줄였다."

조금 더 깊게 보면

분해 과정은 가우스 소거법에서 사용한 행 연산의 배수들을 버리지 않고 아래삼각행렬에 기록해 두는 것과 같습니다. 피벗 위치에 0이 나타나거나 값이 지나치게 작으면 수치적으로 불안정하므로, 실제로는 행을 교환하는 부분피벗팅을 적용한 PA=LU 형태를 사용합니다. 대칭이고 양의 정부호인 행렬에서는 절반의 연산으로 끝나는 콜레스키 분해가 쓰입니다.

주의할 점

가우스 소거법이 하나의 연립방정식을 푸는 절차라면, LU 분해는 그 계산 결과를 재사용 가능한 형태로 저장하는 방법이라는 점이 다릅니다. 또 모든 정사각행렬이 행 교환 없이 LU 분해되지는 않습니다.