선형 방정식 풀이 - 실험 도서관

칠레스키 분해(Cholesky Decomposition)는 주로 양의 정부호 행렬에 대해 특화된 계산 기법으로, 선형 방정식 시스템의 해를 구하는 데 효율적으로 사용될 수 있다. 아래에서는 칠레스키 분해를 이용해 선형 방정식을 푸는 방법을 단계별로 자세히 설명하겠다.

문제 정의

우리는 다음과 같은 선형 방정식 시스템을 고려한다:

$\mathbf{Ax} = \mathbf{b}$

여기서: - $\mathbf{A}$ 는 $n \times n$ 크기의 양의 정부호 행렬이다. - $\mathbf{x}$ 는 $n$ 차원의 미지수 벡터이다. - $\mathbf{b}$ 는 $n$ 차원의 상수 벡터이다.

칠레스키 분해

먼저, 행렬 $\mathbf{A}$ 를 칠레스키 분해한다. 즉, 이렇게 쓸 수 있다:

$\mathbf{A} = \mathbf{LL}^T$

여기서: - $\mathbf{L}$ 은 하삼각 행렬(lower triangular matrix)이다. - $\mathbf{L}^T$ 는 $\mathbf{L}$ 의 전치 행렬(transpose)이다.

분해를 이용한 풀이

칠레스키 분해를 얻은 후, 다음 단계를 따른다:

전진 대입(forward substitution): 행렬 방정식 $\mathbf{Ly} = \mathbf{b}$ 를 푼다.
후진 대입(backward substitution): 행렬 방정식 $\mathbf{L}^T \mathbf{x} = \mathbf{y}$ 를 푼다.

전진 대입 (Forward Substitution)

먼저, $\mathbf{Ly} = \mathbf{b}$ 를 풀기 위해 $\mathbf{y}$ 를 구해야 한다. 이 과정은 하삼각 행렬 $\mathbf{L}$ 의 특성상 순차적으로 각 원소를 구할 수 있다:

$y_i = \frac{1}{L_{ii}} \left( b_i - \sum_{j=1}^{i-1} L_{ij} y_j \right) \quad \text{for} \quad i = 1, 2, \ldots, n$

후진 대입 (Backward Substitution)

그 다음, $\mathbf{L}^T \mathbf{x} = \mathbf{y}$ 를 풀기 위해 $\mathbf{x}$ 를 구해야 한다. 이 과정은 상삼각 행렬 $\mathbf{L}^T$ 의 특성상 순차적으로 각 원소를 구할 수 있다:

$x_i = \frac{1}{L_{ii}} \left( y_i - \sum_{j=i+1}^{n} L_{ji} x_j \right) \quad \text{for} \quad i = n, n-1, \ldots, 1$

알고리즘 예시

다음은 칠레스키 분해를 이용한 선형 방정식 풀이의 전체 알고리즘을 요약한 것이다:

import numpy as np

def cholesky_solve(A, b):
    n = A.shape[0]

    # Step 1: Cholesky decomposition
    L = np.linalg.cholesky(A)

    # Step 2: Forward substitution to solve Ly = b
    y = np.zeros(n)
    for i in range(n):
        y[i] = (b[i] - np.dot(L[i, :i], y[:i])) / L[i, i]

    # Step 3: Backward substitution to solve L^T x = y
    x = np.zeros(n)
    for i in range(n-1, -1, -1):
        x[i] = (y[i] - np.dot(L.T[i, i+1:], x[i+1:])) / L.T[i, i]

    return x

A = np.array([[4, 1], [1, 3]], dtype=np.float64)
b = np.array([1, 2], dtype=np.float64)
x = cholesky_solve(A, b)
print(x)  # Output: [0.09090909 0.63636364]

위 코드에서는 칠레스키 분해를 통해 선형 방정식 시스템을 푸는 과정을 세 단계에 걸쳐 구현하였다.

예제와 설명

칠레스키 분해의 원리를 이해하기 위해 실제 예제를 함께 살펴보자.

예제 문제

다음과 같은 행렬 $\mathbf{A}$ 와 벡터 $\mathbf{b}$ 를 고려하자:

$\mathbf{A} = \begin{pmatrix} 4 & 1 \\ 1 & 3 \end{pmatrix}, \quad \mathbf{b} = \begin{pmatrix} 1 \\ 2 \end{pmatrix}$

칠레스키 분해 단계

행렬 $\mathbf{A}$ 의 칠레스키 분해
행렬 $\mathbf{A}$ 는 양의 정부호 행렬이므로 칠레스키 분해를 통해 다음과 같은 하삼각 행렬 $\mathbf{L}$ 을 찾을 수 있다:

$\mathbf{L} = \begin{pmatrix} 2 & 0 \\ 0.5 & \sqrt{2.75} \end{pmatrix}$

여기서 $\mathbf{L}$ 은 $\mathbf{A}$ 를 다음과 같이 분해할 수 있게 해준다:

$\mathbf{A} = \mathbf{LL}^T$

전진 대입 $\mathbf{Ly} = \mathbf{b}$ 풀기
하삼각 행렬을 이용해 다음과 같은 시스템을 풀자:

$\begin{pmatrix} 2 & 0 \\ 0.5 & \sqrt{2.75} \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \end{pmatrix}$

이를 순차적으로 풀어서:

$y_1 = \frac{1}{2} = 0.5$

$y_2 = \frac{2 - (0.5 \times 0.5)}{\sqrt{2.75}} = 1.22474$

후진 대입 $\mathbf{L}^T \mathbf{x} = \mathbf{y}$ 풀기
상삼각 행렬 $\mathbf{L}^T$ 를 이용해 다음과 같은 시스템을 풀자:

$\begin{pmatrix} 2 & 0.5 \\ 0 & \sqrt{2.75} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} y_1 \\ y_2 \end{pmatrix}$

이를 순차적으로 풀어서:

$x_2 = \frac{y_2}{\sqrt{2.75}} = 0.736$

$x_1 = \frac{y_1 - (0.5 \times x_2)}{2} = 0.0909$

결국 해는 다음과 같다:

$\mathbf{x} = \begin{pmatrix} 0.0909 \\ 0.736 \end{pmatrix}$

칠레스키 분해를 통해 우리는 선형 방정식 시스템을 더 효율적으로 풀 수 있으며, 이는 특히 양의 정부호 행렬에 대해 유용하다. 이 방법은 계산 속도와 정확성을 향상시키고 대규모 행렬에 대해 효율적으로 작동한다.