촐레스키 분해(Cholesky Factorization)는 선형대수학에서 특정 종류의 행렬을 다루는 매우 강력하고 효율적인 도구다. 가장 직관적으로 이 분해를 이해하는 방법은 ‘행렬의 제곱근’ 개념을 떠올리는 것이다. 어떤 양수 $a$가 있을 때, 우리는 이를 $a = (\sqrt{a})^2$와 같이 제곱근의 제곱으로 표현할 수 있다.1 이와 유사하게, 특정 조건을 만족하는 행렬 $A$는 $A = LL^T$라는 형태로 분해할 수 있는데, 여기서 $L$은 $A$의 ‘제곱근’과 같은 역할을 하는 특별한 행렬이다.
이 기법은 프랑스의 군 장교이자 수학자였던 앙드레-루이 촐레스키(André-Louis Cholesky)가 20세기 초, 측지학(geodesy), 즉 지구의 모양과 크기를 측정하는 과정에서 발생하는 대규모 선형 연립방정식을 효율적으로 풀기 위해 개발했다. 그의 연구는 사후인 1924년에 발표되었고, 오늘날 수치해석, 통계학, 금융 공학 등 다양한 분야에서 핵심적인 알고리즘으로 자리 잡았다.2
촐레스키 분해는 행렬의 종류에 따라 약간 다른 형태로 정의된다.
실수 행렬 (Real Matrices): 대칭(Symmetric)이면서 양의 정부호(Positive-Definite)인 $n \times n$ 실수 행렬 $A$는 다음과 같이 유일하게 분해된다.2 \(A = LL^T\) 여기서 $L$은 주대각 원소가 모두 양수인 하삼각행렬(Lower triangular matrix)이며, $L^T$는 $L$의 전치행렬(Transpose)로, 자연스럽게 상삼각행렬(Upper triangular matrix)이 된다.4
복소수 행렬 (Complex Matrices): 에르미트(Hermitian)이면서 양의 정부호인 복소수 행렬 $A$는 다음과 같이 분해된다. \(A = LL^*\) 여기서 $L^*$은 $L$의 켤레 전치(Conjugate transpose)를 의미한다.2 이 교재에서는 주로 실수 행렬을 중심으로 설명하지만, 모든 원리는 복소수 행렬에도 동일하게 확장 적용된다.
분해의 결과로 얻어지는 하삼각행렬 $L$을 촐레스키 인자(Cholesky Factor)라고 부른다.10 촐레스키 분해의 중요한 특징 중 하나는 바로 유일성이다. 행렬 $A$가 양의 정부호(Positive-Definite) 조건을 만족한다면, $L$의 대각 원소가 양수여야 한다는 제약 하에 이 분해는 유일하게 하나로 결정된다.2
만약 행렬 $A$가 양의 정부호가 아닌 양의 준정부호(Positive-Semidefinite)라면, 분해는 여전히 가능하지만 $L$의 대각 원소에 0이 포함될 수 있으며, 이 경우 분해 결과는 더 이상 유일하지 않을 수 있다.2
촐레스키 분해는 왜 이렇게 널리 쓰일까? 그 이유는 ‘특수성’과 ‘효율성’의 절묘한 균형에 있다. 적용 조건이 ‘대칭 양의 정부호’로 다소 까다롭지만, 일단 이 조건을 만족하는 행렬에 대해서는 다른 일반적인 분해 방법(예: LU 분해)보다 계산 속도가 약 2배 빠르고 수치적으로 매우 안정적이다.2 공학, 통계학, 금융 분야에서 자주 등장하는 공분산 행렬이나 헤시안 행렬 같은 중요한 행렬들이 바로 이 ‘대칭 양의 정부호’ 속성을 가지기 때문에, 촐레스키 분해는 특정 유형의 문제들을 해결하는 데 최적화된 ‘전용 고속도로’와 같은 역할을 한다.15
촐레스키 분해를 적용하기 위해서는 행렬이 특정 조건을 반드시 만족해야 한다. 이 조건은 단순한 요구사항을 넘어, 분해 알고리즘의 모든 계산 단계가 수학적으로 성립하기 위한 근본적인 보증 장치 역할을 한다.
행렬 $A$가 촐레스키 분해를 가질 필요충분조건(necessary and sufficient condition)은 $A$가 대칭(Symmetric)이고 양의 정부호(Positive-Definite)인 행렬이라는 것이다. (복소수 행렬의 경우 에르미트이고 양의 정부호).5 이 두 가지 조건을 하나씩 살펴보자.
대칭성 조건($A=A^T$)은 $A = LL^T$라는 분해 형태와 자연스럽게 연결된다. $(LL^T)^T = (L^T)^T L^T = LL^T$이므로 $LL^T$는 항상 대칭 행렬이다. 이 대칭성 덕분에 우리는 행렬의 절반(하삼각 또는 상삼각 부분)만 고려하여 계산할 수 있으며, 이는 계산량을 줄이는 데 결정적인 역할을 한다.
양의 정부호(Positive-Definite)라는 개념은 촐레스키 분해의 심장과도 같다. 이 속성은 여러 가지 동등한 방법으로 정의하고 판별할 수 있다. 중요한 점은 양의 정부호 행렬이 단순히 ‘모든 원소가 양수인 행렬’을 의미하는 것이 아니라는 것이다.19
0이 아닌 모든 실수 벡터 $x$에 대해 이차 형식(quadratic form) $x^T A x$의 값이 항상 0보다 크면 ($x^T A x > 0$), 행렬 $A$는 양의 정부호다.19 이는 가장 근본적인 정의 중 하나다.
물리적으로 이 값은 종종 시스템의 ‘에너지’에 비유되는데, 이 조건은 시스템의 에너지가 항상 양수임을 의미한다.23 기하학적으로는 $f(x) = x^T A x$라는 함수가 원점을 제외한 모든 지점에서 양수 값을 가지는, 아래로 오목한 그릇 모양의 다차원 포물면(paraboloid)을 형성한다는 것을 뜻한다.22
대칭 행렬 $A$의 모든 고유값($\lambda$)이 양수($\lambda > 0$)이면, 그 행렬은 양의 정부호다.19 이는 이론적으로 매우 중요한 판별법이다. 고유값은 행렬 변환이 각 고유벡터 방향으로 벡터를 얼마나 ‘확장’ 또는 ‘축소’하는지를 나타내는 비율이다. 모든 고유값이 양수라는 것은 행렬 $A$에 의한 변환이 어떤 고유벡터의 방향도 뒤집지 않고 같은 방향으로 크기만 조절한다는 것을 의미한다.27
이것은 이차 형식 정의로부터 쉽게 유도할 수 있다. 고유값 방정식 $Ax = \lambda x$의 양변에 $x^T$를 곱하면 $x^T A x = x^T \lambda x = \lambda x^T x = \lambda |x|^2$가 된다. $A$가 양의 정부호이면 좌변 $x^T A x > 0$이고, $x$는 0이 아닌 벡터이므로 $|x|^2 > 0$이다. 따라서 반드시 $\lambda > 0$이어야 한다.22
행렬 $A$의 왼쪽 위에서부터 순서대로 잘라낸 $1 \times 1, 2 \times 2, \dots, n \times n$ 부분 행렬(submatrix)들의 행렬식(determinant)이 모두 양수이면, 행렬 $A$는 양의 정부호다.15 이 방법은 고유값을 직접 계산하는 것보다 계산적으로 더 편리할 때가 많다.
행렬 $A$에 대해 피벗팅 없는 가우스 소거법(Gaussian elimination)을 수행했을 때 나타나는 모든 피벗(pivot) 원소들이 양수이면, 행렬 $A$는 양의 정부호다.23 이 조건은 선행 주부분 행렬식 조건과 밀접하게 연관되어 있다.
$k$번째 피벗은 $\det(A_k) / \det(A_{k-1})$로 계산되기 때문이다.23
행렬 $A$가 $A = R^T R$ 형태로 분해 가능하고, 이때 행렬 $R$의 열들이 선형 독립(linearly independent)이라면, $A$는 양의 정부호다.23 이는 촐레스키 분해의 존재 자체가 양의 정부호의 증거가 됨을 역으로 보여준다.
이론적으로는 여러 판별법이 존재하지만, 수치 계산 환경에서 어떤 행렬이 양의 정부호인지 확인하는 가장 빠르고 안정적인 방법은 직접 촐레스키 분해를 시도해보는 것이다.15 분해가 성공적으로 완료되면 그 행렬은 양의 정부호임이 증명된 것이다. 만약 분해 과정에서 대각 원소를 계산할 때 음수의 제곱근을 마주하게 되어 실패한다면, 그 행렬은 양의 정부호가 아닌 것이다. 이 방법은 고유값 계산과 같이 비용이 많이 드는 연산을 피하게 해주는 매우 실용적인 접근법이다.
| 판별법 (Test) | 조건 (Condition) | 장점 (Pros) | 단점 (Cons) |
|---|---|---|---|
| 이차 형식 | 0이 아닌 모든 벡터 $x$에 대해 $x^T A x > 0$ | 이론적, 기하학적 의미가 명확함 | 모든 $x$에 대해 테스트하는 것은 불가능하여 직접적인 계산법은 아님 |
| 고유값 | 모든 고유값이 양수 ($\lambda > 0$) | 가장 근본적인 속성을 보여줌, 이론적으로 강력함 | 고유값 계산 비용이 매우 높음 ($O(n^3)$) |
| 선행 주부분 행렬식 | 모든 선행 주부분 행렬의 행렬식이 양수 | 고유값 계산보다 빠를 수 있음 | $n$이 커지면 행렬식 계산도 복잡해짐 |
| 피벗 | 가우스 소거 시 모든 피벗이 양수 | 계산적으로 효율적임 | 가우스 소거 과정을 수행해야 함 |
| 촐레스키 분해 시도 | 촐레스키 분해가 성공적으로 완료됨 | 가장 빠르고 수치적으로 안정적인 실용적 방법 | 분해 자체를 시도해야 함 |
촐레스키 분해 알고리즘은 $A = LL^T$라는 정의 그 자체에서 출발한다. 행렬 $A$의 각 원소 $a_{ij}$를 $L$과 $L^T$의 곱으로 표현하고, 이 관계식을 이용해 $L$의 원소 $l_{ij}$를 순차적으로 찾아내는 것이다.10
예를 들어, 3x3 실수 대칭 행렬 $A$와 하삼각행렬 $L$에 대해 $A = LL^T$는 다음과 같이 쓸 수 있다. \(\begin{align*} \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} &= \begin{pmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{pmatrix} \begin{pmatrix} l_{11} & l_{21} & l_{31} \\ 0 & l_{22} & l_{32} \\ 0 & 0 & l_{33} \end{pmatrix} \\ &= \begin{pmatrix} l_{11}^2 & l_{21}l_{11} & l_{31}l_{11} \\ l_{21}l_{11} & l_{21}^2 + l_{22}^2 & l_{31}l_{21} + l_{32}l_{22} \\ l_{31}l_{11} & l_{31}l_{21} + l_{32}l_{22} & l_{31}^2 + l_{32}^2 + l_{33}^2 \end{pmatrix} \end{align*}\) 이제 양변의 원소를 하나씩 비교하며 $L$의 원소를 왼쪽 위부터 열(column) 우선으로 계산해 나갈 수 있다.
이러한 방식은 행렬의 크기가 커져도 동일하게 적용된다.
위에서 유도한 원리를 일반화한 것이 촐레스키-바나키에비치 알고리즘이다. 이 알고리즘은 행렬의 왼쪽 위부터 시작하여 한 번에 한 열씩 계산을 진행한다.2
$n \times n$ 행렬 $A$에 대한 $L$의 원소 $l_{ij}$는 다음과 같이 계산된다.
대각 원소 ($l_{jj}$): \(l_{jj} = \sqrt{a_{jj} - \sum_{k=1}^{j-1} l_{jk}^2}\) 10
비대각 원소 ($l_{ij}$ for $i > j$): \(l_{ij} = \frac{1}{l_{jj}} \left( a_{ij} - \sum_{k=1}^{j-1} l_{ik}l_{jk} \right)\) 4
이 공식들을 보면 양의 정부호 조건의 중요성이 다시 한번 명확해진다. 대각 원소 $l_{jj}$를 계산할 때마다 제곱근 연산이 필요한데, 제곱근 안의 값($a_{jj} - \sum_{k=1}^{j-1} l_{jk}^2$)이 항상 양수여야만 계산이 실수 범위 내에서 계속 진행될 수 있다. 행렬 $A$가 양의 정부호라는 조건은 바로 이 값이 항상 양수임을 수학적으로 보장해주는 역할을 한다.8
이 알고리즘의 계산 복잡도(Computational Complexity)는 약 $n^3/3$ 플롭(flops, 부동소수점 연산 횟수)이다. 이는 약 $2n^3/3$ 플롭이 필요한 LU 분해에 비해 약 두 배 효율적이다.4
다음과 같은 3x3 대칭 양의 정부호 행렬 $A$를 촐레스키 분해해보자.1 \(A = \begin{pmatrix} 4 & 12 & -16 \\ 12 & 37 & -43 \\ -16 & -43 & 98 \end{pmatrix}\) 우리의 목표는 $A = LL^T$를 만족하는 하삼각행렬 $L$을 찾는 것이다. \(L = \begin{pmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{pmatrix}\)
| 단계 | 계산할 원소 | 사용 공식 | 계산 과정 | 현재까지의 L 행렬 |
|---|---|---|---|---|
| 1 | $l_{11}$ | $l_{11} = \sqrt{a_{11}}$ | $l_{11} = \sqrt{4} = 2$ | $\begin{pmatrix} 2 & 0 & 0 \? &? & 0 \? &? &? \end{pmatrix}$ |
| 2 | $l_{21}$ | $l_{21} = a_{21} / l_{11}$ | $l_{21} = 12 / 2 = 6$ | $\begin{pmatrix} 2 & 0 & 0 \ 6 &? & 0 \? &? &? \end{pmatrix}$ |
| 3 | $l_{31}$ | $l_{31} = a_{31} / l_{11}$ | $l_{31} = -16 / 2 = -8$ | $\begin{pmatrix} 2 & 0 & 0 \ 6 &? & 0 \ -8 &? &? \end{pmatrix}$ |
| 4 | $l_{22}$ | $l_{22} = \sqrt{a_{22} - l_{21}^2}$ | $l_{22} = \sqrt{37 - 6^2} = \sqrt{37 - 36} = \sqrt{1} = 1$ | $\begin{pmatrix} 2 & 0 & 0 \ 6 & 1 & 0 \ -8 &? &? \end{pmatrix}$ |
| 5 | $l_{32}$ | $l_{32} = (a_{32} - l_{31}l_{21}) / l_{22}$ | $l_{32} = (-43 - (-8)(6)) / 1 = -43 + 48 = 5$ | $\begin{pmatrix} 2 & 0 & 0 \ 6 & 1 & 0 \ -8 & 5 &? \end{pmatrix}$ |
| 6 | $l_{33}$ | $l_{33} = \sqrt{a_{33} - (l_{31}^2 + l_{32}^2)}$ | $l_{33} = \sqrt{98 - ((-8)^2 + 5^2)} = \sqrt{98 - (64 + 25)} = \sqrt{98 - 89} = \sqrt{9} = 3$ | $\begin{pmatrix} 2 & 0 & 0 \ 6 & 1 & 0 \ -8 & 5 & 3 \end{pmatrix}$ |
따라서 최종적으로 구한 촐레스키 인자 $L$은 다음과 같다. \(L = \begin{pmatrix} 2 & 0 & 0 \\ 6 & 1 & 0 \\ -8 & 5 & 3 \end{pmatrix}\) 검산을 위해 $LL^T$를 계산해보면 원래 행렬 $A$와 일치함을 확인할 수 있다.
촐레스키 분해는 이론적인 우아함을 넘어 다양한 실제 문제 해결에 매우 유용하게 사용된다. 특히 효율성과 수치적 안정성이 중요한 분야에서 그 진가를 발휘한다.
행렬 $A$가 대칭 양의 정부호일 때, 선형 연립방정식 $Ax=b$를 푸는 가장 효율적인 방법은 촐레스키 분해를 이용하는 것이다.2
먼저 $A$를 $LL^T$로 분해하여 방정식을 $LL^Tx=b$로 바꾼다. 그 다음, $L^Tx = y$라는 새로운 벡터 $y$를 도입하면, 복잡했던 원래 문제는 다음과 같은 두 개의 간단한 삼각 시스템 문제로 나뉜다.11
삼각 시스템을 푸는 데 필요한 계산량은 각각 $O(n^2)$에 불과하므로, 전체 해법의 시간 복잡도는 분해 자체에 필요한 $O(n^3)$에 의해 결정된다. 이는 역행렬을 직접 구하는 것보다 훨씬 빠르고 수치적으로 안정적인 방법이다.30
촐레스키 분해의 가장 강력하고 우아한 응용 중 하나는 몬테카를로 시뮬레이션에서 여러 변수 간의 상관관계를 갖는 난수를 생성하는 것이다.2 금융 자산의 가격 변동, 공학 시스템의 불확실성 모델링 등 복잡한 시스템을 시뮬레이션할 때 필수적인 기법이다.
그 원리는 다음과 같다.
목표 설정: 특정 공분산 행렬(Covariance Matrix) $\Sigma$를 따르는 다변수 정규분포 난수 벡터 $X$를 생성하고자 한다. 이 공분산 행렬 $\Sigma$는 변수들 간의 상관 구조를 담고 있다.
재료 준비: 컴퓨터는 서로 아무런 상관관계가 없는(uncorrelated) 독립적인 표준 정규분포 난수들을 쉽게 생성할 수 있다. 이러한 난수들로 구성된 벡터를 $Z$라고 하자. $Z$의 각 원소는 평균이 0, 분산이 1이며, 따라서 $Z$의 공분산 행렬은 항등행렬 $I$이다 ($E = I$).
변환 적용: 목표 공분산 행렬 $\Sigma$를 촐레스키 분해하여 $L$을 구한다 ($\Sigma = LL^T$). 그 다음, 다음과 같은 선형 변환을 독립 난수 벡터 $Z$에 적용한다. \(X = \mu + LZ\) 여기서 $\mu$는 생성하고자 하는 난수 벡터의 평균이다.
결과 검증: 이렇게 생성된 벡터 $X$의 공분산은 다음과 같이 계산된다. \(\begin{align*} Cov(X) &= E \\ &= E \\ &= E \\ &= L E L^T \\ &= L I L^T \\ &= LL^T = \Sigma \end{align*}\) 32
이 과정을 통해, 생성하기 쉬운 독립 난수 벡터 $Z$에 촐레스키 인자 $L$을 곱해주는 간단한 연산만으로 목표했던 복잡한 상관 구조 $\Sigma$를 가진 난수 벡터 $X$를 완벽하게 만들어낼 수 있다. 여기서 촐레스키 인자 $L$은 마치 독립적인 재료에 원하는 ‘상관관계의 맛’을 주입하는 ‘마법 소스’와 같은 역할을 한다.33
촐레스키 분해는 다양한 최적화 문제, 특히 목적 함수가 미분 가능한 경우에 널리 사용된다.
선형 최소제곱법 (Linear Least Squares): 데이터 피팅이나 회귀 분석에서 자주 등장하는 정규방정식(Normal Equation) $A^TAx = A^Tb$를 푸는 데에도 촐레스키 분해가 효과적이다. 행렬 $A$의 열들이 선형 독립이라면, $A^TA$는 항상 대칭 양의 정부호 행렬이 된다. 따라서 이 정규방정식을 촐레스키 분해를 이용해 빠르고 정확하게 풀 수 있다.2
촐레스키 분해는 여러 행렬 분해 기법 중 하나이며, 다른 방법들과 비교할 때 그 특징과 장단점이 명확히 드러난다.
LU 분해는 정방행렬 $A$를 하삼각행렬 $L$과 상삼각행렬 $U$의 곱($A=LU$)으로 분해하는 가장 일반적인 방법 중 하나다.
LDLᵀ 분해는 ‘제곱근 없는(Square-root-free)’ 촐레스키 분해라고도 불린다.2 이는 행렬 $A$를 $A = LDL^T$ 형태로 분해하는 방법으로, 여기서 $L$은 대각 원소가 모두 1인 단위 하삼각행렬(unit lower triangular matrix)이고, $D$는 대각 원소가 모두 양수인 대각행렬(diagonal matrix)이다.2
이 방법의 가장 큰 장점은 알고리즘에서 비용이 많이 들고 정밀도 오류를 유발할 수 있는 제곱근 계산을 피할 수 있다는 점이다.2 이로 인해 특정 계산 환경에서는 촐레스키 분해보다 더 빠르거나 선호될 수 있다.
| 분해법 | 분해 형태 | 적용 행렬 | 계산 비용 | 수치 안정성 | 주요 용도 |
|---|---|---|---|---|---|
| 촐레스키 | $A = LL^T$ | 대칭 양의 정부호 | $O(n^3/3)$ | 매우 높음 (피벗팅 불필요) | 선형 시스템, 공분산 행렬 분해, 몬테카를로 |
| LDLᵀ | $A = LDL^T$ | 대칭 양의 정부호 | $O(n^3/3)$ | 매우 높음 (제곱근 없음) | 촐레스키와 유사, 제곱근 연산 회피 |
| LU | $A = LU$ | 대부분의 정방행렬 | $O(2n^3/3)$ | 피벗팅(LUP) 시 안정적 | 일반적인 선형 시스템 해법 |
| QR | $A = QR$ | 모든 $m \times n$ 행렬 | $O(2mn^2)$ | 매우 높음 | 최소제곱법, 고유값 문제 |
촐레스키 분해는 이론뿐만 아니라 실제 코드 구현도 매우 중요하다. 다행히 대부분의 과학 계산 라이브러리에서 고도로 최적화된 함수를 제공한다.
Python 생태계에서는 NumPy와 SciPy 라이브러리를 통해 촐레스키 분해를 손쉽게 수행할 수 있다.
numpy.linalg.cholesky(A): 이 함수는 행렬 A를 입력받아 하삼각 촐레스키 인자 L을 반환한다. A가 대칭 양의 정부호가 아니면 LinAlgError를 발생시킨다.41scipy.linalg.cholesky(A, lower=True): NumPy와 유사하지만, lower 매개변수를 통해 하삼각(True) 또는 상삼각(False) 인자를 선택하여 반환받을 수 있다.16코드 예제:
다음은 NumPy를 사용한 촐레스키 분해 예제이다.1
import numpy as np
# 앞선 예제에서 사용한 대칭 양의 정부호 행렬
A = np.array([[4, 12, -16],
[12, 37, -43],
[-16, -43, 98]])
try:
# 촐레스키 분해 수행
L = np.linalg.cholesky(A)
print("Original Matrix A:\n", A)
print("\nCholesky Factor L:\n", L)
# 검증: L @ L.T 가 A와 일치하는지 확인
# @는 행렬 곱셈 연산자
reconstructed_A = L @ L.T
print("\nVerification (L @ L.T):\n", reconstructed_A)
# np.allclose는 부동소수점 오차를 감안하여 두 행렬이 거의 같은지 비교
print("\nIs reconstruction close to A?:", np.allclose(A, reconstructed_A))
except np.linalg.LinAlgError:
print("Matrix is not positive definite.")
알고리즘의 작동 원리를 깊이 이해하기 위해, 라이브러리 없이 순수 Python으로 구현해보는 것도 좋은 학습 방법이다.16
NumPy나 SciPy 같은 고수준 라이브러리의 성능은 그 내부에 있다. 이 라이브러리들은 행렬 연산을 위해 수십 년간 최적화된 저수준 포트란 라이브러리인 LAPACK(Linear Algebra PACKage)을 호출한다.
DPOTRF(실수 배정밀도)와 SPOTRF(실수 단정밀도)이다.49DPBTRF와 같은 특화된 루틴도 존재한다.52 이는 실제 고성능 컴퓨팅 환경에서는 문제의 구조에 맞는 최적의 알고리즘을 선택하는 것이 중요함을 보여준다.