# LU 분해 : 풀리지 않는 사례 예시

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

LU 분해는 주어진 정방행렬을 두 개의 삼각행렬, 즉 하삼각행렬(Lower triangular matrix, L)과 상삼각행렬(Upper triangular matrix, U)로 분해하는 방법이다. 이 방법은 연립 방정식 $ Ax = b $의 해를 구하는 데 자주 사용된다. LU 분해는 계산 복잡성을 줄이고, 대규모 선형 시스템을 보다 효율적으로 해결할 수 있게 해준다.

LU 분해는 기본적으로 피벗팅을 수반하지 않는 경우와 부분 피벗팅을 사용하는 경우로 나뉜다. 피벗팅은 행렬이 특이하거나 조건이 나쁜 경우에 발생할 수 있는 수치적인 불안정성을 피하기 위해 사용된다.

#### 풀리지 않는 사례의 개념

LU 분해가 실패하는 경우는 행렬의 특성에 기인한다. 특히, 행렬이 특이(singular)하거나, 행렬의 일부 요소가 0이 되어 분해 과정에서 분모로 등장하는 상황에서 발생할 수 있다. 이러한 경우, LU 분해는 더 이상 유효하지 않으며, 연립 방정식의 해를 구할 수 없게 된다.

**특이 행렬**은 행렬식이 0인 행렬로, 이 경우 행렬은 역행렬을 가지지 않는다. 따라서 LU 분해의 과정에서 분해가 불가능해진다. 예를 들어, 2x2 행렬의 경우, 대각선 요소가 0이 될 때 LU 분해는 실패할 수 있다.

\*\*비정칙 행렬(ill-conditioned matrix)\*\*은 매우 작은 행렬식 값을 가지는 행렬로, 수치적 오류가 커질 가능성이 높다. 이러한 행렬의 경우에도 LU 분해는 매우 불안정하며, 수치적으로 정확한 해를 얻기 어렵게 된다.

#### 풀리지 않는 사례의 구체적 예시

LU 분해가 실패하는 구체적인 예시는 아래와 같다.

**1. 특이 행렬의 경우**\
예를 들어, 다음과 같은 행렬 A가 주어졌다고 가정하자:

$$
A = \begin{pmatrix} 1 & 2 \ 2 & 4 \end{pmatrix}
$$

이 행렬은 특이 행렬로, 행렬식이 0이다:

$$
\text{det}(A) = 1(4) - 2(2) = 4 - 4 = 0
$$

이 경우, LU 분해를 시도하면 두 행이 선형적으로 종속되어 있어 분해가 불가능하다.

**2. 0 요소가 포함된 행렬의 경우**\
LU 분해 과정에서 0이 중요한 피벗 요소로 등장하는 경우 분해가 불가능해질 수 있다. 예를 들어 다음과 같은 행렬 B를 고려해보자:

$$
B = \begin{pmatrix} 0 & 2 & 1 \ 1 & 0 & 3 \ 4 & -1 & 1 \end{pmatrix}
$$

여기서 첫 번째 행의 첫 번째 요소가 0이기 때문에 피벗팅 없이 LU 분해를 직접 수행하려고 하면 분해가 불가능하다. 피벗팅을 적용하지 않으면 첫 번째 단계에서 더 이상 진행할 수 없게 된다.

이러한 경우 LU 분해는 행렬의 재배치(피벗팅)를 통해 해결할 수 있지만, 피벗팅이 불가능하거나 원치 않는 경우에는 LU 분해가 실패하게 된다.

**3. 수치적 불안정성**\
매우 작은 수치적 값이 포함된 행렬의 경우 LU 분해를 수행하면 수치적 오류가 크게 증폭될 수 있다. 예를 들어:

$$
C = \begin{pmatrix} 1 & 1.00001 \ 1.00001 & 1 \end{pmatrix}
$$

이 행렬은 비정칙 행렬로, LU 분해 과정에서 수치적 오류로 인해 해가 매우 부정확해질 수 있다.

#### 해결 방법과 대안

LU 분해가 실패하는 상황에서, 대안적인 방법을 고려할 필요가 있다. 대표적인 방법으로는 **QR 분해**나 \*\*특이값 분해(SVD)\*\*를 사용하는 것이다. 이러한 방법들은 LU 분해보다 더 일반적인 방법으로, 특이 행렬이나 비정칙 행렬에서도 적용 가능하다. 또한, **피벗팅**을 통해 LU 분해를 보다 안정적으로 수행할 수 있으며, 이는 수치적 오류를 줄이는 데 기여할 수 있다.

***

관련 자료:

* Numerical Linear Algebra by Lloyd N. Trefethen and David Bau III
* Matrix Computations by Gene H. Golub and Charles F. Van Loan
* Applied Numerical Linear Algebra by James W. Demmel