숄레스키 분해

숄레스키 분해(Cholesky decomposition)는 에르미트 행렬(Hermitian matrix), 양의 정부호행렬(positive-definite matrix)의 분해에서 사용된다. 촐레스키 분해의 결과는 하삼각행렬과 하삼각행렬의 켤레전치 행렬의 곱으로 표현된다.

정의

에르미트 양의 정부호 행렬 $A$의 숄레스키 분해는 다음과 같은 꼴의 분해이다.

$A=LL^{*}$

여기서 $L$은 하삼각행렬이며, $L^{*}$는 $L$의 켤레전치이다. 또한, $L$의 대각 성분들은 모두 양의 실수이다.

$A$의 모든 성분이 실수이면, $L$의 모든 성분도 실수이며, $A=LL^{T}$로 분해된다.

역사

프랑스의 수학자 앙드레루이 숄레스키(프랑스어: André-Louis Cholesky)가 실수 행렬에 대해 발견했다.

예제

${\begin{aligned}\left({\begin{array}{*{3}{r}}4&12&-16\\12&37&-43\\-16&-43&98\\\end{array}}\right)=\left({\begin{array}{*{3}{r}}2&0&0\\6&1&0\\-8&5&3\\\end{array}}\right)\left({\begin{array}{*{3}{r}}2&6&-8\\0&1&5\\0&0&3\\\end{array}}\right).\end{aligned}}$

응용

이는 효율적인 수치해석에서 유용하게 사용되며, 몬테 카를로 시뮬레이션(Monte Carlo Simulations)에서도 유용하다. 선형 방정식 시스템을 푸는 실제 응용에서, 촐레스키 분해가 LU 분해와 비교했을 때 약 두 배 정도 효율적인 것으로 알려졌다.

계산

${\begin{aligned}\mathbf {A} =\mathbf {LL} ^{T}&={\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}&&({\text{symmetric}})\\L_{21}L_{11}&L_{21}^{2}+L_{22}^{2}&\\L_{31}L_{11}&L_{31}L_{21}+L_{32}L_{22}&L_{31}^{2}+L_{32}^{2}+L_{33}^{2}\end{pmatrix}},\end{aligned}}$

${\begin{aligned}\mathbf {L} ={\begin{pmatrix}{\sqrt {A_{11}}}&0&0\\A_{21}/L_{11}&{\sqrt {A_{22}-L_{21}^{2}}}&0\\A_{31}/L_{11}&\left(A_{32}-L_{31}L_{21}\right)/L_{22}&{\sqrt {A_{33}-L_{31}^{2}-L_{32}^{2}}}\end{pmatrix}}\end{aligned}}$

$L_{j,j}={\sqrt {A_{j,j}-\sum _{k=1}^{j-1}L_{j,k}^{2}}},$

$L_{i,j}={\frac {1}{L_{j,j}}}\left(A_{i,j}-\sum _{k=1}^{j-1}L_{i,k}L_{j,k}\right)\quad {\text{for }}i>j.$

같이 보기

• LU 분해