Lecture 4. A = LU 분해

지난 두 강의의 결과를 합치면 이번 강의의 출발점이 나온다. L2에서 소거의 전 과정을 행렬 하나로 써서 $EA = U$ 를 얻었고, L3에서 역행렬과 $(AB)^{-1} = B^{-1}A^{-1}$ 을 다루었다. 이제 소거 행렬들을 오른쪽으로 넘길 수 있다.

그렇게 넘기면 $A$ 가 두 삼각행렬의 곱으로 쓰인다. 이것을 $A = LU$ 분해라 한다.

이번 강의에서 다룰 것은 네 가지이다. 분해를 유도하는 것, $L$ 의 성분이 소거에 쓴 곱수와 그대로 같다는 것과 그 이유, 이 분해가 실제로 왜 쓸모 있는지, 그리고 행 교환이 필요한 경우이다.

1. $A = LU$ 유도¶

L2에서 쓴 행렬을 그대로 가져온다.

소거 행렬의 역행렬¶

먼저 $E_{21}$ 을 되돌리는 행렬이 필요하다. $E_{21}$ 이 하는 일은 “2행에서 1행의 3배를 빼는 것” 이므로, 되돌리려면 “2행에 1행의 3배를 더하면” 된다. 즉 부호만 바꾸면 된다.

정말 그런지 곱해서 확인해 보자. 행 관점으로 보면 $E_{21}$ 의 각 행이 $E_{21}^{-1}$ 의 행들을 섞는다.

단위행렬이 나왔다. 같은 방식으로 $E_{32}^{-1}$ 도 $(3,2)$ 자리의 부호만 바꾼 것이다.

오른쪽으로 넘기기¶

이제 (2)의 양변 왼쪽에 $E_{32}^{-1}$ 을 곱한다.

한 번 더, 이번에는 $E_{21}^{-1}$ 을 곱한다.

여기서 앞의 두 행렬을 묶어 $L$ 이라 두면 원하는 형태가 된다.

넘기는 순서에 주목하자. $E_{32}$ 가 나중에 곱해졌으므로 먼저 되돌려야 하고, 그 결과 역행렬들은 원래와 반대 순서로 늘어선다. L3에서 본 $(AB)^{-1} = B^{-1}A^{-1}$ 의 순서 뒤집힘이 그대로 나타난 것이다. 소거 단계가 더 많아도 마찬가지이다.

2. $L$ 의 성분은 소거에 쓴 곱수이다¶

(8)의 $L$ 을 실제로 계산해 보자. $E_{21}^{-1}$ 의 각 행이 $E_{32}^{-1}$ 의 행들을 섞는다.

이 행렬을 L2에서 소거할 때 사용한 곱수와 비교해 보자. 그때 쓴 값은 $m_{21} = 3$, $m_{31} = 0$, $m_{32} = 2$ 였다. (11)의 대각선 아래 성분이 바로 그 세 값이다.

$L$ 은 대각선 위가 모두 0인 하삼각행렬(lower triangular matrix)이고, 대각 성분은 전부 1이다. $U$ 는 위삼각행렬이고 대각 성분은 피벗이다.

정말 $LU = A$ 인지 검산해 보자. 행 관점으로 $L$ 의 각 행이 $U$ 의 행들을 섞는다.

(1)의 $A$ 와 같다.

3. 왜 곱수가 그대로 들어가는가¶

여기서 한 가지 이상한 점이 있다. L2에서 소거 행렬들을 곱했을 때는 이렇게 깔끔하지 않았다.

$(3,1)$ 자리에 6 이 나타났다. 우리는 3행에서 1행을 뺀 적이 없는데도 그렇다. 그런데 (11)의 $L$ 에서는 같은 자리가 0 이다. 곱하는 행렬만 바뀌었을 뿐인데 왜 한쪽은 엉키고 다른 쪽은 엉키지 않는가.

소거 행렬을 외적으로 쓰기¶

이유를 보려면 소거 행렬을 다르게 적는 것이 편하다. $\vv{e}_i$ 를 $i$ 번째 성분만 1이고 나머지는 0인 벡터라 하자. L3에서 본 것처럼 열 하나와 행 하나를 곱하면 행렬이 나오는데, $\vv{e}_i \vv{e}_j^{\mathsf{T}}$ 는 $(i,j)$ 자리만 1이고 나머지가 전부 0인 행렬이다.

이 기호를 쓰면 소거 행렬과 그 역행렬을 다음과 같이 쓸 수 있다.

부호만 바꾸면 역행렬이 되는 이유도 이 형태에서 바로 나온다. 두 행렬을 곱해 보자.

가운데 $\vv{e}_j^{\mathsf{T}} \vv{e}_i$ 는 두 표준기저벡터의 내적이다. 소거 행렬은 대각선 아래를 다루므로 언제나 $i \neq j$ 이고, 따라서 이 값은 0이다. 마지막 항이 통째로 사라져 $I$ 만 남는다.

두 소거 행렬을 곱하면¶

이제 두 행렬을 곱해 보자. 계수를 $m$, $m'$ 이라 하고 자리를 $(i,j)$, $(k,l)$ 이라 하면

앞의 세 항은 두 곱수가 각자 제자리에 앉은 것이다. 문제는 마지막 항인데, 여기에도 $\vv{e}_j^{\mathsf{T}} \vv{e}_k$ 가 들어 있다. 이 값은 $j = k$ 일 때만 1이고 그 외에는 0이다.

두 경우를 비교하면¶

이 기준으로 앞의 두 계산을 다시 보자.

$E = E_{32}E_{21}$ 은 왼쪽이 $(i,j) = (3,2)$ 이고 오른쪽이 $(k,l) = (2,1)$ 이다. $j = 2$ 이고 $k = 2$ 이므로 같다. 따라서 $(i, l) = (3, 1)$ 자리에 항이 생긴다. 그 값은 곱수의 부호가 둘 다 음수였으므로

이고, 이것이 (13)에 나타난 6 이다. 왜 하필 이 값인지도 설명이 된다. $E_{32}$ 가 2행을 끌어다 쓰는데, 그 2행은 $E_{21}$ 이 이미 1행을 섞어 놓은 상태이기 때문이다.

$L = E_{21}^{-1}E_{32}^{-1}$ 은 왼쪽이 $(i,j) = (2,1)$ 이고 오른쪽이 $(k,l) = (3,2)$ 이다. $j = 1$ 이고 $k = 3$ 이므로 다르다. 마지막 항이 사라지므로 두 곱수가 각자 제자리에 앉는다.

일반적으로도 그런가¶

소거 행렬이 더 많아도 결론은 같다. $L$ 을 만들 때 역행렬들이 늘어서는 순서는 $E_{21}^{-1}, E_{31}^{-1}, E_{32}^{-1}, E_{41}^{-1}, \dots$ 처럼 열 번호가 커지지 않는 순서이다. 왼쪽에 있는 것을 $(i,j)$, 오른쪽에 있는 것을 $(k,l)$ 이라 하면

이고, 둘을 이으면 $j \le l < k$ 이므로 언제나 $j < k$ 이다. $j = k$ 가 될 수 없으므로 간섭 항은 한 번도 생기지 않는다. 그래서 모든 곱수가 각자 제자리에 그대로 들어앉는다.

반대로 $E$ 를 만들 때는 순서가 뒤집혀 $E_{32}$ 가 $E_{21}$ 의 왼쪽에 오고, 그때 $j = k$ 가 성립해 버린다. 같은 행렬들인데 곱하는 순서 하나로 결과가 갈린다.

4. $LDU$ 분해¶

$U$ 의 대각 성분은 피벗이다. 이 값들을 따로 빼내면 형태가 더 대칭적으로 정리된다. 각 행을 그 행의 피벗으로 나누면 대각이 전부 1인 위삼각행렬이 남는다.

곱해 보면 $D$ 의 $i$ 번째 대각 성분이 $U'$ 의 $i$ 행 전체에 곱해지므로 원래 $U$ 가 나온다. 이것을 (8)에 넣으면 다음과 같다.

이렇게 쓰면 $L$ 과 $U'$ 이 모두 대각이 1이고, 피벗은 가운데 $D$ 에 모인다. $U$ 를 그대로 쓸지 $D$ 를 빼낼지는 표기 관례의 문제이고, 담고 있는 정보는 같다.

5. 왜 $LU$ 를 쓰는가¶

분해를 구해 놓으면 $A\vv{x} = \vv{b}$ 를 두 단계로 풀 수 있다. $A = LU$ 이므로

인데, 여기서 $U\vv{x}$ 를 통째로 $\vv{c}$ 라 두면 문제가 둘로 갈라진다.

$L$ 은 하삼각이므로 위에서 아래로 하나씩 확정된다. 이것을 전진 대입(forward substitution) 이라 한다. $\vv{b} = (2, 12, 2)$ 로 해 보자.

$\vv{c} = (2, 6, -10)$ 이다. L2에서 증강행렬을 소거했을 때 우변이 바뀌어 도착한 값과 같다. 소거가 우변에 한 일이 곧 $L\vv{c} = \vv{b}$ 를 푸는 일이었던 셈이다. 나머지는 L2에서 한 후진 대입 그대로이고, 답은 $(2, 1, -2)$ 이다.

연산량¶

소거에 드는 연산 수를 세어 보자. $j$ 번째 열을 정리할 때 아래에 $n - j$ 개의 행이 있고, 각 행에서 갱신해야 할 성분이 $n - j$ 개이다. 성분마다 곱셈 한 번과 뺄셈 한 번이 든다. 따라서 전체는 다음과 같다.

전진 대입과 후진 대입은 훨씬 싸다. 각각 $i$ 번째 미지수를 구할 때 $n - i$ 번의 곱셈이 드므로

이고, 둘을 합치면 $\vv{b}$ 하나당 약 $n^2$ 이다.

여기서 핵심이 나온다. $LU$ 는 $A$ 에만 의존하고 $\vv{b}$ 와는 무관하다. 그러므로 같은 $A$ 에 대해 우변이 여러 개라면, 분해는 한 번만 하고 대입만 반복하면 된다.

$n = 500$ 이면 $n^3/3 \approx 4.2 \times 10^7$ 이고 $n^2 = 2.5 \times 10^5$ 이므로 약 170배 차이이다. 우변이 100개라면 분해를 재사용하는 쪽이 거의 100배 빠르다.

L3에서 역행렬을 구해 곱하지 말라고 한 이유도 같은 맥락이다. 역행렬을 구하는 데는 약 $n^3$ 이 들어 소거보다 세 배쯤 비싸고, 구해 놓아도 $\vv{b}$ 마다 $n^2$ 이 드는 것은 마찬가지이며, 반올림 오차까지 더 쌓인다.

6. 행 교환이 필요한 경우 : $PA = LU$¶

$A = LU$ 가 언제나 가능한 것은 아니다. L2의 3절에서 본 것처럼 소거 도중 피벗 자리에 0이 나오면 행을 바꿔야 하는데, 행을 바꾸고 나면 그것은 더 이상 원래 $A$ 를 소거한 것이 아니다.

L2에서 본 예를 다시 보자.

2행에서 1행의 3배를 빼면 $(0, 0, -2)$ 가 되어 두 번째 피벗 자리가 0이 된다. 아래에 있는 4 를 끌어올려야 하므로 2행과 3행을 바꾼다. 이 교환을 나타내는 치환행렬은 다음과 같다.

교환을 먼저 해 두면 그다음은 막히지 않고 소거가 끝까지 진행된다. 3행에서 1행의 3배를 빼면 $(0, 0, -2)$ 이고, 두 번째 열은 이미 정리되어 있으므로 곱수가 0이다.

즉 행 교환이 필요한 경우에는 $A$ 가 아니라 행을 미리 정리해 둔 $PA$ 가 분해된다. 어떤 정방행렬이든 적당한 $P$ 를 골라 $PA = LU$ 로 쓸 수 있다.

마치며...¶

이번 강의에서 다룬 것을 정리하면 다음과 같다.

$L$ 의 성분이 공짜로 얻어지는 이유는 역행렬을 곱하는 순서가 간섭을 피하기 때문이었다. $E$ 를 곱할 때는 $j = k$ 가 성립해 없던 성분이 생기지만, $E^{-1}$ 을 반대 순서로 곱하면 $j < k$ 가 보장되어 그런 일이 일어나지 않는다.

그리고 우리는 첫 번째 분해를 얻었다. 복잡한 행렬 하나를 단순한 행렬 둘의 곱으로 바꾼 것이다. 앞으로 이 일을 여러 번 하게 되는데, 그때마다 무엇을 단순하다고 볼지가 달라진다. 여기서는 삼각행렬이 단순한 것이었다.

여기까지 우리는 연립방정식을 푸는 방법을 다루었다. 다음 강의에서는 시선을 옮겨, 전치와 순열을 정리한 뒤 벡터공간(vector space)이라는 개념에 대해 알아보도록 하자.

이번 강의의 내용을 파이썬으로 확인해 보려면 L4 실습 노트북으로 넘어가면 된다. 소거하면서 곱수를 기록해 $L$ 을 직접 만들어 보고, scipy 의 결과와 대조하며, 우변이 여러 개일 때 분해를 재사용하는 것이 실제로 얼마나 빠른지 재 볼 수 있다.