6.53 촐레스키 분해와 양정치 행렬

1. 도입

촐레스키 분해는 대칭 양정치 행렬에 대해 정의되는 특수한 행렬 분해 기법으로, 일반적인 LU 분해의 절반에 해당하는 연산량으로 동일한 정보를 얻을 수 있는 효율적인 분해이다. 양정치성을 활용하여 분해의 존재성과 유일성이 보장되며, 피벗팅 없이도 수치적으로 안정한 결과를 제공한다. 로봇 동역학의 관성 행렬, 칼만 필터의 공분산 행렬, 최적 제어의 헤시안 행렬 등 양정치 구조가 자연스럽게 등장하는 모든 영역에서 핵심적인 계산 도구로 사용된다.

2. 양정치 행렬의 정의

대칭 행렬 A \in \mathbb{R}^{n \times n} 가 임의의 영이 아닌 벡터 \mathbf{x} \in \mathbb{R}^n 에 대하여 다음을 만족할 때, A 를 양정치(positive definite) 행렬이라 한다.

\mathbf{x}^{\top} A \mathbf{x} > 0

만약 모든 \mathbf{x} 에 대해 \mathbf{x}^{\top} A \mathbf{x} \ge 0 만 성립하면 A 를 양반정치(positive semidefinite) 행렬이라 한다.

3. 양정치성의 동치 조건

대칭 행렬 A \in \mathbb{R}^{n \times n} 에 대하여 다음 조건들은 모두 동치이다.

1. A 는 양정치이다.
2. A 의 모든 고유값이 양수이다.
3. A 의 모든 선행 주 소행렬식 \det(A_k) (k = 1, 2, \dots, n)가 양수이다(실베스터 판정법).
4. A 의 모든 주소행렬식이 양수이다.
5. A = B^{\top} B 를 만족하는 가역 행렬 B 가 존재한다.
6. A 의 고유한 촐레스키 분해 A = R^{\top} R 가 존재한다.

이 동치 조건들은 양정치 행렬의 다양한 측면을 보여주며, 특히 (6)이 촐레스키 분해의 존재성을 보장한다.

4. 촐레스키 분해의 정의

대칭 양정치 행렬 A \in \mathbb{R}^{n \times n} 에 대하여, 모든 대각 원소가 양수인 상삼각 행렬 R 이 유일하게 존재하여 다음을 만족한다.

A = R^{\top} R

여기서 R 을 A 의 촐레스키 인자(Cholesky factor)라 한다. 동등하게 하삼각 행렬을 사용하여 A = LL^{\top} 의 형태로도 표현할 수 있으며, 이 경우 L = R^{\top} 의 관계가 성립한다.

정리(촐레스키 분해 정리): 임의의 대칭 양정치 행렬 A 에 대하여, 모든 대각 원소가 양수인 상삼각 행렬 R 이 유일하게 존재하여 A = R^{\top} R 을 만족한다.

5. 촐레스키 분해의 계산 절차

A = LL^{\top} 의 등식을 성분별로 비교하면 다음 점화식을 얻는다. j = 1, 2, \dots, n 에 대해 다음을 순차적으로 수행한다.

먼저 대각 원소를 계산한다.

\ell_{jj} = \sqrt{a_{jj} - \sum_{k=1}^{j-1} \ell_{jk}^2}

다음으로 j 열의 대각 아래쪽 원소를 계산한다.

\ell_{ij} = \frac{1}{\ell_{jj}} \left( a_{ij} - \sum_{k=1}^{j-1} \ell_{ik} \ell_{jk} \right), \quad i = j+1, j+2, \dots, n

이 과정에서 A 가 양정치이면 모든 대각 원소 \ell_{jj} 가 항상 실수이며 양수임이 보장된다. 만약 어느 단계에서 제곱근의 인수가 음수이거나 0 이 되면, A 는 양정치가 아님이 판명된다. 이러한 성질은 양정치성을 검증하는 가장 효율적인 방법으로 활용된다.

6. 연산량과 효율성

촐레스키 분해의 전체 연산량은 \frac{1}{3} n^3 + O(n^2) 부동소수점 연산에 해당한다. 이는 LU 분해의 \frac{2}{3} n^3 의 정확히 절반에 해당하는데, 이는 양정치 행렬의 대칭성을 활용하여 하삼각 부분만 계산하면 되기 때문이다. 또한 추가적인 저장 공간이 필요하지 않으며, L 의 원소들을 A 의 하삼각 부분에 그대로 덮어쓸 수 있어 메모리 효율성도 높다.

7. LDL^T 분해

촐레스키 분해의 변형으로 제곱근 계산을 회피하는 LDL^{\top} 분해가 존재한다. 이 분해는 다음과 같은 형태이다.

A = L D L^{\top}

여기서 L 은 대각 원소가 모두 1 인 단위 하삼각 행렬이며, D 는 양수 대각 원소를 가지는 대각 행렬이다. 이 분해는 L 의 원소가 \ell_{ij} = \tilde{\ell}_{ij} / \tilde{\ell}_{jj}, 그리고 D 의 원소가 d_{jj} = \tilde{\ell}_{jj}^2 의 관계를 통해 표준 촐레스키 분해와 연결된다. LDL^{\top} 분해는 제곱근 연산이 비용이 큰 임베디드 시스템과 정수 연산 환경에서 선호된다.

8. 부정치 행렬에 대한 확장: 부카블로크-카우프만 분해

대칭이지만 부정치(indefinite)인 행렬에 대해서는 표준 촐레스키 분해가 적용되지 않는다. 이 경우 부카블로크-카우프만(Bunch-Kaufman) 분해가 사용되며, 다음 형태를 갖는다.

PAP^{\top} = LDL^{\top}

여기서 P 는 순열 행렬, L 은 단위 하삼각 행렬, D 는 1 \times 1 또는 2 \times 2 블록 대각 행렬이다. 이 분해는 모델 예측 제어의 KKT 시스템과 같이 부정치 대칭 행렬을 처리해야 하는 상황에서 필수적이다.

9. 수치적 안정성

촐레스키 분해는 피벗팅 없이도 매우 안정적인 분해이다. 윌킨슨의 후방 오차 분석에 의하면, 양정치 행렬에 대한 촐레스키 분해는 입력 행렬의 미세한 섭동에 대한 정확한 분해와 일치한다. 구체적으로 계산된 인자 \hat{R} 은 다음 관계를 만족하는 행렬 E 가 존재한다.

\hat{R}^{\top} \hat{R} = A + E, \quad \Vert E \Vert_2 \le c_n \epsilon_{\text{mach}} \Vert A \Vert_2

여기서 c_n 은 n 에 대한 작은 다항식이며, \epsilon_{\text{mach}} 는 기계 정밀도이다. 이는 부분 피벗팅이 적용된 LU 분해와 동등한 수준의 안정성을 의미한다.

10. 양반정치 행렬과 피벗팅 촐레스키 분해

행렬이 엄격 양정치가 아닌 양반정치인 경우에는 표준 촐레스키 분해가 실패할 수 있다. 이때 대각 피벗팅을 적용한 촐레스키 분해(피벗팅 촐레스키)가 사용된다. 이 분해는 다음 형태이다.

P^{\top} A P = R^{\top} R

여기서 P 는 순열 행렬이며, R 의 형태는 A 의 랭크에 따라 결정된다. 이 분해는 양반정치 행렬의 랭크를 수치적으로 결정하는 도구로도 활용된다.

11. 분해 인자의 활용

11.1 연립 방정식 해법

A\mathbf{x} = \mathbf{b} 의 해는 A = R^{\top} R 분해 후 두 단계로 구한다.

먼저 R^{\top} \mathbf{y} = \mathbf{b} 를 전방 대입으로 푼다.

y_i = \frac{1}{\ell_{ii}} \left( b_i - \sum_{j=1}^{i-1} \ell_{ij} y_j \right), \quad i = 1, 2, \dots, n

다음으로 R\mathbf{x} = \mathbf{y} 를 후방 대입으로 푼다.

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

각 대입 단계는 \frac{1}{2} n^2 의 연산량을 요구한다.

11.2 행렬식 계산

촐레스키 분해로부터 행렬식은 다음과 같이 효율적으로 계산된다.

\det(A) = \prod_{i=1}^{n} \ell_{ii}^2

이는 모든 \ell_{ii} 가 양수이므로 \det(A) > 0 임을 자동으로 보장한다.

12. 이차 형식과 제곱합 분해

촐레스키 분해는 양정치 이차 형식의 제곱합 표현을 직접 제공한다.

\mathbf{x}^{\top} A \mathbf{x} = \mathbf{x}^{\top} R^{\top} R \mathbf{x} = \Vert R \mathbf{x} \Vert_2^2 = \sum_{i=1}^{n} \left( \sum_{j=i}^{n} r_{ij} x_j \right)^2

이러한 제곱합 표현은 양정치성의 기하학적 의미를 직접 보여주며, 마할라노비스 거리 계산과 가우스 분포의 백색화 변환에 활용된다.

13. 로봇공학에서의 응용

13.1 관절 공간 관성 행렬 처리

로봇 매니퓰레이터의 관절 공간 관성 행렬 M(q) 는 항상 대칭 양정치이다. 정동역학 방정식 M(q) \ddot{q} = \tau - C(q,\dot{q})\dot{q} - g(q) 에서 가속도를 계산할 때 촐레스키 분해를 사용하면, 일반적인 LU 분해 대비 절반의 연산량으로 안정적인 해를 얻을 수 있다. 매 시간 단계마다 M(q) 가 양정치임이 보장되므로 분해 실패 가능성도 없다.

13.2 칼만 필터의 제곱근 형식

칼만 필터의 공분산 행렬은 이론적으로 항상 대칭 양반정치이지만, 부동소수점 연산의 누적 오차로 인해 시간이 지나면 대칭성과 양정치성이 손상되어 필터가 발산할 수 있다. 이를 방지하기 위해 공분산 행렬 P 대신 그 촐레스키 인자 S (P = SS^{\top})를 직접 갱신하는 제곱근 칼만 필터가 사용된다. 이 방식은 수치적 조건수를 절반으로 줄이고 양정치성을 자동으로 보존한다.

13.3 최적 제어의 KKT 시스템

선형 이차 조절기(LQR)의 리카티 방정식 해를 비롯한 최적 제어 문제에서는 양정치 헤시안 행렬이 자주 등장한다. 이러한 행렬에 대해 촐레스키 분해를 적용하여 효율적으로 검색 방향을 계산할 수 있다. 모델 예측 제어의 내부 루프에서 매 시간 단계마다 발생하는 이차 계획 문제의 해법에서도 촐레스키 분해는 표준 도구로 사용된다.

13.4 자코비안 의사 역행렬 계산

감쇠 최소 제곱법을 이용한 역기구학 계산에서는 다음과 같은 양정치 시스템을 풀어야 한다.

(J^{\top} J + \lambda^2 I) \Delta q = J^{\top} \mathbf{e}

좌변의 행렬은 \lambda > 0 일 때 항상 대칭 양정치이므로 촐레스키 분해를 통해 효율적이고 안정적으로 해결할 수 있다. 이는 특이점 근방에서도 수치적으로 안정한 역기구학 알고리즘을 제공한다.

13.5 가우스 과정 회귀를 이용한 모델 학습

데이터 기반 로봇 동역학 학습에서 사용되는 가우스 과정 회귀는 커널 행렬 K + \sigma^2 I 의 역행렬을 요구한다. 이 행렬은 항상 양정치이므로 촐레스키 분해를 통해 안정적으로 해결되며, 학습 데이터가 추가될 때마다 분해를 점진적으로 갱신하는 알고리즘도 존재한다. 이는 강화 학습과 적응 제어에서 실시간 모델 개선을 가능하게 한다.

13.6 접촉 동역학과 LCP 해법

다물체 접촉 동역학에서 발생하는 선형 상보성 문제(LCP)의 일부 해법은 내부적으로 양정치 부분 시스템을 반복적으로 풀어야 한다. 촐레스키 분해는 이러한 부분 시스템을 효율적으로 해결하며, 마찰 원뿔 근사와 결합된 경우에도 안정적으로 동작한다.

13.7 등각도 위치 추정의 정보 행렬

동시 위치 추정 및 지도 작성(SLAM) 문제에서 정보 행렬 형식의 갱신은 항상 양정치 행렬을 다룬다. 그래프 SLAM의 결합 정보 행렬은 매우 큰 희소 양정치 행렬이며, 희소 촐레스키 분해와 적절한 변수 재정렬(최소 차수, 중첩 분할 등)을 결합하여 대규모 문제를 효율적으로 해결한다.

참고문헌

• Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
• Trefethen, L. N., & Bau, D. (1997). Numerical Linear Algebra. SIAM.
• Higham, N. J. (2002). Accuracy and Stability of Numerical Algorithms (2nd ed.). SIAM.
• Horn, R. A., & Johnson, C. R. (2013). Matrix Analysis (2nd ed.). Cambridge University Press.
• Featherstone, R. (2008). Rigid Body Dynamics Algorithms. Springer.
• Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic Robotics. MIT Press.

Version: 1.0