Cholesky 분해의 기초 수식

정의

Cholesky 분해는 대칭이고 양의 정부호인 행렬에 대해 사용하는 행렬 분해 방법이다. $\mathbf{A}$ 가 대칭 양의 정부호 행렬이라면, $\mathbf{A}$ 는 다음과 같이 표현될 수 있다:

$\mathbf{A} = \mathbf{L} \mathbf{L}^\top$

여기서 $\mathbf{L}$ 은 아래 삼각 행렬이다.

분해 과정

주어진 행렬 $\mathbf{A}$ 를 $n \times n$ 크기의 대칭 양의 정부호 행렬이라고 가정한다.
아래의 식을 사용하여 $\mathbf{L}$ 을 계산한다:

$\mathbf{L}_{ij} = \begin{cases} \sqrt{\mathbf{A}_{ii} - \sum_{k=1}^{i-1} \mathbf{L}_{ik}^2} & \text{if } i = j \\ \frac{1}{\mathbf{L}_{jj}} \left( \mathbf{A}_{ij} - \sum_{k=1}^{j-1} \mathbf{L}_{ik} \mathbf{L}_{jk} \right) & \text{if } i > j \\ 0 & \text{if } i < j \end{cases}$

이 식은 각 행렬 요소 $\mathbf{L}_{ij}$ 를 순서대로 계산한다.

예제

예를 들어, 다음과 같은 $3 \times 3$ 대칭 양의 정부호 행렬 $\mathbf{A}$ 가 있다고 가정해봅시다:

$\mathbf{A} = \begin{pmatrix} 4 & 12 & -16 \\ 12 & 37 & -43 \\ -16 & -43 & 98 \end{pmatrix}$

이를 Cholesky 분해하면:

$\mathbf{L} = \begin{pmatrix} 2 & 0 & 0 \\ 6 & 1 & 0 \\ -8 & 5 & 3 \end{pmatrix}$

이다.

Cholesky 분해 알고리즘

다음은 Cholesky 분해의 기본 알고리즘을 나타낸 의사 코드이다:

행렬 A의 차원을 n이라 정의한다.
초기화: L은 0으로 초기화된 $n \times n$ 행렬이다.
반복문: i = 1부터 n까지
j = 1부터 i까지
- 계산: $L_{ij}$

의사 코드는 다음과 같다:

for i from 1 to n do
    for j from 1 to i do
        sum = 0
        for k from 1 to j-1 do
            sum = sum + L[i, k] * L[j, k]
        if i == j then
            L[i, j] = sqrt(A[i, i] - sum)
        else
            L[i, j] = (1.0 / L[j, j] * (A[i, j] - sum))

위의 알고리즘은 직접 행렬 $\mathbf{L}$ 을 계산하는 방법을 제공한다.

코드 예제

Cholesky 분해를 Python으로 구현한 예제 코드는 다음과 같다:

import numpy as np

def cholesky_decomposition(A):
    """
    Performs a Cholesky decomposition of a symmetric
    positive-definite matrix A. The result is a lower
    triangular matrix L such that A = L * L.T.
    """
    n = A.shape[0]
    L = np.zeros_like(A)

    for i in range(n):
        for j in range(i + 1):
            sum = np.dot(L[i, :j], L[j, :j])
            if i == j:  # Diagonal elements
                L[i, j] = np.sqrt(A[i, i] - sum)
            else:
                if L[j, j] == 0:
                    raise ValueError("Matrix is not positive definite")
                L[i, j] = (A[i, j] - sum) / L[j, j]
    return L

A = np.array([[4, 12, -16], 
              [12, 37, -43], 
              [-16, -43, 98]])

L = cholesky_decomposition(A)
print("L:")
print(L)
print("\nL.T:")
print(L.T)
print("\nReconstructed A:")
print(np.dot(L, L.T))

응용

Cholesky 분해는 여러 분야에서 유용하게 응용될 수 있다:

선형 방정식의 해:
Ax = b 형태의 선형 시스템을 해결할 때 Cholesky 분해를 사용하면 효율적으로 해를 찾을 수 있다. B가 주어졌을 때, $L$ 과 $L^\top$ 로 이루어진 이중 연산으로 문제를 푼다.
최소 자승법:
최소 자승 법칙을 통해 과학 데이터나 회귀 분석에 사용되며, 데이터 피팅의 차원 축소에도 응용된다.
통계 및 금융:
공분산 행렬의 Cholesky 분해를 사용하면 주성분 분석(PCA) 같은 통계적 방법론에 쓰인다.
금융 쪽에서는 몬테카를로 시뮬레이션을 통한 옵션 가격 결정 등에도 활용된다.

Cholesky 분해를 통해 다양한 복잡한 행렬 연산을 효율적으로 처리할 수 있으며, 이는 공학 및 과학적 컴퓨팅에서 중요한 역할을 맡고 있다.