대칭 행렬에서의 LU 분해 - 소프트웨어 융합

대칭 행렬(Symmetric Matrix)은 $\mathbf{A}$ 가 $\mathbf{A}^\text{T} = \mathbf{A}$ 를 만족하는 행렬을 의미한다. 대칭 행렬의 특성은 LU 분해에서 중요한 역할을 하며, 이는 분해의 효율성과 안정성에 긍정적인 영향을 미친다.

대칭 행렬의 LU 분해 정의

대칭 행렬 $\mathbf{A}$ 에 대해 LU 분해를 수행하면 일반적으로 다음과 같은 형태로 나타낼 수 있다.

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

여기서 $\mathbf{L}$ 은 하삼각 행렬(Lower Triangular Matrix)이고, $\mathbf{U}$ 는 상삼각 행렬(Upper Triangular Matrix)이다. 그러나, 대칭 행렬에서는 $\mathbf{U}$ 가 $\mathbf{L}^\text{T}$ 와 동일하게 될 수 있다. 따라서 대칭 행렬의 LU 분해는 다음과 같은 특수한 형태를 가질 수 있다.

$\mathbf{A} = \mathbf{L} \mathbf{L}^\text{T}$

이러한 형태의 분해를 특별히 "Cholesky 분해"라고도 한다. 하지만 Cholesky 분해는 엄밀히 말해 LU 분해의 특수한 경우이며, 이후 비교될 예정이다.

대칭 행렬의 특성

대칭 행렬 $\mathbf{A}$ 는 다음과 같은 유용한 특성을 가지고 있다.

모든 고유값은 실수이다. 이는 대칭 행렬의 고유값 문제를 해결하는 데 있어 수치적 안정성을 제공한다.
직교 대각화가 가능한다. 즉, $\mathbf{A}$ 는 직교 행렬 $\mathbf{Q}$ 와 대각 행렬 $\mathbf{D}$ 에 의해 $\mathbf{A} = \mathbf{Q} \mathbf{D} \mathbf{Q}^\text{T}$ 로 표현될 수 있다.
양의 정부호 가능성: 대칭 행렬이 양의 정부호(Positive Definite)인 경우, $\mathbf{L} \mathbf{L}^\text{T}$ 형태로 LU 분해가 가능한다. 이 경우 모든 대각 성분이 양수이다.

대칭 행렬의 LU 분해의 계산 방법

대칭 행렬에 대한 LU 분해는 일반적인 행렬보다 효율적으로 수행될 수 있다. 특히, $\mathbf{U} = \mathbf{L}^\text{T}$ 의 관계를 이용하여 계산량을 절반으로 줄일 수 있다.

첫 번째 단계: 행렬 $\mathbf{A}$ 의 첫 번째 열을 이용하여 $\mathbf{L}$ 의 첫 번째 열을 구한다. 이는 다음과 같이 표현할 수 있다.

$l_{i1} = \frac{a_{i1}}{u_{11}} \quad \text{for } i = 2, \ldots, n$

두 번째 단계: 나머지 $(n-1) \times (n-1)$ 부분 행렬에 대해 동일한 과정을 반복한다. 즉, 다음의 하위 행렬에 대해 다시 LU 분해를 수행한다.

$\mathbf{A}^{(1)} = \mathbf{A} - \mathbf{L}_1 \mathbf{U}_1^\text{T}$

여기서 $\mathbf{L}_1$ 과 $\mathbf{U}_1$ 는 첫 번째 열과 행을 제외한 부분 행렬에 해당한다.

반복: 위 과정을 반복하여, 최종적으로 $\mathbf{L}$ 과 $\mathbf{U}$ 를 구한다. 계산은 대칭성을 이용하여 절반의 연산만으로 수행될 수 있다.

LU 분해의 대칭 행렬에서의 장점

대칭 행렬에서의 LU 분해는 다음과 같은 장점을 가지고 있다.

계산 효율성: 대칭 행렬에서는 $\mathbf{U} = \mathbf{L}^\text{T}$ 이므로, 일반적인 LU 분해와 비교하여 연산 횟수가 줄어든다. 이는 큰 규모의 행렬을 다룰 때 상당한 성능 향상을 가져올 수 있다.
저장 공간 절약: $\mathbf{L}$ 만 저장하면 $\mathbf{U}$ 는 $\mathbf{L}^\text{T}$ 로 간단히 유도할 수 있기 때문에, 행렬을 저장하는 데 필요한 공간을 절약할 수 있다.
수치적 안정성: 대칭 행렬의 특성상, LU 분해는 수치적으로 더 안정적이며, 특히 양의 정부호 행렬의 경우에는 항상 성공적으로 분해가 가능한다.

예제: 대칭 행렬의 LU 분해

간단한 예제를 통해 대칭 행렬의 LU 분해를 살펴보겠다.

예를 들어, $3 \times 3$ 대칭 행렬 $\mathbf{A}$ 가 주어졌다고 하자.

$\mathbf{A} = \begin{bmatrix} 4 & 2 & 2 \\ 2 & 2 & 0 \\ 2 & 0 & 3 \\ \end{bmatrix}$

이 행렬에 대해 LU 분해를 수행하면, $\mathbf{L}$ 과 $\mathbf{U}$ 는 다음과 같이 구할 수 있다.

$\mathbf{L} = \begin{bmatrix} 2 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & -1 & 1 \\ \end{bmatrix} , \quad \mathbf{U} = \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \\ \end{bmatrix}$

따라서 $\mathbf{A} = \mathbf{L} \mathbf{U}$ 가 성립하며, 이는 대칭 행렬의 특성을 잘 반영하는 결과이다.

Pivoting이 없는 경우와 있는 경우

대칭 행렬에서의 LU 분해에서는 일반적으로 Pivoting이 필요하지 않다고 알려져 있다. 하지만 수치적으로 불안정한 행렬의 경우 Pivoting을 적용하는 것이 필요할 수 있다.

Pivoting이 없는 경우: 대칭 행렬의 경우, Pivoting을 사용하지 않고도 LU 분해를 안정적으로 수행할 수 있는 경우가 많다. 이는 대칭 행렬의 고유한 특성에 기인한다.
Pivoting이 있는 경우: 대칭 행렬이라 하더라도 분해 과정에서 수치적인 불안정성이 발생할 가능성이 있다. 이러한 경우, Partial Pivoting을 도입하여 안정성을 개선할 수 있다.

이와 같이, 대칭 행렬에서의 LU 분해는 수치적 안정성과 계산 효율성 면에서 매우 유리한 접근법이다.