알고리즘의 단계적 설명
그람–슈미트(Gram–Schmidt) 과정은 내적공간에서 주어진 일차독립 벡터 집합으로부터, 동일한 부분공간을 생성하면서 서로 직교하는 벡터 집합(또는 정규직교 기저)을 구성하는 알고리즘이다. 이 과정은 각 단계마다 이전에 구한 직교 벡터들에 대한 정사영(projection)을 빼어 새로운 벡터가 기존 벡터들과 직교하도록 만드는 방식으로 진행된다.
주어진 일차독립 벡터 집합을 \(B = \{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n\}\)이라 하자. 그람–슈미트 과정은 다음과 같은 단계로 진행된다.
- 초기 단계: \(B\)의 첫 번째 벡터를 그대로 취하여, 직교 벡터 집합의 첫 원소로 설정한다. 즉, \[\mathbf{u}_1 = \mathbf{v}_1\] 이라고 둔다.
- 재귀적 단계: \(k=2,3,\dots,n\)에 대해, \(B\)의 \(k\)번째 벡터 \(\mathbf{v}_k\)에서 이미 구한 \(\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_{k-1}\)에 대한 정사영을 모두 빼어, \[ \mathbf{u}_k = \mathbf{v}_k - \sum_{j=1}^{k-1} \frac{\langle \mathbf{v}_k,\, \mathbf{u}_j \rangle}{\langle \mathbf{u}_j,\, \mathbf{u}_j \rangle}\,\mathbf{u}_j \] 라고 둔다. 이렇게 얻은 \(\mathbf{u}_k\)는 \(\mathbf{u}_1, \dots, \mathbf{u}_{k-1}\)와 직교하게 된다. 만약 \(\mathbf{u}_k = \mathbf{0}\)가 된다면, 이는 원래 벡터 집합 \(B\)가 일차독립이 아님을 의미한다.
- 정규화 (선택 사항): 만약 정규직교 기저(orthonormal basis)가 필요하다면, 각 \(\mathbf{u}_k\)를 그 노름으로 나누어 \[ \mathbf{w}_k = \frac{\mathbf{u}_k}{\|\mathbf{u}_k\|}, \] 를 정의한다. 그러면 \(\{\mathbf{w}_1, \mathbf{w}_2, \dots, \mathbf{w}_n\}\)는 정규직교 기저가 된다.
정리 1. (그람–슈미트 과정의 핵심 공식)
내적공간 \(V\)의 일차독립 벡터 집합 \(B = \{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n\}\)에 대하여, 그람–슈미트 과정으로 얻은 직교 벡터 \(\{\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_n\}\)는 다음과 같이 재귀적으로 정의된다.
\[ \mathbf{u}_1 = \mathbf{v}_1,\quad \mathbf{u}_k = \mathbf{v}_k - \sum_{j=1}^{k-1} \frac{\langle \mathbf{v}_k,\, \mathbf{u}_j \rangle}{\langle \mathbf{u}_j,\, \mathbf{u}_j \rangle}\,\mathbf{u}_j \quad (k=2,\dots,n). \]
만약 정규직교 기저가 필요하면, 각 \(\mathbf{u}_k\)를 \(\|\mathbf{u}_k\|\)로 나누어
\[ \mathbf{w}_k = \frac{\mathbf{u}_k}{\|\mathbf{u}_k\|},\quad (k=1,\dots,n) \]
로 정의한다.
보기 1.
\(\mathbb{R}^2\)에서 벡터 \(\mathbf{v}_1 = (1, 1)\)과 \(\mathbf{v}_2 = (1, -1)\)로 구성된 집합 \(B\)가 주어졌다고 하자. 그람–슈미트 과정을 적용하면,
- \(\mathbf{u}_1 = \mathbf{v}_1 = (1, 1)\).
- \(\mathbf{u}_2 = \mathbf{v}_2 - \frac{\langle \mathbf{v}_2,\, \mathbf{u}_1 \rangle}{\langle \mathbf{u}_1,\, \mathbf{u}_1 \rangle}\,\mathbf{u}_1\).
계산하면, \(\langle \mathbf{v}_2, \mathbf{u}_1 \rangle = 1\times1 + (-1)\times1 = 0\)이므로, \(\mathbf{u}_2 = \mathbf{v}_2 = (1,-1)\).
따라서, \(B\) 자체가 이미 직교 집합임을 알 수 있다. 만약 정규직교 기저를 원한다면, 각각의 노름을 계산하여 정규화하면 된다. \(\|\mathbf{u}_1\|=\sqrt{1^2+1^2}=\sqrt{2}\), \(\|\mathbf{u}_2\|=\sqrt{1^2+(-1)^2}=\sqrt{2}\)이므로, 정규직교 기저는 \[\mathbf{w}_1 = \left(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}\right),\quad \mathbf{w}_2 = \left(\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\right)\] 이다.
보기 2.
\(\mathbb{R}^3\)에서 임의의 기저 \(\mathbf{v}_1 = (1, 1, 0)\), \(\mathbf{v}_2 = (1, 0, 1)\), \(\mathbf{v}_3 = (0, 1, 1)\)이 주어졌다고 하자. 그람–슈미트 과정을 적용하여 직교 기저를 구하는 과정을 살펴보면,
- \(\mathbf{u}_1 = \mathbf{v}_1 = (1,1,0)\).
- \(\mathbf{u}_2 = \mathbf{v}_2 - \frac{\langle \mathbf{v}_2,\, \mathbf{u}_1 \rangle}{\langle \mathbf{u}_1,\, \mathbf{u}_1 \rangle}\,\mathbf{u}_1\).
계산하면, \(\langle \mathbf{v}_2, \mathbf{u}_1 \rangle = 1\times1+0\times1+1\times0 = 1\)이고, \(\langle \mathbf{u}_1, \mathbf{u}_1 \rangle = 1^2+1^2+0^2 = 2\).
따라서, \(\mathbf{u}_2 = (1,0,1) - \frac{1}{2}(1,1,0) = \left(1-\frac{1}{2},\, 0-\frac{1}{2},\, 1-0\right) = \left(\frac{1}{2}, -\frac{1}{2}, 1\right).\) - \(\mathbf{u}_3 = \mathbf{v}_3 - \frac{\langle \mathbf{v}_3,\, \mathbf{u}_1 \rangle}{\langle \mathbf{u}_1,\, \mathbf{u}_1 \rangle}\,\mathbf{u}_1 - \frac{\langle \mathbf{v}_3,\, \mathbf{u}_2 \rangle}{\langle \mathbf{u}_2,\, \mathbf{u}_2 \rangle}\,\mathbf{u}_2\).
각 내적을 계산하여 \(\mathbf{u}_3\)를 구하면, 결과적으로 \(\{\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3\}\)가 \(\mathbb{R}^3\)의 직교 기저가 된다.
각 벡터를 정규화하면, 정규직교 기저도 쉽게 얻을 수 있다.
이와 같이, 그람–슈미트 과정은 주어진 일차독립 벡터 집합으로부터 직교(또는 정규직교) 기저를 단계적으로 구성하는 효과적인 알고리즘이다. 이 과정은 내적공간에서 기저 변환 및 정사영, 직교 분해 등 다양한 문제의 해법으로 이어지며, 실용적 계산과 이론적 분석 모두에 널리 활용된다.
다른 벡터공간에서의 예
그람–슈미트 과정은 유클리드 공간뿐 아니라, 다항식 공간이나 함수 공간과 같이 내적이 정의된 다양한 벡터공간에서도 적용할 수 있다. 다음은 두 가지 색다른 공간에서 그람–슈미트 과정을 이용하여 직교(또는 정규직교) 기저를 구성하는 예시이다.
보기 3. (다항식 공간 \(P_2(\mathbb{R})\)에서의 그람–슈미트 과정)
\(P_2(\mathbb{R})\)는 차수가 최대 2인 모든 실수 다항식의 집합으로, \(1\), \(x\), \(x^2\)를 기저로 갖는다. 내적은 다음과 같이 정의한다. \[\langle p, q \rangle = \int_{0}^{1} p(x) \, q(x) \, dx.\] 그람–슈미트 과정을 통해 \(\{1, x, x^2\}\)로부터 직교 기저를 구성하는 과정을 단계별로 살펴보자.
- 첫 번째 벡터: \[u_0(x) = 1.\]
- 두 번째 벡터: \[\begin{aligned} u_1(x) &= x - \frac{\langle x, u_0 \rangle}{\langle u_0, u_0 \rangle} \, u_0(x).\\ \langle x, u_0 \rangle &= \int_{0}^{1} x \, dx = \frac{1}{2} \text{ and } \langle u_0, u_0 \rangle = \int_{0}^{1} 1\,dx = 1. \end{aligned}\] 따라서\[u_1(x) = x - \frac{1}{2}.\]
- 세 번째 벡터: \[\begin{aligned} &u_2(x) = x^2 - \frac{\langle x^2, u_0 \rangle}{\langle u_0, u_0 \rangle}\,u_0(x) - \frac{\langle x^2, u_1 \rangle}{\langle u_1, u_1 \rangle}\,u_1(x).\\ &\langle x^2, u_0 \rangle = \int_{0}^{1} x^2\,dx = \frac{1}{3}.\\ &\langle u_1, u_1 \rangle = \int_{0}^{1} \left(x-\frac{1}{2}\right)^2 dx = \frac{1}{12}.\\ &\langle x^2, u_1 \rangle = \int_{0}^{1} x^2\left(x-\frac{1}{2}\right)dx = \frac{1}{12}. \end{aligned}\] 따라서 \[u_2(x) = x^2 - \frac{1}{3} - \frac{\frac{1}{12}}{\frac{1}{12}}\left(x-\frac{1}{2}\right) = x^2 - \frac{1}{3} - \left(x-\frac{1}{2}\right).\] 정리하면, \[u_2(x) = x^2 - x + \frac{1}{6}.\]
따라서, 직교 기저는 \[\left\{u_0(x)=1,\, u_1(x)=x-\frac{1}{2},\, u_2(x)=x^2-x+\frac{1}{6}\right\}\]이 된다. 만약 정규직교 기저가 필요하다면, 각 \(u_i(x)\)를 그 노름으로 나누어 \[w_i(x) = \frac{u_i(x)}{\|u_i\|}\]로 정규화하면 된다.
보기 4. (함수 공간 \(L^2([-\pi,\pi])\)에서의 그람–슈미트 과정)
\(L^2([-\pi,\pi])\)는 구간 \([-\pi,\pi]\)에서 정의된 제곱 적분 가능한 함수들의 공간이며, 내적은 \[\langle f, g \rangle = \int_{-\pi}^{\pi} f(x) \, g(x) \, dx\]로 정의한다.
이 공간에서, 다음 세 함수 \[\{f_1(x)=1,\, f_2(x)=x,\, f_3(x)=x^2\}\]는 일차독립이지만, 서로 직교하지 않다. 그람–슈미트 과정을 적용하여 직교 기저를 구성하는 과정을 간략히 살펴보자.
- 첫 번째 함수: \[u_1(x) = f_1(x) = 1.\]
- 두 번째 함수: \[ \begin{aligned} &u_2(x) = f_2(x) - \frac{\langle f_2, u_1 \rangle}{\langle u_1, u_1 \rangle}\, u_1(x).\\ &\langle f_2, u_1 \rangle = \int_{-\pi}^{\pi} x\,dx = 0,\\ &\langle u_1, u_1 \rangle = \int_{-\pi}^{\pi} 1\,dx = 2\pi . \end{aligned}\] 따라서 \[u_2(x) = x.\]
- 세 번째 함수: \[\begin{aligned} &u_3(x) = f_3(x) - \frac{\langle f_3, u_1 \rangle}{\langle u_1, u_1 \rangle}\, u_1(x) - \frac{\langle f_3, u_2 \rangle}{\langle u_2, u_2 \rangle}\, u_2(x).\\ &\langle f_3, u_1 \rangle = \int_{-\pi}^{\pi} x^2\,dx = \frac{2\pi^3}{3},\\ &\langle u_1, u_1 \rangle = 2\pi ,\\ &\langle f_3, u_2 \rangle = \int_{-\pi}^{\pi} x^3\,dx = 0 ,\\ &\langle u_2, u_2 \rangle = \int_{-\pi}^{\pi} x^2\,dx = \frac{2\pi^3}{3}. \end{aligned}\] 따라서 \[u_3(x) = x^2 - \frac{\frac{2\pi^3}{3}}{2\pi} \cdot 1 - 0\cdot x = x^2 - \frac{\pi^2}{3}.\]
따라서 \(L^2([-\pi,\pi])\)의 부분공간 \( \text{span}\{1,x,x^2\}\)에 대해, 그람–슈미트 과정을 통해 얻은 직교 기저는 \[ \left\{u_1(x)=1,\, u_2(x)=x,\, u_3(x)=x^2-\frac{\pi^2}{3}\right\}\] 이다. 정규직교 기저를 원하면 각 함수에 대해 노름을 계산하여 정규화하면 된다.
이와 같이, 그람–슈미트 과정은 다항식 공간이나 함수 공간과 같이 표준 좌표계가 아닌, 다양한 내적공간에서도 적용 가능하며, 주어진 기저를 직교(정규직교) 기저로 변환하여, 내적, 거리, 투영 등의 기하학적 개념을 보다 쉽게 다룰 수 있도록 한다.
