27.37 LU 분해의 정의와 수치적 안정성을 위한 부분 피벗팅

1. LU 분해의 정의

LU 분해(LU decomposition 또는 LU factorization)는 정사각 행렬 $\mathbf{A} \in \mathbb{R}^{n \times n}$ 을 하삼각 행렬(lower triangular matrix) $\mathbf{L}$ 과 상삼각 행렬(upper triangular matrix) $\mathbf{U}$ 의 곱으로 표현하는 것이다.

$\mathbf{A} = \mathbf{L}\mathbf{U}$

여기서 $\mathbf{L}$ 은 대각 원소가 모두 1인 단위 하삼각 행렬로 정규화하는 것이 관례이다.

$\mathbf{L} = \begin{pmatrix} 1 & 0 & \cdots & 0 \\ l_{21} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{n1} & l_{n2} & \cdots & 1 \end{pmatrix}, \quad \mathbf{U} = \begin{pmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ 0 & u_{22} & \cdots & u_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{nn} \end{pmatrix}$

LU 분해는 가우스 소거법의 행렬적 표현이다. 전방 소거 과정에서 각 단계의 행 연산은 기본 하삼각 행렬 $\mathbf{L}_k$ 에 의한 왼쪽 곱셈에 해당하며, 전체 과정은 $\mathbf{L}_{n-1}\cdots\mathbf{L}_2\mathbf{L}_1\mathbf{A} = \mathbf{U}$ 로 표현된다. 따라서 $\mathbf{A} = \mathbf{L}_1^{-1}\mathbf{L}_2^{-1}\cdots\mathbf{L}_{n-1}^{-1}\mathbf{U} = \mathbf{L}\mathbf{U}$ 이다. 기본 하삼각 행렬의 역행렬과 곱이 다시 단위 하삼각 행렬이 된다는 성질에 의해, $\mathbf{L}$ 의 대각선 아래 원소는 가우스 소거법에서 사용한 승수(multiplier) $m_{ik} = a_{ik}^{(k)}/a_{kk}^{(k)}$ 와 정확히 일치한다.

2. LU 분해의 존재 조건

모든 정사각 행렬이 피벗팅 없이 LU 분해를 가지는 것은 아니다.

정리: $n \times n$ 행렬 $\mathbf{A}$ 가 피벗팅 없이 LU 분해를 가질 필요충분조건은, $\mathbf{A}$ 의 모든 선행 주소행렬(leading principal minor)이 0이 아닌 것이다. 즉, $k = 1, 2, \ldots, n-1$ 에 대하여 $\det(\mathbf{A}_{1:k, 1:k}) \neq 0$ 이어야 한다.

이 조건이 충족되면 LU 분해는 유일하다(단위 하삼각 정규화 하에서).

간단한 반례로, $\mathbf{A} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ 은 첫 번째 피벗이 0이므로 피벗팅 없이는 LU 분해가 존재하지 않는다. 이 문제를 해결하기 위해 행 교환(피벗팅)을 도입한다.

3. LU 분해 알고리즘

두몰리틀(Doolittle) 알고리즘에 의한 LU 분해의 계산은 다음과 같다. $\mathbf{A} = \mathbf{L}\mathbf{U}$ 에서 원소를 직접 비교하여 $\mathbf{L}$ 과 $\mathbf{U}$ 를 구한다.

$k = 1, 2, \ldots, n$ 에 대하여:

$u_{kj} = a_{kj} - \sum_{s=1}^{k-1} l_{ks}u_{sj}, \quad j = k, k+1, \ldots, n$

$l_{ik} = \frac{1}{u_{kk}}\left(a_{ik} - \sum_{s=1}^{k-1} l_{is}u_{sk}\right), \quad i = k+1, k+2, \ldots, n$

이 알고리즘의 총 연산 횟수는 약 $\frac{2}{3}n^3$ 이며, 가우스 소거법과 동일하다. $\mathbf{L}$ 과 $\mathbf{U}$ 는 $\mathbf{A}$ 와 같은 공간에 저장할 수 있다. $\mathbf{L}$ 의 대각 원소가 1임을 알고 있으므로, $\mathbf{A}$ 의 저장 공간에 $\mathbf{U}$ 의 상삼각 부분과 $\mathbf{L}$ 의 하삼각 부분(대각선 제외)을 겹쳐서 저장하는 것이 표준 구현이다.

4. 부분 피벗팅을 포함한 PLU 분해

실용적인 LU 분해에서는 수치적 안정성을 위해 부분 피벗팅(partial pivoting)을 적용한다. 결과는 다음 형태이다.

$\mathbf{P}\mathbf{A} = \mathbf{L}\mathbf{U}$

여기서 $\mathbf{P}$ 는 행 교환을 기록한 순열 행렬(permutation matrix)이다. 순열 행렬은 직교 행렬이므로 $\mathbf{P}^{-1} = \mathbf{P}^\top$ 이다.

부분 피벗팅의 절차: $k$ 번째 단계에서, $k$ 열의 $k$ 행 이하 원소 중 절댓값이 가장 큰 원소를 찾아 해당 행과 $k$ 행을 교환한다.

$p = \arg\max_{i \geq k} |a_{ik}^{(k)}|$

이 교환은 $\mathbf{P}$ 에 기록된다.

부분 피벗팅의 핵심 효과는 모든 승수의 절댓값이 1 이하가 되도록 보장하는 것이다. $|l_{ik}| = |m_{ik}| = |a_{ik}^{(k)}|/|a_{kk}^{(k)}| \leq 1$ 이다. 이로 인해 소거 과정에서 원소의 크기가 과도하게 증가하는 것을 방지한다.

성장 인자(Growth Factor): 가우스 소거법의 수치적 안정성은 성장 인자 $\rho = \frac{\max_{i,j,k}|a_{ij}^{(k)}|}{\max_{i,j}|a_{ij}|}$ 에 의해 결정된다. 부분 피벗팅에서 이론적 최악의 경우 $\rho$ 는 $2^{n-1}$ 에 달할 수 있으나, 실제로는 거의 항상 작은 값을 유지한다. Trefethen and Schreiber (1990)은 실용적 상황에서 부분 피벗팅의 성장 인자가 $O(n^{1/2})$ 정도임을 경험적으로 보인 바 있다.

5. LU 분해를 이용한 연립방정식 풀이

$\mathbf{A}\mathbf{x} = \mathbf{b}$ 에서 $\mathbf{P}\mathbf{A} = \mathbf{L}\mathbf{U}$ 이면, $\mathbf{L}\mathbf{U}\mathbf{x} = \mathbf{P}\mathbf{b}$ 이다. 이를 두 단계로 풀 수 있다.

1단계: 전방 대입. $\mathbf{L}\mathbf{y} = \mathbf{P}\mathbf{b}$ 를 풀어 $\mathbf{y}$ 를 구한다. $O(n^2)$ .

2단계: 후방 대입. $\mathbf{U}\mathbf{x} = \mathbf{y}$ 를 풀어 $\mathbf{x}$ 를 구한다. $O(n^2)$ .

LU 분해의 장점은 분해를 한 번 수행하면( $O(n^3/3)$ ), 서로 다른 우변 벡터 $\mathbf{b}_1, \mathbf{b}_2, \ldots$ 에 대하여 각각 $O(n^2)$ 만으로 해를 구할 수 있다는 것이다. $p$ 개의 우변에 대하여 총 복잡도는 $O(n^3/3 + pn^2)$ 이며, 이는 각각 독립적으로 가우스 소거법을 적용하는 $O(pn^3/3)$ 에 비해 $p$ 가 클 때 크게 유리하다.

6. 행렬식과 역행렬의 계산

LU 분해를 통해 행렬식을 효율적으로 계산할 수 있다.

$\det(\mathbf{A}) = \det(\mathbf{P}^{-1})\det(\mathbf{L})\det(\mathbf{U}) = (-1)^s \prod_{i=1}^{n} u_{ii}$

여기서 $s$ 는 행 교환의 횟수이다. $\det(\mathbf{L}) = 1$ (단위 하삼각), $\det(\mathbf{P}^{-1}) = (-1)^s$ 이다.

역행렬 $\mathbf{A}^{-1}$ 은 $\mathbf{A}\mathbf{X} = \mathbf{I}$ 를 $n$ 개의 연립방정식으로 풀어 구할 수 있다. LU 분해를 한 번 수행한 후, 단위 행렬의 각 열벡터 $\mathbf{e}_i$ 에 대하여 전방/후방 대입을 반복하면 총 $O(n^3/3 + n \cdot n^2) = O(n^3)$ 이다.

7. 특수 구조의 LU 분해

대역 행렬(Banded Matrix): 대역폭(bandwidth) $p$ 인 행렬에서 LU 분해의 복잡도는 $O(np^2)$ 으로 감소한다. 삼대각 행렬(tridiagonal matrix)의 경우 $p = 1$ 이므로 $O(n)$ 에 분해가 완료된다.

희소 행렬(Sparse Matrix): 희소 행렬의 LU 분해에서는 채워짐(fill-in) 현상을 최소화하기 위해 행과 열의 순서를 재배열한다. 근사 최소 차수(approximate minimum degree) 순서나 중첩 분할(nested dissection) 순서가 사용된다.

8. 딥러닝에서의 LU 분해 활용

가역 네트워크의 야코비안: 정규화 흐름에서 LU 분해를 직접 매개변수화하여 가역 선형 변환을 구성하는 기법이 있다. Kingma and Dhariwal (2018)의 “Glow: Generative Flow with Invertible 1x1 Convolutions“에서 $1 \times 1$ 합성곱의 가중치 행렬을 $\mathbf{W} = \mathbf{P}\mathbf{L}(\mathbf{U} + \text{diag}(\mathbf{s}))$ 로 매개변수화하면, 로그 행렬식이 $\log|\det(\mathbf{W})| = \sum_i \log|s_i|$ 로 $O(n)$ 에 계산된다. $\mathbf{P}$ 는 고정된 순열 행렬이고, $\mathbf{L}$ 과 $\mathbf{U}$ 는 학습 가능한 삼각 행렬, $\mathbf{s}$ 는 학습 가능한 대각 벡터이다.

배치 선형 시스템: 딥러닝 추론 과정에서 배치 단위의 선형 시스템 $\mathbf{A}_i\mathbf{x}_i = \mathbf{b}_i$ ( $i = 1, \ldots, B$ )를 풀어야 하는 경우가 있다. GPU 기반 LU 분해 구현은 배치 처리에 최적화되어 있으며, PyTorch의 torch.linalg.solve나 torch.linalg.lu_factor 등이 내부적으로 cuSOLVER의 배치 LU 분해를 호출하여 병렬 처리한다.

수치 안정성과 학습: 학습 과정에서 가중치 행렬이 특이에 가까워지면 LU 분해의 피벗 원소가 0에 근접하여 수치적 불안정이 발생할 수 있다. 이를 방지하기 위해 가중치 정규화, 스펙트럼 클리핑(spectral clipping), 또는 직교 제약 등의 기법을 병행하는 것이 중요하다.