Forward Substitution은 선형 시스템을 해결하기 위한 수치 해법 중 하나로, 특히 하삼각 행렬(𝑳)과 연관된 문제에서 사용된다. 이 방법은 LU 분해를 통해 얻은 하삼각 행렬 $\mathbf{L}$와 벡터 $\mathbf{y}$가 주어졌을 때, 선형 시스템 $\mathbf{L} \mathbf{y} = \mathbf{b}$를 풀기 위해 사용된다.

하삼각 행렬과 Forward Substitution의 기본 개념

하삼각 행렬은 대각선 위의 모든 원소가 0인 정사각 행렬이다. 예를 들어, 3x3 하삼각 행렬 $\mathbf{L}$는 다음과 같이 표현된다:

Forward Substitution은 이와 같은 형태의 행렬을 사용하여 선형 시스템을 단계적으로 해결한다.

Forward Substitution 과정

Forward Substitution의 기본 아이디어는 행렬 $\mathbf{L}$의 각 행에 대해 차례대로 방정식을 풀어가는 것이다. $\mathbf{L}$이 하삼각 행렬이기 때문에, 먼저 첫 번째 방정식부터 시작하여 순차적으로 해결할 수 있다.

1. 첫 번째 방정식: 첫 번째 방정식은 다음과 같이 간단한다:

여기서 $y_1$은 다음과 같이 구할 수 있다:

1. 두 번째 방정식: 두 번째 방정식은 다음과 같이 나타낼 수 있다:

이 방정식에서 $y_1$ 값을 이미 알고 있으므로, 이를 이용해 $y_2$을 계산할 수 있다:

1. 세 번째 방정식: 세 번째 방정식은 다음과 같다:

이전의 $y_1$과 $y_2$ 값을 이용하여 $y_3$을 계산할 수 있다:

이러한 과정을 통해 모든 $y_i$ 값을 구할 수 있으며, 일반적인 $n \times n$ 하삼각 행렬에 대해서도 동일한 방법이 적용된다.

일반적인 $n \times n$ 행렬에 대한 Forward Substitution

$n \times n$ 하삼각 행렬 $\mathbf{L}$과 $\mathbf{b}$ 벡터가 주어졌을 때, Forward Substitution은 다음과 같은 단계로 수행된다:

1. 초기 조건으로 $y_1 = \frac{b_1}{l_{11}}$을 계산한다.
2. 각 $i$번째 행에 대해:

를 계산하여 $y_i$ 값을 구한다.

이 알고리즘은 순차적으로 진행되며, 계산된 값을 다음 단계의 계산에 사용한다. 따라서 Forward Substitution은 $O(n^2)$의 시간 복잡도를 가지며, 효율적인 계산을 제공한다.

Forward Substitution의 예제

Forward Substitution을 좀 더 명확하게 이해하기 위해, 예제를 통해 실제로 계산하는 과정을 살펴보겠다. 예를 들어, 다음과 같은 하삼각 행렬 $\mathbf{L}$과 벡터 $\mathbf{b}$가 주어졌다고 가정한다:

Forward Substitution을 사용하여 벡터 $\mathbf{y}$를 계산하는 과정은 다음과 같다:

1. 첫 번째 방정식:

따라서:

1. 두 번째 방정식:

이미 $y_1 = 2$인 것을 알기 때문에:

1. 세 번째 방정식:

$y_1 = 2$와 $y_2 = \frac{1}{5}$을 사용하여:

결과적으로, 벡터 $\mathbf{y}$는 다음과 같다:

Forward Substitution의 장단점

장점

• 단순함: Forward Substitution은 하삼각 행렬에 대해 직접적으로 적용 가능하며, 알고리즘이 비교적 간단한다.
• 효율성: 시간 복잡도 $O(n^2)$로, 중간 계산 결과를 순차적으로 사용하여 매우 효율적으로 계산이 가능한다.
• 안정성: 하삼각 행렬의 특성상, 계산 과정에서 나누기를 할 때 행렬의 대각선 원소만을 이용하므로 수치적 안정성이 보장된다.

단점

• 제약 조건: Forward Substitution은 반드시 하삼각 행렬에 대해서만 적용 가능한다. 이외의 행렬에 대해서는 다른 방법을 사용해야 한다.
• 수치적 오류: $l_{ii}$ 값이 매우 작을 경우, $y_i$ 계산에서 수치적 오류가 발생할 수 있다. 이는 특히 행렬의 대각선 원소들이 0에 가깝거나, 조건수가 나쁜 경우 문제가 될 수 있다.