선형 시스템 해법으로서의 LU 분해

LU 분해는 선형 시스템을 효율적으로 해결하는 데 매우 유용한 도구이다. 이 절에서는 LU 분해를 사용하여 선형 시스템을 해결하는 방법에 대해 자세히 설명하겠다. 이를 이해하기 위해 우선적으로 선형 시스템의 기본 구조를 이해하는 것이 중요하다.

선형 시스템의 정의

선형 시스템은 다음과 같은 형태로 주어진다:

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

여기서: - $\mathbf{A}$ 는 $n \times n$ 크기의 계수 행렬(matrix)이다. - $\mathbf{x}$ 는 $n \times 1$ 크기의 미지수 벡터(vector)이다. - $\mathbf{b}$ 는 $n \times 1$ 크기의 결과 벡터이다.

이 시스템의 목적은 미지수 벡터 $\mathbf{x}$ 를 구하는 것이다.

LU 분해의 기본 개념

LU 분해는 행렬 $\mathbf{A}$ 를 두 개의 행렬, 즉 하나의 하삼각 행렬(lower triangular matrix) $\mathbf{L}$ 과 하나의 상삼각 행렬(upper triangular matrix) $\mathbf{U}$ 로 분해하는 방법이다. 이 방법은 다음과 같이 표현된다:

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

여기서: - $\mathbf{L}$ 은 대각선 상의 모든 성분이 1인 $n \times n$ 하삼각 행렬이다. - $\mathbf{U}$ 는 상삼각 행렬로, 대각선 상의 성분들이 0이 아니다.

이 분해를 통해, 선형 시스템 $\mathbf{A} \mathbf{x} = \mathbf{b}$ 는 다음과 같은 두 단계로 해결될 수 있다:

전방 대치 (Forward Substitution): $\mathbf{L}$ 과 $\mathbf{b}$ 를 사용하여 중간 벡터 $\mathbf{y}$ 를 구함.
후방 대치 (Backward Substitution): $\mathbf{U}$ 와 $\mathbf{y}$ 를 사용하여 최종 해 $\mathbf{x}$ 를 구함.

전방 대치 (Forward Substitution)

우선, $\mathbf{L}\mathbf{U}\mathbf{x} = \mathbf{b}$ 를 $\mathbf{L}\mathbf{y} = \mathbf{b}$ 로 분해한다. 여기서 $\mathbf{y}$ 는 중간 벡터로, $\mathbf{U}\mathbf{x} = \mathbf{y}$ 를 만족한다.

전방 대치 과정을 통해 $\mathbf{y}$ 를 다음과 같이 구할 수 있다:

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

이 과정은 하삼각 행렬 $\mathbf{L}$ 의 특성을 활용하여 $y_1, y_2, \ldots, y_n$ 을 순차적으로 구하는 방법이다. 이때, $i$ 번째 방정식은 다음과 같이 표현된다:

$y_i = b_i - \sum_{j=1}^{i-1} L_{ij} y_j \quad \text{for} \quad i = 1, 2, \ldots, n$

여기서 $L_{ij}$ 는 행렬 $\mathbf{L}$ 의 요소를 나타낸다.

후방 대치 (Backward Substitution)

이제 상삼각 행렬 $\mathbf{U}$ 와 중간 벡터 $\mathbf{y}$ 를 사용하여 $\mathbf{x}$ 를 구할 차례이다. 후방 대치 과정은 다음과 같이 이루어진다:

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

이 과정은 상삼각 행렬 $\mathbf{U}$ 의 특성을 활용하여 $x_n, x_{n-1}, \ldots, x_1$ 을 역순으로 구하는 방법이다. 이때, $i$ 번째 방정식은 다음과 같이 표현된다:

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

여기서 $U_{ij}$ 는 행렬 $\mathbf{U}$ 의 요소를 나타낸다.

LU 분해의 장점

LU 분해를 통해 선형 시스템을 해결하는 주요 장점은 다음과 같다:

효율성: $\mathbf{A}$ 가 여러 개의 다른 $\mathbf{b}$ 벡터에 대해 사용될 때, LU 분해를 한 번만 수행하고 각 $\mathbf{b}$ 에 대해 전방 대치와 후방 대치만 수행하면 된다. 이는 전체 계산 비용을 크게 절감한다.
재사용 가능성: 만약 행렬 $\mathbf{A}$ 가 변하지 않고, 다른 $\mathbf{b}$ 벡터들에 대해 해를 구해야 한다면, $\mathbf{L}$ 과 $\mathbf{U}$ 의 분해 결과를 여러 번 사용할 수 있다.
수치적 안정성: Pivoting을 포함한 LU 분해는 수치적으로 안정된 방식으로 선형 시스템을 해결할 수 있는 방법을 제공한다. 이는 고정 소수점 계산이나 큰 규모의 문제를 해결할 때 특히 중요하다.

LU 분해를 사용한 선형 시스템의 해법 과정 요약

LU 분해를 이용한 선형 시스템의 해법 과정을 요약하면 다음과 같다:

LU 분해: 행렬 $\mathbf{A}$ 를 하삼각 행렬 $\mathbf{L}$ 과 상삼각 행렬 $\mathbf{U}$ 로 분해한다.

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

전방 대치: $\mathbf{L}\mathbf{y} = \mathbf{b}$ 에서 중간 벡터 $\mathbf{y}$ 를 구한다.

$y_i = b_i - \sum_{j=1}^{i-1} L_{ij} y_j \quad \text{for} \quad i = 1, 2, \ldots, n$

후방 대치: $\mathbf{U}\mathbf{x} = \mathbf{y}$ 에서 최종 해 $\mathbf{x}$ 를 구한다.

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

LU 분해를 사용하지 않는 경우의 문제점

LU 분해를 사용하지 않고 선형 시스템을 직접 해결하려고 할 때, 예를 들어 역행렬을 계산하여 해를 구하는 방법은 실질적으로 비효율적이며 수치적으로 불안정할 수 있다. 행렬의 크기가 커질수록 이러한 문제는 더욱 심각해지며, 계산 복잡도가 매우 증가하게 된다.

대안적으로, 가우스 소거법을 사용할 수 있지만, 이 경우에도 Pivoting이 없는 경우 수치적 불안정성을 야기할 수 있다. 반면 LU 분해는 이러한 문제들을 체계적으로 해결해 준다.

LU 분해의 예제

LU 분해를 통한 선형 시스템 해결 방법을 예를 들어 살펴보겠다. 다음과 같은 간단한 시스템을 고려해 봅시다:

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

LU 분해: $\mathbf{A}$ 를 $\mathbf{L}$ 과 $\mathbf{U}$ 로 분해한다.

$\mathbf{L} = \begin{pmatrix} 1 & 0 \\ 0.5 & 1 \end{pmatrix}, \quad \mathbf{U} = \begin{pmatrix} 2 & 3 \\ 0 & 2.5 \end{pmatrix}$

전방 대치: $\mathbf{L}\mathbf{y} = \mathbf{b}$ 에서 $\mathbf{y}$ 를 구한다.

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

후방 대치: $\mathbf{U}\mathbf{x} = \mathbf{y}$ 에서 $\mathbf{x}$ 를 구한다.

$\mathbf{x} = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$

따라서, 최종 해는 $\mathbf{x} = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$ 이다.

LU 분해의 제한점

LU 분해는 선형 시스템 해법으로 매우 유용하지만, 일부 제한점도 존재한다. 예를 들어, 행렬이 특이(singular)하거나 조건 수가 매우 클 경우 LU 분해는 제대로 작동하지 않을 수 있다. 이러한 상황에서는 다른 수치적 방법을 고려해야 한다.