Lecture 17. 직교행렬과 그람-슈미트

지난 강의 마지막에 힌트를 하나 남겼다. $A$ 의 열들이 서로 직교했다면 $A^{\mathsf{T}}A$ 가 대각행렬이 되어 모든 것이 쉬워진다고.

실제로 그렇다. 그리고 생각보다 더 쉬워진다. 직교기저에서는 계수를 구하는 데 연립방정식을 풀 필요가 없다. 내적 한 번이면 끝난다. 역행렬도 소거도 필요 없다.

그렇다면 할 일은 하나이다. 주어진 벡터들을 직교로 만들어 버리자. 그 절차가 그람-슈미트이고, 그 과정을 기록한 것이 $A = QR$ 이다.

미리 말해 두면, 이번 강의에서 배우는 계산은 후반부의 뜻밖의 자리에서 다시 나타난다. $\sin$ 과 $\cos$ 의 계수를 구하는 자리에서이다.

1. 정규직교와 직교행렬¶

이 벡터들을 열로 세워 $Q = \begin{bmatrix} \vv{q}_1 & \cdots & \vv{q}_n \end{bmatrix}$ 라 하자. $Q^{\mathsf{T}}Q$ 의 $(i, j)$ 성분은 $Q^{\mathsf{T}}$ 의 $i$ 행과 $Q$ 의 $j$ 열의 곱, 곧 $\vv{q}_i^{\mathsf{T}}\vv{q}_j$ 이다. 정의에 의해 대각은 1이고 나머지는 0이다.

Q^{\mathsf{T}}Q = I

(2)

정사각행렬일 때만 두 곱이 모두 $I$ 가 된다. 그때는 (2)의 등식과 L3의 역행렬의 유일성((19))에서 다음이 나온다.

Q \text{ 가 정사각} \quad\Longrightarrow\quad Q^{-1} = Q^{\mathsf{T}}

(3)

역행렬을 구하는 일이 전치로 끝난다. 소거도 나눗셈도 없다.

길이를 바꾸지 않는다¶

$Q$ 를 곱해도 벡터의 길이가 변하지 않는다. (2)의 등식을 가운데에 끼워 넣으면 된다.

\|Q\vv{x}\|^2 = (Q\vv{x})^{\mathsf{T}}(Q\vv{x}) = \vv{x}^{\mathsf{T}}Q^{\mathsf{T}}Q\vv{x} = \vv{x}^{\mathsf{T}}\vv{x} = \|\vv{x}\|^2

(4)

같은 계산으로 내적도 보존된다.

(Q\vv{x})^{\mathsf{T}}(Q\vv{y}) = \vv{x}^{\mathsf{T}}Q^{\mathsf{T}}Q\vv{y} = \vv{x}^{\mathsf{T}}\vv{y}

(5)

길이도 각도도 그대로이다. 그러므로 직교행렬이 하는 일은 회전이거나 반사이다. 모양을 바꾸지 않고 방향만 돌린다.

가장 익숙한 예가 L5의 순열행렬(Definition 1)이다. 열이 표준기저벡터를 늘어놓은 것이라 정규직교이고, 하는 일은 성분의 자리를 바꾸는 것뿐이니 길이가 변할 리 없다. $2 \times 2$ 회전행렬도 마찬가지이다.

Q = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}, \qquad Q^{\mathsf{T}}Q = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}

(6)

2. 직교기저의 위력¶

이제 이번 강의의 핵심이다.

기저 $\vv{v}_1, \dots, \vv{v}_n$ 이 주어지고 벡터 $\vv{b}$ 를 그 기저로 쓰고 싶다고 하자.

\vv{b} = x_1\vv{v}_1 + x_2\vv{v}_2 + \cdots + x_n\vv{v}_n

(7)

계수 $x_i$ 를 구하려면 $V\vv{x} = \vv{b}$ 를 풀어야 한다. 연립방정식이고, 소거가 필요하다. 계수들이 서로 얽혀 있어 하나만 따로 구할 수 없기 때문이다.

기저가 정규직교이면 사정이 완전히 달라진다. 같은 식을 놓고 양변에 $\vv{q}_j^{\mathsf{T}}$ 를 곱해 보자.

\vv{q}_j^{\mathsf{T}}\vv{b} = x_1\,\vv{q}_j^{\mathsf{T}}\vv{q}_1 + \cdots + x_j\,\vv{q}_j^{\mathsf{T}}\vv{q}_j + \cdots + x_n\,\vv{q}_j^{\mathsf{T}}\vv{q}_n

(8)

정규직교의 정의에 의해 $j$ 번째를 뺀 모든 항이 0이고, $j$ 번째는 $x_j \cdot 1$ 이다.

x_j = \vv{q}_j^{\mathsf{T}}\vv{b}

(9)

연립방정식이 사라졌다. 계수 하나를 구하는 데 내적 한 번이면 된다. 다른 계수를 몰라도 된다.

\vv{b} = (\vv{q}_1^{\mathsf{T}}\vv{b})\,\vv{q}_1 + (\vv{q}_2^{\mathsf{T}}\vv{b})\,\vv{q}_2 + \cdots + (\vv{q}_n^{\mathsf{T}}\vv{b})\,\vv{q}_n

(10)

Figure 1:왼쪽은 계수가 서로 얽혀 있어 연립방정식이 필요하고, 오른쪽은 각 계수가 따로 떨어져 나온다.

이것은 사실 투영이다¶

(10)의 각 항을 L15의 직선 투영 공식과 비교해 보자. 그때 $\vv{a}$ 방향으로의 투영은 다음과 같았다((4)).

\vv{p} = \vv{a}\,\frac{\vv{a}^{\mathsf{T}}\vv{b}}{\vv{a}^{\mathsf{T}}\vv{a}}

(11)

$\vv{a}$ 가 $\vv{q}_i$ 이면 길이가 1이라 분모가 1이고, 남는 것이 정확히 $(\vv{q}_i^{\mathsf{T}}\vv{b})\vv{q}_i$ 이다.

3. 투영과 최소제곱이 쉬워진다¶

L15의 투영행렬은 $P = A(A^{\mathsf{T}}A)^{-1}A^{\mathsf{T}}$ 였다((18)). $A$ 자리에 $Q$ 를 넣으면 가운데가 통째로 사라진다.

P = Q(Q^{\mathsf{T}}Q)^{-1}Q^{\mathsf{T}} = Q\,I^{-1}Q^{\mathsf{T}} = QQ^{\mathsf{T}}

(12)

1절에서 정체를 미뤄 둔 $QQ^{\mathsf{T}}$ 가 이것이다. $Q$ 의 열이 만드는 공간으로의 투영행렬이다. $Q$ 가 정사각이면 $QQ^{\mathsf{T}} = QQ^{-1} = I$ 인데, 그때는 열공간이 $\R^m$ 전체라 투영할 것이 없으니 맞는 결론이다.

최소제곱도 마찬가지이다. 정규방정식에 $A = Q$ 를 넣으면

Q^{\mathsf{T}}Q\,\hat{\vv{x}} = Q^{\mathsf{T}}\vv{b} \qquad\Longrightarrow\qquad \hat{\vv{x}} = Q^{\mathsf{T}}\vv{b}

(13)

가 된다. 풀 것이 없다. 성분으로 쓰면 $\hat{x}_i = \vv{q}_i^{\mathsf{T}}\vv{b}$ 이니 2절과 같은 식이다.

4. 그람-슈미트¶

좋다는 것은 알겠는데, 주어진 벡터가 직교가 아니면 어떻게 하는가. 직교로 만들면 된다.

독립인 벡터 $\vv{a}_1, \dots, \vv{a}_n$ 이 있다고 하자. 첫 번째는 방향을 그대로 두고 길이만 1로 맞춘다.

\vv{q}_1 = \frac{\vv{a}_1}{\|\vv{a}_1\|}

(14)

두 번째는 $\vv{q}_1$ 방향 성분을 걷어내고 남은 것을 쓴다. 걷어내는 양이 바로 3절의 투영이다.

\vv{v}_2 = \vv{a}_2 - (\vv{q}_1^{\mathsf{T}}\vv{a}_2)\,\vv{q}_1, \qquad \vv{q}_2 = \frac{\vv{v}_2}{\|\vv{v}_2\|}

(15)

정말 직교하는지 확인하자. $\vv{q}_1$ 을 곱해 보면 된다.

\vv{q}_1^{\mathsf{T}}\vv{v}_2 = \vv{q}_1^{\mathsf{T}}\vv{a}_2 - (\vv{q}_1^{\mathsf{T}}\vv{a}_2)\,\vv{q}_1^{\mathsf{T}}\vv{q}_1 = \vv{q}_1^{\mathsf{T}}\vv{a}_2 - \vv{q}_1^{\mathsf{T}}\vv{a}_2 = 0

(16)

$\vv{q}_1^{\mathsf{T}}\vv{q}_1 = 1$ 이라 두 항이 같아져 사라진다. 세 번째부터는 이미 만든 방향의 성분을 전부 걷어낸다.

\vv{v}_k = \vv{a}_k - \sum_{i<k} (\vv{q}_i^{\mathsf{T}}\vv{a}_k)\,\vv{q}_i, \qquad \vv{q}_k = \frac{\vv{v}_k}{\|\vv{v}_k\|}

(17)

\vv{a}_2 에서 \vv{q}_1 성분을 빼면 남는 것이 \vv{q}_1 과 직교하고,
\vv{a}_3 에서 평면 성분을 빼면 남는 것이 평면과 직교한다. — Figure 2: $\vv{a}_2$ 에서 $\vv{q}_1$ 성분을 빼면 남는 것이 $\vv{q}_1$ 과 직교하고, $\vv{a}_3$ 에서 평면 성분을 빼면 남는 것이 평면과 직교한다.

예제¶

$\vv{a}_1 = (1, 1, 1)$ , $\vv{a}_2 = (1, 0, 2)$ , $\vv{a}_3 = (-1, 1, 3)$ 으로 해 보자.

\|\vv{a}_1\| = \sqrt{3} \qquad\Longrightarrow\qquad \vv{q}_1 = \frac{1}{\sqrt3}(1, 1, 1)

(18)

$\vv{q}_1^{\mathsf{T}}\vv{a}_2 = (1 + 0 + 2)/\sqrt3 = \sqrt3$ 이므로 빼는 양은 $\sqrt3 \cdot \frac{1}{\sqrt3}(1,1,1) = (1,1,1)$ 이다.

\vv{v}_2 = (1, 0, 2) - (1, 1, 1) = (0, -1, 1) \qquad\Longrightarrow\qquad \vv{q}_2 = \frac{1}{\sqrt2}(0, -1, 1)

(19)

세 번째는 두 번 뺀다. $\vv{q}_1^{\mathsf{T}}\vv{a}_3 = (-1+1+3)/\sqrt3 = \sqrt3$ 이고 $\vv{q}_2^{\mathsf{T}}\vv{a}_3 = (0-1+3)/\sqrt2 = \sqrt2$ 이므로 빼는 양은 $(1,1,1) + (0,-1,1) = (1, 0, 2)$ 이다.

\vv{v}_3 = (-1, 1, 3) - (1, 0, 2) = (-2, 1, 1) \qquad\Longrightarrow\qquad \vv{q}_3 = \frac{1}{\sqrt6}(-2, 1, 1)

(20)

셋이 서로 직교하는지는 내적 세 번으로 확인된다. $(1,1,1)\cdot(0,-1,1) = 0$ , $(1,1,1)\cdot(-2,1,1) = 0$ , $(0,-1,1)\cdot(-2,1,1) = 0$ 이다.

5. $A = QR$ ¶

그람-슈미트를 다 돌리면 $Q$ 를 얻는다. 그런데 원래의 $\vv{a}$ 들은 어디로 갔는가. $Q$ 만으로 $A$ 를 되돌릴 수 있어야 한다.

$R = Q^{\mathsf{T}}A$ 로 두자. 그러면

QR = QQ^{\mathsf{T}}A = PA = A

(21)

이다. (12)에서 $QQ^{\mathsf{T}}$ 가 $C(Q)$ 로의 투영행렬인데, 그람-슈미트가 $\vv{a}$ 들에서 $\vv{q}$ 들을 만들었으므로 두 공간이 같고, 따라서 $A$ 의 열은 이미 그 공간 안에 있어 투영해도 그대로이다.

A = QR, \qquad R = Q^{\mathsf{T}}A, \qquad R_{ij} = \vv{q}_i^{\mathsf{T}}\vv{a}_j

(22)

왜 $R$ 이 상삼각인가¶

$i > j$ 인 자리를 보자. 그람-슈미트를 거꾸로 읽으면 (17)에서 $\vv{a}_j = \|\vv{v}_j\|\vv{q}_j + \sum_{i<j}(\vv{q}_i^{\mathsf{T}}\vv{a}_j)\vv{q}_i$ 이므로, $\vv{a}_j$ 는 $\vv{q}_1, \dots, \vv{q}_j$ 의 결합이다. 그런데 $i > j$ 이면 $\vv{q}_i$ 는 그 목록에 없고 목록의 모든 벡터와 직교하므로

R_{ij} = \vv{q}_i^{\mathsf{T}}\vv{a}_j = 0 \qquad (i > j)

(23)

이다.

$LU$ 에 이은 두 번째 분해이다. 둘의 성격이 다르다. $LU$ 는 소거의 기록이고 $QR$ 은 직교화의 기록이다.

	$A = LU$	$A = QR$
무엇을 한 기록인가	행에 대한 소거	열에 대한 직교화
왼쪽 조각	하삼각 $L$ — 뺀 배수	$Q$ — 만들어 낸 방향
오른쪽 조각	상삼각 $U$ — 남은 것	상삼각 $R$ — 조립 설명서
쓰는 곳	$A\vv{x} = \vv{b}$ 를 빨리	최소제곱을 안전하게

6. $QR$ 로 최소제곱을 푼다¶

L16에서 남긴 찜찜함을 여기서 던다. 정규방정식에 $A = QR$ 을 넣어 보자.

A^{\mathsf{T}}A\hat{\vv{x}} = A^{\mathsf{T}}\vv{b} \qquad\Longrightarrow\qquad (QR)^{\mathsf{T}}(QR)\,\hat{\vv{x}} = (QR)^{\mathsf{T}}\vv{b}

(24)

왼쪽을 풀어 쓰면 가운데에 $Q^{\mathsf{T}}Q = I$ 가 나타나 사라진다.

R^{\mathsf{T}}\underbrace{Q^{\mathsf{T}}Q}_{=\,I}R\,\hat{\vv{x}} = R^{\mathsf{T}}Q^{\mathsf{T}}\vv{b} \qquad\Longrightarrow\qquad R^{\mathsf{T}}R\,\hat{\vv{x}} = R^{\mathsf{T}}Q^{\mathsf{T}}\vv{b}

(25)

$R$ 의 대각 성분은 $\|\vv{v}_k\|$ 이고 전부 0이 아니므로 $R$ 은 가역이고, 따라서 $R^{\mathsf{T}}$ 도 가역이다. 양변 앞의 $R^{\mathsf{T}}$ 를 지우면 다음이 남는다.

R\,\hat{\vv{x}} = Q^{\mathsf{T}}\vv{b}

(26)

$R$ 이 상삼각이므로 L2의 후진 대입으로 끝난다. 그리고 결정적으로, 계산 과정에 $A^{\mathsf{T}}A$ 가 등장하지 않는다.

마치며...¶

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

대상	내용
정규직교	서로 직교하고 길이가 1. $Q^{\mathsf{T}}Q = I$
정사각일 때	$Q^{-1} = Q^{\mathsf{T}}$ . 역행렬이 전치로 끝난다
길이와 각도	보존된다. 직교행렬은 회전이거나 반사이다
직교기저의 계수	$x_j = \vv{q}_j^{\mathsf{T}}\vv{b}$ — 연립방정식이 필요 없다
투영	$P = QQ^{\mathsf{T}}$ , 최소제곱은 $\hat{\vv{x}} = Q^{\mathsf{T}}\vv{b}$
그람-슈미트	이미 만든 방향의 성분을 빼고 남은 것을 정규화
$A = QR$	$R_{ij} = \vv{q}_i^{\mathsf{T}}\vv{a}_j$ , 상삼각인 것은 절차의 순서 때문
$QR$ 최소제곱	$R\hat{\vv{x}} = Q^{\mathsf{T}}\vv{b}$ . $A^{\mathsf{T}}A$ 를 만들지 않는다

여기까지가 이 교재의 전반부이다.

돌아보면 하나의 이야기였다. $A\vv{x} = \vv{b}$ 를 푸는 법에서 출발해 소거와 분해를 배웠고, 해가 사는 공간을 정의하고 네 부분공간의 지도를 그렸으며, 각도를 들여와 해가 없는 문제에까지 답했다. 시선이 계산에서 공간으로, 공간에서 각도로 올라간 여정이었다.

다음 강의부터 시선이 한 번 더 바뀐다. 지금까지 $A$ 는 $\vv{b}$ 를 만들어 내는 도구였다. 이제부터는 $A$ 자체를 이해하려 한다. 이 행렬은 무엇을 하는가. 이 행렬이 바꾸지 않는 방향은 무엇인가. 여러 번 적용하면 어떻게 되는가.

그 물음들을 따라가다 보면 오늘 배운 직교기저를 계속 다시 만나게 된다. 대칭행렬의 고유벡터로, 푸리에의 기저 함수로, 그리고 마지막에는 특이값 분해의 두 벌 기저로.

이번 강의의 내용을 파이썬으로 확인해 보려면 L17 실습 노트북으로 넘어가면 된다. 그람-슈미트를 단계별로 기록하는 함수를 만들어 각 단계를 애니메이션으로 보고, $R$ 의 대각 아래가 정말 0인지 확인하며, $QR$ 로 푼 최소제곱이 정규방정식보다 얼마나 안전한지 조건수로 재 볼 수 있다.