정의

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

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

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

분해 과정

  1. 주어진 행렬 \mathbf{A}를 n \times n 크기의 대칭 양의 정부호 행렬이라고 가정한다.
  2. 아래의 식을 사용하여 \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 분해의 기본 알고리즘을 나타낸 의사 코드이다:

  1. 행렬 A의 차원을 n이라 정의한다.
  2. 초기화: L은 0으로 초기화된 n \times n 행렬이다.
  3. 반복문: i = 1부터 n까지
  4. 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 분해는 여러 분야에서 유용하게 응용될 수 있다:

  1. 선형 방정식의 해:

  2. Ax = b 형태의 선형 시스템을 해결할 때 Cholesky 분해를 사용하면 효율적으로 해를 찾을 수 있다. B가 주어졌을 때, L과 L^\top로 이루어진 이중 연산으로 문제를 푼다.

  3. 최소 자승법:

  4. 최소 자승 법칙을 통해 과학 데이터나 회귀 분석에 사용되며, 데이터 피팅의 차원 축소에도 응용된다.

  5. 통계 및 금융:

  6. 공분산 행렬의 Cholesky 분해를 사용하면 주성분 분석(PCA) 같은 통계적 방법론에 쓰인다.
  7. 금융 쪽에서는 몬테카를로 시뮬레이션을 통한 옵션 가격 결정 등에도 활용된다.

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