맨위로가기

하우스홀더 변환

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

1. 개요

하우스홀더 변환은 주어진 벡터를 특정 초평면에 대해 반사시키는 변환이다. 이 변환은 법선 벡터로 정의되는 초평면에 직교하는 단위 벡터를 사용하여 표현되며, 하우스홀더 행렬을 통해 나타낼 수 있다. 하우스홀더 행렬은 에르미트 행렬, 유니타리 행렬, 대합 행렬이며, 고유값은 ±1이고 행렬식은 -1이다. 기하 광학에서 정반사를 표현하고, 수치 선형대수에서 QR 분해, 헤센베르크 형태로의 변환 등에 활용된다. 특히 QR 분해를 계산하거나, 삼중대각화를 수행하는 데 사용되며, 유니타리 변환과의 관계를 통해 효율적인 연산자 매개변수화를 가능하게 한다.

더 읽어볼만한 페이지

  • 변환 (함수) - 아핀 변환
    아핀 변환은 아핀 공간에서 직선의 형태와 평행성을 유지하는 변환으로, 선형 변환과 평행 이동의 결합으로 표현되며, 컴퓨터 그래픽스와 이미지 처리 등 여러 분야에서 활용되고 확대 행렬을 이용해 행렬 곱셈으로 나타낼 수 있다.
  • 변환 (함수) - 선형 변환
    선형 변환은 벡터의 덧셈과 스칼라 곱셈을 보존하는 특정 조건을 만족하는 두 벡터 공간 사이의 함수로서, 유한 차원 벡터 공간에서는 행렬로 표현될 수 있다.
  • 수치선형대수학 - 가우스 소거법
    가우스 소거법은 연립 일차 방정식의 해를 구하기 위해 행렬을 사다리꼴로 변환하는 알고리즘이며, 기본 행 연산을 통해 전진 소거와 후퇴 대입 단계를 거쳐 해를 계산하고, 행렬식 계산 등 다양한 분야에 응용된다.
  • 수치선형대수학 - LINPACK
    LINPACK은 부동소수점 연산 성능을 평가하는 벤치마크 프로그램이자 FORTRAN 라이브러리로, 슈퍼컴퓨터 성능 측정 기준으로 사용되는 HPLinpack 벤치마크의 기반이 되었으며, TOP500 목록에서 고성능 컴퓨터 순위를 결정하는 데 기여한다.
  • 행렬 - 스핀 (물리학)
    스핀은 양자역학적 각운동량으로, 양자화된 값을 가지며 자기 쌍극자 모멘트를 유발하여 다양한 분야에 응용되고 스핀트로닉스 기술 발전에 기여하지만, 전자의 스핀 기원은 아직 완전히 밝혀지지 않았다.
  • 행렬 - 파울리 행렬
    파울리 행렬은 양자역학에서 스핀을 나타내는 데 사용되는 에르미트 행렬이자 유니타리 행렬로, 행렬식은 -1이고 대각합은 0이며, 리 대수의 생성원이자 파울리 벡터로 정의되어 다양한 물리학 분야에서 활용된다.
하우스홀더 변환

2. 정의

하우스홀더 변환은 벡터 공간에서 특정 초평면에 대한 반사를 나타내는 선형 변환이다. 반사 초평면은 초평면에 직교하는 단위 벡터(길이가 1인 벡터)인 ''법선 벡터''로 정의할 수 있다. 이 초평면에 대한 점 x의 반사는 다음과 같은 선형 변환으로 표현된다.

:x - 2\langle x, v\rangle v = x - 2v\left(v^* x\right),

여기서 v는 켤레 전치 행렬 v^\textsf{*를 갖는 열 단위 벡터이다.

2. 1. 변환 (Transformation)

주어진 벡터를 초평면에 대해 반사시킨다. 반사 초평면은 법선 벡터로 정의된다.

반사 초평면은 초평면에 직교하는 단위 벡터(길이가 1인 벡터)인 ''법선 벡터''로 정의할 수 있다. 이 초평면에 대한 점 x의 반사는 다음과 같은 선형 변환이다.

:x - 2\langle x, v\rangle v = x - 2v\left(v^* x\right),

여기서 v는 켤레 전치 행렬 v^\textsf{*를 갖는 열 단위 벡터로 주어진다.

거울 반사를 정의하는 초평면은 이에 직교하는 단위 열 벡터 (길이 1의 벡터) \boldsymbol{v}에 의해 정의할 수 있다. 이 초평면에 관한 점 \boldsymbol{x}의 거울상은 선형 변환

:\boldsymbol{x}' := \boldsymbol{x} - 2 \langle \boldsymbol{x}, \boldsymbol{v} \rangle \boldsymbol{v} = \boldsymbol{x} - 2 \boldsymbol{v}(\boldsymbol{v}^*\boldsymbol{x})

로 주어진다. 이 변환 \boldsymbol{x}에서 \boldsymbol{x}'를 '''하우스홀더 변환'''이라고 부른다. 단, \boldsymbol{v}^*는 \boldsymbol{v}의 에르미트 전치이다.

2. 2. 하우스홀더 행렬 (Householder Matrix)

하우스홀더 변환의 표현 행렬은 '''하우스홀더 행렬'''이라고 불리며, 벡터의 텐서 곱을 사용하여 다음과 같이 표현할 수 있다.

:P = I - 2vv^*

여기서 I는 항등 행렬이다.

하우스홀더 변환에 의한 4 \times 4 matrix 의 3중대각행렬 유도 과정은 다음과 같다.[7]

:\mathbf{A} = \begin{bmatrix}

4&1&-2&2 \\

1 & 2 &0&1 \\

  • 2 & 0 &3& -2 \\

2 & 1 & -2&-1 \end{bmatrix}

우선, 첫번째 하우스홀더 행렬을 구하면 다음과 같다.

:Q_1 = \begin{bmatrix}

1&0&0&0 \\

0 &-1/3&2/3&-2/3 \\

0 & 2/3 &2/3& 1/3 \\

0 & -2/3 &1/3& 2/3 \end{bmatrix}

이를 이용하여 다음을 얻는다.

:A_1 = Q_1 A Q_1 = \begin{bmatrix}

4&-3&0&0 \\

  • 3 & 10/3 &1&4/3 \\

0 & 1 &5/3& -4/3 \\

0 & 4/3 & -4/3&-1 \end{bmatrix}

A_1을 이용해서 다음을 계산한다.

:Q_2=\begin{bmatrix}

1&0&0&0 \\

0&1 &0&0 \\

0 & 0 &-3/5&-4/5 \\

0 & 0 & -4/5&3/5 \end{bmatrix}

최종적으로 다음 행렬을 얻는다.

:A_2 = Q_2 A_1 Q_2=\begin{bmatrix}

4&-3&0&0 \\

  • 3 &10/3 &-5/3&0 \\

0 & -5/3 &-33/25& -68/75 \\

0 &0 & -68/75&149/75 \end{bmatrix}



이것은 두 단계를 거쳐 프로세스가 완료된다.

이것의 최종 결과는 원래의 것과 유사한 형태인 3 \times 3행렬의 3중대각행렬이다.

3. 성질


  • 에르미트 행렬이다.
  • 유니타리 행렬이다.
  • 대합 행렬이다.
  • 하우스홀더 행렬은 고유값 \pm 1을 갖는다. 반사 행렬을 생성하는 데 사용된 벡터 v에 u가 직교하는 경우, Pu = u임을 알 수 있다. 즉, 1은 중복도 n - 1의 고유값이다. v에 직교하는 n - 1개의 독립적인 벡터가 있기 때문이다. 또한, Pv = -v이므로, -1은 중복도 1의 고유값이다.
  • 하우스홀더 반사 행렬의 행렬식은 -1이다. 행렬식은 고유값들의 곱인데, 이 경우 하나의 고유값은 -1이고 나머지는 1이기 때문이다.

4. 응용

하우스홀더 변환은 다음과 같은 분야에서 응용된다.


  • 기하 광학: 정반사는 하우스홀더 행렬을 사용하여 표현할 수 있다.[1]
  • 수치 선형대수: 하우스홀더 변환은 QR 분해, 삼중대각행렬 변환, 헤센베르크 행렬 변환 등에 사용된다.[2][3] 특히, 대칭 또는 에르미트 행렬의 경우 하우스홀더 변환은 대칭성을 유지하면서 삼중대각행렬로 변환할 수 있다는 특징이 있다.[3]

4. 1. 기하 광학 (Geometric Optics)

정반사는 하우스홀더 행렬을 사용하여 표현할 수 있다.[1]

4. 2. 수치 선형대수 (Numerical Linear Algebra)

하우스홀더 변환은 QR 분해, 삼중대각행렬 변환, 헤센베르크 행렬 변환 등에 사용된다.[2][3] 특히, 대칭 또는 에르미트 행렬의 경우 하우스홀더 변환은 대칭성을 유지하면서 삼중대각행렬로 변환할 수 있다.[3]

다음은 4 \times 4 행렬을 하우스홀더 변환을 사용하여 삼중대각행렬로 유도하는 과정이다.[7]

:\mathbf{A} = \begin{bmatrix}

4&1&-2&2 \\

1 & 2 &0&1 \\

  • 2 & 0 &3& -2 \\

2 & 1 & -2&-1 \end{bmatrix}

첫 번째 하우스홀더 행렬은 다음과 같다.

:Q_1 = \begin{bmatrix}

1&0&0&0 \\

0 &-1/3&2/3&-2/3 \\

0 & 2/3 &2/3& 1/3 \\

0 & -2/3 &1/3& 2/3 \end{bmatrix}

A_1 = Q_1 A Q_1 = \begin{bmatrix}

4&-3&0&0 \\

  • 3 & 10/3 &1&4/3 \\

0 & 1 &5/3& -4/3 \\

0 & 4/3 & -4/3&-1 \end{bmatrix}

A_1을 이용하여 Q_2를 구한다.

:Q_2=\begin{bmatrix}

1&0&0&0 \\

0&1 &0&0 \\

0 & 0 &-3/5&-4/5 \\

0 & 0 & -4/5&3/5 \end{bmatrix}

A_2 = Q_2 A_1 Q_2=\begin{bmatrix}

4&-3&0&0 \\

  • 3 &10/3 &-5/3&0 \\

0 & -5/3 &-33/25& -68/75 \\

0 &0 & -68/75&149/75 \end{bmatrix}



두 단계를 거치면 원래 행렬과 유사한 형태인 3 \times 3 삼중대각행렬을 얻을 수 있다.

4. 2. 1. QR 분해 (QR Decomposition)

하우스홀더 반사는 QR 분해를 계산하는 데 사용된다. 먼저 행렬의 한 열을 표준 기저 벡터의 배수로 반사하고, 변환 행렬을 계산하고, 원래 행렬과 곱한 다음 해당 곱의 (i, i) 소행렬을 재귀적으로 수행하는 방식으로 이루어진다.[2] 이를 위해 복소 벡터 '''x'''를 복소 벡터 '''e'''의 복소 배수로 변환하는 에르미트 유니타리 행렬 '''Q'''를 찾는다. QR 분해의 경우, '''e'''는 단위 좌표 벡터가 되며, 예를 들어 k번째 좌표가 될 것이다. '''Q''' = '''I''' - '''u u'''* 형태의 복소 행렬 '''Q'''는 '''u'''* '''u''' = 2를 가지며, 에르미트 유니타리 행렬이 되는 원하는 속성을 가진다. 여기서 *는 켤레 전치를 나타낸다. 관련된 두 벡터가 '''x'''와 '''e'''뿐이므로 벡터 '''u'''는 '''u''' = a '''x''' + b '''e'''의 형태를 가져야 하며, 여기서 a와 b는 결정되어야 하는 복소 계수이다. '''u'''에 대한 전체 위상 인자는 중요하지 않으므로, 계수 a는 양의 실수로 선택할 수 있다. 이제 '''Q''' '''x''' = '''x''' (1 – a ('''u'''* '''x''')) - '''e''' (b ('''u'''* '''x''')). 벡터 '''x'''의 계수가 0이 되려면, '''u'''* '''x'''의 두 항은 180도의 배수 내에서 동일한 위상을 가져야 하므로, arg(b) = arg('''e'''* '''x''')가 180도의 배수 내에 있어야 한다. 180도의 짝수 또는 홀수 배수를 선택하는지에 따라 두 가지 해가 있다. 따라서 벡터 '''x'''의 복소 계수가 0이 되려면 a와 b의 절댓값에 대한 두 개의 선형 방정식을 풀어야 한다. a와 b의 위상은 이미 결정되었다. '''e'''를 k번째 단위 좌표 벡터로 가정하여 '''e'''* '''e''' = 1 및 xk= '''e'''* '''x'''로 하고 |'''x'''|= sqrt('''x'''* '''x''')로 하자. 그러면 a와 b는 a =1/sqrt (|'''x'''| (|'''x'''|+ |xk|)) 및 b = a |'''x'''| exp(i*arg(xk)) 또는 a =1/sqrt (|'''x'''| (|'''x'''|- |xk|)) 및 b = - a |'''x'''| exp(i*arg(xk))로 간단하게 표현할 수 있다. '''e'''의 승수는 두 해 모두 -b/a이다. 첫 번째 해가 더 나은데, 분모가 |'''x'''|에 비해 0에 가까워질 수 없기 때문이다.[2]

하우스홀더 변환은 QR 분해를 수행하기 위해 QR법의 첫 번째 단계로, 수치 선형대수에서 널리 사용된다.[2]

4. 2. 2. 삼중대각화 (Tridiagonalization)

하우스홀더 변환을 사용하여 주어진 행렬을 삼중대각행렬로 변환하는 과정을 살펴본다.

4 × 4 행렬의 삼중대각행렬 유도 과정은 다음과 같다.[7]

:\mathbf{A} = \begin{bmatrix}

4&1&-2&2 \\

1 & 2 &0&1 \\

  • 2 & 0 &3& -2 \\

2 & 1 & -2&-1 \end{bmatrix}

먼저, 첫 번째 하우스홀더 행렬을 구한다.

:Q_1 = \begin{bmatrix}

1&0&0&0 \\

0 &-1/3&2/3&-2/3 \\

0 & 2/3 &2/3& 1/3 \\

0 & -2/3 &1/3& 2/3 \end{bmatrix}

:A_1 = Q_1 A Q_1 = \begin{bmatrix}

4&-3&0&0 \\

  • 3 & 10/3 &1&4/3 \\

0 & 1 &5/3& -4/3 \\

0 & 4/3 & -4/3&-1 \end{bmatrix}

:A_1을 이용하여 Q_2를 구한다.

:Q_2=\begin{bmatrix}

1&0&0&0 \\

0&1 &0&0 \\

0 & 0 &-3/5&-4/5 \\

0 & 0 & -4/5&3/5 \end{bmatrix}

:A_2 = Q_2 A_1 Q_2=\begin{bmatrix}

4&-3&0&0 \\

  • 3 &10/3 &-5/3&0 \\

0 & -5/3 &-33/25& -68/75 \\

0 &0 & -68/75&149/75 \end{bmatrix}



두 단계를 거치면 과정이 완료된다.

최종 결과는 원래 행렬과 유사한 형태인 3 × 3 삼중대각행렬이다.

이 절차는 Burden과 Faires의 수치 해석에 제시되어 있으며, 약간 변경된 \operatorname{sgn} 함수를 사용한다 (\operatorname{sgn}(0) = 1).[4]

각 단계의 하우스홀더 행렬을 구하기 위해 \alpha와 r을 결정해야 한다.

:\begin{align}

\alpha &= -\operatorname{sgn}\left(a_{21}\right)\sqrt{\sum_{j=2}^n a_{j1}^2}; \\

r &= \sqrt{\frac{1}{2}\left(\alpha^2 - a_{21}\alpha\right)};

\end{align}

\alpha와 r로부터 벡터 v를 구성한다.

:v^{(1)} = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix},

여기서 v_1 = 0, v_2 = \frac{a_{21} - \alpha}{2r}이고, k = 3, 4 \ldots n에 대해 v_k = \frac{a_{k1}}{2r}이다.

그런 다음 다음을 계산한다.

:\begin{align}

P^1 &= I - 2v^{(1)} \left(v^{(1)}\right)^\textsf{T} \\

A^{(2)} &= P^1 AP^1

\end{align}

P^1을 구하고 A^{(2)}를 계산한 후, k = 2, 3, \ldots, n - 2에 대해 이 과정을 반복한다.

:\begin{align}

\alpha &= -\operatorname{sgn}\left(a^k_{k+1,k}\right)\sqrt{\sum_{j=k+1}^n \left(a^k_{jk}\right)^2} \\[2pt]

r &= \sqrt{\frac{1}{2}\left(\alpha^2 - a^k_{k+1,k}\alpha\right)} \\[2pt]

v^k_1 &= v^k_2 = \cdots = v^k_k = 0 \\[2pt]

v^k_{k+1} &= \frac{a^k_{k+1,k} - \alpha}{2r} \\

v^k_j &= \frac{a^k_{jk}}{2r} \text{ for } j = k + 2,\ k + 3,\ \ldots,\ n \\

P^k &= I - 2v^{(k)} \left(v^{(k)}\right)^\textsf{T} \\

A^{(k+1)} &= P^k A^{(k)}P^k

\end{align}

이러한 방식으로 삼중 대각선 대칭 행렬을 얻을 수 있다.

5. 다른 유니타리 변환과의 관계

하우스홀더 변환은 단위 법선 벡터 v를 갖는 초평면에 대한 반사이다. N×N 유니타리 변환 U는 UU^* = I를 만족하며, 유니타리 행렬의 행렬식과 대각합을 통해 고유값 \lambda_i가 단위 모듈러스를 갖는다는 것을 알 수 있다. 이는 산술 평균과 기하 평균의 관계를 통해 증명된다.

실수 값을 갖는 유니타리 행렬은 직교 행렬 UU^\textsf{T} = I를 만족한다. 모든 직교 행렬은 기븐스 회전과 하우스홀더 반사의 곱으로 QR 분해될 수 있다. 직교 행렬로 벡터를 곱하면 벡터의 길이가 보존되며, 회전과 반사는 벡터의 길이를 변화시키지 않는 기하학적 연산이기 때문이다.

하우스홀더 변환은 군론에서 정의된 유니타리 행렬의 표준 코셋 분해와 일대일 관계를 가지며, 유니타리 연산자를 효율적으로 매개변수화할 수 있게 한다.[5]

단일 하우스홀더 변환은 행렬의 모든 열에 작용할 수 있어 QR 분해 및 삼대각화에 계산 비용이 가장 낮다. 그러나 이러한 계산 최적성은 하우스홀더 연산을 병렬화하기 어렵게 만든다. 따라서 하우스홀더 변환은 순차적 처리를 하는 조밀 행렬에 적합하고, 기븐스 회전은 희소 행렬 및 병렬 처리에 적합하다.

6. 예제

4x4 행렬의 3중대각행렬 유도 과정은 다음과 같다.[7]

:\mathbf{A} = \begin{bmatrix}

4&1&-2&2 \\

1 & 2 &0&1 \\


  • 2 & 0 &3& -2 \\

2 & 1 & -2&-1 \end{bmatrix}

먼저, 첫 번째 하우스홀더 행렬을 구한다.

:Q_1 = \begin{bmatrix}

1&0&0&0 \\

0 &-1/3&2/3&-2/3 \\

0 & 2/3 &2/3& 1/3 \\

0 & -2/3 &1/3& 2/3 \end{bmatrix}

:A_1 = Q_1 A Q_1 = \begin{bmatrix}

4&-3&0&0 \\

  • 3 & 10/3 &1&4/3 \\

0 & 1 &5/3& -4/3 \\

0 & 4/3 & -4/3&-1 \end{bmatrix}

A_1을 이용하여 Q_2를 구한다.

:Q_2=\begin{bmatrix}

1&0&0&0 \\

0&1 &0&0 \\

0 & 0 &-3/5&-4/5 \\

0 & 0 & -4/5&3/5 \end{bmatrix}

:A_2 = Q_2 A_1 Q_2=\begin{bmatrix}

4&-3&0&0 \\

  • 3 &10/3 &-5/3&0 \\

0 & -5/3 &-33/25& -68/75 \\

0 &0 & -68/75&149/75 \end{bmatrix}



이 과정을 두 단계 거치면 완료된다. 최종 결과는 원래 행렬과 유사한 형태인 3x3 3중대각행렬이다. 이 예제는 Burden과 Faires에서도 가져온 것으로, 하우스홀더 방법을 사용하여 주어진 행렬을 유사 삼각 대각 행렬 A3으로 변환한다.

참조

[1] 논문 Unitary Triangularization of a Nonsymmetric Matrix https://hal.archives[...]
[2] 웹사이트 Householder matrix, Lectures on matrix algebra. https://www.statlect[...]
[3] 논문 Toward a parallel solver for generalized complex symmetric eigenvalue problems 2010-05-01
[4] 서적 Numerical analysis Thomson Brooks/Cole 2016
[5] 논문 The canonical coset decomposition of unitary matrices through Householder transformations
[6] 논문 The canonical coset decomposition of unitary matrices through Householder transformations
[7] 문서 This example is taken from the book "Numerical Analysis" by Richard L. Burden (Author), J. Douglas Faires


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

문의하기 : help@durumis.com