맨위로가기

기븐스 회전

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

기븐스 회전은 수학에서 사용되는 행렬로, 특정 위치의 값을 0으로 만드는 데 활용된다. 이 회전은 주로 QR 분해와 같은 행렬 분해, 고윳값 계산, 클리포드 대수 등 다양한 분야에서 사용된다. 3차원 공간에서의 기븐스 회전은 세 가지 기본 회전 행렬로 표현되며, 이들을 조합하여 모든 회전 행렬을 생성할 수 있다. 기븐스 회전은 안정적인 계산이 가능하며, 병렬화가 용이하고 희소 행렬에 효율적이라는 장점이 있다.

더 읽어볼만한 페이지

  • 3차원 회전 - 방향
    방향은 2차원, 3차원 공간에서 방향 벡터로 표현되며, 단위 벡터, 각도(편각), 방향각, 방위각, 방향 코사인 등으로 나타낼 수 있고, 언어적으로는 가로세로, 상하, 전후, 좌우와 같은 상대적인 표현이 사용되기도 한다.
  • 3차원 회전 - 오일러 각
    오일러 각은 레온하르트 오일러가 소개한 3차원 공간 좌표계의 회전으로 강체의 방향을 나타내는 세 개의 각도이며, 로봇 제어 등 기기 제어 분야에서 널리 쓰이고, 회전축 순서에 따라 정오일러 각과 테이트-브라이언 각으로 나뉜다.
  • 수치선형대수학 - 가우스 소거법
    가우스 소거법은 연립 일차 방정식의 해를 구하기 위해 행렬을 사다리꼴로 변환하는 알고리즘이며, 기본 행 연산을 통해 전진 소거와 후퇴 대입 단계를 거쳐 해를 계산하고, 행렬식 계산 등 다양한 분야에 응용된다.
  • 수치선형대수학 - LINPACK
    LINPACK은 부동소수점 연산 성능을 평가하는 벤치마크 프로그램이자 FORTRAN 라이브러리로, 슈퍼컴퓨터 성능 측정 기준으로 사용되는 HPLinpack 벤치마크의 기반이 되었으며, TOP500 목록에서 고성능 컴퓨터 순위를 결정하는 데 기여한다.
  • 행렬 - 스핀 (물리학)
    스핀은 양자역학적 각운동량으로, 양자화된 값을 가지며 자기 쌍극자 모멘트를 유발하여 다양한 분야에 응용되고 스핀트로닉스 기술 발전에 기여하지만, 전자의 스핀 기원은 아직 완전히 밝혀지지 않았다.
  • 행렬 - 파울리 행렬
    파울리 행렬은 양자역학에서 스핀을 나타내는 데 사용되는 에르미트 행렬이자 유니타리 행렬로, 행렬식은 -1이고 대각합은 0이며, 리 대수의 생성원이자 파울리 벡터로 정의되어 다양한 물리학 분야에서 활용된다.
기븐스 회전
개요
유형선형 변환
공간R^2
연관 분야수치해석, 선형 대수학
정의
정의벡터 공간의 기저를 보존하는 회전 변환
특징2차원 공간에서 특정 각도만큼 벡터를 회전시키는 데 사용됨
표현
행렬 표현G = cos(θ), -sin(θ)], [sin(θ), cos(θ)
변수θ: 회전 각도
활용
활용 분야QR 분해
특이값 분해
고유값 알고리즘
설명수치 안정성이 뛰어나고 병렬 처리에 적합함
관련 항목
관련 항목회전 행렬
하우스홀더 변환
수치 선형 대수

2. 성질

기븐스 회전 행렬의 전치 행렬을 사용하여 벡터를 변환하면 다음과 같은 성질을 만족한다.



\begin{pmatrix}

c & s \\


  • s & c \\

\end{pmatrix}^{T}

\begin{pmatrix}

a \\

b

\end{pmatrix}

=

\begin{pmatrix}

c & -s \\

s & c \\

\end{pmatrix}

\begin{pmatrix}

a \\

b

\end{pmatrix}

=

\begin{pmatrix}

r \\

0

\end{pmatrix}



여기서 각 변수는 다음과 같이 정의된다.

r= {\sqrt{a^2+b^2}} (벡터 (a, b)의 크기)

c = }

s = }

이는 기븐스 회전을 이용하여 벡터의 특정 성분(여기서는 두 번째 성분 b)을 0으로 만들 수 있음을 보여준다. 이때 사용되는 c와 s는 각각 특정 각도 \theta에 대한 코사인 (\cos \theta)과 사인 (\sin \theta) 값에 해당한다.

3. 행렬 표현

기븐스 회전은 다음과 같은 형태의 행렬로 나타낼 수 있다.

:G(i, j, \theta) =

\begin{bmatrix} 1 & \cdots & 0 & \cdots & 0 & \cdots & 0 \\

\vdots & \ddots & \vdots & & \vdots & & \vdots \\

0 & \cdots & c & \cdots & -s & \cdots & 0 \\

\vdots & & \vdots & \ddots & \vdots & & \vdots \\

0 & \cdots & s & \cdots & c & \cdots & 0 \\

\vdots & & \vdots & & \vdots & \ddots & \vdots \\

0 & \cdots & 0 & \cdots & 0 & \cdots & 1

\end{bmatrix},

여기서 ''c'' = cos ''θ''와 ''s'' = sin ''θ''는 ''i''번째 행과 ''j''번째 열의 교차점에 나타난다. 즉, 고정된 ''i'' > ''j''에 대해 기븐스 행렬의 0이 아닌 요소는 다음과 같다.

:\begin{align}

g_{kk} &{}= 1 \qquad \text{for} \ k \ne i,\,j\\

g_{kk} &{}= c \qquad \text{for} \ k = i,\,j\\

g_{ji} &{} = -g_{ij}= -s\\

\end{align}

곱 ''G''(''i'', ''j'', ''θ'')'''x'''는 ''θ'' 라디안으로 (''i'', ''j'') 평면에서 벡터 '''x'''의 반시계 방향 회전을 나타내므로 기븐스 회전이라는 이름이 붙었다.

4. 안정적인 계산

기븐스 회전 행렬 ''G''(''i'', ''j'', ''θ'')가 다른 행렬 ''A''의 왼쪽에 곱해지면, 즉 ''G A'' 연산에서는 ''A''의 ''i''번째 행과 ''j''번째 행만 영향을 받는다. 따라서 문제는 주어진 ''a''와 ''b''에 대해 다음 식을 만족하는 ''c'' = cos ''θ''와 ''s'' = -sin ''θ''를 찾는 것으로 단순화할 수 있다.

: \begin{bmatrix} c & -s \\ s & c \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} r \\ 0 \end{bmatrix}

여기서 r = \sqrt{a^2 + b^2}는 벡터 (''a'',''b'')의 길이이다.

''θ''를 직접 계산하는 경우는 거의 없으며, 대신 ''c''와 ''s''를 직접 구한다. 가장 간단한 해는 다음과 같다.

:\begin{align}

c &{}\larr a / r \\

s &{}\larr -b / r.

\end{align}[1]

하지만 ''r''을 계산하는 과정에서 오버플로나 언더플로가 발생할 수 있다. 이 문제를 피하기 위해 골럽(Golub)과 밴 로안(Van Loan)이 제시한 방법[1]이 있으며, 이는 여러 프로그래밍 언어에서 hypot 함수로 구현되어 있다.

다음은 실수에 대한 기븐스 회전을 최소한으로 구현한 포트란 코드 예시이다. 입력값 'a' 또는 'b'가 0인 경우가 많다면, 여기에 제시된 방법처럼 코드를 최적화할 수 있다.



subroutine givens_rotation(a, b, c, s, r)

real a, b, c, s, r

real h, d

if (b .ne. 0.0) then

h = hypot(a, b)

d = 1.0 / h

c = abs(a) * d

s = sign(d, a) * b

r = sign(1.0, a) * h

else

c = 1.0

s = 0.0

r = a

end if

return

end



또한, 에드워드 앤더슨(Edward Anderson)이 LAPACK을 개선하는 과정에서 발견한 중요한 수치적 고려 사항은 연속성이다. 이를 만족시키려면 ''r''이 항상 양수가 되도록 해야 한다.[2] 다음은 이 알고리즘을 구현한 MATLAB/GNU Octave 코드이다.



function [c, s, r] = givens_rotation(a, b)

if b == 0;

c = sign(a);

if (c == 0);

c = 1.0; % 다른 언어와 달리 MatLab의 sign 함수는 입력 0에 대해 0을 반환한다.

end;

s = 0;

r = abs(a);

elseif a == 0;

c = 0;

s = -sign(b);

r = abs(b);

elseif abs(a) > abs(b);

t = b / a;

u = sign(a) * sqrt(1 + t * t);

c = 1 / u;

s = -c * t;

r = a * u;

else

t = a / b;

u = sign(b) * sqrt(1 + t * t);

s = -1 / u;

c = t / u;

r = b * u;

end

end



IEEE 754 표준의 `copysign(x,y)` 함수는 `y`의 부호를 `x`에 안전하고 효율적으로 복사하는 방법을 제공한다. 이 함수를 사용할 수 없다면, 절댓값 함수 `abs`와 부호 함수 `sgn`을 이용하여 `abs(''x'') * sgn(''y'')` 형태로 구현하는 것이 대안이 될 수 있다.

5. 행렬에 대한 작용

기븐스 회전은 행렬에 왼쪽 또는 오른쪽에서 곱해져 각각 행 연산 또는 열 연산으로 작용할 수 있다.

왼쪽에서 곱하는 행 연산은 특정 두 행 사이에서 데이터를 이동시키지만, 항상 같은 열 내에서 이루어진다. 이 연산은 영향을 받는 두 행의 각 열에 해당하는 요소 쌍을 하나의 벡터로 간주하고, 이를 특정 각도만큼 회전시키는 효과를 가진다. 행 추가 연산과 달리 기븐스 회전은 영향을 받는 두 행 모두를 변경시킨다.

오른쪽에서 곱하는 열 연산은 특정 두 열 사이에서 데이터를 이동시키며, 항상 같은 행 내에서 이루어진다. 행 연산과 유사하게, 영향을 받는 두 열의 각 행에 해당하는 요소 쌍을 벡터로 보고 동일한 각도로 회전시킨다.

또한, 행렬 유사성을 유지해야 하는 일부 알고리즘에서는 기븐스 회전을 켤레 작용으로 적용하기도 한다. 이는 특정 두 행에 대해 회전을 적용한 후(왼쪽 곱셈), 이어서 동일한 두 열에 대해서도 같은 각도로 회전을 적용하는(오른쪽 곱셈) 방식이다. 야코비 회전은 이러한 켤레 작용을 이용하여 행렬의 특정 비대각 요소를 0으로 만드는 대표적인 예시다.

수치 선형 대수에서 기븐스 회전의 주된 용도는 행렬의 특정 요소를 0으로 만드는 것이다. 이는 행렬의 QR 분해 계산 등에 효과적으로 활용된다. 기븐스 회전은 하우스홀더 변환과 비교했을 때, 각 회전 연산을 독립적으로 수행할 수 있어 병렬 처리에 유리하며, 희소 행렬에 적용할 경우 연산 효율성이 더 높다는 장점을 가진다.

5. 1. 행 연산

행렬에 기븐스 회전을 왼쪽에서 곱하는 것은 행 연산으로 작용한다. 이 연산은 행 사이에서 데이터를 이동시키지만, 항상 같은 열 안에서만 이루어진다. 행 추가 연산과는 다르게, 기븐스 회전은 영향을 받는 두 행 모두를 변경시킨다. 이것이 '회전'으로 불리는 이유를 이해하기 위해, 영향을 받는 두 행을 각각 벡터 (x_1, x_2, \dots, x_n)과 (y_1, y_2, \dots, y_n)으로 표현할 수 있다.



\begin{bmatrix}

\vdots & \vdots & \ddots & \vdots \\

x_1 & x_2 & \dots & x_n \\

\vdots & \vdots & \ddots & \vdots \\

y_1 & y_2 & \dots & y_n \\

\vdots & \vdots & \ddots & \vdots

\end{bmatrix}



기븐스 회전의 효과는 각 열 k에 대해 벡터 (x_k, y_k)를 특정 각도로 회전시키는 것과 같다. 알고리즘에서는 종종 특정 위치의 요소가 0이 되도록 이 회전 각도를 선택하며, 다른 열에서 발생하는 변화는 부수적인 결과로 받아들여진다.

수치 선형 대수에서 기븐스 회전을 이용한 행 연산은 벡터나 행렬의 특정 요소를 0으로 만드는 데 주로 사용된다. 예를 들어, 행렬의 QR 분해를 계산하는 과정에서 활용될 수 있다. 하우스홀더 변환과 비교했을 때 기븐스 회전은 병렬 처리가 용이하고, 희소 행렬의 경우 연산 횟수가 더 적다는 장점이 있다.

5. 2. 열 연산

행렬에 작용하는 기븐스 회전은 오른쪽에서 열 연산으로 작용할 수도 있다. 이 경우, 두 열 사이에서 데이터가 이동하지만 항상 같은 행 내에서 이루어진다. 행 연산의 경우와 마찬가지로, 각 행의 해당 열에 위치한 요소 쌍 (x_k,y_k)를 동일한 각도로 회전시킨다. 이때 행렬에서의 요소 배치는 다음과 같다.



\begin{bmatrix}

\dots & x_1 & \dots & y_1 & \dots \\

\dots & x_2 & \dots & y_2 & \dots \\

\ddots & \vdots & \ddots & \vdots & \ddots \\

\dots & x_n & \dots & y_n & \dots

\end{bmatrix}



일부 알고리즘, 특히 행렬 유사성을 유지하는 데 관련된 알고리즘은 기븐스 회전을 켤레 작용으로 적용한다. 즉, 두 행 사이에서 특정 각도로 회전하고, 이어서 해당 열 사이에서도 동일한 각도로 회전하는 방식이다. 이 경우, 행과 열 회전 모두의 영향을 받는 네 개의 요소에 대한 변환은 더 복잡하다. 야코비 회전은 이러한 켤레 작용을 통해 해당 네 요소 중 두 개의 비대각(off-diagonal) 요소를 0으로 만드는 데 사용된다.

수치 선형 대수에서 기븐스 회전은 주로 벡터나 행렬의 특정 성분을 0으로 만드는 데 사용된다. 이러한 특징은 행렬의 QR 분해 계산 등에 유용하다. 하우스홀더 변환과 비교할 때, 기븐스 회전은 병렬 처리가 더 쉽고, 특히 희소 행렬에 적용할 경우 연산량이 더 적을 수 있다는 장점이 있다.

5. 3. 켤레 작용

행렬에 기븐스 회전을 적용하는 방식은 크게 세 가지로 나눌 수 있다.

첫째, 행렬의 왼쪽에 기븐스 회전 행렬을 곱하는 것은 행 연산에 해당한다. 이는 특정 두 행 사이에서 데이터를 이동시키는 연산으로, 항상 같은 열 안에서만 데이터가 교환된다. 예를 들어, i행과 j행에 대한 기븐스 회전을 적용하면, 각 k열에 대해 i행의 k번째 요소(x_k)와 j행의 k번째 요소(y_k)로 이루어진 벡터 (x_k, y_k)가 특정 각도 \theta만큼 회전하게 된다. 이 연산은 행 추가 연산과 달리, 영향을 받는 두 행의 모든 요소가 변경될 수 있다.



G(i, j, \theta) \begin{bmatrix} \vdots \\ x \\ \vdots \\ y \\ \vdots \end{bmatrix} = \begin{bmatrix} \vdots \\ x' \\ \vdots \\ y' \\ \vdots \end{bmatrix} \quad \text{ (여기서 } x, y \text{는 행 벡터)}



알고리즘에서는 종종 특정 위치의 요소를 0으로 만들기 위해 이 회전 각도 \theta를 선택하며, 다른 요소들의 변화는 부수적인 결과로 받아들여진다.

둘째, 행렬의 오른쪽에 기븐스 회전 행렬을 곱하는 것은 열 연산에 해당한다. 이는 특정 두 열 사이에서 데이터를 이동시키는 연산으로, 항상 같은 행 안에서만 데이터가 교환된다. 예를 들어, i열과 j열에 대한 기븐스 회전을 적용하면, 각 k행에 대해 i열의 k번째 요소(x_k)와 j열의 k번째 요소(y_k)로 이루어진 벡터 (x_k, y_k)가 특정 각도 \theta만큼 회전하게 된다.



\begin{bmatrix} \dots & x & \dots & y & \dots \end{bmatrix} G(i, j, \theta)^T = \begin{bmatrix} \dots & x' & \dots & y' & \dots \end{bmatrix} \quad \text{ (여기서 } x, y \text{는 열 벡터)}



셋째, 켤레 작용은 특정 알고리즘, 특히 행렬 유사성을 보존해야 하는 경우에 사용된다. 이는 행렬 A에 대해 G A G^T 형태로 기븐스 회전을 적용하는 것을 의미한다. 즉, 특정 두 행(i행, j행)에 대해 각도 \theta로 회전하고(왼쪽 곱셈 G), 동시에 해당 두 열(i열, j열)에 대해서도 동일한 각도 \theta로 회전하는(오른쪽 곱셈 G^T) 연산이다. 이 경우, 두 회전의 영향을 동시에 받는 네 개의 요소(a_{ii}, a_{ij}, a_{ji}, a_{jj})에 대한 변환은 행 연산이나 열 연산만 적용할 때보다 더 복잡하다. 야코비 회전은 이러한 켤레 작용을 이용하여 대칭 행렬의 비대각 요소 두 개(a_{ij}와 a_{ji})를 0으로 만드는 대표적인 예시다.

수치 선형 대수 분야에서 기븐스 회전은 주로 벡터나 행렬의 특정 성분을 0으로 만드는 데 활용된다. 이러한 성질은 행렬의 QR 분해를 계산하는 과정 등에서 유용하게 사용된다. 기븐스 회전은 하우스홀더 변환과 비교했을 때 몇 가지 장점을 가진다. 첫째, 각 회전 연산이 독립적으로 수행될 수 있어 병렬 처리에 유리하다. 둘째, 희소 행렬(대부분의 요소가 0인 행렬)의 경우, 0이 아닌 요소에만 연산을 적용할 수 있어 계산 효율성이 높을 수 있다.

6. 3차원 기븐스 회전

3차원 공간에는 세 가지 기본적인 기븐스 회전이 있다. 각 회전은 좌표축 중 하나를 기준으로 수행된다.


  • '''X축 기준 회전:'''



R_X(\theta) =

\begin{bmatrix}

1 & 0 & 0 \\

0 & \cos \theta & -\sin \theta \\

0 & \sin \theta & \cos \theta

\end{bmatrix}


  • '''Y축 기준 회전:'''



R_Y(\theta) =

\begin{bmatrix}

\cos \theta & 0 & -\sin \theta \\

0 & 1 & 0 \\

\sin \theta & 0 & \cos \theta

\end{bmatrix}


  • '''Z축 기준 회전:'''



R_Z(\theta) =

\begin{bmatrix}

\cos \theta & -\sin \theta & 0 \\

\sin \theta & \cos \theta & 0 \\

0 & 0 & 1

\end{bmatrix}



이 회전들은 자기사상이므로 원하는 만큼 여러 번 서로 합성할 수 있다. 다만, 행렬 곱셈과 마찬가지로 회전의 순서가 중요하며, 일반적으로 교환 법칙이 성립하지 않는다(g \circ f \neq f \circ g).

데번포트의 체인 회전 정리에 따르면, 이 세 가지 기본 기븐스 회전을 적절한 순서로 합성하여 3차원 공간에서의 모든 회전 행렬을 생성할 수 있다. 이는 공간의 표준 기저 벡터들을 원하는 방향의 다른 기저 벡터들로 변환할 수 있음을 의미한다.

회전을 올바른 순서로 수행하면, 최종 변환 행렬에 사용된 각도들은 특정 규칙에 따른 최종 좌표계의 오일러 각과 같아진다. 예를 들어, R = R_Y(\theta_3) \cdot R_X(\theta_2) \cdot R_Z(\theta_1)와 같이 회전을 합성하면, 이는 공간의 기저를 테이트-브라이언 각 규칙 ''z-x-y'' (롤, 피치, 요 각 YPR = (\theta_3, \theta_2, \theta_1))을 따르는 좌표계로 변환하는 것과 같다.

역으로, 3차원 공간의 모든 회전 행렬은 이 세 가지 기본 회전 연산자의 곱으로 분해될 수 있다.

두 기븐스 회전 g \circ f를 합성하는 것은 벡터에 먼저 f 변환을 적용하고 그 결과에 g 변환을 적용하는 연산자를 의미한다. 이때 f와 g는 각각 공간의 좌표축을 기준으로 하는 회전이다. 이는 오일러 각에서의 외재적 회전 개념과 유사하다.

7. 활용

기븐스 회전은 선형대수학의 여러 수치 계산 문제에서 유용하게 활용된다. 특히 행렬의 특정 위치에 있는 원소를 선택적으로 0으로 만들 수 있는 능력 덕분에 다양한 알고리즘의 핵심 요소로 사용된다.

주요 활용 분야는 다음과 같다.


  • QR 분해: 행렬을 직교 행렬(Q)과 상삼각행렬(R)의 곱으로 분해하는 과정에 기븐스 회전을 사용할 수 있다. 여러 번의 기븐스 회전을 행렬에 순차적으로 적용하여 원하는 형태의 상삼각행렬을 만들 수 있으며, 이 과정에서 사용된 회전 변환들을 조합하여 직교 행렬을 얻는다. 이 방법은 특히 희소 행렬의 구조를 효과적으로 유지하면서 QR 분해를 수행할 수 있다는 장점이 있다.[1][2]
  • QR 알고리즘: 행렬의 고윳값과 고유벡터를 계산하는 반복적인 방법인 QR 알고리즘에서도 기븐스 회전이 중요한 역할을 한다. QR 알고리즘의 각 단계는 QR 분해와 유사한 계산을 포함하는데, 기븐스 회전을 사용하면 이 계산 과정을 효율적으로 수행하여 전체 알고리즘의 계산 복잡도를 줄일 수 있다.


이 외에도 기븐스 회전은 최소 제곱 문제 해결, 특잇값 분해(SVD) 계산 등 다양한 수치 선형대수 문제에 응용될 수 있다.

7. 1. QR 분해

기븐스 회전은 행렬의 QR 분해를 계산하는 데 사용될 수 있다. QR 분해는 주어진 행렬 A를 직교 행렬 Q와 상삼각행렬 R의 곱, 즉 A = QR 형태로 나타내는 행렬 분해 방법이다.[1][2]

기븐스 회전을 이용한 QR 분해 과정은 다음과 같다. 먼저, 행렬 A에서 0으로 만들고자 하는 특정 성분을 선택한다. 해당 성분을 0으로 만드는 기븐스 회전 행렬 G를 구성하여 A에 곱한다. 이 과정을 필요한 성분들에 대해 반복적으로 수행한다. 예를 들어, 행렬 A를 상삼각행렬로 만들기 위해 필요한 일련의 기븐스 회전 행렬을 G_1, G_2, ..., G_k라고 하면, 이들을 순서대로 A에 곱하여 상삼각행렬 R을 얻는다.

:R = G_k \cdots G_2 G_1 A

이때, 직교 행렬 Q는 각 단계에서 사용된 기븐스 회전 행렬들의 전치를 곱하여 계산된다.

:Q = G_1^T G_2^T \cdots G_k^T

이렇게 얻어진 Q와 R은 A = QR의 관계를 만족하며, Q는 직교 행렬이고 R은 상삼각행렬이다. 기븐스 회전을 이용하면 특정 위치의 값을 선택적으로 0으로 만들 수 있어, 희소 행렬(sparse matrix)의 QR 분해에 특히 유용하게 사용될 수 있다. 상세한 계산 과정은 아래 예제 섹션에서 확인할 수 있다.

7. 1. 1. 예제

다음과 같은 3x3 행렬 A_1이 주어졌다고 가정하자.

: A_1 =

\begin{bmatrix} 6 & 5 & 0 \\

5 & 1 & 4 \\

0 & 4 & 3 \\

\end{bmatrix}

이 행렬에 대해 QR 분해를 계산하기 위해 기븐스 회전을 두 번 반복하여 상삼각행렬을 만든다. (여기서는 A_1의 (3, 1) 성분이 이미 0이다.)

원하는 상삼각행렬을 만들기 위해서는 성분 (2, 1)과 (3, 2)를 0으로 만들어야 한다. 먼저 성분 (2, 1)을 0으로 만들기 위해 다음과 같은 회전 행렬 G_1을 사용한다.

:G_{1} =

\begin{bmatrix} c & -s & 0 \\

s & c & 0 \\

0 & 0 & 1 \\

\end{bmatrix}

이 회전 행렬을 A_1에 적용한다.

:

\begin{align}

G_1 A_1 &{}= A_2 \\

&{} = \begin{bmatrix} c & -s & 0 \\

s & c & 0 \\

0 & 0 & 1 \\

\end{bmatrix}

\begin{bmatrix} 6 & 5 & 0 \\

5 & 1 & 4 \\

0 & 4 & 3 \\

\end{bmatrix}

\end{align}



여기서 c와 s 값은 다음과 같이 계산된다.

: r = \sqrt{6^2 + 5^2} \approx 7.8102

: c = 6 / r \approx 0.7682

: s= -5 / r \approx -0.6402

계산된 c와 s 값을 사용하여 행렬 곱셈을 수행하면 다음과 같은 A_2를 얻는다.

:A_2 \approx \begin{bmatrix} 7.8102 & 4.4813 & 2.5607 \\

0 & -2.4327 & 3.0729 \\

0 & 4 & 3 \\

\end{bmatrix}

다음으로, 성분 (3, 2)를 0으로 만들기 위해 두 번째 회전 행렬 G_2를 사용한다.

:G_{2} =

\begin{bmatrix} 1 & 0 & 0 \\

0 & c & -s \\

0 & s & c \\

\end{bmatrix}

이 회전 행렬을 A_2에 적용한다.

:

\begin{align}

G_2 A_2 &{}= A_3 \\

&{}\approx \begin{bmatrix} 1 & 0 & 0 \\

0 & c & -s \\

0 & s & c \\

\end{bmatrix}

\begin{bmatrix} 7.8102 & 4.4813 & 2.5607 \\

0 & -2.4327 & 3.0729 \\

0 & 4 & 3 \\

\end{bmatrix}

\end{align}



여기서 c와 s 값은 다음과 같이 계산된다.

: r \approx \sqrt{(-2.4327)^2 + 4^2} \approx 4.6817

: c\approx -2.4327 / r \approx -0.5196

: s \approx -4 / r \approx -0.8544

계산된 c와 s 값을 사용하여 행렬 곱셈을 수행하면 다음과 같은 A_3를 얻는다.

:A_3 \approx

\begin{bmatrix} 7.8102 & 4.4813 & 2.5607 \\

0 & 4.6817 & 0.9664 \\

0 & 0 & -4.1843 \\

\end{bmatrix} = R



이 새로운 행렬 A_3는 QR 분해를 수행하는 데 필요한 상삼각행렬 R이다.

직교 행렬 Q는 사용된 회전 행렬들의 전치를 곱하여 다음과 같이 형성된다.

:Q = G_{1}^T\, G_{2}^T



이 행렬 곱셈을 수행하면 다음과 같은 Q를 얻는다.

:Q \approx

\begin{bmatrix} 0.7682 & 0.3327 & 0.5470 \\

0.6402 & -0.3992 & -0.6564 \\

0 & 0.8544 & -0.5196 \\

\end{bmatrix}

이로써 기븐스 회전을 두 번 반복하여 QR 분해 (A = QR)를 계산하는 과정이 완료되었다.

7. 2. QR 알고리즘 (고윳값 계산)

기븐스 회전은 행렬의 고윳값을 찾는 QR 알고리즘의 계산 과정을 효율적으로 만드는 데 사용될 수 있다. QR 분해(A = QR)를 통해 상삼각행렬 R과 직교행렬 Q를 구한 후, QR 알고리즘의 다음 단계는 A' = RQ를 계산하는 것이다. 이때 Q는 여러 기븐스 회전 행렬의 곱(Q = G_1 G_2 \dots G_{k})으로 표현될 수 있다 (k는 필요한 회전 횟수). 따라서 A' = R (G_1 G_2 \dots G_{k})를 계산해야 한다.

만약 Q 행렬을 먼저 명시적으로 계산한 후 R과 곱하면 O(n^3)의 계산량이 필요하다 (n은 행렬의 크기). 하지만 기븐스 회전의 구조를 활용하면 이 계산을 더 효율적으로 수행할 수 있다. A' = RQ를 계산할 때, Q = G_1 G_2 \dots G_{k} 전체를 미리 계산하는 대신, R에 각 기븐스 행렬 G_i를 순차적으로 오른쪽에서 곱하는 방식으로 계산한다. 즉, (\dots((R G_1) G_2) \dots G_k) 와 같이 계산한다.

각 기븐스 행렬 G_i를 오른쪽에 곱하는 연산은 이전 결과 행렬의 두 열만 변경시킨다. 따라서 이 개별 곱셈은 O(n)의 계산량만 필요하다. n \times n 행렬을 상삼각행렬로 만들기 위해 필요한 기븐스 회전의 총 개수는 대략 O(n^2) 이지만, QR 알고리즘의 한 단계인 RQ 계산에서는 R이 이미 상삼각행렬(또는 헤센베르크 행렬) 형태를 유지하는 경우가 많아, 필요한 기븐스 행렬(G_i)의 개수는 더 적을 수 있다. 특히, A를 상삼각화하는 과정(A=QR)에서 사용된 기븐스 행렬(G_i^T)들을 역순으로 적용하는 방식으로 RQ를 계산하면, 총 O(n^2)의 계산량으로 A'를 얻을 수 있다. 이는 Q를 먼저 구하는 방식의 O(n^3)보다 훨씬 효율적이다.

저장 공간 측면에서도 이점이 있다. 전체 Q 행렬(n \times n)을 저장하려면 n^2개의 원소가 필요하지만, 각 기븐스 회전은 회전 각도 또는 두 개의 값(c와 s) 및 적용 위치 정보로 완전히 정의된다. 따라서 QR 분해에 사용된 모든 기븐스 회전 정보를 저장하는 데 필요한 공간은 O(n^2)보다 훨씬 작다 (예: 헤센베르크 행렬의 QR 분해는 O(n)개의 회전만 필요).

아래는 원본 소스에서 제시된 RQ 계산의 일부 예시이다. 여기서 A_3는 R에 해당하고, G_1^T, G_2^T는 QR 분해 과정(A=QR에서 Q^T A = R)에 사용된 기븐스 행렬들이며, Q = (G_1^T G_2^T \dots)^T = \dots G_2 G_1 이다. 따라서 RQ 계산은 R (G_1^T G_2^T \dots)^T = R \dots G_2 G_1 형태로 진행되어야 한다. 소스의 예시는 R G_1^T G_2^T를 계산하는 것처럼 보이는데, 이는 Q를 G_1^T G_2^T로 잘못 정의했거나 특정 단계의 중간 계산을 보여주는 것일 수 있다. 일반적인 A' = RQ 계산은 R에 G_i들을 순차적으로 곱하는 것이다. 소스의 계산 자체는 다음과 같다.



\begin{aligned}

(A_3 G_1^T) G_2^T

\approx{}&

\begin{bmatrix}

8.8687& -1.5575& 2.5607\\

2.9972& 3.5965& 0.9665\\

0& 0& -4.1843

\end{bmatrix} G_2^T

\approx

\begin{bmatrix}

8.8687& 2.9972& 0.0\\

2.9972&-1.0430&-3.5750\\

0& -3.5750& 2.1742

\end{bmatrix}

\end{aligned}


8. 클리포드 대수

클리포드 대수와 그 하위 구조인 기하 대수에서 회전은 이중 벡터로 표현된다. 기븐스 회전은 기저 벡터의 외적에 의해 표현된다. 임의의 기저 벡터 쌍 \mathbf e_i, \mathbf e_j가 주어졌을 때 기븐스 회전 이중 벡터는 다음과 같다.

: B_{ij} = \mathbf e_i \wedge \mathbf e_j.

임의의 벡터에 대한 이들의 작용은 다음과 같이 표현된다.

: v=e^{-(\theta/2)(\mathbf e_i \wedge \mathbf e_j)}u e^{(\theta/2)(\mathbf e_i \wedge \mathbf e_j)},

여기서

: e^{(\theta/2)(\mathbf e_i \wedge \mathbf e_j)}= \cos(\theta/2)+ \sin(\theta/2) \mathbf e_i \wedge \mathbf e_j.

9. 참고 문헌


  • 골럽, 진 H.; 밴 로안, 찰스 F. (1996), ''행렬 계산'' (3판), 존스 홉킨스, ISBN 978-0-8018-5414-9.
  • 빈델, D.; 뎀멜, J.; 카한, W.; 마르케스, O. (2000), ''기븐스 회전을 안정적이고 효율적으로 계산하기''. LAPACK 워킹 노트 148, 테네시 대학교, UT-CS-00-449, 2001년 1월 31일.
  • 야마모토 테츠로 (2003년 6월). ''수치해석 입문''. 증정판. 사이언스사. ISBN 4-7819-1038-6.
  • 모리 마사타케. ''수치해석'' 제2판. 쿄리츠 출판.

참조

[1] 서적 Numerical Methods for Least Squares Problems https://books.google[...] SIAM 1996
[2] 웹사이트 Discontinuous Plane Rotations and the Symmetric Eigenvalue Problem http://www.netlib.or[...] University of Tennessee at Knoxville and Oak Ridge National Laboratory 2000-12-04


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com