# 연립 방정식에 대한 행렬 해법: LU 분해

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

LU 분해는 행렬을 두 개의 삼각행렬, 즉 하삼각행렬(Lower triangular matrix, L)과 상삼각행렬(Upper triangular matrix, U)로 분해하는 방법이다. 이러한 분해는 선형 방정식 시스템의 해법을 단순화하고, 계산 효율성을 높이는 데 중요한 역할을 한다.

**LU 분해**의 정의는 다음과 같다. 주어진 $ n \times n $ 행렬 A가 있을 때, 이를 $ A = LU $로 분해할 수 있다면, L은 대각선이 모두 1인 하삼각행렬이며, U는 상삼각행렬이 된다. 이때 L과 U는 각각의 특성에 따라 A의 구조를 간단하게 분석하는 데 사용된다.

LU 분해는 가우스 소거법과 밀접한 관련이 있다. 가우스 소거법을 통해 행렬을 상삼각행렬로 변환하는 과정에서 발생하는 요소들을 L 행렬에 저장함으로써, A 행렬을 LU의 곱으로 나타낼 수 있다.

#### LU 분해의 절차

LU 분해를 수행하는 방법에는 여러 가지가 있지만, 가장 일반적인 방법은 행렬 A에 대한 가우스 소거법을 사용하는 것이다. 이 과정은 다음과 같은 단계로 이루어진다.

**1. 가우스 소거법 적용**\
가우스 소거법은 주어진 행렬 A를 상삼각행렬 U로 변환하는 과정이다. 이 과정에서 사용되는 각 단계의 스칼라 곱과 행 연산은 L 행렬의 요소로 기록된다. 예를 들어, 첫 번째 열에서 피봇팅을 통해 다른 행을 제거할 때 사용된 스칼라 값은 L의 하삼각 요소로 저장된다.

**2. 하삼각행렬(L)과 상삼각행렬(U) 구성**\
가우스 소거법이 완료되면, A는 U로 변환된다. 동시에, L 행렬은 가우스 소거 과정에서 사용된 스칼라 값들로 구성된다. 이때, L은 단위 하삼각행렬(대각선이 1)로, U는 변환된 상삼각행렬이 된다.

**3. 분해 결과 확인**\
LU 분해가 완료되면, 행렬 A는 $ A = LU $의 형태로 표현된다. 이 결과는 원래의 행렬 A와 동일한지 확인함으로써 분해의 정확성을 검증할 수 있다.

#### LU 분해를 이용한 선형 방정식 해법

LU 분해는 연립 방정식을 푸는 데 매우 유용하다. 이를 통해 $ Ax = b $ 형태의 선형 방정식 시스템을 다음과 같이 해결할 수 있다.

**1. LY = B를 풀기**\
먼저, LU 분해를 통해 얻은 하삼각행렬 L을 사용하여 중간 변수 Y를 구한다. 이때 LY = B를 풀어 Y를 구하는 것은 비교적 간단한 전방 대입(forward substitution) 과정을 통해 이루어진다.

**2. UX = Y를 풀기**\
이제 상삼각행렬 U와 중간 변수 Y를 사용하여 최종 해 X를 구한다. 이 과정은 후방 대입(backward substitution) 방법을 통해 수행된다.

**3. 전체 과정 요약**\
LU 분해를 통해 복잡한 연립 방정식을 두 개의 간단한 대입 문제로 나누어 해결할 수 있으며, 이는 계산의 효율성을 크게 높인다. 특히, 여러 개의 벡터 b에 대해 같은 계수 행렬 A를 사용할 때, LU 분해를 한 번만 수행하고 각 b에 대해 다른 해를 구할 수 있어 매우 유용하다.

#### LU 분해의 조건 및 한계

LU 분해는 매우 유용한 도구이지만, 모든 행렬에 대해 적용 가능한 것은 아니다. 특히, 특정 행렬의 경우 피봇팅이 필요하거나, 분해가 불가능한 경우도 있다.

**1. 피봇팅 필요성**\
LU 분해는 일반적으로 행렬의 일부 열이 0인 경우나, 작은 수치적 오차가 발생할 가능성이 있는 경우에 피봇팅을 요구한다. 피봇팅은 행렬의 열을 재배치하여 분해 과정에서 수치적 안정성을 확보하는 방법이다.

**2. 특이 행렬의 경우**\
행렬 A가 특이 행렬이거나 행렬식이 0인 경우, LU 분해는 수행할 수 없다. 이러한 행렬은 역행렬을 가지지 않으므로, LU 분해를 통한 해법이 성립하지 않는다.

**3. 대칭 행렬에 대한 Cholesky 분해와의 비교**\
대칭 양의 정부호 행렬의 경우, LU 분해 대신 Cholesky 분해를 사용하는 것이 더 효율적일 수 있다. Cholesky 분해는 A를 $ LL^T $로 분해하며, 이 경우 계산량이 절반으로 줄어드는 장점이 있다.

***

관련 자료:

* 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