촐레스키 분해

수치해석 구조해석 마지막 수정: 2026-07-09 05:02:08

촐레스키 분해 Cholesky Decomposition
분해 형태	A = LLᵀ
적용 조건	대칭 양정치 행렬 (SPD)
연산량	LU의 약 1/2 (n³/3)
관련 분해	LU 분해, QR 분해
주요 응용	유한요소 강성행렬, 정규방정식

1. 개요[편집]

대칭이고 양정치라면, 굳이 두 번 일할 필요 없다.

촐레스키 분해(Cholesky Decomposition)는 대칭 양정치(symmetric positive-definite, SPD) 행렬 $A$ 를 하삼각행렬 $L$ 과 그 전치의 곱 $A = LL^{\mathsf T}$ 로 나타내는 분해다. LU 분해의 특수한 경우이지만, 행렬이 대칭이고 양정치라는 강한 조건을 만족하면 위쪽 삼각형을 따로 저장·계산할 필요가 없어져 연산량과 메모리가 정확히 절반으로 줄어든다.¹ 그래서 SPD 행렬을 만났을 때 촐레스키를 안 쓰는 건 그냥 손해다.

프랑스 육군 측지 장교였던 앙드레루이 촐레스키(André-Louis Cholesky)가 삼각측량 문제를 풀려고 고안했는데, 정작 본인은 제1차 세계대전에서 전사하고 유고로 발표되며 세상에 알려졌다.² 오늘날엔 구조해석의 강성행렬, 최소자승의 정규방정식, 몬테카를로 방법의 상관 샘플링까지, SPD가 나오는 곳이라면 어디서나 등장하는 일꾼이 됐다.

2. 알고리즘과 절반의 연산량[편집]

분해식은 $A = LL^{\mathsf T}$ 를 성분별로 풀어 재귀적으로 얻는다. 대각 성분과 비대각 성분이 각각

L_{jj} = \sqrt{A_{jj} - \sum_{k=1}^{j-1} L_{jk}^2}, \qquad L_{ij} = \frac{1}{L_{jj}}\left(A_{ij} - \sum_{k=1}^{j-1} L_{ik}L_{jk}\right)

로 계산된다. 총 연산량은 대략 $n^3/3$ 으로, LU 분해( $2n^3/3$ )의 딱 절반이다. 대칭성 덕에 절반만 훑으면 되기 때문. 게다가 SPD 행렬은 피벗팅 없이도 수치적으로 안정해서, 가우스 소거법에서 골머리를 앓던 부분 피벗팅을 생략할 수 있다는 게 큰 매력이다. 다만 대각 성분에 제곱근이 들어가는 게 거슬리면, 제곱근을 피한 $A = LDL^{\mathsf T}$ 변형을 쓰기도 한다.

3. 양정치 판정기[편집]

촐레스키 분해에는 숨은 보너스가 있다. 양정치성 판정 도구로 쓸 수 있다는 것. 분해를 진행하다 대각 성분 $L_{jj}$ 의 제곱근 안이 0 이하가 되면(음수의 제곱근이 나오면), 그 순간 “이 행렬은 양정치가 아니다”라고 확정할 수 있다. 고유값을 다 구해서 부호를 확인하는 것보다 훨씬 싸고 빠르다.³

이 성질은 최적화에서 특히 요긴하다. 뉴턴-랩슨법 기반 최적화에서 헤시안 행렬이 양정치인지(즉 현재 방향이 하강 방향인지) 확인하는 데, 촐레스키가 성공하느냐 실패하느냐가 곧 판정이 된다. 실패하면 헤시안을 수정(modified Cholesky)해 강제로 양정치로 만들어 밀고 나가기도 한다.

4. 응용[편집]

4.1. 유한요소 강성행렬[편집]

유한요소법으로 조립한 선형 정적 구조 문제의 강성행렬 $K$ 는 (적절한 경계 조건이 걸리면) 대칭 양정치가 된다. 그래서 $Ku = f$ 를 푸는 표준 직접법이 바로 촐레스키다. 실제 상용 구조해석 솔버(예: NASTRAN)의 직접 솔버 상당수가 희소행렬용 촐레스키(sparse Cholesky)를 기반으로 한다. 여기서는 채우기(fill-in)를 줄이는 재정렬(reordering)과 결합해 대규모 문제를 다룬다.

4.2. 정규방정식[편집]

최소자승법의 정규방정식 $A^{\mathsf T}A\,x = A^{\mathsf T}b$ 에서 $A^{\mathsf T}A$ 는 (풀랭크면) SPD다. 촐레스키로 빠르게 풀 수 있지만, 조건수가 제곱으로 나빠진다는 함정이 있어 병적 문제에선 QR 분해나 특이값 분해에 자리를 내준다. “싸고 빠르지만 예민하다”가 요약.

4.3. 몬테카를로 상관 샘플링[편집]

주어진 공분산행렬 $\Sigma$ 를 따르는 상관 있는 난수를 만드는 표준 레시피가 촐레스키다. $\Sigma = LL^{\mathsf T}$ 로 분해한 뒤, 독립 표준정규 벡터 $z$ 에 $L$ 을 곱하면 $Lz$ 가 정확히 원하는 공분산 구조를 갖는다.

\mathrm{Cov}(Lz) = L\,\mathrm{Cov}(z)\,L^{\mathsf T} = LL^{\mathsf T} = \Sigma

몬테카를로 방법 기반 금융 시뮬레이션, 불확실성 정량화(UQ), 가우시안 프로세스 회귀가 모두 이 한 줄에 기대고 있다.

5. 현업에서의 촐레스키[편집]

SPD임이 보장되는 순간, 다른 분해는 고민할 이유가 없다. 반값에 안정성까지 공짜다.
대각 성분 제곱근 안이 음수로 나왔다면? 축하한다, 당신의 행렬은 양정치가 아니거나 반올림 오차로 준정치 경계에 걸린 것이다. 물성치나 경계 조건, 특이한 구속을 의심하라.⁴
대규모 희소 문제에서는 순수 직접법인 촐레스키와 반복법인 크리로프 부분공간법(특히 켤레기울기법, CG) 사이에서 저울질한다. CG의 전처리기로 불완전 촐레스키(incomplete Cholesky)를 쓰는 하이브리드도 흔하다.

6. 관련 문서[편집]

“절반”이 나오는 이유는 순전히 대칭성 때문이다. 위삼각과 아래삼각이 서로 전치라 한쪽만 저장·계산하면 나머지는 공짜로 따라온다. 공짜라는 말에 엔지니어가 약한 건 국룰이다. ↩
촐레스키는 1918년 전사했고, 그의 방법은 동료 브누아(Commandant Benoît)가 1924년에 소개하며 세상에 나왔다. 본인은 자기 이름이 SPD 행렬의 대명사가 될 줄 몰랐을 것이다. ↩
물론 이론적으로는 “모든 선행 주부분행렬식이 양수” 같은 실베스터 판정도 있지만, 실전에서 행렬식을 계산하는 건 촐레스키를 돌리는 것보다 훨씬 비싸고 불안정하다. 그냥 촐레스키를 돌려보고 터지나 안 터지나 보는 게 최고다. ↩
유한요소에서 강체 모드(rigid body mode)를 구속하지 않으면 강성행렬이 특이해져 촐레스키가 대각에서 0을 만나 멈춘다. “왜 안 돌아가지”의 8할은 경계 조건 누락이다. ↩