Sholesky 분해 알고리즘 - 실험 도서관

알고리즘의 단계별 설명

Sholesky 분해 알고리즘은 주어진 양의 정부호 행렬 $\mathbf{A}$ 를 하삼각행렬 $\mathbf{L}$ 과 그의 전치행렬 $\mathbf{L}^T$ 의 곱으로 분해하는 방법이다. 수학적으로, $\mathbf{A} = \mathbf{L} \mathbf{L}^T$ 로 표현된다. 이 알고리즘을 단계별로 설명하겠다.

단계 1: 행렬 초기화

먼저 분해하고자 하는 행렬 $\mathbf{A}$ 를 $n \times n$ 행렬로 정의한다. Sholesky 분해는 대칭행렬의 특성을 이용하므로 $\mathbf{A}$ 는 반드시 대칭이어야 한다.

$\mathbf{A} = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{12} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1n} & a_{2n} & \cdots & a_{nn} \end{pmatrix}$

단계 2: 하삼각행렬 $\mathbf{L}$ 초기화

하삼각행렬 $\mathbf{L}$ 의 모든 원소를 0으로 초기화한다.

$\mathbf{L} = \begin{pmatrix} l_{11} & 0 & \cdots & 0 \\ l_{21} & l_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{n1} & l_{n2} & \cdots & l_{nn} \end{pmatrix}$

단계 3: 대각선 원소 계산

대각선 원소 $l_{ii}$ 는 다음과 같이 계산된다.

$l_{ii} = \sqrt{ a_{ii} - \sum_{k=1}^{i-1} l_{ik}^2 }$

예를 들어, 첫 번째 대각선 원소 $l_{11}$ 는 다음과 같이 계산된다.

$l_{11} = \sqrt{ a_{11} }$

단계 4: 비대각선 원소 계산

대각선 아래의 원소 $l_{ij}$ ( $i > j$ )는 다음과 같이 계산된다.

$l_{ij} = \frac{1}{l_{jj}} \left( a_{ij} - \sum_{k=1}^{j-1} l_{ik} l_{jk} \right)$

예를 들어, $l_{21}$ 는 다음과 같이 계산된다.

$l_{21} = \frac{1}{l_{11}} \left( a_{21} \right)$

단계 5: 과정을 반복하여 $\mathbf{L}$ 완성

알고리즘은 i=1부터 n까지 반복해서 $\mathbf{L}$ 의 모든 원소를 계산한다. 대각선 원소와 비대각선 원소를 차례로 계산하여 $\mathbf{L}$ 행렬을 완성한다.

이를 요약하면, 전체 알고리즘은 다음과 같은 반복 형태로 이루어진다.

for i in range(n):
    for j in range(i+1):
        if i == j:
            L[i][i] = sqrt(A[i][i] - sum(L[i][k]**2 for k in range(i)))
        else:
            L[i][j] = (A[i][j] - sum(L[i][k] * L[j][k] for k in range(j))) / L[j][j]

단계 6: $\mathbf{L}$ 의 검증

최종적으로, 분해된 하삼각행렬 $\mathbf{L}$ 을 이용해 $\mathbf{L} \mathbf{L}^T$ 를 구하고, 이를 원래의 행렬 $\mathbf{A}$ 와 비교하여 정확성을 검증할 수 있다.

$\mathbf{A} \approx \mathbf{L} \mathbf{L}^T$