기븐스 회전

수치해석 마지막 수정: 2026-07-12 04:11:03

1. 개요[편집]

기븐스 회전 Givens Rotation
분야	선형대수 × 수치해석
정체	2차원 평면 회전 행렬
목적	행렬 원소 하나를 정밀하게 0으로
대표 응용	QR 분해, 고유값 문제
경쟁 기법	하우스홀더 반사(Householder)

원소 하나를 저격해서 0으로 만드는 데는, 회전만 한 게 없다.

기븐스 회전(Givens rotation)은 2차원 평면에서의 회전을 나타내는 직교행렬로, 벡터나 행렬의 특정 원소를 정확히 0으로 만드는 데 쓰이는 수치선형대수의 기본 도구다. 회전은 벡터의 길이를 보존하는 직교변환이므로, 수치적으로 안정적이면서도 딱 노리는 한 원소만 골라 소거할 수 있다는 것이 최대 강점.

이름은 미국의 수학자 월러스 기븐스(Wallace Givens)에서 왔다. QR 분해나 고유값 문제에서, 행렬을 상삼각형이나 삼중대각형으로 조금씩 깎아나갈 때 이 회전을 하나씩 적용한다. 하우스홀더 반사가 열 전체를 한 방에 정리하는 “도끼”라면, 기븐스 회전은 원소를 하나씩 다듬는 “정” 같은 도구다.¹

2. 회전 행렬[편집]

$i$ 번째와 $j$ 번째 좌표축이 만드는 평면에서 각도 $\theta$ 만큼 회전하는 기븐스 회전 $G(i, j, \theta)$ 는, 단위행렬에서 네 원소만 바꾼 형태다. 핵심인 $2 \times 2$ 부분만 떼어 보면:

\begin{pmatrix} c & s \\ -s & c \end{pmatrix}, \qquad c = \cos\theta, \quad s = \sin\theta

이 행렬을 벡터 $(a, b)^\top$ 에 적용해 두 번째 성분을 0으로 만들고 싶다면, 각도를 직접 구할 필요 없이 $c$ 와 $s$ 만 정하면 된다.

c = \frac{a}{\sqrt{a^2 + b^2}}, \qquad s = \frac{b}{\sqrt{a^2 + b^2}}

이렇게 하면 $\begin{pmatrix} c & s \\ -s & c \end{pmatrix}\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} \sqrt{a^2+b^2} \\ 0 \end{pmatrix}$ 이 되어, 아래쪽 성분이 깔끔하게 소거된다. 실제 구현에서는 $\sqrt{a^2+b^2}$ 가 오버플로/언더플로하지 않도록 스케일링한 안전한 버전(예: BLAS의 drotg)을 쓴다.²

3. QR 분해: 하우스홀더 vs 기븐스[편집]

QR 분해는 행렬 $A$ 를 직교행렬 $Q$ 와 상삼각행렬 $R$ 의 곱으로 쪼개는 것이다. 기븐스 회전으로 QR을 만들려면, 대각선 아래의 원소들을 왼쪽 아래부터 하나씩 회전으로 0을 만들어 나가면 된다. 소거가 끝나 남은 상삼각행렬이 $R$ 이고, 사용한 회전들을 모아 전치하면 $Q$ 가 된다.

하우스홀더 반사와 비교하면 다음과 같다.

하우스홀더 — 한 번의 반사로 한 열 아래 전체를 소거한다. 조밀(dense) 행렬 전체를 분해할 때는 연산량이 약 2/3 수준이라 더 효율적. 밀집 행렬 QR의 기본값이다.
기븐스 — 원소를 하나씩 소거하므로 조밀 행렬에는 다소 느리지만, 이미 0인 자리를 건드리지 않는다는 결정적 장점이 있다.

즉 대부분의 원소가 이미 0인 희소행렬이나, 헤센베르크(Hessenberg)·삼중대각처럼 0이 아닌 원소가 소수인 구조에서는 기븐스가 압도적으로 유리하다. 소거할 원소가 몇 개 없으니 회전도 몇 번이면 끝나기 때문.

4. 희소성과 점진적 갱신[편집]

기븐스 회전의 진가는 국소성에 있다. 회전 하나는 두 행(또는 두 열)에만 영향을 주므로, 행렬의 나머지 부분은 손대지 않는다. 이 성질이 두 가지 실무 상황에서 빛난다.

첫째, 희소행렬의 채움(fill-in)을 최소화한다. 하우스홀더는 열 전체를 뒤섞어 0이던 자리를 다시 채워버리기 쉽지만, 기븐스는 필요한 두 행만 건드려 희소 구조를 최대한 보존한다.

둘째, 점진적 갱신(incremental update)에 이상적이다. 최소자승 문제를 풀다가 데이터가 한 줄 추가되었다고 하자. 이미 만들어둔 QR 분해를 처음부터 다시 계산할 필요 없이, 새 행에 대해 기븐스 회전 몇 번만 적용하면 $R$ 이 갱신된다. 실시간으로 데이터가 흘러 들어오는 온라인 최소자승법이나 칼만 필터, 이동 창(sliding window) 회귀에서 이 트릭이 필수다.³ 행 하나 추가에 전체 재계산은 낭비 of the century다.

5. 고유값 계산에서의 역할[편집]

기븐스 회전은 고유값 문제를 푸는 알고리즘의 심장부에도 있다. 대칭행렬의 고전적 야코비(Jacobi) 방법은 대각선 밖의 가장 큰 원소를 골라 기븐스 회전으로 0을 만드는 일을 반복해, 행렬을 점점 대각행렬로 몰아간다. 남은 대각원소가 곧 고유값. 수렴은 느리지만 병렬화가 쉽고 정확도가 높아 여전히 쓰인다.

현대적인 QR 알고리즘에서도, 행렬을 헤센베르크 형태로 만든 뒤 기븐스 회전으로 QR 반복을 값싸게 수행한다(bulge chasing). “회전으로 원소를 하나씩 밀어낸다”는 단순한 발상이, 고유값·특이값(특이값 분해) 계산의 밑바닥을 떠받치고 있는 셈이다.

6. 관련 문서[편집]

하우스홀더가 “반사(reflection)“이고 기븐스가 “회전(rotation)“인 것이 재미있는 대비다. 둘 다 직교변환이지만, 반사는 방향(orientation)을 뒤집고 회전은 보존한다. 소거 효율은 반사가 낫고, 정밀 저격은 회전이 낫다. ↩
$a$ 나 $b$ 가 너무 크면 $a^2+b^2$ 가 오버플로한다. 그래서 실무 코드는 둘 중 큰 값으로 나눠 스케일을 맞춘 뒤 제곱근을 취한다. 이런 세심함을 무시하면 멀쩡한 행렬에서 갑자기 inf가 튀어나온다. ↩
데이터 한 줄 들어올 때마다 전체 QR을 다시 돌리는 코드를 실제로 본 적이 있다면, 그 순간의 답답함을 잊지 못할 것이다. 기븐스 갱신은 $O(n^2)$ 을 $O(n)$ 으로 바꿔준다. 일단 돌려서 안 되면 그때 기븐스를 떠올리자. ↩