그람-슈미트 정규화 방법을 이용한 QR 분해

QR 분해는 정사각 행렬 $\mathbf{A}$ 를 직교 행렬 $\mathbf{Q}$ 와 상삼각 행렬 $\mathbf{R}$ 로 분해하는 기법이다. 이 장에서는 그람-슈미트 정규화 방법을 이용해 QR 분해를 수행하는 과정을 상세히 다룬다.

그람-슈미트 정규화 방법의 개요

그람-슈미트 정규화(Gram-Schmidt orthogonalization) 방법은 주어진 벡터 집합에서 직교 집합을 생성하는 과정이다. 이 방법은 선형 대수학에서 중요한 기법으로, 직교 행렬 $\mathbf{Q}$ 를 구성하는 데 사용된다.

벡터 집합 $\{\mathbf{a}_1, \mathbf{a}_2, \dots, \mathbf{a}_n\}$ 이 주어졌을 때, 이들로부터 직교 집합 $\{\mathbf{q}_1, \mathbf{q}_2, \dots, \mathbf{q}_n\}$ 을 생성하는 과정은 다음과 같다:

첫 번째 벡터 $\mathbf{q}_1$ 는 원래 벡터 $\mathbf{a}_1$ 와 동일하게 설정한다.
두 번째 벡터 $\mathbf{q}_2$ 는 $\mathbf{a}_2$ 에서 $\mathbf{q}_1$ 에 대한 투영을 제거한 후 얻는다.
일반적으로, $\mathbf{q}_k$ 는 $\mathbf{a}_k$ 에서 앞선 모든 직교 벡터들 $\mathbf{q}_1, \mathbf{q}_2, \dots, \mathbf{q}_{k-1}$ 에 대한 투영을 제거한 후 얻는다.

수식으로 표현하면, $k$ 번째 직교 벡터 $\mathbf{q}_k$ 는 다음과 같이 정의된다:

$\mathbf{q}_k = \mathbf{a}_k - \sum_{j=1}^{k-1} \text{proj}_{\mathbf{q}_j} \mathbf{a}_k$

여기서 $\text{proj}_{\mathbf{q}_j} \mathbf{a}_k$ 는 $\mathbf{a}_k$ 가 $\mathbf{q}_j$ 에 투영된 성분으로, 아래와 같이 계산된다:

$\text{proj}_{\mathbf{q}_j} \mathbf{a}_k = \frac{\mathbf{q}_j^\top \mathbf{a}_k}{\mathbf{q}_j^\top \mathbf{q}_j} \mathbf{q}_j$

이 과정은 모든 $k$ 에 대해 반복하여, $\mathbf{q}_1, \mathbf{q}_2, \dots, \mathbf{q}_n$ 이라는 직교 집합을 생성한다.

QR 분해에서 그람-슈미트 방법의 적용

QR 분해에서는 행렬 $\mathbf{A}$ 를 직교 행렬 $\mathbf{Q}$ 와 상삼각 행렬 $\mathbf{R}$ 로 분해하는데, 여기서 $\mathbf{Q}$ 는 그람-슈미트 방법을 통해 얻은 직교 벡터들로 구성된다.

$\mathbf{A}$ 를 열 벡터 $\mathbf{A} = [\mathbf{a}_1 \ \mathbf{a}_2 \ \dots \ \mathbf{a}_n]$ 로 표현하면, $\mathbf{Q}$ 는 열 벡터 $\mathbf{Q} = [\mathbf{q}_1 \ \mathbf{q}_2 \ \dots \ \mathbf{q}_n]$ 로 구성되며, $\mathbf{R}$ 은 다음과 같은 상삼각 행렬이다:

$\mathbf{R} = \begin{bmatrix} r_{11} & r_{12} & \dots & r_{1n} \\ 0 & r_{22} & \dots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & r_{nn} \end{bmatrix}$

여기서 $r_{ij}$ 는 $\mathbf{a}_j$ 가 직교 벡터 $\mathbf{q}_i$ 에 투영된 크기를 의미하며, 다음과 같이 계산된다:

$r_{ij} = \mathbf{q}_i^\top \mathbf{a}_j \quad (1 \leq i \leq j \leq n)$

QR 분해 과정의 단계별 설명

초기화: $\mathbf{A} = [\mathbf{a}_1 \ \mathbf{a}_2 \ \dots \ \mathbf{a}_n]$ 로 주어진 행렬의 첫 번째 열 $\mathbf{a}_1$ 을 가져와 $\mathbf{q}_1 = \mathbf{a}_1 / \|\mathbf{a}_1\|$ 로 설정한다. 이때 $r_{11} = \|\mathbf{a}_1\|$ 이다.
직교화: 각 $k$ 번째 열 $\mathbf{a}_k$ 에 대해, 직교 벡터 $\mathbf{q}_k$ 를 다음과 같이 생성한다:

$\mathbf{q}_k = \mathbf{a}_k - \sum_{j=1}^{k-1} r_{jk} \mathbf{q}_j$

여기서 $r_{jk} = \mathbf{q}_j^\top \mathbf{a}_k$ 로 계산한다.

정규화: $\mathbf{q}_k$ 를 정규화하여 $r_{kk}$ 를 구하고, $\mathbf{q}_k = \mathbf{q}_k / r_{kk}$ 로 설정한다.
행렬 $\mathbf{R}$ 의 구성: 상삼각 행렬 $\mathbf{R}$ 은 각 단계에서 계산된 $r_{ij}$ 값을 이용해 구성된다.

예제: QR 분해의 실제 계산

주어진 행렬 $\mathbf{A}$ 에 대해 그람-슈미트 정규화 방법을 적용하여 $\mathbf{Q}$ 와 $\mathbf{R}$ 을 구하는 과정을 예제를 통해 확인해 보자.

예제

행렬 $\mathbf{A}$ 가 다음과 같이 주어졌다고 가정하자:

$\mathbf{A} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 2 \\ 1 & 2 & 0 \end{bmatrix}$

첫 번째 열 벡터 $\mathbf{a}_1 = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$ 에 대해 $\mathbf{q}_1$ 을 구한다:

$\mathbf{q}_1 = \frac{\mathbf{a}_1}{\|\mathbf{a}_1\|} = \frac{1}{\sqrt{3}} \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$

$r_{11} = \|\mathbf{a}_1\| = \sqrt{3}$

두 번째 열 벡터 $\mathbf{a}_2 = \begin{bmatrix} 1 \\ 0 \\ 2 \end{bmatrix}$ 에 대해, $\mathbf{q}_1$ 에 대한 투영을 제거한 후 $\mathbf{q}_2$ 를 구한다:

$r_{12} = \mathbf{q}_1^\top \mathbf{a}_2 = \frac{1}{\sqrt{3}} \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}^\top \begin{bmatrix} 1 \\ 0 \\ 2 \end{bmatrix} = \frac{3}{\sqrt{3}} = \sqrt{3}$

$\mathbf{q}_2 = \mathbf{a}_2 - r_{12}\mathbf{q}_1 = \begin{bmatrix} 1 \\ 0 \\ 2 \end{bmatrix} - \sqrt{3} \cdot \frac{1}{\sqrt{3}} \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ -1 \\ 1 \end{bmatrix}$

$r_{22} = \|\mathbf{q}_2\| = \sqrt{2}, \quad \mathbf{q}_2 = \frac{1}{\sqrt{2}} \begin{bmatrix} 0 \\ -1 \\ 1 \end{bmatrix}$

세 번째 열 벡터 $\mathbf{a}_3 = \begin{bmatrix} 1 \\ 2 \\ 0 \end{bmatrix}$ 에 대해 $\mathbf{q}_1$ 과 $\mathbf{q}_2$ 에 대한 투영을 제거한 후 $\mathbf{q}_3$ 를 구한다:

$r_{13} = \mathbf{q}_1^\top \mathbf{a}_3 = \frac{1}{\sqrt{3}} \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}^\top \begin{bmatrix} 1 \\ 2 \\ 0 \end{bmatrix} = \frac{3}{\sqrt{3}} = \sqrt{3}$

$r_{23} = \mathbf{q}_2^\top \mathbf{a}_3 = \frac{1}{\sqrt{2}} \begin{bmatrix} 0 \\ -1 \\ 1 \end{bmatrix}^\top \begin{bmatrix} 1 \\ 2 \\ 0 \end{bmatrix} = -\frac{2}{\sqrt{2}} = -\sqrt{2}$

$\mathbf{q}_3 = \mathbf{a}_3 - r_{13}\mathbf{q}_1 - r_{23}\mathbf{q}_2 = \begin{bmatrix} 1 \\ 2 \\ 0 \end{bmatrix} - \sqrt{3} \cdot \frac{1}{\sqrt{3}} \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} + \sqrt{2} \cdot \frac{1}{\sqrt{2}} \begin{bmatrix} 0 \\ -1 \\ 1 \end{bmatrix}$

$= \begin{bmatrix} 1 \\ 2 \\ 0 \end{bmatrix} - \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} + \begin{bmatrix} 0 \\ -1 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}$

이전 단계에서 $\mathbf{q}_3$ 가 $\mathbf{0}$ 벡터가 되었기 때문에, 이 벡터는 더 이상 유효한 직교 벡터로 사용할 수 없다. 따라서 이 경우에는 QR 분해 과정에서 $\mathbf{A}$ 가 완전 계수(rank-deficient)인 상황을 나타낸다. 이런 경우에는 QR 분해 과정이 멈추며, 행렬 $\mathbf{R}$ 은 정사각 행렬이 아닌 더 작은 크기의 상삼각 행렬이 된다.

이 예제는 QR 분해를 수행할 때 발생할 수 있는 특수한 상황을 잘 보여준다. 따라서, $\mathbf{A}$ 가 완전 계수가 아닌 경우, 즉 행렬의 열들이 선형 독립이 아닌 경우에는 QR 분해의 결과가 달라질 수 있다.

일반적인 QR 분해 알고리즘

그람-슈미트 정규화 방법을 이용한 QR 분해의 일반적인 알고리즘을 단계별로 정리하면 다음과 같다:

입력: 행렬 $\mathbf{A} \in \mathbb{R}^{m \times n}$ (열 벡터로 구성된 행렬)
출력: 직교 행렬 $\mathbf{Q} \in \mathbb{R}^{m \times n}$ 과 상삼각 행렬 $\mathbf{R} \in \mathbb{R}^{n \times n}$
초기화: $\mathbf{Q}$ 와 $\mathbf{R}$ 을 초기화한다.
반복:
각 열 벡터 $\mathbf{a}_k$ 에 대해, $\mathbf{q}_k$ 를 그람-슈미트 방법으로 계산한다.
투영 성분을 제거하고, 직교 벡터 $\mathbf{q}_k$ 를 정규화한다.
상삼각 행렬 $\mathbf{R}$ 의 성분 $r_{jk}$ 를 계산한다.
종료: 행렬 $\mathbf{Q}$ 와 $\mathbf{R}$ 을 반환한다.

이 알고리즘은 직관적이고 단순하지만, 그람-슈미트 방법 자체가 수치적으로 불안정할 수 있다는 단점이 있다. 이로 인해, 계산 과정에서 작은 오차가 쌓이면서 직교성이 손상될 가능성이 있다. 이를 해결하기 위해 수정된 그람-슈미트 방법(modified Gram-Schmidt method)이 사용되기도 한다.

수정된 그람-슈미트 방법

수정된 그람-슈미트 방법은 수치적 안정성을 개선하기 위해 기존의 그람-슈미트 방법을 약간 변형한 방식이다. 이 방법은 각 단계마다 벡터 $\mathbf{a}_k$ 에 대한 투영을 한 번에 모두 제거하지 않고, 단계별로 투영을 제거하면서 직교화를 진행한다.

수정된 그람-슈미트 방법은 다음과 같은 절차로 진행된다:

초기화: $\mathbf{Q}$ 와 $\mathbf{R}$ 을 초기화한다.
첫 번째 벡터: 첫 번째 벡터 $\mathbf{q}_1 = \mathbf{a}_1 / \|\mathbf{a}_1\|$ 로 설정하고, $r_{11} = \|\mathbf{a}_1\|$ 을 계산한다.
반복:
각 $k$ 번째 열 벡터 $\mathbf{a}_k$ 에 대해, $\mathbf{q}_j$ (1 $\leq$ j < k)으로부터 $r_{jk}$ 를 계산하고, $\mathbf{a}_k$ 에서 해당 성분을 제거한다.
이 과정을 반복하여 투영 성분이 모두 제거된 후, $\mathbf{q}_k$ 를 정규화한다.
정규화된 $\mathbf{q}_k$ 를 $\mathbf{Q}$ 에 추가하고, 상삼각 행렬 $\mathbf{R}$ 의 성분 $r_{kk}$ 을 계산한다.
종료: 행렬 $\mathbf{Q}$ 와 $\mathbf{R}$ 을 반환한다.

수정된 그람-슈미트 방법은 기존의 방법보다 계산 오차가 덜 누적되며, 더 안정적인 결과를 제공한다. 따라서 실무에서는 이 방법이 더 자주 사용된다.

그람-슈미트 방법의 한계와 대안

그람-슈미트 방법과 수정된 그람-슈미트 방법은 개념적으로 이해하기 쉬운 QR 분해 방법이지만, 수치적 안정성 문제로 인해 실제 대규모 행렬에 적용할 때는 주의가 필요하다. 특히, 입력 행렬 $\mathbf{A}$ 의 열 벡터가 거의 선형 종속일 때 문제가 발생할 수 있다.

이러한 한계를 극복하기 위해 하우스홀더 변환(Householder transformation)이나 기븐스 회전(Givens rotation)과 같은 대안적인 QR 분해 방법이 사용되기도 한다. 이러한 방법들은 수치적으로 더 안정적이며, 대규모 행렬에 대한 QR 분해에 더 적합한다.