행렬 인수분해 $A=LU$

가우스 소거법에서 소거 과정을 나타내는 행렬을 $E_{ij}$라고 할 때, 그 역행렬은 $L_{ij}$로 나타낼 수 있다.

핵심적으로 다음처럼 이해할 수 있다.

$E$는 제거하는 행렬이고, $L$은 제거했던 것을 다시 추가하는 행렬이다.

소거 행렬 $E$에서는 주대각 요소를 제외한 위치에 $-\ell_{ij}$가 들어간다.
반대로 $L=E^{-1}$에서는 해당 위치에 $\ell_{ij}$가 들어간다.

즉,

$$E : -\ell_{ij} \quad \longleftrightarrow \quad L : \ell_{ij}$$

행 교환이 없는 전체 forward elimination은 $L$로 반전된다.
이때 $L$은 여전히 하삼각행렬이다.

원본 행렬 $A$는 다음과 같이 복구된다.

$$A = LU$$

즉, $A$는 하삼각행렬과 상삼각행렬의 곱으로 분해된다.

$$A = (\text{lower triangular})(\text{upper triangular})$$

---

$A=LU$의 의미

$Ax=b$에 가우스 소거를 적용하면 다음 형태에 도달한다.

$$Ax=b \quad \longrightarrow \quad Ux=c$$

여기서 $U$는 위삼각행렬이다.
$Ux=c$는 back substitution으로 해를 구할 수 있다.

삼각형 시스템을 푸는 비용은 대략 다음과 같다.

$$O\left(\frac{n^2}{2}\right)$$

반면, $U$를 찾기 위한 소거 비용은 대략 다음과 같다.

$$O\left(\frac{n^3}{3}\right)$$

따라서 선형 시스템을 풀 때 가장 큰 비용은 보통 소거 과정에서 발생한다.

$A=LU$는 행 교환이 없는 가우스 소거법을 행렬 인수분해로 표현한 것이다.

• $U$는 주대각선에 pivot들을 가진다.
• $\ell_{ij}$는 $L$의 주대각선 아래에 위치한다.
• $L$은 $E^{-1}$에 해당한다.

---

$L$, $U$에서 0의 위치 예측

$A$의 구조에 따라 $L$과 $U$에서 0이 나타나는 위치를 어느 정도 예측할 수 있다.

• $A$의 행이 0으로 시작하면, $L$의 해당 행도 0으로 시작한다.
• $A$의 열이 0으로 시작하면, $U$의 해당 행도 0으로 시작한다.

즉, $A$의 희소 구조는 어느 정도 $L$, $U$에도 반영된다.

---

왜 $A=LU$인가

$U$의 3번째 행이 만들어지는 소거 과정을 생각해보자.

3번째 행은 이전 두 행을 이용해 제거된다.

$$\text{Row 3 of } U = \text{Row 3 of } A - \ell_{31}(\text{Row 1 of } U) - \ell_{32}(\text{Row 2 of } U)$$

이 식을 다시 정리하면 다음과 같다.

$$\text{Row 3 of } A = \ell_{31}(\text{Row 1 of } U) + \ell_{32}(\text{Row 2 of } U) + 1(\text{Row 3 of } U)$$

즉, $A$의 3번째 행은 $U$의 행들을 $L$의 3번째 행의 계수로 선형결합한 것이다.

따라서 $L$의 3번째 행은 다음과 같은 계수를 가진다.

$$[\ell_{31} \ \ell_{32} \ 1]$$

이 관점에서 보면 $LU$는 $U$의 행들을 $L$의 계수로 다시 조합하여 원래의 $A$를 복원하는 과정이다.

---

$A=LDU$ 분해

$A=LU$에서 $L$은 주대각선이 모두 1인 단위 하삼각행렬이다.
반면 $U$는 대각선에 pivot들을 가지고 있다.

이때 $U$의 각 행을 해당 pivot으로 나누어 대각선을 1로 만들면, pivot들은 별도의 대각행렬 $D$로 분리된다.

즉,

$$LU \to LDU$$

예를 들어 다음과 같이 볼 수 있다.

$$\begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 2 & 8 \\ 0 & 5 \end{bmatrix} \to \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 2 & 0 \\ 0 & 5 \end{bmatrix} \begin{bmatrix} 1 & 4 \\ 0 & 1 \end{bmatrix}$$

이때 각 행렬의 의미는 다음과 같다.

• $L$: 단위 하삼각행렬
• $D$: 대각행렬
• $U$: 단위 상삼각행렬

따라서 $LDU$ 분해는 pivot들을 $D$에 따로 모아둔 형태라고 볼 수 있다.

---

Two Triangular System

하나의 square system은 두 개의 triangular system으로 나누어 풀 수 있다.

원래 문제는 다음과 같다.

$$Ax=b$$

만약 $A=LU$로 분해되어 있다면 다음과 같이 쓸 수 있다.

$$LUx=b$$

여기서 $Ux=c$라고 두면 다음이 된다.

$$Lc=b$$

따라서 $Ax=b$를 푸는 과정은 두 단계로 나뉜다.

1. $A=LU$로 인수분해한다.
2. $Lc=b$를 forward substitution으로 풀어 $c$를 구한다.
3. $Ux=c$를 back substitution으로 풀어 $x$를 구한다.

즉,

$$Ax=b \quad \Longleftrightarrow \quad \begin{cases} Lc=b \\ Ux=c \end{cases}$$

---

예시

다음 선형 시스템을 생각한다.

$$\begin{align} u + 2v &= 5 \\ 4u + 9v &= 21 \end{align}$$

이는 다음 행렬 방정식이다.

$$Ax=b$$

소거 후에는 다음 $Ux=c$ 형태가 된다.

$$\begin{align} u + 2v &= 5 \\ v &= 1 \end{align}$$

이제 $A=LU$ 분해를 확인해보자.

$$[\ A \ | \ I \ ] = \begin{bmatrix} 1 & 2 & 1 & 0 \\ 4 & 9 & 0 & 1 \end{bmatrix}$$

소거를 수행하면 다음과 같다.

$$\to \begin{bmatrix} 1 & 2 & 1 & 0 \\ 0 & 1 & -4 & 1 \end{bmatrix} = [\ U \ | \ L^{-1} \ ]$$

여기서 $L$은 다음과 같다.

$$L = \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix}$$

먼저 $Lc=b$를 푼다.

$$\begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \end{bmatrix} = \begin{bmatrix} 5 \\ 21 \end{bmatrix}$$

전방 대입을 통해 다음을 얻는다.

$$c = \begin{bmatrix} 5 \\ 1 \end{bmatrix}$$

이제 $Ux=c$를 푼다.

$$\begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 5 \\ 1 \end{bmatrix}$$

후방 대입을 통해 다음을 얻는다.

$$x = \begin{bmatrix} 3 \\ 1 \end{bmatrix}$$

---

조던 소거와 역행렬

앞에서는 소거를 통해 다음 형태를 얻었다.

$$[\ U \ | \ L^{-1} \ ]$$

조던 소거는 여기서 한 단계 더 나아가 대각선 위의 원소들도 0으로 만든다.

즉, 다음 형태까지 만든다.

$$[\ I \ | \ A^{-1} \ ]$$

예제에서는 다음과 같다.

$$\to \begin{bmatrix} 1 & 0 & 9 & -2 \\ 0 & 1 & -4 & 1 \end{bmatrix} = [\ I \ | \ A^{-1} \ ]$$

따라서 역행렬은 다음과 같다.

$$A^{-1} = \begin{bmatrix} 9 & -2 \\ -4 & 1 \end{bmatrix}$$

$2 \times 2$ 행렬의 역행렬 공식은 다음과 같다.

$$A^{-1} = \frac{1}{\det(A)} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}$$

이 예제에서는 $\det(A)=1$이므로 위 결과와 일치한다.

---

소거법의 비용

가우스 소거법으로 선형 방정식 $A\boldsymbol{x}=\boldsymbol{b}$를 풀 때 필요한 비용은 주로 곱셈과 뺄셈 연산의 횟수로 분석한다.

핵심은 행렬의 크기가 $n \times n$일 때, $n$이 커질수록 연산 횟수가 얼마나 빠르게 증가하는지이다.

---

1. 전방 소거: $A \to U$

전방 소거의 목표는 행렬 $A$를 상삼각행렬 $U$로 변환하는 것이다.

이 과정은 곧 $A=LU$ 분해에 해당한다.

연산량은 대략 다음 합으로 나타난다.

$$n^2 + (n-1)^2 + \cdots + 1^2$$

$n$이 충분히 클 때 이 합은 다음에 근사한다.

$$\frac{1}{3}n^3$$

따라서 전방 소거에는 대략 다음 비용이 든다.

$$\frac{1}{3}n^3$$

즉, 약 $\frac{1}{3}n^3$회의 곱셈과 약 $\frac{1}{3}n^3$회의 뺄셈이 필요하다.

---

2. 해 구하기: $Lc=b$, $Ux=c$

$A=LU$ 분해가 끝난 뒤에는 두 개의 삼각형 시스템을 푼다.

$$Lc=b$$ $$Ux=c$$

$Lc=b$는 forward substitution으로 풀고, $Ux=c$는 back substitution으로 푼다.

각 대입 과정은 대략 $\frac{1}{2}n^2$의 비용이 든다.
따라서 두 과정을 합치면 전체 비용은 대략 다음과 같다.

$$n^2$$

즉, 해를 구하는 단계는 $O(n^2)$이다.

---

$n^3$와 $n^2$의 의미

가장 비용이 많이 드는 작업은 행렬 $A$ 자체를 분해하는 단계이다.

$$A \to LU$$

이 단계는 대략 $O(n^3)$의 비용이 든다.

반면, 일단 $A=LU$ 분해가 끝나면 새로운 $b$에 대해 해를 구하는 비용은 $O(n^2)$이다.

즉, 같은 $A$에 대해 여러 개의 다른 우변 $b$를 풀어야 한다면, $A=LU$를 한 번 구해두는 것이 효율적이다.

예를 들어 $n=1000$일 때 $A$ 분해에 1초가 걸린다고 하자.
$n=10000$으로 10배 커지면, $n^3$ 비용은 $10^3=1000$배가 된다.

따라서 시간은 대략 1000초로 증가한다.

---

특별한 경우: 띠 행렬

띠 행렬(band matrix)은 0이 아닌 값들이 주대각선 주변의 좁은 띠 폭 $w$ 안에만 모여 있는 행렬이다.

희소 행렬(sparse matrix)의 대표적인 형태 중 하나이다.

띠 행렬에서는 소거와 대입 비용이 크게 줄어든다.

일반적인 dense matrix에서는 소거 비용이 다음과 같다.

$$O\left(\frac{1}{3}n^3\right)$$

띠 행렬에서는 다음과 같이 줄어든다.

$$O(nw^2)$$

또한 일반적인 대입 비용은 다음과 같다.

$$O(n^2)$$

띠 행렬에서는 다음과 같이 줄어든다.

$$O(2nw)$$

실제 공학 문제에서는 0이 많은 희소 행렬이 자주 등장하므로, 이런 구조를 활용하면 계산 비용을 크게 줄일 수 있다.

---

정리

1. 행 교환이 없는 가우스 소거의 인수분해는 $A=LU$이다.

2. 하삼각행렬 $L$은 소거 과정에서 사용한 multiplier $\ell_{ij}$를 그대로 가진다.

3. $LU$는 원래 행렬 $A$를 복원한다.

4. $Lc=b$는 전방 대입으로 풀고, $Ux=c$는 후방 대입으로 푼다.

5. 인수분해 비용은 대략 다음과 같다.

$$O\left(\frac{1}{3}(n^3-n)\right)$$

6. 해를 도출하는 대입 비용은 대략 다음과 같다.

$$O(n^2)$$

7. 띠 행렬에서는 소거 비용이 다음처럼 줄어든다.

$$O\left(\frac{1}{3}n^3\right) \to O(nw^2)$$

8. 띠 행렬에서는 대입 비용도 다음처럼 줄어든다.

$$O(n^2) \to O(2nw)$$