LU 분해(LU Decomposition)는 주어진 정방행렬을 두 개의 행렬, 즉 하삼각행렬(Lower triangular matrix, L)과 상삼각행렬(Upper triangular matrix, U)의 곱으로 분해하는 기법입니다. 이 분해는 선형 방정식 풀이, 역행렬 계산, 행렬식(det) 계산, 수치 해석 등 다양한 분야에서 활용됩니다. 이번 글에서는 LU 분해의 개념, 수학적 원리, 분해 과정, 그리고 적용 사례를 소개합니다.
1. LU 분해란?
LU 분해는 정방행렬 \( A \in \mathbb{R}^{n \times n} \)에 대해 다음과 같이 표현됩니다:
\[ A = LU \]
- \( L \): 단위 하삼각행렬 (대각성분이 1, 아래에 값 존재)
- \( U \): 상삼각행렬 (위에 값 존재, 아래는 0)
예시
\[ A = \begin{bmatrix} 2 & 3 \\ 4 & 7 \end{bmatrix} \Rightarrow L = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}, \quad U = \begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix} \]
2. 분해 조건
- 모든 선형 독립한 열을 갖는 정방행렬은 LU 분해 가능
- 단, 일부 경우에는 행 교환(Pivoting)을 포함한 PA = LU 형태의 분해가 필요 (P는 순열행렬)
3. LU 분해 알고리즘 (without pivoting)
가우스 소거법(Gaussian elimination)과 유사한 방식으로, 상삼각행렬을 만드는 동시에 하삼각 요소를 추적해 L을 구성합니다.
단계 1: 첫 번째 열 기준으로 소거
\[ l_{21} = \frac{a_{21}}{a_{11}}, \quad u_{11} = a_{11}, \quad u_{12} = a_{12}, \ldots \]
단계 2: 두 번째 열 기준 반복
\[ l_{32} = \frac{a’_{32}}{u_{22}}, \ldots \]
이 과정을 반복하여 \( A = LU \) 분해 완료
4. LU 분해의 활용
4-1. 선형 방정식 풀이 \( Ax = b \)
LU 분해 후 다음 두 단계를 거칩니다:
- \( Ly = b \)에 대해 전진 대입(Forward Substitution)
- \( Ux = y \)에 대해 후진 대입(Backward Substitution)
여러 개의 \( b \) 벡터에 대해 빠르게 해를 구할 수 있음
4-2. 행렬식 계산
\[ \det(A) = \det(L)\det(U) = \prod_{i=1}^n u_{ii} \]
4-3. 역행렬 계산
LU 분해를 통해 각 열에 대해 연립방정식을 풀어 \( A^{-1} \)을 계산할 수 있음
5. 수정 LU 분해: 행 교환 포함 (PLU 분해)
특정 행렬은 직접적인 LU 분해가 불가능하거나 수치적으로 불안정할 수 있습니다. 이 경우 다음과 같은 형태로 분해합니다:
\[ PA = LU \]
- \( P \): 순열행렬 (행의 순서 교환)
결론
LU 분해는 행렬 계산을 효율화하는 핵심 기법으로, 선형 방정식 풀이와 행렬 연산의 속도 및 안정성을 크게 향상시킵니다.
가우스 소거법과 병행하여 손쉽게 구현 가능하며, 특히 컴퓨터 연산에서 반복되는 연립방정식 해결 시 매우 유리합니다.
정방행렬 뿐 아니라, 부분 피봇팅을 통해 거의 모든 행렬에도 적용 가능한 확장성이 큰 분해 기법입니다.