[ Linear Algebra, Friedberg ] 그람-슈미트 직교화 과정

Definition of orthonormal basis

$\mathsf{V}$를 내적 공간이라 하자. 이 때, $\beta\subseteq\mathsf{V}$가 다음 두 조건을 만족 할 때, 정규직교 기저라고 한다.

① $\beta$가 정규직교여야 한다.

② $\beta$가 ordered basis여야 한다.

여기서, 정규직교는 다음 두 조건을 모두 만족하는 집합을 의미한다.

$\forall v_i,~v_j\in\mathsf{V}:\left<v_i,~v_j\right>=\begin{cases}1 & \left( i=j \right )\\0 & \left(i\neq j \right )\end{cases}$

Theorem 6.3

$\mathsf{V}$를 내적공간이라 하고, $S=\left\{v_1,~v_2,\cdots,~v_k\right\}\subseteq\mathsf{V}$가 직교한다고 가정하자.

이 때, $y\in\mathrm{span}\left(S\right)$하면

$\displaystyle y=\sum_{i=1}^k \frac{\left<y,~v_i\right>}{\lVert{v_i}\rVert^2}v_i$

로 나타낼 수 있다.

$y$가 $\mathrm{span}\left(S\right)$에 속하므로 $a_1,~a_2,~\cdots,~a_k$가 존재하여 $\displaystyle y=\sum_{i=1}^k a_iv_i$로 표현할 수 있다.

이 때, 정규직교의 성질에 의해 $S$의 서로 다른 두 벡터를 내적할 시 $0$이 된다는 사실을 이용하자.

$y\ $와 $v_i\ $를 내적하면

$\left<y,~v_i\right>\\=\left<a_1v_1+a_2v_2+\cdots+a_kv_k,~v_i\right>\\=\displaystyle\sum_{j=1}^k\left<a_jv_j,~v_i\right>\\=\left<a_iv_i,~v_i\right>~\left(\because~i\neq j\Rightarrow \left<v_i,~v_j\right>=0\right)\\=a_i\lVert v_i \rVert^2$

이 된다.

따라서 $a_i=\frac{\left<y,~v_i\right>}{\lVert v_i\rVert^2}$이므로

$\displaystyle y=\sum_{i=1}^k \frac{\left<y,~v_i\right>}{\lVert{v_i}\rVert^2}v_i$ 이다.

6.3의 정리와 정규직교 기저를 합쳐보자.

$\dim\left(\mathsf{V}\right)=n$이라 하고, 정규직교기저 $\beta\subseteq\mathsf{V}$에 대해 $\beta=\left\{v_1,~v_2,~\cdots,~v_n\right\}$이라 하자.

기저의 성질에 의해, $\text{span}\left(\beta\right)=\mathsf{V}$이고, Theorem 6.3에 의해 임의의 $y\in\mathsf{V}$에 의해 $\displaystyle y=\sum_{i=1}^k \frac{\left<y,~v_i\right>}{\lVert{v_i}\rVert^2}v_i$로 나타낼 수 있다.

정규하므로 $\lVert v_i\rVert^2=1$이고, $\displaystyle y=\sum_{i=1}^k \left<y,~v_i\right>$로 나타난다.

이 때까지 우리는 계수들(위에선 $a_1,~a_2,~\cdots,~a_n$이 해당)을 구하기 위해서는 연립방정식이나 Gaussian Elimation을 사용했어야만 했다.

하지만, 정규직교기저를 활용하면 저런 복잡한 과정을 거칠 것 없이 그냥 내적만 해주면 된다는 크나큰 장점이 있다.

또한, 정규직교기저는 내적의 계산의 양을 줄여준다.

예를 들어, $x=a_1v_1+a_2v_2+\cdots+a_nv_n$이라 하고, $y=b_1v_1+b_2v_2+\cdots+b_nv_n$이라 하자.

이 때, 일반적으로 $\left<x,~y\right>$는 $\displaystyle \sum_{i=1}^n a_ib_iv_i$와는 다르다.

하지만, 정규직교기저에서는 이가 성립한다. (서로 다른 것끼리 내적할 시 0이 되는 성질때문이다)

이는, 두 벡터의 내적을 계산하는데 굉장히 빠른 시간 복잡도를 보여준다.

원래라면, $N$차원의 두 벡터의 내적을 연산하는데 소요되는 시간은 $O(N^3)$인 반면에, 정규직교기저에 한해서는 $O(N)$에 연산할 수 있다.

마지막으로 QR decomposition을 할 때도 정규기저 벡터를 활용한다. 정확하겐, 정규기저 벡터를 만드는 그람-슈미트 과정에서 유도한다.

위에서 알 수 있다시피 정규직교기저는 일반적인 기저에 비해 조건이 굉장히 많다.

정규화도 되어있어야 하고, 직교화도 되어있어야 하며, 기저 조건도 만족해야한다.

근데, 만들면 보는 일단 만들면 보는 이득이 굉장히 많다. 선형결합을 편하게 알 수 있다는게 가장 크다

그래서, 우리는 정규직교가 아닌 아무 기저 벡터나 들고, 이를 정규직교화만 할 수 있으면 된다.

이러한 과정이 Gram-Schmidt process이다.

Theorem 6.4

$\mathsf{V}$를 내적공간이라 하고, $S=\left\{w_1,~w_2,~\cdots,w_n\right\}\subseteq\mathsf{V}$이 선형 독립이라 하자. (기저일 필요는 없다)

이 때, $S'=\left\{v_1,~v_2,~\cdots,~v_n\right\}$을

$v_1=w_1,~v_k=w_k-\displaystyle \sum_{j=1}^{k-1}\frac{\left<w_k,~v_j\right>}{\lVert v_j\rVert^2}v_j\qquad for\quad 2\le k\le n$

이라 하자.

그러면, 다음 두 가지 성질이 성립한다.

① $S'$는 직교한다.

② $\text{span}(S)=\text{span}(S')$

증명이 다소 기므로 밖에 서술한다.

우리가 증명해야 하는 직교성과, 서로 생성하는 벡터공간이 동일함이다.

먼저 직교성부터 증명하자.

직교성을 증명하기 위해선 $S'$의 서로 다른 두 벡터를 들고 와서 내적했을 때 $0$이 됨을 보이면 된다.

근데..... $v_k$가 생긴게 예사롭지가 않다. $v_k$ 이전에 있는 모든 벡터들을 들고와 내적을 해야한다니....?

일반성을 잃지 않고 $i<j$라 했을 때, $\left<v_i,~v_j\right>$에서 $v_j$를 풀어서 서술했을 때 $v_i$의 요소가 확실히 있음을 알 수 있다.

만약, 이전의 벡터들이 이미 직교됨을($v_1, ~v_2,~\cdots,~v_{j-1}$까지) 모두 직교됨을 보장한다면, $v_j$와 다른 것들이 내적함을 보일 때 굉장히 편하지 않을까??

이에 근거하여 수학적 귀납법을 사용하자.

$S$가 기저일 필요는 없으니까 $\dim\left(S\right)$를 기준으로 수학적 귀납법을 사용하자.

$\dim S=1$일 땐, $S'=S$이고, 하나의 원소에 대해선 직교성을 볼 필요도 없다.

$\dim S=k$일 때 $S$로 인해 만들어진 $k$차원의 $S''$이 직교한다 하자.

이 때, 선형 독립을 유지하는 벡터 $w_{k+1}$을 생각하자. $S\cup w_{k+1}$은 동일하게 independent하므로 조건을 위반하지 않는다.

이제, 앞의 process대로 $v_{k+1}$을 추가하자.

$v_{k+1}=w_{k+1}-\displaystyle\sum_{i=1}^k \frac{\left<w_{k+1},v_i\right>}{\lVert v_i\rVert^2}v_i$이다.

이 때, $v_j\in S''$에 대해 $\left<v_{k+1},~v_j\right>$을 생각하자.

$v_i\neq v_j~\Rightarrow~\left<v_i,~v_j\right>=0$이므로

$\left<v_{k+1},~v_j\right>$에서 살아남는건 $\left<w_{k+1},~v_j\right>-\frac{\left<w_{k+1},~v_j\right>}{\lVert v_j\rVert^2}\left<v_j,~v_j\right>$이고, 정리하면 $0$이다.

따라서, 모든 벡터와 perpendicular하므로 orthogonal하다.

2번을 증명하자.

$y\in\text{span}\left(S'\right)$에 대해 그람-슈미트식을 대입하면 $w_1,~w_2,~\cdots,~w_n$에 관한 식으로 나오므로 $y\in\text{span}\left(S\right)$이고, 따라서 $\text{span}(S')\subseteq\text{span}(S)$임은 자명하다.

또한, $S'$도 independent하기 때문에 (Theorem 6.3 Corollary, 한번 증명해보면 좋을 것 같다) $\dim\left(S'\right)=\dim\left(S\right)$이고, 따라서 $\text{span}\left(S'\right)=\text{span}\left(S\right)$이다. (QED)

모든 유한차원 vector space에는 적어도 하나의 basis을 가진다.

따라서, 모든 유한차원 vector space에는 적어도 하나의 orthonormal basis가 있음을 알 수 있다.

예를 통해 적용해보자.

$w_1:=\left(1,~0,~1,~0\right),~w_2:=\left(1,~1,~1,~1\right),~w_3:=\left(0,~1,~2,~1\right)$이라 하자.

이 때, $\left\{w_1,~w_2,~w_3\right\}$은 독립이다. 따라서, 그람-슈미트 과정을 쓸 수 있다.

$S'=\left\{v_1,~v_2,~v_3\right\}$을 그람-슈미트 과정을 적용한 집합이라 하면, $v_1=w_1$이다.

$v_2=w_2-\frac{\left<w_2,~v_1\right>}{\lVert v_1\rVert^2}v_1$이고, 계산하면 $\left(1,~1,~1,~1\right)-\frac{2}{2}(1,~0,~1,~0)=(0,~1,~0,~1)$이다.

마지막으로, $v_3=w_3-\frac{\left<w_3,~v_1\right>}{\lVert v_1\rVert^2}v_1-\frac{\left<w_3,~v_2\right>}{\lVert v_2\rVert^2}v_2=(-1,~0,~1,~0)$이다.

다음 포스팅에서는 직교 여집합과, 이를 이용한 orthonormal화 replacement theorem에 대해 알아보도록 한다.