# LU 분해 - 풀리는 사례 예시

#### LU 분해의 기본 개념

LU 분해는 주어진 정사각 행렬 A를 두 개의 삼각 행렬, 즉 하나의 하삼각 행렬 L과 하나의 상삼각 행렬 U로 분해하는 방법이다. 이 방법은 선형 시스템의 해를 구하는 데 매우 유용하며, 특히 컴퓨터 연산에서 중요한 역할을 한다. LU 분해는 일반적으로 가우스 소거법을 통해 이루어지며, 분해된 행렬을 사용하여 연립 방정식을 효율적으로 푸는 것이 가능하다.

\*\*하삼각 행렬(Lower Triangular Matrix, L)\*\*은 대각선 위의 원소가 모두 0인 행렬로, LU 분해에서는 주로 선행 가우스 소거 단계에서 생성된다. 이 행렬의 특징은 대각선 아래의 원소만이 비제로 값을 가질 수 있다는 점이다.

\*\*상삼각 행렬(Upper Triangular Matrix, U)\*\*은 대각선 아래의 원소가 모두 0인 행렬로, LU 분해의 결과로 얻어진다. 이 행렬은 최종 가우스 소거 단계에서 형성되며, 대각선 위의 원소만 비제로 값을 가진다.

LU 분해의 주요 이점은 복잡한 행렬 방정식을 두 단계의 삼각 행렬 방정식으로 나눌 수 있다는 점에 있다. 이러한 방식은 계산 효율성을 높이고, 특히 큰 규모의 시스템을 다룰 때 매우 유리하다.

#### LU 분해를 통한 연립 방정식의 해법

LU 분해를 사용하여 연립 방정식을 푸는 과정은 다음과 같다. 먼저, 행렬 A를 LU로 분해한 후, 이를 이용하여 연립 방정식을 두 단계로 나누어 해결한다.

주어진 연립 방정식 $ Ax = b $에서 A가 LU로 분해되었다고 가정하자. 이 경우, 방정식은 다음과 같이 쓸 수 있다.

$$
LUx = b
$$

이제, $ Ux = y $로 대체하여 다음과 같은 두 개의 방정식으로 분리할 수 있다.

1. $ Ly = b $
2. $ Ux = y $

첫 번째 방정식 $ Ly = b $는 하삼각 행렬 L을 이용한 전방 대입(forward substitution)으로 해결된다. 두 번째 방정식 $ Ux = y $는 상삼각 행렬 U를 이용한 후방 대입(backward substitution)으로 해결된다.

**전방 대입**은 하삼각 행렬을 사용하여 y를 구하는 과정이다. 이 과정은 각 방정식에서 하나의 미지수만이 포함된 하위 삼각형부터 시작하여 차례대로 y를 계산한다.

**후방 대입**은 상삼각 행렬을 사용하여 최종 해 x를 구하는 과정이다. 이 경우, 역순으로 계산이 진행되며, 가장 마지막 행부터 시작하여 차례대로 x를 계산한다.

#### 사례 예시: LU 분해를 통한 연립 방정식 풀이

다음의 간단한 사례를 통해 LU 분해를 이용한 연립 방정식의 해결 과정을 설명하겠다.

주어진 연립 방정식 시스템을 다음과 같이 정의하자:

$$
A = \begin{pmatrix} 2 & 3 & 1 \ 4 & 7 & 2 \ 6 & 18 & 5 \end{pmatrix}, \quad b = \begin{pmatrix} 5 \ 11 \ 23 \end{pmatrix}
$$

1. **LU 분해**: 행렬 A를 LU로 분해하자. 이는 다음과 같이 이루어진다:

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

2. **전방 대입**: 먼저 $ Ly = b $를 푼다. 이는 다음과 같다:

$$
\begin{pmatrix} 1 & 0 & 0 \ 2 & 1 & 0 \ 3 & 4 & 1 \end{pmatrix} \begin{pmatrix} y\_1 \ y\_2 \ y\_3 \end{pmatrix} = \begin{pmatrix} 5 \ 11 \ 23 \end{pmatrix}
$$

이 식을 풀면 $ y\_1 = 5 $, $ y\_2 = 1 $, $ y\_3 = 0 $을 얻는다.

3. **후방 대입**: 다음으로 $ Ux = 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 \ 1 \ 0 \end{pmatrix}
$$

이 식을 풀면 최종 해는 $ x\_1 = 1 $, $ x\_2 = 1 $, $ x\_3 = 0 $이 된다.

이로써 LU 분해를 이용한 연립 방정식의 풀이 과정을 마무리할 수 있다.

***

관련 자료:

* Linear Algebra and Its Applications by Gilbert Strang
* Matrix Computations by Gene H. Golub and Charles F. Van Loan
* Numerical Linear Algebra by Lloyd N. Trefethen and David Bau III