기븐스 회전을 이용한 QR 분해

기븐스 회전(Givens rotation)은 QR 분해에서 중요한 역할을 하는 알고리즘 중 하나로, 대규모 행렬의 QR 분해를 효율적으로 계산하는 데 사용된다. 기븐스 회전은 주로 희소 행렬이나 대각선 요소가 중요한 행렬에 대해 효과적이다. 이 방법은 행렬의 개별 요소에 대해 회전을 적용하여 하삼각 요소를 제거하고, 결국 상삼각 행렬을 얻는 방식으로 작동한다.

기븐스 회전의 기본 개념

기븐스 회전은 2차원 평면에서 벡터를 회전시키는 방식으로 특정 요소를 0으로 만든다. 수학적으로 기븐스 회전은 단위 행렬에 대한 작은 회전 변환으로 정의된다. 회전 변환은 2차원 벡터에 대해 다음과 같이 표현된다:

$\mathbf{G}(i, j, \theta) = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}$

여기서 $\theta$ 는 회전 각도를 나타내며, 이 변환은 행렬의 특정 두 요소를 회전시켜 하나를 0으로 만든다.

기븐스 회전 행렬의 정의

기븐스 회전 행렬 $\mathbf{G}(i, j, \theta)$ 는 $n \times n$ 단위 행렬 $\mathbf{I}$ 에서 두 개의 행과 열을 회전시키는 형태로 정의된다. 행렬 $\mathbf{A}$ 의 $i$ 번째 행과 $j$ 번째 행을 회전시키는 회전 행렬 $\mathbf{G}_{ij}$ 는 다음과 같이 나타낼 수 있다:

$\mathbf{G}_{ij}(\theta) = \mathbf{I} - \left(1 - \cos\theta\right) (\mathbf{e}_i \mathbf{e}_i^T + \mathbf{e}_j \mathbf{e}_j^T) + \sin\theta (\mathbf{e}_i \mathbf{e}_j^T - \mathbf{e}_j \mathbf{e}_i^T)$

여기서 $\mathbf{e}_i$ 와 $\mathbf{e}_j$ 는 표준 단위 벡터이다.

기븐스 회전을 이용한 QR 분해의 과정

QR 분해에서 기븐스 회전의 목적은 행렬 $\mathbf{A}$ 의 하삼각 부분을 0으로 만들어 상삼각 행렬 $\mathbf{R}$ 을 얻는 것이다. 이때 회전 행렬을 순차적으로 곱하여 직교 행렬 $\mathbf{Q}$ 를 얻는다.

초기 설정: 행렬 $\mathbf{A}$ 를 상삼각 형태로 변환하기 위해, 하삼각 요소 $\mathbf{a}_{ij}$ 를 제거할 두 행 $i$ 와 $j$ 를 선택한다.
회전 각도 계산: 요소 $\mathbf{a}_{ii}$ 와 $\mathbf{a}_{ji}$ 를 사용하여 회전 각도 $\theta$ 를 계산한다. 각도는 다음과 같이 구할 수 있다:

$r = \sqrt{a_{ii}^2 + a_{ji}^2}, \quad c = \frac{a_{ii}}{r}, \quad s = \frac{a_{ji}}{r}$

여기서 $c$ 와 $s$ 는 각각 $\cos\theta$ 와 $\sin\theta$ 에 해당한다.

기븐스 회전 적용: 행렬 $\mathbf{A}$ 에 대해 회전 행렬 $\mathbf{G}_{ij}$ 를 왼쪽에서 곱하여 해당 요소를 0으로 만든다:

$\mathbf{G}_{ij} \mathbf{A}$

이 과정을 통해 행렬의 특정 하삼각 요소를 제거한다.

반복: 모든 하삼각 요소에 대해 위의 과정을 반복하여, 최종적으로 상삼각 행렬 $\mathbf{R}$ 을 얻는다.
직교 행렬 $\mathbf{Q}$ 계산: 모든 회전 행렬의 곱을 통해 직교 행렬 $\mathbf{Q}$ 를 계산한다:

$\mathbf{Q} = \mathbf{G}_1^T \mathbf{G}_2^T \dots \mathbf{G}_k^T$

여기서 $\mathbf{G}_k$ 는 각 회전 단계에서 사용된 기븐스 회전 행렬이다.

기븐스 회전의 수치적 안정성

기븐스 회전은 주로 수치적으로 안정적이며, 특히 대규모 행렬에서 효과적이다. 이는 특정 요소를 직접 0으로 만드는 방식이기 때문에, 계산 과정에서 발생할 수 있는 수치적 불안정을 최소화할 수 있다.

기븐스 회전의 효율성

기븐스 회전은 행렬의 희소성을 유지하면서 QR 분해를 수행할 수 있는 장점이 있다. 이는 행렬의 일부 요소만 수정하여 상삼각 행렬을 얻기 때문에, 기존의 비희소 행렬을 다루는 방법에 비해 계산 비용이 절감된다. 특히, 희소 행렬에서 기븐스 회전은 상당히 효율적이며, 이러한 특성은 대규모 계산에서 중요한 이점으로 작용한다.

또한, 기븐스 회전은 직교성의 보존이라는 측면에서도 우수한다. 계산 과정에서 행렬의 직교성이 유지되므로, 결과적으로 얻어진 직교 행렬 $\mathbf{Q}$ 의 성질이 정확하게 보장된다.

기븐스 회전과 그람-슈미트 정규화의 비교

기븐스 회전을 이용한 QR 분해는 그람-슈미트 정규화와 비교될 수 있다. 그람-슈미트 정규화는 기하학적 직관을 바탕으로 벡터들을 직교화시키는 방법인데, 이 방법은 직교화 과정에서 수치적 불안정성 문제를 일으킬 수 있다. 특히, 그람-슈미트 과정에서는 벡터의 길이가 매우 작은 경우, 수치 오차로 인해 직교성이 제대로 보장되지 않을 수 있다.

반면, 기븐스 회전은 벡터의 개별 요소를 회전시켜 직교 행렬을 직접적으로 계산하므로, 수치적 안정성이 상대적으로 뛰어난다. 따라서 기븐스 회전은 그람-슈미트 정규화 방법에 비해 더 신뢰할 수 있는 QR 분해를 제공한다.

기븐스 회전의 구현

기븐스 회전을 실제로 구현하는 방법을 고려할 때, 주로 사용하는 언어에 따라 코드가 다소 달라질 수 있다. 아래에 Python을 이용한 기븐스 회전의 구현 예제를 제공한다.

import numpy as np

def givens_rotation(A):
    (rows, cols) = np.shape(A)
    Q = np.identity(rows)
    R = A.copy()

    for i in range(cols):
        for j in range(i + 1, rows):
            if R[j, i] != 0:
                r = np.hypot(R[i, i], R[j, i])
                c = R[i, i] / r
                s = -R[j, i] / r

                G = np.identity(rows)
                G[[i, j], [i, j]] = c
                G[i, j] = s
                G[j, i] = -s

                R = np.dot(G, R)
                Q = np.dot(Q, G.T)

    return Q, R

A = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
Q, R = givens_rotation(A)

print("Q Matrix:")
print(Q)
print("R Matrix:")
print(R)

위 코드에서 givens_rotation 함수는 행렬 $\mathbf{A}$ 를 입력받아 직교 행렬 $\mathbf{Q}$ 와 상삼각 행렬 $\mathbf{R}$ 을 반환한다. 이 알고리즘은 $\mathbf{A}$ 의 하삼각 요소를 제거하기 위해 기븐스 회전을 적용하며, 각 회전 단계에서 $\mathbf{Q}$ 와 $\mathbf{R}$ 을 갱신한다.

기븐스 회전의 응용

기븐스 회전은 다양한 응용 분야에서 중요한 역할을 한다. 대표적인 예로는 다음과 같은 분야에서의 활용을 들 수 있다:

선형 회귀 분석: 선형 회귀 분석에서, QR 분해를 사용하여 회귀 계수를 계산할 수 있다. 특히, 기븐스 회전을 사용한 QR 분해는 데이터의 차원이 매우 큰 경우에도 안정적으로 회귀 계수를 구할 수 있다.
최소 제곱 문제 해결: QR 분해는 최소 제곱 문제를 해결하는 데 사용된다. 특히, 희소 행렬의 경우 기븐스 회전은 최소 제곱 해를 구하는 데 매우 효율적이다.
신호 처리 및 통신: 기븐스 회전은 신호 처리와 통신에서 필터링, 신호 분리, 채널 추정 등의 작업에 사용된다. 이러한 응용에서 기븐스 회전은 높은 계산 효율성과 수치적 안정성을 제공한다.

이와 같이 기븐스 회전은 수치 선형 대수학에서 매우 중요한 도구로, 다양한 실제 문제 해결에 널리 사용되고 있다.