4.4b Gram-Schmidt

정규직교 벡터를 이용하면 계산이 쉬워지는 장점이 있습니다. 이번 포스팅에서는  Gram-Schmidt 과정을 통해서 정규직교기저를 만드는 과정을 배워보겠습니다.

Gram-Schmidt 과정의 원리

프로젝션과 최소 자승 근사법에서 배운 식들에는 $A^{T}A$가 포함됩니다. 앞서 배운 것과 같이 정규직교($Q^{T}Q$ = $I$)를 이용하면 최소 자승 해는 $\hat{x}$ = $Q^{T}b$로 매우 간단해집니다. 이 때문에 정규직교 벡터 또는 기저를 만들고 싶은데, Gram-Schmidt 방법은 주어진 선형 독립 벡터들을 정규직교로 바꿔주는 과정입니다. 

그러면 Gram-Schmidt 과정을 설명하겠습니다.

 

Gram-Schmidt 과정은 다음과 같이 크게 두 부분으로 나눌 수 있습니다.
1) 주어진 선형 독립 벡터들을 서로 직교하도록 만든다.
2) 직교 벡터들을 각자의 길이로 나눠주어 길이가 1이 되도록 한다.

그럼 세 개의 독립 벡터 $a$, $b$, $c$가 있다고 가정 하겠습니다. Gram-Schmidt 방법에서는 먼저 세 벡터를 서로 직교하는 벡터 $A$, $B$, $C$로 만들 것입니다. 이것이 1) 과정입니다. 

 

먼저, $A$ = $a$로 첫 번째 벡터는 원래 벡터 $a$를 그대로 선택합니다.
다음은, $b$를 $A$에 수직하는 $B$로 만들겠습니다. 

이를 위해서 프로젝션에서 배운 식을 이용합니다.
$b$에서 $A$로의 프로젝션을 빼주면 $A$에 수직 한 성분만 남게 됩니다. 
즉, $B$ = $b\:-$ $\frac{A^{T}b}{A^{T}A}A$. (4.2b 직선으로의 프로젝션 참조)

 

다음 그림은 이를 시각화 하였습니다.

 
$A$와 $B$의 내적을 구하면 $A$와 $B$가 수직함을 보일 수 있습니다.
$A^{T}B$ = $A^{T}(b\:-  \frac{A^{T}b}{A^{T}A}A)$ = $A^{T}b\:-$ $A^{T}b$ 

다음은 세 번째 $c$에서 $A$와 $B$ 방향의 성분을 빼줍니다.
그러면 $A$와 $B$에 수직인 성분만 남게될 것입니다.

 

위 식과 비슷하게 다음 식을 유도할 수 있습니다.
$C$ = $c\:-  \frac{A^{T}c}{A^{T}A}A$ $-$  $\frac{B^{T}c}{B^{T}B}B$.

만약 네 번째 벡터 $d$가 있다면, $d$에서 $A$, $B$, $C$로의 프로젝션을 빼주어 $D$를 만들 수 있습니다. 더 많은 벡터가 있다면 이를 반복합니다.

이제 서로 수직인 벡터 $A$, $B$, $C$를 구했습니다.
다음은 각 벡터를 길이로 나누어 주어 단위벡터를 만듭니다.
$q_{1}$ = $A/||A||$, $q_{2}$ = $B/||B||$, $q_{3}$ = $C/||C||$.

이렇게 정규직교 벡터 $q_{1}$, $q_{2}$, $q_{3}$를 만들 수 있습니다.

Gram-Schmidt 예제

다음 세 벡터를 정규직교로 만들겠습니다.

$a$ = $\begin{pmatrix} \begin{array}{r} 1 \\ -1 \\ 0 \end{array} \end{pmatrix}$, $b$ = $\begin{pmatrix} \begin{array}{r} 2 \\ 0 \\ -2 \end{array} \end{pmatrix}$, $c$ = $\begin{pmatrix} \begin{array}{r} 3 \\ -3 \\ 3 \end{array} \end{pmatrix}$.

위 설명의 과정을 따라
$A$ = $a$.

다음은 $B$를 구합니다.

$A^{T}A$ = $\begin{pmatrix} \begin{array}{rrr} 1 & -1 & 0 \end{array} \end{pmatrix}$$\begin{pmatrix} \begin{array}{r} 1 \\ -1 \\ 0 \end{array} \end{pmatrix}$ = 2 

$A^{T}b$ = $\begin{pmatrix} \begin{array}{rrr} 1 & -1 & 0 \end{array} \end{pmatrix}$$\begin{pmatrix} \begin{array}{r} 2 \\ 0 \\ -2 \end{array} \end{pmatrix}$ = 2

따라서

$B$ = $b\:- \frac{2}{2}A$ = $\begin{pmatrix} \begin{array}{r} 1 \\ 1 \\ -2 \end{array} \end{pmatrix}$.

다음은 $C$를 구합니다.

 

다음 값들을 계산합니다.
$A^{T}c$ = 6
$B^{T}c$ = –6
$B^{T}B$ = 6
이 값들을 식에 대입하면,

$C$ = $c\:-  \frac{6}{2} A\:+\: \frac{6}{6} B$ = $\begin{pmatrix} \begin{array}{r} 1 \\ 1 \\ 1 \end{array} \end{pmatrix}$.

마지막으로 $A$, $B$, $C$를 각각 길이로 나누어줍니다.
그러면 정규직교 벡터

$q_{1}$ = $\frac{1}{2}$$\begin{pmatrix} \begin{array}{r} 1 \\ -1 \\ 0 \end{array} \end{pmatrix}$

$q_{2}$ = $\frac{1}{6}$$\begin{pmatrix} \begin{array}{r} 1 \\ 1 \\ -2 \end{array} \end{pmatrix}$

$q_{3}$ = $\frac{1}{3}$$\begin{pmatrix} \begin{array}{r} 1 \\ 1 \\ 1 \end{array} \end{pmatrix}$ 

를 구했습니다.

A = QR: QR factorization

다음 행렬 $A$는 $QR$로 분해될 수 있습니다.

$A$ = $\begin{pmatrix} \begin{array}{rrr} a & b & c \end{array} \end{pmatrix}$

= $\begin{pmatrix} \begin{array}{rrr} & & \\ q_{1} & q_{2} & q_{3} \\ & & \end{array} \end{pmatrix}$$\begin{pmatrix} \begin{array}{rrr} q_{1}^{T}a & q_{1}^{T}b & q_{1}^{T}c \\ 0 & q_{2}^{T}b & q_{2}^{T}c \\ 0 & 0 & q_{3}^{T}c \end{array} \end{pmatrix}$

 

위 예에서는

$A$ = $\begin{pmatrix} \begin{array}{rrr} 1 & 2 & 3 \\ -1 & 0 & -3 \\ 0 & -2 & 3 \end{array} \end{pmatrix}$

= $\begin{pmatrix} \begin{array}{rrr} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} & \frac{1}{\sqrt{3}} \\ -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} & \frac{1}{\sqrt{3}} \\ 0 & -\frac{2}{\sqrt{6}} & \frac{1}{\sqrt{3}} \end{array} \end{pmatrix}$$\begin{pmatrix} \begin{array}{rrr} \sqrt{2} & \sqrt{2} & \sqrt{18} \\ 0 & \sqrt{6} & -\sqrt{6} \\ 0 & 0 & \sqrt{3} \end{array} \end{pmatrix}$