숄레스키 분해

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

정의

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

$A=L{L}^{*}$

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

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

역사

프랑스의 수학자 앙드레루이 숄레스키(틀:Llang)가 실수 행렬에 대해 발견했다.

예제

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

응용

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

계산

$\begin{array}{cc}𝐀={𝐋𝐋}^T& =\left(\begin{array}{ccc}{L}_{11}& 0& 0\\ L_{21}& L_{22}& 0\\ L_{31}& L_{32}& L_{33}\end{array}\right)\left(\begin{array}{ccc}{L}_{11}& L_{21}& L_{31}\\ 0& L_{22}& L_{32}\\ 0& 0& L_{33}\end{array}\right)\\ & =\left(\begin{array}{ccc}{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{array}\right),\end{array}$

$\begin{array}{c}𝐋=\left(\begin{array}{ccc}\sqrt{A_{11}}& 0& 0\\ A_{21}/L_{11}& \sqrt{A_{22}-L_{21}^2}& 0\\ A_{31}/L_{11}& (A_{32}-L_{31}{L}_{21})/L_{22}& \sqrt{A_{33}-L_{31}^2-L_{32}^2}\end{array}\right)\end{array}$

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

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

같이 보기

• LU 분해