연립 방정식의 해법 - 실험 도서관

LU 분해는 연립 방정식의 해법에 매우 유용한 도구이다. 일반적인 선형 시스템은 다음과 같은 형태를 갖는다:

$\mathbf{A} \mathbf{x} = \mathbf{b}$

여기서, - $\mathbf{A}$ 는 $n \times n$ 크기의 계수 행렬, - $\mathbf{x}$ 는 $n \times 1$ 크기의 미지수 벡터, - $\mathbf{b}$ 는 $n \times 1$ 크기의 상수 벡터이다.

LU 분해는 행렬 $\mathbf{A}$ 를 두 개의 행렬로 분해하는 방법이다:

$\mathbf{A} = \mathbf{L} \mathbf{U}$

여기서, - $\mathbf{L}$ 은 하삼각 행렬(lower triangular matrix), - $\mathbf{U}$ 는 상삼각 행렬(upper triangular matrix)이다.

이 분해를 이용하여, 연립 방정식 $\mathbf{A} \mathbf{x} = \mathbf{b}$ 는 다음과 같이 두 단계로 풀 수 있다:

$\mathbf{L} \mathbf{U} \mathbf{x} = \mathbf{b}$

이를 두 단계로 나누면: 1. Forward Substitution: 먼저, 중간 변수 $\mathbf{y}$ 를 정의하여 다음과 같은 방정식을 푼다.

$\mathbf{L} \mathbf{y} = \mathbf{b}$

Backward Substitution: 그런 다음, $\mathbf{y}$ 를 이용해 다음 방정식을 푼다.

$\mathbf{U} \mathbf{x} = \mathbf{y}$

이제 각각의 단계에 대해 더 자세히 알아보겠다.

Forward Substitution

Forward substitution은 하삼각 행렬 $\mathbf{L}$ 에 대한 연립 방정식을 푸는 과정이다. $\mathbf{L}$ 은 하삼각 행렬이므로, $\mathbf{L}$ 의 각 원소는 다음과 같은 특성을 갖는다:

$l_{ij} = 0 \quad \text{for } i < j$

따라서, $\mathbf{L} \mathbf{y} = \mathbf{b}$ 를 풀기 위한 절차는 다음과 같다:

$\mathbf{L}$ 의 첫 번째 행에서 첫 번째 미지수 $y_1$ 를 계산한다:

$y_1 = \frac{b_1}{l_{11}}$

두 번째 행에서는 $y_2$ 를 계산한다:

$y_2 = \frac{b_2 - l_{21} y_1}{l_{22}}$

이 과정을 계속하여, $n$ 번째 행에서 $y_n$ 를 계산한다:

$y_n = \frac{b_n - \sum_{j=1}^{n-1} l_{nj} y_j}{l_{nn}}$

이 과정은 하삼각 행렬의 성질을 이용하여 순차적으로 해를 구하는 방식이다.

Backward Substitution

Backward substitution은 상삼각 행렬 $\mathbf{U}$ 에 대한 연립 방정식을 푸는 과정이다. $\mathbf{U}$ 는 상삼각 행렬이므로, $\mathbf{U}$ 의 각 원소는 다음과 같은 특성을 갖는다:

$u_{ij} = 0 \quad \text{for } i > j$

따라서, $\mathbf{U} \mathbf{x} = \mathbf{y}$ 를 풀기 위한 절차는 다음과 같다:

$\mathbf{U}$ 의 마지막 행에서 $x_n$ 을 계산한다:

$x_n = \frac{y_n}{u_{nn}}$

그 이전의 행에서는 $x_{n-1}$ 을 계산한다:

$x_{n-1} = \frac{y_{n-1} - u_{n-1,n} x_n}{u_{n-1,n-1}}$

이 과정을 거꾸로 진행하여, 첫 번째 미지수 $x_1$ 까지 구한다:

$x_1 = \frac{y_1 - \sum_{j=2}^{n} u_{1j} x_j}{u_{11}}$

이 과정은 상삼각 행렬의 성질을 이용하여 순차적으로 해를 구하는 방식이다.

LU 분해의 예제

LU 분해를 활용하여 연립 방정식을 푸는 과정을 실제 예제를 통해 살펴보겠다. 다음과 같은 선형 시스템이 있다고 가정한다:

$\begin{pmatrix} 2 & 3 & 1 \\ 4 & 7 & 2 \\ 6 & 18 & 5 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 5 \\ 10 \\ 20 \end{pmatrix}$

이 시스템에서 행렬 $\mathbf{A}$ 를 LU 분해하면 다음과 같이 된다:

$\mathbf{A} = \mathbf{L} \mathbf{U} = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 3 & 1 \end{pmatrix} \begin{pmatrix} 2 & 3 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$

이제, 첫 번째 단계로 Forward Substitution을 사용하여 $\mathbf{L} \mathbf{y} = \mathbf{b}$ 를 푼다:

$\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 3 & 1 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix} = \begin{pmatrix} 5 \\ 10 \\ 20 \end{pmatrix}$

이 시스템을 풀면:

$y_1 = 5$

$y_2 = 10 - 2 \times 5 = 0$

$y_3 = 20 - 3 \times 0 - 3 \times 5 = 5$

따라서, 중간 변수 $\mathbf{y}$ 는 다음과 같다:

$\mathbf{y} = \begin{pmatrix} 5 \\ 0 \\ 5 \end{pmatrix}$

다음으로, Backward Substitution을 사용하여 $\mathbf{U} \mathbf{x} = \mathbf{y}$ 를 푼다:

$\begin{pmatrix} 2 & 3 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 5 \\ 0 \\ 5 \end{pmatrix}$

이 시스템을 풀면:

$x_3 = 5$

$x_2 = 0$

$x_1 = \frac{5 - 3 \times 0 - 1 \times 5}{2} = 0$

따라서, 최종 해는 다음과 같다:

$\mathbf{x} = \begin{pmatrix} 0 \\ 0 \\ 5 \end{pmatrix}$

LU 분해의 효율성

LU 분해는 연립 방정식을 푸는 데 있어 매우 효율적이다. 특히, 여러 개의 연립 방정식을 동일한 계수 행렬 $\mathbf{A}$ 로 풀어야 할 때 유용하다. 행렬 $\mathbf{A}$ 의 LU 분해는 한 번만 수행하면 되고, 이후 각 다른 상수 벡터 $\mathbf{b}$ 에 대해 Forward Substitution과 Backward Substitution을 수행하여 해를 구할 수 있기 때문이다.

LU 분해는 일반적으로 시간 복잡도 $O(n^3)$ 의 연산이 필요하지만, 각 연립 방정식의 해를 구하는 데 필요한 Forward Substitution과 Backward Substitution은 $O(n^2)$ 의 연산만을 필요로 한다. 따라서, 행렬 $\mathbf{A}$ 가 고정된 경우 여러 개의 $\mathbf{b}$ 에 대해 연립 방정식을 풀 때 매우 효율적이다.

특별한 경우의 LU 분해

LU 분해는 모든 행렬에 대해 항상 존재하는 것은 아니다. 행렬이 특이 행렬(singular matrix)인 경우 LU 분해가 존재하지 않을 수 있다. 또한, 행렬이 충분히 "좋은" 성질을 갖지 못할 경우, LU 분해가 매우 불안정해질 수 있다. 이런 경우, 행렬을 적절히 변형하거나, Pivoting 기법을 사용하여 LU 분해를 수행하는 것이 필요하다.

LU 분해를 활용한 연립 방정식의 해법은 선형 대수학에서 매우 중요한 방법 중 하나이다. 이 방법은 연립 방정식의 해를 구하는 효율적이고 안정적인 방법을 제공하며, 특히 여러 개의 연립 방정식을 반복해서 풀어야 하는 상황에서 유용하다.