LU 분해

수치해석 시뮬레이션 마지막 수정: 2026-07-08 04:23:47

1. 개요[편집]

한 번 분해해두면, 우변만 바뀌는 문제는 공짜로 푼다. 게으른 자를 위한 선형대수의 축복.

LU 분해(LU decomposition)는 정사각행렬 $A$ 를 하삼각행렬(lower triangular) $L$ 과 상삼각행렬(upper triangular) $U$ 의 곱으로 인수분해하는 것이다.

A = LU

여기서 $L$ 은 대각 성분이 모두 1인 단위 하삼각행렬, $U$ 는 상삼각행렬이다. 본질적으로 가우스 소거법의 전진 소거 과정에서 나온 배수(multiplier)들을 버리지 않고 $L$ 에 저장한 것이 LU 분해다. 즉 둘은 같은 계산의 두 얼굴인데, LU 분해가 훨씬 실용적인 이유는 한 번 분해해두면 재활용이 가능하기 때문이다.

이 재활용성 덕에 LU 분해는 수치해석의 밥줄이 되었다. 구조해석에서 하중 조건(우변)만 바꿔가며 여러 케이스를 돌리거나, 반복법의 전처리기로 불완전 LU를 쓸 때 모두 이 분해가 주인공이다.

2. 왜 분해하는가[편집]

$A\mathbf{x} = \mathbf{b}$ 를 그냥 가우스 소거법으로 풀면 우변 $\mathbf{b}$ 가 하나 바뀔 때마다 $O(n^3)$ 소거를 처음부터 다시 해야 한다. 미련한 짓이다.

반면 $A = LU$ 로 한 번 분해( $O(n^3)$ )해두면, 이후 임의의 우변에 대해 다음 두 단계로 해를 구할 수 있다.

L\mathbf{y} = \mathbf{b} \quad(\text{전진대입}), \qquad U\mathbf{x} = \mathbf{y} \quad(\text{후진대입})

이 두 삼각 시스템 풀이는 각각 $O(n^2)$ 밖에 안 든다. 그래서 우변이 100개든 1000개든, 비싼 분해는 딱 한 번이고 나머지는 껌값이다. 이게 LU 분해가 단순 소거법을 이긴 결정적 한 방이다.

3. 전진대입과 후진대입[편집]

삼각행렬을 푸는 것은 놀랍도록 간단하다. 전진대입(forward substitution)은 $L\mathbf{y} = \mathbf{b}$ 에서 위에서부터 차례로 풀어 내려간다.

y_i = b_i - \sum_{j=1}^{i-1} \ell_{ij}\, y_j, \qquad i = 1, 2, \dots, n

( $L$ 의 대각이 1이라 나눗셈이 없다.) 이렇게 얻은 $\mathbf{y}$ 로 후진대입(back substitution)을 수행한다.

x_i = \frac{1}{u_{ii}}\left( y_i - \sum_{j=i+1}^{n} u_{ij}\, x_j \right), \qquad i = n, n-1, \dots, 1

두 대입 모두 미지수를 하나씩 순차적으로 확정하므로 재귀적 의존성이 있다. 이 때문에 삼각 풀이는 병렬 컴퓨팅에서 병렬화가 까다로운 대표적 골칫거리로 꼽힌다.¹

4. 피벗팅과 존재성[편집]

모든 행렬이 곱게 LU로 쪼개지는 건 아니다. 소거 도중 대각 피벗이 0이 되면 그 자리에서 알고리즘이 멈춘다. 그래서 실무에서는 가우스 소거법과 마찬가지로 부분 피벗팅을 곁들여 행을 교환하며, 그 결과는 치환행렬 $P$ 를 동원한 다음 형태가 된다.

PA = LU

이렇게 하면 $A$ 가 정칙(nonsingular)인 한 분해가 항상 존재하고 수치적으로도 안정하다. LAPACK의 dgetrf, MATLAB의 lu(), NumPy의 scipy.linalg.lu 모두 이 $PA=LU$ 를 반환한다. 피벗팅 없는 순수 $A=LU$ 는 대각 우세(diagonally dominant)하거나 대칭 양의 정부호인 얌전한 행렬에만 안전하게 통한다.

5. 촐레스키 분해[편집]

행렬이 대칭 양의 정부호(symmetric positive definite, SPD)라는 특권을 누린다면, LU 분해의 상위 호환인 촐레스키 분해(Cholesky decomposition)를 쓸 수 있다.

A = L L^{\mathsf{T}}

여기서 $L$ 은 하삼각행렬이고, $U$ 를 따로 저장할 필요 없이 $L^{\mathsf{T}}$ 가 그 역할을 한다. 덕분에 저장 공간이 절반, 연산량도 절반( $\tfrac{1}{3}n^3$ )으로 줄어든다.² 게다가 피벗팅 없이도 무조건 안정해서 코드가 깔끔하다. SPD 행렬은 구조해석의 강성행렬이나 유한요소법 이산화에서 흔하게 튀어나오므로, 촐레스키는 이 바닥에서 사랑받는 국룰 분해다.

만약 제곱근 계산이 부담스럽거나 반양정부호(semi-definite)까지 다뤄야 하면, 제곱근을 피한 변형인 $A = LDL^{\mathsf{T}}$ 분해를 쓰기도 한다.

6. 희소성과 채움현상[편집]

LU 분해가 희소행렬을 만나면 이야기가 복잡해진다. 원래 0이던 자리가 소거 과정에서 0이 아닌 값으로 채워지는 채움현상(fill-in)이 발생하기 때문이다.³ 이걸 방치하면 $L$ 과 $U$ 가 원래 $A$ 보다 훨씬 빽빽해져서 메모리와 연산이 폭발한다.

그래서 희소 직접 솔버(sparse direct solver)는 분해 전에 행과 열을 영리하게 재배열(reordering)해 채움현상을 최소화한다. AMD(Approximate Minimum Degree)나 nested dissection 같은 순서화 알고리즘이 여기 동원되며, PARDISO·MUMPS·UMFPACK 같은 라이브러리가 이 마법을 대신 부려준다. 그럼에도 3차원 대규모 문제에서는 채움현상을 완전히 이기기 어려워, 결국 반복법과 다중격자법에 자리를 내주는 경우가 많다.

7. 관련 문서[편집]

순차 의존성 때문에 삼각 풀이(triangular solve)는 GPU에서 특히 애를 먹인다. 레벨 스케줄링(level scheduling)으로 병렬 가능한 미지수들을 묶어 처리하지만, 밀집 행렬 곱셈만큼 시원하게 뻥 뚫리진 않는다. ↩
앙드레루이 촐레스키(André-Louis Cholesky)는 프랑스 육군 측량 장교였다. 삼각측량 계산을 빨리 하려고 만든 방법인데, 정작 본인은 1918년 1차 대전에서 전사해 이 방법이 사후에야 출판되었다. 측량하다 만든 게 지금은 분자동역학까지 굴린다. ↩
채움현상이 얼마나 얄미운가 하면, 아주 성긴 행렬도 순서를 잘못 잡으면 분해 결과가 거의 밀집 행렬이 되어버린다. “0을 잘 정렬하는 것”이 곧 성능이라는, 직관에 반하는 세계다. ↩