숄레스키 분해

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

숄레스키 분해는 에르미트 양의 정부호 행렬을 하삼각 행렬 L과 그 켤레 전치 L*의 곱으로 분해하는 방법이다. 이 분해는 선형 방정식 시스템의 수치적 해법, 선형 최소 자승법, 비선형 최적화, 몬테카를로 시뮬레이션, 칼만 필터, 행렬 반전 등 다양한 분야에 응용된다. 숄레스키 분해는 숄레스키 알고리즘, 숄레스키-바나키에비츠 알고리즘, 숄레스키-크라우트 알고리즘 등 여러 알고리즘으로 계산할 수 있으며, LDL 분해와 같은 변형도 존재한다. 또한, 숄레스키 분해는 블록 변형, 랭크-1 업데이트, 행과 열의 추가 및 제거를 통해 효율적으로 업데이트될 수 있다. 불완전 숄레스키 분해는 연립 1차 방정식의 해법에서 전처리 기법으로 사용된다. 숄레스키 분해는 C, 파이썬, 매트랩, R, 줄리아, C++, Java 등 다양한 프로그래밍 언어와 라이브러리에서 구현되어 있다.

더 읽어볼만한 페이지

행렬 분해 - QR 분해
QR 분해는 행렬을 직교 행렬과 상삼각 행렬의 곱으로 분해하는 방법으로, 실수 또는 복소수 행렬을 직교/유니터리 행렬 Q와 상삼각 행렬 R의 곱으로 표현하여 선형대수학의 계산 및 분석에 활용되며, 그람-슈미트 과정, 하우스홀더 변환, 기븐스 회전 등 다양한 계산 방법이 존재한다.
행렬 분해 - 조르당 표준형
조르당 표준형은 대수적으로 닫힌 체 위에서 정사각 행렬을 유사 변환하여 얻을 수 있는 특정한 형태의 행렬로, 조르당 블록으로 구성되며 고윳값, 중복도, 특성/최소 다항식과 관련 있고, 스펙트럼 사영 정리, 케일리-해밀턴 정리 등 다양한 정리 증명과 행렬 계산에 응용된다.
수치선형대수학 - 가우스 소거법
가우스 소거법은 연립 일차 방정식의 해를 구하기 위해 행렬을 사다리꼴로 변환하는 알고리즘이며, 기본 행 연산을 통해 전진 소거와 후퇴 대입 단계를 거쳐 해를 계산하고, 행렬식 계산 등 다양한 분야에 응용된다.
수치선형대수학 - LINPACK
LINPACK은 부동소수점 연산 성능을 평가하는 벤치마크 프로그램이자 FORTRAN 라이브러리로, 슈퍼컴퓨터 성능 측정 기준으로 사용되는 HPLinpack 벤치마크의 기반이 되었으며, TOP500 목록에서 고성능 컴퓨터 순위를 결정하는 데 기여한다.
선형대수학 - 벡터 공간
벡터 공간은 체 위의 가군으로 정의되는 대수적 구조로, 벡터 덧셈과 스칼라 곱셈 연산을 가지며 특정 공리들을 만족하고, 기저, 차원, 선형 사상 등의 개념을 통해 수학과 물리학 등 다양한 분야에서 활용된다.
선형대수학 - 선형 결합
선형 결합은 벡터 공간에서 벡터들의 스칼라 곱의 합으로 표현되는 식으로, 벡터 집합의 선형 독립성 판단 및 부분 공간 생성과 관련되며, 계수 제약을 통해 다양한 종류의 결합을 정의할 수 있고, 위상 벡터 공간이나 가군으로 일반화될 수 있다.

숄레스키 분해

2. 정의

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

: $A=LL^*$

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

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

2. 1. 양의 준정부호 행렬

에르미트 행렬 '''A'''가 양의 정부호가 아닌 양의 준정부호 행렬이라면, '''L'''의 대각선 요소가 0이 될 수 있다는 점을 제외하면, '''A''' = '''LL'''* 형태의 분해를 갖는다.^[7]

이 분해는 고유하지 않을 수 있다. 예를 들어, 다음과 같은 식이 모든 θ에 대해 성립한다.

\begin{bmatrix}0 & 0 \\0 & 1\end{bmatrix} = \mathbf L \mathbf L^*, \quad \quad \mathbf L=\begin{bmatrix}0 & 0\\ \cos \theta & \sin\theta\end{bmatrix},

그러나 '''A'''의 랭크가 r인 경우, 정확히 r개의 양의 대각선 요소와 모든 0을 포함하는 n − r개의 열을 가진 고유한 하삼각 행렬 '''L'''이 존재한다.^[8]

또는, 피벗 선택을 고정하면 분해를 고유하게 만들 수 있다. 공식적으로, '''A'''가 랭크 r의 n × n 양의 준정부호 행렬인 경우, PAP^T가

\mathbf L =  \begin{bmatrix} \mathbf L_1 & 0 \\ \mathbf L_2 & 0\end{bmatrix}

여기서 L₁은 양의 대각선을 가진 r × r 하삼각 행렬이다.^[9]의 형태의 고유한 분해를 갖도록 하는, 적어도 하나의 순열 행렬 P가 존재한다.

2. 2. LDL 분해

숄레스키 분해의 변형으로, A = LDL^* 형태로 분해하는 방법이다. 여기서 L은 하부 단위 삼각(단위 삼각) 행렬이고, D는 대각 행렬이다.^[10] 즉, L의 대각선 요소는 분해에 추가 대각 행렬 D를 도입하는 대신 1로 지정해야 한다. LDL 분해는 기본적으로 동일한 알고리즘으로 계산하고 사용할 수 있지만 제곱근 추출을 피할 수 있다는 주요 장점을 갖는다.^[10]

이러한 이유로 LDL 분해는 종종 ''제곱근 없는 숄레스키'' 분해라고 불린다. 실수 행렬의 경우, 인수분해는 A = LDL^T 형식을 가지며, 종종 LDLT 분해 (또는 LDL^T 분해, 또는 LDL′)라고 불린다. 이는 실대칭 행렬의 고유값 분해, A = QΛQ^T를 연상시키지만, Λ와 D가 유사 행렬이 아니기 때문에 실제로 상당히 다르다.

LDL 분해는 LL^* 형식의 고전적인 숄레스키 분해와 다음과 같이 관련되어 있다.

:'''A''' = '''LDL'''^* = '''L'''D^1/2(D^1/2)^*'''L'''^* = '''L'''D^1/2('''L'''D^1/2)^*.

반대로, 양의 정부호 행렬의 고전적인 숄레스키 분해 A = CC^*가 주어지면, S가 C의 주 대각선을 포함하는 대각 행렬인 경우, A는 L D L^*로 분해될 수 있다. 여기서

:'''L''' = '''C'''S^-1 (이것은 각 열을 재조정하여 대각선 요소를 1로 만든다),

:'''D''' = '''S'''².
A가 양의 정부호이면, D의 대각선 요소는 모두 양수이다. 양의 반정부호 A의 경우, 대각선 D에 있는 0이 아닌 요소의 수가 정확히 A의 랭크인 L D L^* 분해가 존재한다.^[11] 숄레스키 분해가 존재하지 않는 일부 부정 행렬은 D에 음수 항목이 있는 LDL 분해를 갖는다. ''n'' − 1 선행 주 마이너가 특이값이 아니면 충분하다.^[12]

수정 숄레스키 분해(개정 숄레스키 분해라고도 함)는 제곱근 연산을 사용하지 않고 사칙 연산만으로 계산을 수행한다. 따라서 행렬이 실대칭 행렬이면 계산은 실수 사칙 연산만으로 수행할 수 있다.

수정 숄레스키 분해에서는

:'''A'' = '''LDL'''^*

의 형태로 분해를 계산한다. 여기서, '''D'''는 대각 행렬이며, 행렬 '''L'''의 대각 성분은 모두 1로 한다. 단, 분해 과정에서 영 피벗에 의한 나눗셈이 발생하면 계산이 실패하고 분해가 존재하지 않을 수도 있다.

주의: 수정 숄레스키 분해는 행렬이 정칙 행렬이더라도 존재하지 않는 경우가 있다(예를 들어 대각 요소가 0이고 비대각 요소가 1인 2차 대칭 행렬은 정칙 행렬이지만 숄레스키 분해나 수정 숄레스키 분해가 존재하지 않는 간단한 예이다). 행렬이 정부호일 때 분해는 반드시 존재한다. 영에 의한 나눗셈의 어려움을 대칭적인 피벗 교환으로 회피할 수 있는 경우도 있지만, 위의 2차 대칭 행렬의 예와 같이 회피가 불가능한 경우가 있다.

수정 숄레스키 분해를 더욱 확장하여 D를 대칭적인 삼중 대각 행렬로 하는 Aasen 방법, 또는 D를 1차 또는 2차 대칭 행렬로 이루어진 블록 대각 행렬로 분해를 수행하는 Bunch-Kaufman 방법 등이 알려져 있으며, 이 경우에는 분해가 반드시 존재한다.

또한, 행렬 A가 복소 대칭(A^T=A)인 경우에도, 실대칭 행렬과 마찬가지로 사칙 연산을 복소수를 사용하여 수행함으로써 (계산이 도중에 실패하지 않는다면) 분해 A = LDL^T를 얻을 수 있다.

3. 역사

프랑스의 수학자 앙드레루이 숄레스키(André-Louis Cholesky)가 실수 행렬에 대해 발견했다. 숄레스키의 1910년 원고 ''Sur la résolution numérique des systèmes d'équations linéaires''는 [http://bibnum.education.fr/mathematiques/algebre/sur-la-resolution-numerique-des-systemes-d-equations-lineaires BibNum]에서 온라인으로 분석 가능하다.en^프랑스어

4. 예제

다음은 3x3 실수 대칭 행렬의 숄레스키 분해 예시이다.

: $\begin{pmatrix}4 & 12 & -16 \\12 & 37 & -43 \\$

16 & -43 & 98

\end{pmatrix}=\begin{pmatrix}2 & 0 & 0 \\6 & 1 & 0 \\

8 & 5 & 3

\end{pmatrix}\begin{pmatrix}2 & 6 & -8 \\0 & 1 & 5 \\0 & 0 & 3\end{pmatrix}.

다음은 LDLᵀ 분해 예시이다.

:

\begin{pmatrix}4 & 12 & -16 \\12 & 37 & -43 \\

16 & -43 & 98

\end{pmatrix}=\begin{pmatrix}1 & 0 & 0 \\3 & 1 & 0 \\

4 & 5 & 1

\end{pmatrix}\begin{pmatrix}4 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 9\end{pmatrix}\begin{pmatrix}1 & 3 & -4 \\0 & 1 & 5 \\0 & 0 & 1\end{pmatrix}.

5. 기하학적 해석

숄레스키 분해는 켤레 축의 특정 선택과 동일하다.^[13] 타원은 단위 원의 선형 이미지이다. 두 벡터 $v_1, v_2$ 는 타원의 켤레 축이며, $v_1$ 은 첫 번째 축에 평행하고 $v_2$ 는 처음 두 축으로 뻗어 있는 평면 내에 있도록 선택된다.

행렬

V := [v_1 | v_2 | \cdots | v_n]

을 정의하면,

v_i^T A v_j = \delta_{ij}

는

V^TAV = I

와 같다. 켤레 축의 다른 선택은 다른 분해에 해당한다.

촐레스키 분해는

v_1

을 첫 번째 축에 평행하도록,

v_2

를 처음 두 축으로 뻗어 있는 평면 내에 있도록 선택하는 것과 같다. 이런 방식으로

V

는 상삼각 행렬이 된다. 그러면,

A = LL^T

이고, 여기서

L = (V^{-1})^T

는 하삼각 행렬이다.

마찬가지로, 주성분 분석은

v_1, ..., v_n

을 수직으로 선택하는 것과 일치한다. 그런 다음

\lambda = 1/\|v_i\|^2

및

\Sigma = \mathrm{diag}(\lambda_1, ..., \lambda_n)

이라고 할 때,

V = U\Sigma^{-1/2}

이고, 여기서

U

는 직교 행렬이다. 그러면

A = U\Sigma U^T

가 생성된다.

6. 응용

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

== 선형 방정식 시스템의 수치적 해법 ==

숄레스키 분해는 선형 방정식 시스템 '''Ax''' = '''b'''의 수치적 해를 구하는 데 사용된다.^[23] 만약 '''A'''가 대칭 행렬이며 양의 정부호 행렬이라면, 숄레스키 분해 '''A''' = '''LL'''^*를 계산한 다음, 전진 대입으로 '''Ly''' = '''b'''를 풀어 '''y'''를 구하고, 마지막으로 후진 대입으로 '''L'''^*'''x''' = '''y'''를 풀어 '''x'''를 구함으로써 해결할 수 있다.

선형 시스템을 대칭 형태로 만들 수 있는 경우, 숄레스키 분해는 우수한 효율성과 수치적 안정성을 위해 선택되는 방법이다. LU 분해에 비해, 대략 두 배 더 효율적이다.^[2]

== 선형 최소 제곱법 ==

선형 최소 자승법 문제의 정규 방정식은 숄레스키 분해를 통해 효율적으로 풀 수 있다.^[23] 이는 편미분 방정식의 수치적 해법에서 자주 발생한다.

== 비선형 최적화 ==

뉴턴 방법의 변형인 준 뉴턴 방법을 사용하여 비선형 다변수 함수를 최소화할 수 있다. 반복 k에서 탐색 단계는 $B_k p_k = -g_k$ 를 $p_k$ 에 대해 풀어 정의된 방향 $p_k$ 로 진행된다. $p_k$ 는 단계 방향, $g_k$ 는 기울기, $B_k$ 는 각 반복에서 랭크-1 업데이트를 반복하여 형성된 헤시안 행렬의 근사값이다.^[14] 잘 알려진 두 가지 업데이트 공식은 데이비돈-플레처-파월 (DFP)과 브로이덴-플레처-골드파르브-샤노 (BFGS)이다.^[14] 헤시안 행렬의 역 근사값을 업데이트하는 대신 헤시안 행렬 자체의 근사값에 대한 숄레스키 분해를 업데이트하면 반올림 오류로 인한 양의 정부호 조건 손실을 방지할 수 있다.^[14]

== 몬테카를로 시뮬레이션 ==

숄레스키 분해는 여러 상관 변수를 가진 시스템을 시뮬레이션하기 위한 몬테카를로 방법에서 흔히 사용된다.^[15] 공분산 행렬은 하부 삼각 행렬을 제공하도록 분해된다. 이것을 상관관계가 없는 관측값의 벡터에 적용하면 모델링되는 시스템의 공분산 특성을 가진 샘플 벡터가 생성된다.^[15]

단순화된 예시로, 주어진 상관 계수 $\rho$ 를 가진 두 개의 상관 정규 변수 $x_1$ 과 $x_2$ 를 생성하는 경우를 들 수 있다. 먼저 박스-뮬러 변환 등을 통해 두 개의 상관관계가 없는 가우스 확률 변수 $z_1$ 과 $z_2$ 를 생성한다. 필요한 상관 계수 $\rho$ 가 주어지면, 상관 정규 변수는 변환 $x_1 = z_1$ 과 $x_2 = \rho z_1 + \sqrt{1 - \rho^2} z_2$ 를 통해 얻을 수 있다.

== 칼만 필터 ==

숄레스키 분해는 무향 칼만 필터에서 시그마 점 집합을 선택하는 데 사용된다.^[23] 칼만 필터는 길이 ''N''의 벡터 '''x'''로 시스템의 평균 상태와 ''N'' × ''N'' 행렬 '''P'''로 공분산을 추적한다. 행렬 '''P'''는 항상 양의 반정부호이며 '''LL'''^T로 분해될 수 있다. '''L'''의 열은 평균 '''x'''에서 더하고 빼서 시그마 점이라고 하는 2''N''개의 벡터 집합을 형성할 수 있으며, 이러한 시그마 점은 시스템 상태의 평균과 공분산을 완전히 포착한다.^[23]

== 행렬 반전 ==

에르미트 행렬의 역행렬은 숄레스키 분해를 사용하여 계산할 수 있으며, $n^3$ 연산( $\tfrac{1}{2} n^3$ 곱셈)이 소요된다.^[10] 전체 역행렬 계산은 제자리에서 효율적으로 수행될 수도 있다. 비에르미트 행렬 '''B'''의 역행렬은 다음 항등식을 사용하여 계산할 수 있다.

: $\mathbf{B}^{-1} = \mathbf{B}^* (\mathbf{B B}^*)^{-1}.$

여기서 '''BB'''*는 항상 에르미트 행렬이다. 숄레스키 분해는 선형 방정식 시스템을 푸는 실제 응용에서 LU 분해와 비교했을 때 약 두 배 정도 효율적이며, 몬테 카를로 시뮬레이션에서도 유용하게 사용된다.^[23]

6. 1. 선형 방정식 시스템의 수치적 해법

숄레스키 분해는 선형 방정식 시스템 '''Ax''' = '''b'''의 수치적 해를 구하는 데 사용된다.^[23] 만약 '''A'''가 대칭 행렬이며 양의 정부호 행렬이라면, 숄레스키 분해 '''A''' = '''LL'''^*를 계산한 다음, 전진 대입으로 '''Ly''' = '''b'''를 풀어 '''y'''를 구하고, 마지막으로 후진 대입으로 '''L'''^*'''x''' = '''y'''를 풀어 '''x'''를 구함으로써 해결할 수 있다.

선형 시스템을 대칭 형태로 만들 수 있는 경우, 숄레스키 분해는 우수한 효율성과 수치적 안정성을 위해 선택되는 방법이다. LU 분해에 비해, 대략 두 배 더 효율적이다.^[2]

6. 2. 선형 최소 제곱법

선형 최소 자승법 문제의 정규 방정식은 숄레스키 분해를 통해 효율적으로 풀 수 있다.^[23] 이는 편미분 방정식의 수치적 해법에서 자주 발생한다.

6. 3. 비선형 최적화

뉴턴 방법의 변형인 준 뉴턴 방법을 사용하여 비선형 다변수 함수를 최소화할 수 있다. 반복 k에서 탐색 단계는

B_k p_k = -g_k

를

p_k

에 대해 풀어 정의된 방향

p_k

로 진행된다.

p_k

는 단계 방향,

g_k

는 기울기,

B_k

는 각 반복에서 랭크-1 업데이트를 반복하여 형성된 헤시안 행렬의 근사값이다.^[14] 잘 알려진 두 가지 업데이트 공식은 데이비돈-플레처-파월 (DFP)과 브로이덴-플레처-골드파르브-샤노 (BFGS)이다.^[14] 헤시안 행렬의 역 근사값을 업데이트하는 대신 헤시안 행렬 자체의 근사값에 대한 숄레스키 분해를 업데이트하면 반올림 오류로 인한 양의 정부호 조건 손실을 방지할 수 있다.^[14]

6. 4. 몬테카를로 시뮬레이션

숄레스키 분해는 여러 상관 변수를 가진 시스템을 시뮬레이션하기 위한 몬테카를로 방법에서 흔히 사용된다.^[15] 공분산 행렬은 하부 삼각 행렬을 제공하도록 분해된다. 이것을 상관관계가 없는 관측값의 벡터에 적용하면 모델링되는 시스템의 공분산 특성을 가진 샘플 벡터가 생성된다.^[15]

단순화된 예시로, 주어진 상관 계수

\rho

를 가진 두 개의 상관 정규 변수

x_1

과

x_2

를 생성하는 경우를 들 수 있다. 먼저 박스-뮬러 변환 등을 통해 두 개의 상관관계가 없는 가우스 확률 변수

z_1

과

z_2

를 생성한다. 필요한 상관 계수

\rho

가 주어지면, 상관 정규 변수는 변환

x_1 = z_1

과

x_2 =  \rho z_1 + \sqrt{1 - \rho^2} z_2

를 통해 얻을 수 있다.

6. 5. 칼만 필터

숄레스키 분해는 무향 칼만 필터에서 시그마 점 집합을 선택하는 데 사용된다.^[23] 칼만 필터는 길이 ''N''의 벡터 '''x'''로 시스템의 평균 상태와 ''N'' × ''N'' 행렬 '''P'''로 공분산을 추적한다. 행렬 '''P'''는 항상 양의 반정부호이며 '''LL'''^T로 분해될 수 있다. '''L'''의 열은 평균 '''x'''에서 더하고 빼서 시그마 점이라고 하는 2''N''개의 벡터 집합을 형성할 수 있으며, 이러한 시그마 점은 시스템 상태의 평균과 공분산을 완전히 포착한다.^[23]

6. 6. 행렬 반전

에르미트 행렬의 역행렬은 숄레스키 분해를 사용하여 계산할 수 있으며,

n^3

연산(

\tfrac{1}{2} n^3

곱셈)이 소요된다.^[10] 전체 역행렬 계산은 제자리에서 효율적으로 수행될 수도 있다. 비에르미트 행렬 '''B'''의 역행렬은 다음 항등식을 사용하여 계산할 수 있다.

:

\mathbf{B}^{-1} = \mathbf{B}^* (\mathbf{B B}^*)^{-1}.

여기서 '''BB'''*는 항상 에르미트 행렬이다. 숄레스키 분해는 선형 방정식 시스템을 푸는 실제 응용에서 LU 분해와 비교했을 때 약 두 배 정도 효율적이며, 몬테 카를로 시뮬레이션에서도 유용하게 사용된다.^[23]

7. 계산

숄레스키 분해를 계산하는 다양한 방법이 있다. 일반적으로 널리 사용되는 알고리즘의 계산 복잡성은 ''O''(''n''³)이다. 아래 설명된 알고리즘은 모두 실수 연산의 경우 약 (1/3)''n''³ FLOPs (''n''³/6번의 곱셈과 같은 횟수의 덧셈)을 사용하며, 복소수 연산의 경우 (4/3)''n''³ FLOPs를 사용한다.^[16] 여기서 ''n''은 행렬 '''A'''의 크기이다. 따라서, 이는 2''n''³/3 FLOPs를 사용하는 LU 분해보다 계산 비용이 절반이다(Trefethen과 Bau 1997 참조).

아래 알고리즘 중 어떤 것이 더 빠른지는 구현 세부 사항에 따라 다르다. 일반적으로 첫 번째 알고리즘은 데이터에 덜 규칙적인 방식으로 접근하기 때문에 약간 더 느리다.

=== 숄레스키 알고리즘 ===

숄레스키 알고리즘은 가우스 소거법의 변형된 형태로, 분해 행렬 '''L'''을 계산하는 데 사용된다. 재귀적으로 하삼각행렬 L을 계산한다.

'''A'''가 실수 행렬인 경우, 에르미트 행렬은 대칭 행렬이 되고, 켤레 전치는 전치 행렬이 된다.

숄레스키 분해는 '''A'''를 순차적으로 '''L'''과 '''L'''^*로 묶어 전진 소거하는 방식으로 생각할 수 있다.

:

이때 의 에르미트성은 유지된다.

숄레스키 분해의 재귀적 알고리즘은 먼저 로 정의한다.

번째 단계에서, 에르미트성을 유지하면서 의 행과 열을 전진 소거하여 를 생성한다. 는 행·열까지 전진 소거된 에르미트 행렬이므로, 다음과 같이 표현할 수 있다.

: $\boldsymbol{A}^{(i)}=\begin{bmatrix}\boldsymbol{I}_{i-1} & 0 & 0 \\0 & a_{i,i} & \boldsymbol{b}_{i}^{*} \\0 & \boldsymbol{b}_{i} & \boldsymbol{B}^{(i)}\end{bmatrix}$

여기서 는 차의 단위 행렬, 는 번째 대각 성분, 는 열의 하삼각부, 는 의 ''i''+1행·열 이후의 부분으로 역시 에르미트이다.

다음으로, 을 다음과 같이 정의한다.

: $\boldsymbol{L}_{i}: =\begin{bmatrix}\boldsymbol{I}_{i-1} & 0 & 0 \\0 & \sqrt{a_{i,i}} & 0 \\0 & \dfrac{1}{\sqrt{a_{i,i}}} \boldsymbol{b}_{i} & \boldsymbol{I}_{n-i}\end{bmatrix}$

그러면 '''A'''''^(''i'')는 다음과 같이 표현된다.

: $\boldsymbol{A}^{(i)}=\boldsymbol{L}_{i}\boldsymbol{A}^{(i+1)}\boldsymbol{L}_{i}^{*}$

여기서 는 다음과 같다.

: $\boldsymbol{A}^{(i+1)}=\begin{bmatrix}\boldsymbol{I}_{i-1} & 0 & 0 \\0 & 1 & 0 \\0 & 0 & \boldsymbol{B}^{(i)} - \dfrac{1}{a_{i,i}} \boldsymbol{b}_{i} \boldsymbol{b}_{i}^{*}\end{bmatrix}$

는 행렬의 곱이다.

을 의 차수로 하여, 이 단계를 번 반복하면 = 이 되어 숄레스키 분해가 종료된다.

: $\boldsymbol{A}^{(1)} = \boldsymbol{L}_{1} \boldsymbol{L}_{2} \dotsb \boldsymbol{L}_{n} \boldsymbol{A}^{(n+1)} \boldsymbol{L}_{n}^{*} \dotsb \boldsymbol{L}_{2}^{*} \boldsymbol{L}_{1}^{*}$

: $\boldsymbol{L} := \boldsymbol{L}_{1} \boldsymbol{L}_{2} \dotsb \boldsymbol{L}_{n}$

위 식을 통해,

: $\boldsymbol{A} = \boldsymbol{L} \boldsymbol{L}^{*}$

임을 확인할 수 있다.

구체적인 계산 방법은 다음과 같다.

: $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.$

=== 숄레스키-바나키에비츠 알고리즘 ===

숄레스키-바나키에비츠 알고리즘은 행렬 '''L'''의 왼쪽 위 모서리에서 시작하여 행 단위로 계산을 수행한다.

: $\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{대칭}) \\ 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}$

위 식을 통해 아래와 같은 결과를 얻는다.

: $\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}$

따라서 '''L'''의 각 항목은 다음 공식으로 계산된다.

: $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.$

복소수 에르미트 행렬의 경우, 다음 공식이 적용된다.

: $L_{j,j} = \sqrt{ A_{j,j} - \sum_{k=1}^{j-1} L_{j,k}^*L_{j,k} }$

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

5×5 행렬에 대한 제자리 숄레스키-바나키에비츠 알고리즘의 접근 패턴(흰색)과 쓰기 패턴(노란색)

아래는 C로 작성된 알고리즘이다.

```C

for (i = 0; i < dimensionSize; i++) {

for (j = 0; j <= i; j++) {

float sum = 0;

for (k = 0; k < j; k++)

sum += L[i][k] * L[j][k];

if (i == j)

L[i][j] = sqrt(A[i][i] - sum);

else

L[i][j] = (1.0 / L[j][j] * (A[i][j] - sum));

}

}

```

Fortran과 같은 벡터화 프로그래밍 언어에서는 dot product와 행렬 곱셈을 결합하여 알고리즘을 간결하게 표현할 수 있다.

```Fortran

do i = 1, size(A,1)

L(i,i) = sqrt(A(i,i) - dot_product(L(i,1:i-1), L(i,1:i-1)))

L(i+1:,i) = (A(i+1:,i) - matmul(conjg(L(i,1:i-1)), L(i+1:,1:i-1))) / L(i,i)

end do

```

여기서 `conjg`는 요소의 복소 공액을 의미한다.

=== 숄레스키-크라우트 알고리즘 ===

숄레스키-크라우트 알고리즘은 행렬 L의 왼쪽 위 모서리에서 시작하여 열 단위로 계산을 수행한다. 이 알고리즘은 숄레스키-바나키에비츠 알고리즘과 유사하지만, 계산 순서에 차이가 있다.

다음은 숄레스키 분해의 일반적인 형태이다.

:

\begin{align}\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{대칭})   \\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{align}

:

\begin{align}\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{align}

L의 항목은 다음 공식을 사용하여 계산할 수 있다.

:

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.

복소수 에르미트 행렬의 경우 다음 공식이 적용된다.

:

L_{j,j} = \sqrt{ A_{j,j} - \sum_{k=1}^{j-1} L_{j,k}^*L_{j,k} },

:

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

C 언어에서는 다음과 같이 구현할 수 있다.

```C

for (j = 0; j < dimensionSize; j++) {

float sum = 0;

for (k = 0; k < j; k++) {

sum += L[j][k] * L[j][k];

}

L[j][j] = sqrt(A[j][j] - sum);

for (i = j + 1; i < dimensionSize; i++) {

sum = 0;

for (k = 0; k < j; k++) {

sum += L[i][k] * L[j][k];

}

L[i][j] = (1.0 / L[j][j] * (A[i][j] - sum));

}

}

```

Fortran과 같은 벡터화 프로그래밍 언어에서는 내적(dot product)과 행렬 곱셈(matrix multiplication)을 활용하여 더 간결하게 표현할 수 있다.

```Fortran

do i = 1, size(A,1)

L(i,i) = sqrt(A(i,i) - dot_product(L(1:i-1,i), L(1:i-1,i)))

L(i,i+1:) = (A(i,i+1:) - matmul(conjg(L(1:i-1,i)), L(1:i-1,i+1:))) / L(i,i)

end do

```

여기서 `conjg`는 요소의 복소 공액을 의미한다.

=== 계산 안정성 ===

숄레스키 분해는 잘 조정된 선형 방정식 시스템에서 피벗 연산 없이도 안정적으로 해를 계산할 수 있는 알고리즘이다.^[17] 이는 LU 분해와 비교했을 때, 피벗 전략을 사용하지 않으면 불안정해질 수 있는 LU 분해와 달리, 숄레스키 분해는 항상 작은 오차를 보장한다는 장점을 가진다.

구체적으로, '''Ax''' = '''b'''의 해를 숄레스키 분해를 통해 계산한 결과 '''y'''는 섭동 시스템 ('''A''' + '''E''')'''y''' = '''b'''를 만족하며, 이때 행렬 '''E'''의 2-노름(||·||₂)은 ||'''E'''||₂ ≤ c_nε||'''A'''||₂를 만족한다. 여기서 c_n는 n에 의존하는 작은 상수이고, ε는 단위 반올림 오차를 나타낸다.^[17]

숄레스키 분해에서 제곱근 연산은 반올림 오차로 인해 음수가 되는 경우가 발생할 수 있지만, 이는 행렬의 조건이 매우 나쁠 때만 발생한다.^[17] 이러한 문제를 해결하기 위해 분해되는 행렬에 대각선 보정 행렬을 추가하여 양의 정부호를 유지하는 방법이 있다. 이는 분해의 정확도를 다소 떨어뜨릴 수 있지만, 최적화에서의 뉴턴 방법과 같이 안정성을 향상시키는 데 유용하게 사용될 수 있다.^[17]

=== LDL 분해 계산 ===

'''A'''가 대칭 행렬일 때 제곱근을 취할 필요가 없는 대안적인 형태는 대칭 부정 분해^[18]이다. 다음과 같이 행렬을 분해한다.

:

\begin{align}\mathbf{A} = \mathbf{LDL}^\mathrm{T} & =\begin{pmatrix}   1 & 0 & 0 \\L_{21} & 1 & 0 \\L_{31} & L_{32} & 1\\\end{pmatrix}\begin{pmatrix}   D_1 & 0 & 0 \\0 & D_2 & 0 \\0 & 0 & D_3\\\end{pmatrix}\begin{pmatrix}   1 & L_{21} & L_{31} \\0 & 1 & L_{32} \\0 & 0 & 1\\\end{pmatrix} \\[8pt]& = \begin{pmatrix}   D_1 &   &(\mathrm{symmetric})   \\L_{21}D_1 & L_{21}^2D_1 + D_2& \\L_{31}D_1 & L_{31}L_{21}D_{1}+L_{32}D_2 & L_{31}^2D_1 + L_{32}^2D_2+D_3.\end{pmatrix}.\end{align}

'''D'''와 '''L'''의 성분에 대해 다음과 같은 재귀 관계가 적용된다.

:

D_j = A_{jj} - \sum_{k=1}^{j-1} L_{jk}^2 D_k,

:

L_{ij} = \frac{1}{D_j} \left( A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk} D_k \right) \quad \text{for } i>j.

'''D'''에서 생성된 대각선 요소가 0이 아닌 한 이 방법은 작동하며, 분해가 고유하게 된다. '''A'''가 실수이면 '''D'''와 '''L'''은 실수이다.

복소 에르미트 행렬 '''A'''에 대해 다음 공식이 적용된다.

:

D_{j} = A_{jj} - \sum_{k=1}^{j-1} L_{jk}L_{jk}^* D_k,

:

L_{ij} = \frac{1}{D_j} \left( A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk}^* D_k \right) \quad \text{for } i>j.

마찬가지로, 액세스 패턴을 사용하면 원하는 경우 전체 계산을 제자리에서 수행할 수 있다.

수정 숄레스키 분해는 제곱근 연산을 사용하지 않고 사칙 연산만으로 계산을 수행하여, 행렬이 실대칭 행렬이면 실수 사칙 연산만으로 계산할 수 있다는 장점이 있다. 수정 숄레스키 분해에서는

:

\boldsymbol{A} = \boldsymbol{LDL}^{*}

의 형태로 분해를 계산한다. 여기서, 는 대각 행렬이며, 행렬 의 대각 성분은 모두 1로 한다. 단, 분해 과정에서 영 피벗에 의한 나눗셈이 발생하면 계산이 실패하고 분해가 존재하지 않을 수도 있다.

행렬이 정칙 행렬이더라도 수정 숄레스키 분해가 존재하지 않는 경우가 있다. 행렬이 정부호일 때 분해는 반드시 존재한다. 영에 의한 나눗셈의 어려움은 대칭적인 피벗 교환으로 회피할 수 있는 경우도 있지만, 회피가 불가능한 경우도 있다.

수정 숄레스키 분해를 더욱 확장하여 D를 대칭적인 삼중 대각 행렬로 하는 Aasen 방법, 또는 D를 1차 또는 2차 대칭 행렬로 이루어진 블록 대각 행렬로 분해를 수행하는 Bunch-Kaufman 방법 등이 알려져 있으며, 이 경우에는 분해가 반드시 존재한다.

또한, 행렬

A

가 복소 대칭(

A^T=A

)인 경우에도, 실대칭 행렬과 마찬가지로 복소수를 사용하여 사칙 연산을 수행함으로써 분해

A = LDL^T

를 얻을 수 있다.

=== 블록 변형 ===

부정부호 행렬에 숄레스키 분해, 즉 '''LDL'''* 인수분해를 사용할 때는 주의 깊은 피벗팅이 없으면 불안정하다고 알려져 있다.^[19] 특히, 인수분해 요소들이 임의로 커질 수 있다. 이를 개선하기 위해 블록 부분 행렬(일반적으로 2 × 2)에 대해 인수분해를 수행할 수 있다.^[20]

다음과 같이 행렬 '''A'''를 나타낼 수 있다.

\mathbf{A} = \mathbf{LDL}^\mathrm{T} =\begin{pmatrix}\mathbf I & 0 & 0 \\\mathbf L_{21} & \mathbf I & 0 \\\mathbf L_{31} & \mathbf L_{32} & \mathbf I\\\end{pmatrix}\begin{pmatrix}\mathbf D_1 & 0 & 0 \\0 & \mathbf D_2 & 0 \\0 & 0 & \mathbf D_3\\\end{pmatrix}\begin{pmatrix}\mathbf I & \mathbf L_{21}^\mathrm T & \mathbf L_{31}^\mathrm T \\0 & \mathbf I & \mathbf L_{32}^\mathrm T \\0 & 0 & \mathbf I\\\end{pmatrix}

위 식에서 모든 요소는 정방 부분 행렬이다. 이를 통해 다음과 같은 재귀 관계를 얻을 수 있다.

\mathbf D_j = \mathbf A_{jj} - \sum_{k=1}^{j-1} \mathbf L_{jk} \mathbf D_k \mathbf L_{jk}^\mathrm T,

\mathbf L_{ij} = \left(\mathbf A_{ij} - \sum_{k=1}^{j-1} \mathbf L_{ik} \mathbf D_k \mathbf L_{jk}^\mathrm T\right) \mathbf D_j^{-1}.

이러한 계산은 행렬 곱과 명시적인 역행렬 계산을 포함하므로 실제 블록 크기가 제한된다.

=== 분해 업데이트 ===

숄레스키 분해는 행렬

\mathbf{A}

가 변경되었을 때, 업데이트된 행렬

\tilde{\mathbf{A}}

의 숄레스키 분해

\tilde{\mathbf{L}} \tilde{\mathbf{L}}^*

를 효율적으로 계산하기 위해 사용될 수 있다.

\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{x} \mathbf{x}^*

와 같이 행렬

\mathbf{A}

가 업데이트 되는 경우를 랭크-1 업데이트라고 한다.^[21] 랭크-1 업데이트를 수행하는 Matlab 코드는 다음과 같다.

```matlab

function [L] = cholupdate(L, x)

n = length(x);

for k = 1:n

r = sqrt(L(k, k)^2 + x(k)^2);

c = r / L(k, k);

s = x(k) / L(k, k);

L(k, k) = r;

if k < n

L((k+1):n, k) = (L((k+1):n, k) + s * x((k+1):n)) / c;

x((k+1):n) = c * x((k+1):n) - s * L((k+1):n, k);

end

end

end

```

\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{M} \mathbf{M}^*

와 같이 행렬

\mathbf{M}

에 대해 분해를 업데이트하는 것은 랭크-n 업데이트라고 하며,

\mathbf{M}

의 각 열에 대해 랭크-1 업데이트를 순차적으로 수행하여 구할 수 있다.

\tilde{\mathbf{A}} = \mathbf{A} - \mathbf{x} \mathbf{x}^*

와 같이 뺄셈으로 업데이트가 이루어지는 경우는 랭크-1 다운데이트라고 하며, 새로운 행렬

\tilde{\mathbf{A}}

가 여전히 양의 정부호일 경우에 적용할 수 있다. 랭크-1 업데이트 코드에서 r과 L((k+1):n, k)에 대한 할당의 두 덧셈을 뺄셈으로 바꾸면 랭크-1 다운데이트를 수행할 수 있다.

=== 행과 열 추가 및 제거 ===

대칭 양의 정부호 행렬 '''A'''가 블록 형태로 표현될 때, 기존 촐레스키 분해 '''L'''을 이용하여 새로운 행과 열이 추가된 행렬

\tilde{\mathbf{A}}

의 촐레스키 분해

\tilde{\mathbf{S}}

를 계산할 수 있다.

\mathbf{A} =\begin{pmatrix}\mathbf A_{11} & \mathbf A_{13} \\\mathbf A_{13}^{\mathrm{T}} & \mathbf A_{33} \\\end{pmatrix}

\mathbf{L} =\begin{pmatrix}\mathbf L_{11} &  \mathbf L_{13} \\0      & \mathbf L_{33} \\\end{pmatrix},

\begin{align}\tilde{\mathbf{A}} &=\begin{pmatrix}\mathbf A_{11} & \mathbf A_{12} & \mathbf A_{13} \\\mathbf A_{12}^{\mathrm{T}} & \mathbf A_{22} & \mathbf A_{23} \\\mathbf A_{13}^{\mathrm{T}} & \mathbf A_{23}^{\mathrm{T}} &  \mathbf A_{33} \\\end{pmatrix}\end{align}

\begin{align}\tilde{\mathbf{S}} &=\begin{pmatrix}\mathbf S_{11} & \mathbf S_{12} & \mathbf S_{13} \\0 & \mathbf S_{22} & \mathbf S_{23} \\0 & 0 &  \mathbf S_{33} \\\end{pmatrix}.\end{align}

삼각 행렬에서 쉽게 찾을 수 있는

\mathbf A \mathbf x = \mathbf b

의 해를

\mathbf A \setminus \mathbf{b}

로 표기하고,

\mathbf M

의 촐레스키 분해를

\text{chol} (\mathbf M)

으로 표기하면, 다음과 같은 관계를 통해

\tilde{\mathbf{S}}

를 구할 수 있다.^[22]

\begin{align}\mathbf S_{11} &= \mathbf L_{11}, \\\mathbf S_{12} &= \mathbf L_{11}^{\mathrm{T}} \setminus \mathbf A_{12}, \\\mathbf S_{13} &= \mathbf L_{13}, \\\mathbf S_{22} &= \mathrm{chol} \left(\mathbf A_{22}  - \mathbf S_{12}^{\mathrm{T}} \mathbf S_{12}\right), \\\mathbf S_{23} &= \mathbf S_{22}^{\mathrm{T}} \setminus \left(\mathbf A_{23} - \mathbf S_{12}^{\mathrm{T}} \mathbf S_{13}\right), \\\mathbf S_{33} &= \mathrm{chol} \left(\mathbf L_{33}^{\mathrm{T}} \mathbf L_{33} - \mathbf S_{23}^{\mathrm{T}} \mathbf S_{23}\right).\end{align}

반대로, 행과 열이 제거된 행렬 '''A'''의 촐레스키 인수 '''L'''은 다음과 같이 계산할 수 있다.^[22]

\begin{align}\mathbf L_{11} &= \mathbf S_{11}, \\\mathbf L_{13} &= \mathbf S_{13}, \\\mathbf L_{33} &= \mathrm{chol} \left(\mathbf S_{33}^{\mathrm{T}} \mathbf S_{33} + \mathbf S_{23}^{\mathrm{T}} \mathbf S_{23}\right).\end{align}

7. 1. 숄레스키 알고리즘

숄레스키 알고리즘은 가우스 소거법의 변형된 형태로, 분해 행렬 '''L'''을 계산하는 데 사용된다. 재귀적으로 하삼각행렬 L을 계산한다.

'''A'''가 실수 행렬인 경우, 에르미트 행렬은 대칭 행렬이 되고, 켤레 전치는 전치 행렬이 된다.

숄레스키 분해는 '''A'''를 순차적으로 '''L'''과 '''L'''^*로 묶어 전진 소거하는 방식으로 생각할 수 있다.

:

이때 의 에르미트성은 유지된다.

숄레스키 분해의 재귀적 알고리즘은 먼저 로 정의한다.

번째 단계에서, 에르미트성을 유지하면서 의 행과 열을 전진 소거하여 를 생성한다. 는 행·열까지 전진 소거된 에르미트 행렬이므로, 다음과 같이 표현할 수 있다.

:

\boldsymbol{A}^{(i)}=\begin{bmatrix}\boldsymbol{I}_{i-1} & 0 & 0 \\0 & a_{i,i} & \boldsymbol{b}_{i}^{*} \\0 & \boldsymbol{b}_{i} & \boldsymbol{B}^{(i)}\end{bmatrix}

여기서 는 차의 단위 행렬, 는 번째 대각 성분, 는 열의 하삼각부, 는 의 ''i''+1행·열 이후의 부분으로 역시 에르미트이다.

다음으로, 을 다음과 같이 정의한다.

:

\boldsymbol{L}_{i}: =\begin{bmatrix}\boldsymbol{I}_{i-1} & 0 & 0 \\0 & \sqrt{a_{i,i}} & 0 \\0 & \dfrac{1}{\sqrt{a_{i,i}}} \boldsymbol{b}_{i} & \boldsymbol{I}_{n-i}\end{bmatrix}

그러면 '''A'''''^(''i'')는 다음과 같이 표현된다.

:

\boldsymbol{A}^{(i)}=\boldsymbol{L}_{i}\boldsymbol{A}^{(i+1)}\boldsymbol{L}_{i}^{*}

여기서 는 다음과 같다.

:

\boldsymbol{A}^{(i+1)}=\begin{bmatrix}\boldsymbol{I}_{i-1} & 0 & 0 \\0 & 1 & 0 \\0 & 0 & \boldsymbol{B}^{(i)} - \dfrac{1}{a_{i,i}} \boldsymbol{b}_{i} \boldsymbol{b}_{i}^{*}\end{bmatrix}

는 행렬의 곱이다.

을 의 차수로 하여, 이 단계를 번 반복하면 = 이 되어 숄레스키 분해가 종료된다.

:

\boldsymbol{A}^{(1)} = \boldsymbol{L}_{1} \boldsymbol{L}_{2} \dotsb \boldsymbol{L}_{n} \boldsymbol{A}^{(n+1)} \boldsymbol{L}_{n}^{*} \dotsb \boldsymbol{L}_{2}^{*} \boldsymbol{L}_{1}^{*}

:

\boldsymbol{L} := \boldsymbol{L}_{1} \boldsymbol{L}_{2} \dotsb \boldsymbol{L}_{n}

위 식을 통해,

:

\boldsymbol{A} = \boldsymbol{L} \boldsymbol{L}^{*}

임을 확인할 수 있다.

구체적인 계산 방법은 다음과 같다.

:

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.

7. 2. 숄레스키-바나키에비츠 알고리즘

숄레스키-바나키에비츠 알고리즘은 행렬 '''L'''의 왼쪽 위 모서리에서 시작하여 행 단위로 계산을 수행한다.

\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{대칭})   \\  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}

위 식을 통해 아래와 같은 결과를 얻는다.

\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}

따라서 '''L'''의 각 항목은 다음 공식으로 계산된다.

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.

복소수 에르미트 행렬의 경우, 다음 공식이 적용된다.

L_{j,j} = \sqrt{ A_{j,j} - \sum_{k=1}^{j-1} L_{j,k}^*L_{j,k} }

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

아래는 C로 작성된 알고리즘이다.

```C

for (i = 0; i < dimensionSize; i++) {

for (j = 0; j <= i; j++) {

float sum = 0;

for (k = 0; k < j; k++)

sum += L[i][k] * L[j][k];

if (i == j)

L[i][j] = sqrt(A[i][i] - sum);

else

L[i][j] = (1.0 / L[j][j] * (A[i][j] - sum));

}

}

```

Fortran과 같은 벡터화 프로그래밍 언어에서는 dot product와 행렬 곱셈을 결합하여 알고리즘을 간결하게 표현할 수 있다.

```Fortran

do i = 1, size(A,1)

L(i,i) = sqrt(A(i,i) - dot_product(L(i,1:i-1), L(i,1:i-1)))

L(i+1:,i) = (A(i+1:,i) - matmul(conjg(L(i,1:i-1)), L(i+1:,1:i-1))) / L(i,i)

end do

```

여기서 `conjg`는 요소의 복소 공액을 의미한다.

7. 3. 숄레스키-크라우트 알고리즘

숄레스키-크라우트 알고리즘은 행렬 L의 왼쪽 위 모서리에서 시작하여 열 단위로 계산을 수행한다. 이 알고리즘은 숄레스키-바나키에비츠 알고리즘과 유사하지만, 계산 순서에 차이가 있다.

다음은 숄레스키 분해의 일반적인 형태이다.

:

\begin{align}\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{대칭})   \\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{align}

:

\begin{align}\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{align}

L의 항목은 다음 공식을 사용하여 계산할 수 있다.

:

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.

복소수 에르미트 행렬의 경우 다음 공식이 적용된다.

:

L_{j,j} = \sqrt{ A_{j,j} - \sum_{k=1}^{j-1} L_{j,k}^*L_{j,k} },

:

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

C 언어에서는 다음과 같이 구현할 수 있다.

```C

for (j = 0; j < dimensionSize; j++) {

float sum = 0;

for (k = 0; k < j; k++) {

sum += L[j][k] * L[j][k];

}

L[j][j] = sqrt(A[j][j] - sum);

for (i = j + 1; i < dimensionSize; i++) {

sum = 0;

for (k = 0; k < j; k++) {

sum += L[i][k] * L[j][k];

}

L[i][j] = (1.0 / L[j][j] * (A[i][j] - sum));

}

}

```

Fortran과 같은 벡터화 프로그래밍 언어에서는 내적(dot product)과 행렬 곱셈(matrix multiplication)을 활용하여 더 간결하게 표현할 수 있다.

```Fortran

do i = 1, size(A,1)

L(i,i) = sqrt(A(i,i) - dot_product(L(1:i-1,i), L(1:i-1,i)))

L(i,i+1:) = (A(i,i+1:) - matmul(conjg(L(1:i-1,i)), L(1:i-1,i+1:))) / L(i,i)

end do

```

여기서 `conjg`는 요소의 복소 공액을 의미한다.

7. 4. 계산 안정성

숄레스키 분해는 잘 조정된 선형 방정식 시스템에서 피벗 연산 없이도 안정적으로 해를 계산할 수 있는 알고리즘이다.^[17] 이는 LU 분해와 비교했을 때, 피벗 전략을 사용하지 않으면 불안정해질 수 있는 LU 분해와 달리, 숄레스키 분해는 항상 작은 오차를 보장한다는 장점을 가진다.

구체적으로, '''Ax''' = '''b'''의 해를 숄레스키 분해를 통해 계산한 결과 '''y'''는 섭동 시스템 ('''A''' + '''E''')'''y''' = '''b'''를 만족하며, 이때 행렬 '''E'''의 2-노름(||·||₂)은 ||'''E'''||₂ ≤ c_nε||'''A'''||₂를 만족한다. 여기서 c_n는 n에 의존하는 작은 상수이고, ε는 단위 반올림 오차를 나타낸다.^[17]

숄레스키 분해에서 제곱근 연산은 반올림 오차로 인해 음수가 되는 경우가 발생할 수 있지만, 이는 행렬의 조건이 매우 나쁠 때만 발생한다.^[17] 이러한 문제를 해결하기 위해 분해되는 행렬에 대각선 보정 행렬을 추가하여 양의 정부호를 유지하는 방법이 있다. 이는 분해의 정확도를 다소 떨어뜨릴 수 있지만, 최적화에서의 뉴턴 방법과 같이 안정성을 향상시키는 데 유용하게 사용될 수 있다.^[17]

7. 5. LDL 분해 계산

'''A'''가 대칭 행렬일 때 제곱근을 취할 필요가 없는 대안적인 형태는 대칭 부정 분해^[18]이다. 다음과 같이 행렬을 분해한다.

:

\begin{align}\mathbf{A} = \mathbf{LDL}^\mathrm{T} & =\begin{pmatrix}   1 & 0 & 0 \\L_{21} & 1 & 0 \\L_{31} & L_{32} & 1\\\end{pmatrix}\begin{pmatrix}   D_1 & 0 & 0 \\0 & D_2 & 0 \\0 & 0 & D_3\\\end{pmatrix}\begin{pmatrix}   1 & L_{21} & L_{31} \\0 & 1 & L_{32} \\0 & 0 & 1\\\end{pmatrix} \\[8pt]& = \begin{pmatrix}   D_1 &   &(\mathrm{symmetric})   \\L_{21}D_1 & L_{21}^2D_1 + D_2& \\L_{31}D_1 & L_{31}L_{21}D_{1}+L_{32}D_2 & L_{31}^2D_1 + L_{32}^2D_2+D_3.\end{pmatrix}.\end{align}

'''D'''와 '''L'''의 성분에 대해 다음과 같은 재귀 관계가 적용된다.

:

D_j = A_{jj} - \sum_{k=1}^{j-1} L_{jk}^2 D_k,

:

L_{ij} = \frac{1}{D_j} \left( A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk} D_k \right) \quad \text{for } i>j.

'''D'''에서 생성된 대각선 요소가 0이 아닌 한 이 방법은 작동하며, 분해가 고유하게 된다. '''A'''가 실수이면 '''D'''와 '''L'''은 실수이다.

복소 에르미트 행렬 '''A'''에 대해 다음 공식이 적용된다.

:

D_{j} = A_{jj} - \sum_{k=1}^{j-1} L_{jk}L_{jk}^* D_k,

:

L_{ij} = \frac{1}{D_j} \left( A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk}^* D_k \right) \quad \text{for } i>j.

마찬가지로, 액세스 패턴을 사용하면 원하는 경우 전체 계산을 제자리에서 수행할 수 있다.

수정 숄레스키 분해는 제곱근 연산을 사용하지 않고 사칙 연산만으로 계산을 수행하여, 행렬이 실대칭 행렬이면 실수 사칙 연산만으로 계산할 수 있다는 장점이 있다. 수정 숄레스키 분해에서는

:

\boldsymbol{A} = \boldsymbol{LDL}^{*}

의 형태로 분해를 계산한다. 여기서, 는 대각 행렬이며, 행렬 의 대각 성분은 모두 1로 한다. 단, 분해 과정에서 영 피벗에 의한 나눗셈이 발생하면 계산이 실패하고 분해가 존재하지 않을 수도 있다.

행렬이 정칙 행렬이더라도 수정 숄레스키 분해가 존재하지 않는 경우가 있다. 행렬이 정부호일 때 분해는 반드시 존재한다. 영에 의한 나눗셈의 어려움은 대칭적인 피벗 교환으로 회피할 수 있는 경우도 있지만, 회피가 불가능한 경우도 있다.

수정 숄레스키 분해를 더욱 확장하여 D를 대칭적인 삼중 대각 행렬로 하는 Aasen 방법, 또는 D를 1차 또는 2차 대칭 행렬로 이루어진 블록 대각 행렬로 분해를 수행하는 Bunch-Kaufman 방법 등이 알려져 있으며, 이 경우에는 분해가 반드시 존재한다.

또한, 행렬

A

가 복소 대칭(

A^T=A

)인 경우에도, 실대칭 행렬과 마찬가지로 복소수를 사용하여 사칙 연산을 수행함으로써 분해

A = LDL^T

를 얻을 수 있다.

7. 6. 블록 변형

부정부호 행렬에 숄레스키 분해, 즉 '''LDL'''* 인수분해를 사용할 때는 주의 깊은 피벗팅이 없으면 불안정하다고 알려져 있다.^[19] 특히, 인수분해 요소들이 임의로 커질 수 있다. 이를 개선하기 위해 블록 부분 행렬(일반적으로 2 × 2)에 대해 인수분해를 수행할 수 있다.^[20]

다음과 같이 행렬 '''A'''를 나타낼 수 있다.

\mathbf{A} = \mathbf{LDL}^\mathrm{T} =\begin{pmatrix}\mathbf I & 0 & 0 \\\mathbf L_{21} & \mathbf I & 0 \\\mathbf L_{31} & \mathbf L_{32} & \mathbf I\\\end{pmatrix}\begin{pmatrix}\mathbf D_1 & 0 & 0 \\0 & \mathbf D_2 & 0 \\0 & 0 & \mathbf D_3\\\end{pmatrix}\begin{pmatrix}\mathbf I & \mathbf L_{21}^\mathrm T & \mathbf L_{31}^\mathrm T \\0 & \mathbf I & \mathbf L_{32}^\mathrm T \\0 & 0 & \mathbf I\\\end{pmatrix}

위 식에서 모든 요소는 정방 부분 행렬이다. 이를 통해 다음과 같은 재귀 관계를 얻을 수 있다.

\mathbf D_j = \mathbf A_{jj} - \sum_{k=1}^{j-1} \mathbf L_{jk} \mathbf D_k \mathbf L_{jk}^\mathrm T,

\mathbf L_{ij} = \left(\mathbf A_{ij} - \sum_{k=1}^{j-1} \mathbf L_{ik} \mathbf D_k \mathbf L_{jk}^\mathrm T\right) \mathbf D_j^{-1}.

이러한 계산은 행렬 곱과 명시적인 역행렬 계산을 포함하므로 실제 블록 크기가 제한된다.

7. 7. 분해 업데이트

숄레스키 분해는 행렬

\mathbf{A}

가 변경되었을 때, 업데이트된 행렬

\tilde{\mathbf{A}}

의 숄레스키 분해

\tilde{\mathbf{L}} \tilde{\mathbf{L}}^*

를 효율적으로 계산하기 위해 사용될 수 있다.

\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{x} \mathbf{x}^*

와 같이 행렬

\mathbf{A}

가 업데이트 되는 경우를 랭크-1 업데이트라고 한다.^[21] 랭크-1 업데이트를 수행하는 Matlab 코드는 다음과 같다.

```matlab

function [L] = cholupdate(L, x)

n = length(x);

for k = 1:n

r = sqrt(L(k, k)^2 + x(k)^2);

c = r / L(k, k);

s = x(k) / L(k, k);

L(k, k) = r;

if k < n

L((k+1):n, k) = (L((k+1):n, k) + s * x((k+1):n)) / c;

x((k+1):n) = c * x((k+1):n) - s * L((k+1):n, k);

end

end

end

```

\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{M} \mathbf{M}^*

와 같이 행렬

\mathbf{M}

에 대해 분해를 업데이트하는 것은 랭크-n 업데이트라고 하며,

\mathbf{M}

의 각 열에 대해 랭크-1 업데이트를 순차적으로 수행하여 구할 수 있다.

\tilde{\mathbf{A}} = \mathbf{A} - \mathbf{x} \mathbf{x}^*

와 같이 뺄셈으로 업데이트가 이루어지는 경우는 랭크-1 다운데이트라고 하며, 새로운 행렬

\tilde{\mathbf{A}}

가 여전히 양의 정부호일 경우에 적용할 수 있다. 랭크-1 업데이트 코드에서 r과 L((k+1):n, k)에 대한 할당의 두 덧셈을 뺄셈으로 바꾸면 랭크-1 다운데이트를 수행할 수 있다.

7. 8. 행과 열 추가 및 제거

대칭 양의 정부호 행렬 '''A'''가 블록 형태로 표현될 때, 기존 촐레스키 분해 '''L'''을 이용하여 새로운 행과 열이 추가된 행렬

\tilde{\mathbf{A}}

의 촐레스키 분해

\tilde{\mathbf{S}}

를 계산할 수 있다.

\mathbf{A} =\begin{pmatrix}\mathbf A_{11} & \mathbf A_{13} \\\mathbf A_{13}^{\mathrm{T}} & \mathbf A_{33} \\\end{pmatrix}

\mathbf{L} =\begin{pmatrix}\mathbf L_{11} &  \mathbf L_{13} \\0      & \mathbf L_{33} \\\end{pmatrix},

\begin{align}\tilde{\mathbf{A}} &=\begin{pmatrix}\mathbf A_{11} & \mathbf A_{12} & \mathbf A_{13} \\\mathbf A_{12}^{\mathrm{T}} & \mathbf A_{22} & \mathbf A_{23} \\\mathbf A_{13}^{\mathrm{T}} & \mathbf A_{23}^{\mathrm{T}} &  \mathbf A_{33} \\\end{pmatrix}\end{align}

\begin{align}\tilde{\mathbf{S}} &=\begin{pmatrix}\mathbf S_{11} & \mathbf S_{12} & \mathbf S_{13} \\0 & \mathbf S_{22} & \mathbf S_{23} \\0 & 0 &  \mathbf S_{33} \\\end{pmatrix}.\end{align}

삼각 행렬에서 쉽게 찾을 수 있는

\mathbf A \mathbf x = \mathbf b

의 해를

\mathbf A \setminus \mathbf{b}

로 표기하고,

\mathbf M

의 촐레스키 분해를

\text{chol} (\mathbf M)

으로 표기하면, 다음과 같은 관계를 통해

\tilde{\mathbf{S}}

를 구할 수 있다.^[22]

\begin{align}\mathbf S_{11} &= \mathbf L_{11}, \\\mathbf S_{12} &= \mathbf L_{11}^{\mathrm{T}} \setminus \mathbf A_{12}, \\\mathbf S_{13} &= \mathbf L_{13}, \\\mathbf S_{22} &= \mathrm{chol} \left(\mathbf A_{22}  - \mathbf S_{12}^{\mathrm{T}} \mathbf S_{12}\right), \\\mathbf S_{23} &= \mathbf S_{22}^{\mathrm{T}} \setminus \left(\mathbf A_{23} - \mathbf S_{12}^{\mathrm{T}} \mathbf S_{13}\right), \\\mathbf S_{33} &= \mathrm{chol} \left(\mathbf L_{33}^{\mathrm{T}} \mathbf L_{33} - \mathbf S_{23}^{\mathrm{T}} \mathbf S_{23}\right).\end{align}

반대로, 행과 열이 제거된 행렬 '''A'''의 촐레스키 인수 '''L'''은 다음과 같이 계산할 수 있다.^[22]

\begin{align}\mathbf L_{11} &= \mathbf S_{11}, \\\mathbf L_{13} &= \mathbf S_{13}, \\\mathbf L_{33} &= \mathrm{chol} \left(\mathbf S_{33}^{\mathrm{T}} \mathbf S_{33} + \mathbf S_{23}^{\mathrm{T}} \mathbf S_{23}\right).\end{align}

8. 양의 준정부호 행렬에 대한 증명

양의 준정부호 행렬 $\mathbf{A}$ 가 주어졌을 때, 수열 $\left(\mathbf{A}_k\right)_k := \left(\mathbf{A} + \frac{1}{k} \mathbf{I}_n\right)_k$ 는 양의 정부호 행렬로 구성된다. 이는 다항식 함수 미적분에 대한 스펙트럼 사상 정리에 의해 바로 얻을 수 있다. 또한, 작용소 노름에서 $\mathbf{A}_k \rightarrow \mathbf{A}$ ( $k \rightarrow \infty$ ) 가 성립한다.

양의 정부호 행렬의 경우에서 각 $\mathbf{A}_k$ 는 촐레스키 분해 $\mathbf{A}_k = \mathbf{L}_k\mathbf{L}_k^*$ 를 갖는다. 작용소 노름의 성질에 의해, $\| \mathbf{L}_k \|^2 \leq \| \mathbf{L}_k \mathbf{L}_k^* \| = \| \mathbf{A}_k \|$ 가 성립한다. 여기서 $\leq$ 는 작용소 노름을 갖춘 $M_n(\mathbb{C})$ 가 C* 대수이기 때문에 성립한다. 따라서 $\left(\mathbf{L}_k \right)_k$ 는 작용소의 바나흐 공간에서 유계 집합이므로 상대적으로 콤팩트하다 (기저 벡터 공간이 유한 차원이기 때문). 결과적으로, $\mathbf{L}$ 을 극한으로 갖는 수렴하는 부분 수열이 존재하며, 이를 $\left( \mathbf{L}_k \right)_k$ 로 표기한다.

모든 $x$ 와 $y$ 에 대해, $\langle \mathbf{A} x, y \rangle = \left\langle \lim \mathbf{A}_k x, y \right\rangle = \langle \lim \mathbf{L}_k \mathbf{L}_k^* x, y \rangle = \langle \mathbf{L} \mathbf{L}^*x, y \rangle$ 이므로, $\mathbf{A} = \mathbf{L}\mathbf{L}^*$ 이다. 기저 벡터 공간이 유한 차원이기 때문에 작용소 공간의 모든 위상은 동등하므로, $\left( \mathbf{L}_k \right)_k$ 가 노름에서 $\mathbf{L}$ 로 수렴한다는 것은 성분별로도 수렴한다는 것을 의미한다. 각 $\mathbf{L}_k$ 가 음이 아닌 대각 성분을 갖는 하삼각 행렬이기 때문에, $\mathbf{L}$ 또한 그러하다.

양의 반정부호 에르미트 행렬 $\mathbf{A}$ 는 제곱근 행렬의 곱 $\mathbf{A} = \mathbf{B} \mathbf{B}^*$ 로 나타낼 수 있다. QR 분해를 $\mathbf{B}^*$ 에 적용하면 $\mathbf{B}^* = \mathbf{Q}\mathbf{R}$ ( $\mathbf{Q}$ 는 유니타리 행렬, $\mathbf{R}$ 은 상삼각 행렬)을 얻는다. 이를 원래 등식에 대입하면 $A = \mathbf{B} \mathbf{B}^* = (\mathbf{QR})^*\mathbf{QR} = \mathbf{R}^*\mathbf{Q}^*\mathbf{QR} = \mathbf{R}^*\mathbf{R}$ 이 된다. $\mathbf{L} = \mathbf{R}^*$ 로 놓으면 증명이 완료된다.

9. 일반화

숄레스키 분해는 연산자 항목을 가진 행렬로 일반화될 수 있다. 힐베르트 공간/Hilbert space^영어의 수열 $\{\mathcal{H}_n \}$ 에 대해, 직합 $\mathcal{H} = \bigoplus_n \mathcal{H}_n$ 에 작용하는 연산자 행렬

$\mathbf{A} =\begin{bmatrix}\mathbf{A}_{11} & \mathbf{A}_{12} & \mathbf{A}_{13} & \; \\\mathbf{A}_{12}^* & \mathbf{A}_{22} & \mathbf{A}_{23} & \; \\\mathbf{A} _{13}^* & \mathbf{A}_{23}^* & \mathbf{A}_{33} & \; \\\; & \; & \; & \ddots\end{bmatrix}$

를 고려한다. 여기서 각

$\mathbf{A}_{ij} : \mathcal{H}_j \rightarrow \mathcal{H} _i$

는 유계 연산자이다. 만약 가 모든 유한 와 임의의

$h \in \bigoplus_{n = 1}^k \mathcal{H}_k ,$

에 대해 $\langle h, \mathbf{A} h\rangle \ge 0$ 을 만족하는 의미에서 양의 정부호(반정부호)이면, 하삼각 연산자 행렬 가 존재하여 }}. 또한 의 대각 항목을 양수로 취할 수 있다.

10. 프로그래밍 라이브러리 구현

C 프로그래밍 언어에서는 GNU 과학 라이브러리가 숄레스키 분해의 여러 구현을 제공한다. 맥시마 컴퓨터 대수 시스템의 함수 `cholesky`는 숄레스키 분해를 계산한다. GNU 옥타브 수치 계산 시스템은 숄레스키 분해를 계산, 업데이트 및 적용하는 여러 함수를 제공한다. LAPACK 라이브러리는 포트란, C 및 대부분의 언어에서 액세스할 수 있는 고성능 숄레스키 분해 구현을 제공한다.

파이썬에서는 `numpy.linalg` 모듈의 함수 `cholesky`가 숄레스키 분해를 수행한다. 매트랩에서 `chol` 함수는 숄레스키 분해를 제공하며, 기본적으로 입력 행렬의 상 삼각 인수를 사용하여 $A = R^* R$ 을 계산한다. 여기서 $R$ 은 상 삼각 행렬이다. 하 삼각 인수를 대신 사용하기 위해 플래그를 전달할 수 있다. R에서 `chol` 함수는 숄레스키 분해를 제공한다. 줄리아에서는 `LinearAlgebra` 표준 라이브러리의 `cholesky` 함수가 숄레스키 분해를 제공한다. 매스매티카에서는 "''CholeskyDecomposition''" 함수를 행렬에 적용할 수 있다.

C++에서는, Armadillo (C++ 라이브러리)의 `chol` 명령, Eigen 라이브러리, ROOT 패키지의 `TDecompChol` 클래스 등 여러 선형 대수 라이브러리가 이 분해를 지원한다. Analytica에서 `Decompose` 함수는 숄레스키 분해를 제공한다. [https://commons.apache.org/proper/commons-math/commons-math-docs/apidocs/org/apache/commons/math4/legacy/linear/CholeskyDecomposition.html Apache Commons Math 라이브러리]는 Java, Scala 및 기타 모든 JVM 언어에서 사용할 수 있는 구현을 가지고 있다.

LAPACK(LAPACK)은 밀집 선형 대수 문제를 해결하기 위한 FORTRAN 서브루틴 모음이다. ALGLIB(ALGLIB)는 LAPACK의 일부를 C++, C#, Delphi, Visual Basic 등으로 이식한 것을 포함한다. libflame(libflame)은 LAPACK 기능을 갖춘 C 라이브러리이다. 텍사스 대학교 오스틴에서 [http://www.cs.utexas.edu/users/flame/Movies.html#Chol 촐레스키 분해의 고성능 구현에 대한 노트 및 비디오]를 제공한다. [http://upcommons.upc.edu/pfc/handle/2099.1/10988/ 촐레스키: TBB + Threads + SSE]는 TBB, 스레드 및 SSE를 사용하여 CF의 구현을 설명하는 책이다(스페인어). 구글에서 제공하는 라이브러리 "Ceres Solver"에서도 숄레스키 분해를 지원한다. Matlab의 [https://web.archive.org/web/20120807190828/http://infohost.nmt.edu/~borchers/ldlt.html LDL 분해] 루틴도 참고할 수 있다. Armadillo(Armadillo)는 C++ 선형 대수 패키지이다. Rosetta Code(Rosetta Code)는 프로그래밍 개요 사이트이며, [https://rosettacode.org/wiki/Cholesky_decomposition 숄레스키 분해 페이지]를 제공한다. AlgoWiki(AlgoWiki)는 알고리즘 속성 및 구현 기능에 대한 열린 백과사전이며, [https://algowiki-project.org/en/Cholesky_decomposition 숄레스키 분해 페이지]를 제공한다. 인텔® oneAPI 수학 커널 라이브러리(Intel® oneAPI Math Kernel Library)는 수치 계산을 위한 인텔 최적화 수학 라이브러리이다.

11. 불완전 숄레스키 분해

불완전 숄레스키 분해는 계수가 대칭 행렬인 연립 1차 방정식을 풀 때 사용되는 기법이다. 이는 수정 숄레스키 분해에서 행렬 A를 A = LDL^* 로 분해하는 대신, 다음과 같이 분해 잔차 행렬 N을 도입하여 분해한다.

: A = LDL^* + N이 방법은 분해 과정 및 전진, 후퇴 대입의 계산량을 줄이고, 행렬 L의 비영 요소 저장에 필요한 메모리 양을 줄이기 위해, 행렬 L의 비영 요소 수를 억제한다. 불완전 숄레스키 분해는 켤레 기울기법과 같은 반복법을 이용한 연립 1차 방정식 해법에서 전처리 기법 중 하나로 활용된다.

참조

_[1] 간행물 Note sur une méthode de résolution des équations normales provenant de l'application de la méthode des moindres carrés à un système d'équations linéaires en nombre inférieur à celui des inconnues (Procédé du Commandant Cholesky) 1924
_[2] 서적 Numerical Recipes in C: The Art of Scientific Computing https://archive.org/[...] Cambridge University England EPress 2009-01-28
_[3] 문서 Golub, Van Loan, 1996, p=143, Horn, Johnson, 1985, p=407, Trefethen, Bau, 1997, p=174
_[4] 문서 Horn, Johnson, 1985, p=407
_[5] 웹사이트 matrices - Diagonalizing a Complex Symmetric Matrix https://mathoverflow[...] 2020-01-25
_[6] 간행물 Toward a parallel solver for generalized complex symmetric eigenvalue problems 2010-05-01
_[7] 문서 Golub, Van Loan, 1996, p=147
_[8] 서적 Numerical Linear Algebra for Applications in Statistics Springer 1998
_[9] 서적 Reliable Numerical Computation Oxford University Press
_[10] 간행물 Matrix Inversion Using Cholesky Decomposition
_[11] PhD A Semidefinite Programming Approach to the Graph Realization Problem: Theory, Applications and Extensions http://www.se.cuhk.e[...] 2007
_[12] 문서 Golub, Van Loan, 1996, loc=Theorem 4.1.3
_[13] 문서 Algorithms for ellipsoids. https://tcg.mae.corn[...] Cornell University Report No. FDA (2008): 08-01
_[14] 서적 Introduction to Optimum Design https://books.google[...] Elsevier 2004-06-02
_[15] 문서 Matlab randn documentation http://www.mathworks[...] mathworks.com
_[16] 문서 ?potrf Intel® Math Kernel Library https://software.int[...]
_[17] 간행물 Modified Cholesky Algorithms: A Catalog with New Approaches http://www.cs.umd.ed[...] 2006-08-08
_[18] 서적 Fundamentals of Matrix Computations https://archive.org/[...] Wiley
_[19] 서적 Numerical Optimization Springer
_[20] 간행물 Analysis of Block LDLT Factorizations for Symmetric Indefinite Matrices 2007-08-24
_[21] 서적 Basic decompositions Soc. for Industrial and Applied Mathematics
_[22] 문서 Osborne, M. (2010), Appendix B
_[23] 서적 https://archive.org/[...] 2009-01-28

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com