6.48 그람-슈미트 정규 직교화 과정

1. 도입

선형대수학의 많은 응용에서 정규 직교 기저의 사용은 계산을 단순화하고 수치적 안정성을 향상시킨다. 그러나 실제 문제에서 자연스럽게 주어지는 벡터들은 일반적으로 일차 독립이긴 해도 정규 직교 관계를 만족하지 않는다. 그람-슈미트 정규 직교화 과정(Gram-Schmidt orthonormalization process)은 임의의 일차 독립 벡터 집합을 정규 직교 집합으로 변환하는 체계적인 절차이며, 이는 현대 수치 선형대수학의 가장 기본적인 알고리듬 중 하나이다.

2. 직교화 문제의 정식화

$\mathbb{R}^n$ 의 일차 독립 벡터 $\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_k$ 가 주어졌다고 하자. 그람-슈미트 과정은 다음의 두 조건을 만족하는 벡터들 $\mathbf{q}_1, \mathbf{q}_2, \ldots, \mathbf{q}_k$ 를 구성한다.

정규 직교성: $\mathbf{q}_i^\top \mathbf{q}_j = \delta_{ij}$ ( $i, j = 1, 2, \ldots, k$ ).
부분 공간의 보존: 각 $j$ 에 대하여 $\mathrm{span}\{\mathbf{a}_1, \ldots, \mathbf{a}_j\} = \mathrm{span}\{\mathbf{q}_1, \ldots, \mathbf{q}_j\}$ .

두 번째 조건은 정규 직교화 과정이 점진적임을 의미한다. 즉, 각 단계에서 새로 구성된 벡터 $\mathbf{q}_j$ 는 기존의 정규 직교 벡터들과 함께 원래 벡터들이 생성하는 부분 공간을 정확히 같이 생성한다.

3. 고전적 그람-슈미트 알고리듬

고전적인 그람-슈미트 알고리듬은 다음의 단계로 구성된다.

1단계. 첫 번째 벡터를 정규화한다.

$\mathbf{q}_1 = \frac{\mathbf{a}_1}{\|\mathbf{a}_1\|}$

2단계. $j = 2, 3, \ldots, k$ 에 대하여 다음을 수행한다.

(a) $\mathbf{a}_j$ 로부터 이미 구성된 정규 직교 벡터들의 사영을 차감한다.

$\mathbf{u}_j = \mathbf{a}_j - \sum_{i=1}^{j-1} (\mathbf{q}_i^\top \mathbf{a}_j) \mathbf{q}_i$

(b) 그 결과를 정규화한다.

$\mathbf{q}_j = \frac{\mathbf{u}_j}{\|\mathbf{u}_j\|}$

이 알고리듬의 핵심 아이디어는 각 새 벡터에서 이전 벡터들의 방향에 대한 성분을 모두 차감함으로써 직교성을 보장하는 것이다.

4. 알고리듬의 정당성

그람-슈미트 알고리듬이 올바르게 작동함을 단계별로 확인하자.

부분 공간 보존: 정의로부터 $\mathbf{q}_j$ 는 $\mathbf{a}_1, \ldots, \mathbf{a}_j$ 의 일차 결합이다. 또한 $\mathbf{a}_j$ 를 $\mathbf{q}_1, \ldots, \mathbf{q}_j$ 의 일차 결합으로 표현할 수 있다.

$\mathbf{a}_j = \|\mathbf{u}_j\| \mathbf{q}_j + \sum_{i=1}^{j-1} (\mathbf{q}_i^\top \mathbf{a}_j) \mathbf{q}_i$

따라서 $\mathrm{span}\{\mathbf{a}_1, \ldots, \mathbf{a}_j\} = \mathrm{span}\{\mathbf{q}_1, \ldots, \mathbf{q}_j\}$ 가 성립한다.

정규 직교성: 귀납적으로 증명한다. $\mathbf{q}_1$ 은 단위 벡터이므로 $\mathbf{q}_1^\top \mathbf{q}_1 = 1$ 이다. $\mathbf{q}_1, \ldots, \mathbf{q}_{j-1}$ 이 정규 직교라 가정하자. $i < j$ 에 대하여

$\mathbf{q}_i^\top \mathbf{u}_j = \mathbf{q}_i^\top \mathbf{a}_j - \sum_{l=1}^{j-1} (\mathbf{q}_l^\top \mathbf{a}_j) (\mathbf{q}_i^\top \mathbf{q}_l) = \mathbf{q}_i^\top \mathbf{a}_j - \mathbf{q}_i^\top \mathbf{a}_j = 0$

이므로 $\mathbf{q}_i^\top \mathbf{q}_j = \frac{1}{\|\mathbf{u}_j\|} \mathbf{q}_i^\top \mathbf{u}_j = 0$ 이다. 또한 $\mathbf{q}_j$ 는 정의에 의하여 단위 벡터이다. $\blacksquare$

5. QR 분해와의 관계

그람-슈미트 과정은 행렬의 QR 분해와 직접적으로 연결된다. 일차 독립 벡터 $\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_n$ 을 열로 가지는 행렬을 $A \in \mathbb{R}^{m \times n}$ 이라 하자 ( $m \geq n$ ). 그람-슈미트 과정으로 얻은 정규 직교 벡터들을 열로 가지는 행렬을 $Q \in \mathbb{R}^{m \times n}$ 이라 하면, 다음의 관계가 성립한다.

$A = QR$

여기서 $R \in \mathbb{R}^{n \times n}$ 는 상삼각 행렬이며, 그 원소는 다음과 같이 정의된다.

$R_{ij} = \begin{cases} \mathbf{q}_i^\top \mathbf{a}_j & i < j \\ \|\mathbf{u}_j\| & i = j \\ 0 & i > j \end{cases}$

대각 원소 $R_{jj} = \|\mathbf{u}_j\|$ 는 모두 양수이며, 이는 분해의 유일성을 보장한다. 즉, $A$ 의 QR 분해에서 $R$ 의 대각 원소가 양수가 되도록 부호를 정하면 분해는 유일하다.

6. 수정 그람-슈미트 알고리듬

고전적 그람-슈미트 알고리듬은 수학적으로는 정확하지만, 부동 소수점 산술에서 수치적 불안정성을 보이는 단점이 있다. 특히 입력 벡터들이 거의 일차 종속에 가까운 경우 직교성이 심각하게 손상될 수 있다. 이를 개선한 것이 수정 그람-슈미트 알고리듬(modified Gram-Schmidt algorithm)이다.

수정 알고리듬에서는 사영의 차감을 한 번에 수행하는 대신, 매 단계마다 이미 계산된 새로운 직교 벡터를 즉시 활용한다.

알고리듬. $j = 1, 2, \ldots, k$ 에 대하여:

$\mathbf{u}_j = \mathbf{a}_j$ 로 초기화한다.
$i = 1, 2, \ldots, j-1$ 에 대하여:

$\mathbf{u}_j \leftarrow \mathbf{u}_j - (\mathbf{q}_i^\top \mathbf{u}_j) \mathbf{q}_i$
$\mathbf{q}_j = \mathbf{u}_j / \|\mathbf{u}_j\|$ .

이 알고리듬은 수학적으로는 고전적 알고리듬과 동등한 결과를 산출하지만, 수치적으로 훨씬 안정하다. 그 이유는 매 단계에서 차감 항이 더 작은 값을 사용하므로 자릿수 손실이 줄어들기 때문이다.

7. 두 알고리듬의 수치적 비교

고전적 알고리듬과 수정 알고리듬의 수치적 차이를 명확히 이해하는 것은 중요하다. 두 알고리듬의 출력 정규 직교성을 다음의 양으로 측정할 수 있다.

$\|Q^\top Q - I\|_F$

이론적으로 이 양은 영이어야 하지만, 부동 소수점 산술에서는 알고리듬과 입력의 조건에 따라 달라진다. 대략적으로

고전적 그람-슈미트: 오차 $O(\epsilon \kappa^2(A))$
수정 그람-슈미트: 오차 $O(\epsilon \kappa(A))$

여기서 $\epsilon$ 은 기계 정밀도이고 $\kappa(A)$ 는 입력 행렬의 조건수이다. 조건수가 큰 경우 두 알고리듬의 정확도 차이는 극적이며, 실제 응용에서는 항상 수정 알고리듬이 선호된다.

8. 재직교화

수정 그람-슈미트 알고리듬조차도 매우 병조건 문제에서는 직교성의 손실을 보일 수 있다. 이를 더욱 개선하기 위한 기법이 재직교화(reorthogonalization)이다. 이는 그람-슈미트 단계를 두 번 적용함으로써 직교성을 거의 기계 정밀도 수준으로 회복시킨다.

알고리듬. 각 $\mathbf{a}_j$ 에 대하여:

그람-슈미트 단계를 적용하여 $\mathbf{u}_j$ 를 얻는다.
$\mathbf{u}_j$ 에 대하여 다시 그람-슈미트 단계를 적용한다 (재직교화).
결과를 정규화한다.

이 두 번의 직교화를 “한 번이면 부족하지만 두 번이면 충분하다(twice is enough)“라는 격언으로 표현하기도 한다. 재직교화는 계산 비용이 두 배가 되지만, 매우 정확한 직교성을 요구하는 응용에서 필수적이다.

9. 일반화된 그람-슈미트

표준 내적 대신 다른 양정치 내적에 대해서도 그람-슈미트 과정을 일반화할 수 있다. 양정치 행렬 $W$ 에 대하여 가중 내적

$\langle \mathbf{x}, \mathbf{y} \rangle_W = \mathbf{x}^\top W \mathbf{y}$

을 정의하면, 이 내적에 대한 정규 직교화 과정은 표준 알고리듬에서 내적을 가중 내적으로 대체함으로써 얻어진다. 이는 가중 최소 제곱 문제와 일반화된 고유값 문제에서 활용된다.

또한 함수 공간에서 정의된 내적에 대해서도 유사한 알고리듬이 적용 가능하며, 이는 르장드르 다항식, 체비셰프 다항식, 라게르 다항식 등의 직교 다항식 체계를 구성하는 기초가 된다.

10. 그람-슈미트와 다른 직교화 기법의 비교

그람-슈미트 외에도 여러 직교화 기법이 존재한다. 각각은 고유한 장단점을 가진다.

기법	수치 안정성	계산 비용	적용 영역
고전적 그람-슈미트	낮음	낮음	교육, 단순 응용
수정 그람-슈미트	중간	낮음	일반 응용
하우스홀더	매우 높음	중간	QR 분해, SVD
기븐스 회전	매우 높음	높음	희소 행렬, 갱신

하우스홀더 변환과 기븐스 회전은 그람-슈미트보다 수치적으로 더 안정한 QR 분해를 제공하지만, 그람-슈미트는 점진적이고 명시적이라는 장점이 있다. 특히 새로운 벡터가 점진적으로 추가되는 상황에서는 그람-슈미트의 자연스러운 점진성이 매우 유용하다.

11. 부분 공간으로의 정사영

그람-슈미트 과정은 부분 공간으로의 직교 사영의 자연스러운 도구이다. 부분 공간 $V = \mathrm{span}\{\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_k\}$ 의 정규 직교 기저 $\{\mathbf{q}_1, \mathbf{q}_2, \ldots, \mathbf{q}_k\}$ 가 그람-슈미트 과정으로 얻어지면, 임의의 벡터 $\mathbf{x}$ 의 $V$ 위로의 직교 사영은 다음과 같이 주어진다.

$P_V \mathbf{x} = \sum_{i=1}^{k} (\mathbf{q}_i^\top \mathbf{x}) \mathbf{q}_i$

이는 최소 제곱 근사 문제와 직접적으로 연결된다. $\mathbf{x}$ 를 $V$ 의 원소로 가장 잘 근사하는 벡터는 정확히 $P_V \mathbf{x}$ 이다.

12. 최소 제곱 문제로의 응용

선형 시스템 $A\mathbf{x} = \mathbf{b}$ 의 최소 제곱 해는 그람-슈미트 과정을 통하여 얻어진 QR 분해를 활용하여 효율적으로 계산될 수 있다. $A = QR$ 이면 정규 방정식 $A^\top A \mathbf{x} = A^\top \mathbf{b}$ 는 $R^\top R \mathbf{x} = R^\top Q^\top \mathbf{b}$ 로 변환되며, $R$ 이 가역인 경우 $R\mathbf{x} = Q^\top \mathbf{b}$ 로 단순화된다. 상삼각 행렬에 대한 후진 대입을 통하여 해를 직접 계산할 수 있다.

이 접근법은 정규 방정식을 직접 형성하는 방법보다 수치적으로 훨씬 안정적이다. 그 이유는 $A^\top A$ 의 조건수가 $A$ 의 조건수의 제곱이 되어 수치 오차가 증폭되기 때문이다.

13. 점진적 업데이트와 갱신

그람-슈미트 과정의 점진적 성질은 새로운 벡터가 추가되거나 제거될 때 기존의 분해를 효율적으로 갱신할 수 있게 한다. 새 벡터 $\mathbf{a}_{k+1}$ 이 추가되는 경우 단순히 한 번의 그람-슈미트 단계를 적용하여 $\mathbf{q}_{k+1}$ 을 추가하면 된다. 이는 적응형 알고리듬과 온라인 학습에서 중요한 이점이다.

14. 로봇공학에서의 응용

14.1 좌표축 직교화

자세 추정 알고리듬에서 추정된 회전 행렬은 누적된 수치 오차로 인하여 정확한 직교성을 만족하지 않을 수 있다. 그람-슈미트 과정을 회전 행렬의 열에 적용함으로써 가까운 직교 행렬로 보정할 수 있다. 다만 이 방법은 가장 정확한 정사영은 아니며, SVD 기반 방법보다 정확도가 다소 떨어진다는 점에 유의하여야 한다.

14.2 매니퓰레이터 자코비안의 직교 분해

자코비안 행렬의 열 공간을 정규 직교 기저로 표현하면, 작업 공간에서의 운동을 직교 성분으로 분해할 수 있다. 이는 작업 우선순위 제어, 임피던스 제어의 방향 분리, 그리고 부분 작업의 독립적 처리에 활용된다.

14.3 영 공간 기저의 구성

여유 매니퓰레이터의 자코비안의 영 공간에 대한 정규 직교 기저는 그람-슈미트 과정을 통하여 효율적으로 구성될 수 있다. 이 기저는 영 공간 사영과 부차 작업의 표현에 활용된다.

14.4 점 구름 처리에서의 국소 좌표계

점 구름의 각 점 주변의 국소 좌표계를 구성할 때 그람-슈미트 과정이 사용된다. 표면 법선 방향을 시작으로 두 개의 정규 직교한 접선 방향을 구성함으로써 국소적인 정규 직교 기저가 얻어지며, 이는 표면 패치 처리와 형상 분석에 활용된다.

14.5 칼만 필터의 제곱근 형식

칼만 필터의 제곱근 형식 구현에서 공분산 행렬의 제곱근을 직교 변환을 통하여 갱신하는 절차에서 그람-슈미트 또는 그 변형이 사용된다. 이는 공분산 행렬의 양정치성을 자동으로 보존하면서 수치적 안정성을 향상시킨다.

14.6 부분 공간 식별

데이터 기반 시스템 식별에서 부분 공간을 추정하는 과정에 그람-슈미트 과정이 활용된다. 한켈 행렬의 열 공간에 대한 정규 직교 기저를 통하여 시스템의 차수와 동특성이 추출된다.

14.7 크릴로프 부분 공간 방법

대규모 선형 시스템과 고유값 문제를 푸는 크릴로프 부분 공간 방법(예: 아놀디 반복, 란초스 반복)의 핵심 단계는 그람-슈미트 과정의 일반화된 형태이다. 이 방법들은 대규모 로봇 시뮬레이션과 실시간 최적화에 활용된다.

14.8 그래프 라플라시안의 고유 분해

다중 로봇 시스템의 통신 그래프에 대한 라플라시안 행렬의 고유 분해에서 그람-슈미트 과정은 고유 공간의 기저를 구성하는 데 사용된다. 이로부터 군집의 합의 동역학과 형상 형성 능력이 분석된다.

참고문헌

Trefethen, L. N., & Bau, D. (2022). Numerical Linear Algebra (25th Anniversary ed.). SIAM.
Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
Strang, G. (2023). Introduction to Linear Algebra (6th ed.). Wellesley-Cambridge Press.
Björck, Å. (2015). Numerical Methods in Matrix Computations. Springer.
Higham, N. J. (2002). Accuracy and Stability of Numerical Algorithms (2nd ed.). SIAM.
Saad, Y. (2003). Iterative Methods for Sparse Linear Systems (2nd ed.). SIAM.

Version: 1.0