QR 분해

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

1. 개요
2. 정의
3. QR 분해 계산 방법
4. 행렬식 및 고윳값과의 관계
5. 열 피벗팅
6. 선형 역문제(Linear Inverse Problem)에의 활용
7. 일반화
참조

1. 개요

QR 분해는 실수 또는 복소수 행렬을 직교(또는 유니터리) 행렬 Q와 상삼각 행렬 R의 곱으로 분해하는 방법이다. 정사각 행렬뿐만 아니라 직사각 행렬에도 적용 가능하며, 그람-슈미트 과정, 하우스홀더 변환, 기븐스 회전 등의 방법을 통해 계산할 수 있다. QR 분해는 행렬식 계산, 선형 역문제 해결, 열 피벗팅을 통한 수치적 안정성 향상 등에 활용되며, 이와사와 분해로 일반화될 수 있다.

더 읽어볼만한 페이지

행렬 분해 - 조르당 표준형
조르당 표준형은 대수적으로 닫힌 체 위에서 정사각 행렬을 유사 변환하여 얻을 수 있는 특정한 형태의 행렬로, 조르당 블록으로 구성되며 고윳값, 중복도, 특성/최소 다항식과 관련 있고, 스펙트럼 사영 정리, 케일리-해밀턴 정리 등 다양한 정리 증명과 행렬 계산에 응용된다.
행렬 분해 - 슈어 분해
슈어 분해는 행렬을 분해하는 방법으로, 복소수 슈어 분해, 실수 슈어 분해, 일반화 슈어 분해(QZ 분해) 등이 있으며, QR 알고리즘으로 계산되고 리 군론 등에 응용된다.
수치선형대수학 - 가우스 소거법
가우스 소거법은 연립 일차 방정식의 해를 구하기 위해 행렬을 사다리꼴로 변환하는 알고리즘이며, 기본 행 연산을 통해 전진 소거와 후퇴 대입 단계를 거쳐 해를 계산하고, 행렬식 계산 등 다양한 분야에 응용된다.
수치선형대수학 - LINPACK
LINPACK은 부동소수점 연산 성능을 평가하는 벤치마크 프로그램이자 FORTRAN 라이브러리로, 슈퍼컴퓨터 성능 측정 기준으로 사용되는 HPLinpack 벤치마크의 기반이 되었으며, TOP500 목록에서 고성능 컴퓨터 순위를 결정하는 데 기여한다.

QR 분해

2. 정의

QR 분해는 주어진 행렬을 직교 행렬과 상삼각 행렬의 곱으로 나타내는 것이다.^[10]

실수체 또는 복소수체 $\mathbb K$ 성분의 $m\times n$ 행렬 $M$ 은 항상 다음과 같이 분해할 수 있으며, 이를 $M$ 의 '''(두꺼운) QR 분해'''((thick) QR decomposition^영어)라고 한다.^[10]

: $M=QR$

여기서

$Q$ 는 $\mathbb K$ 성분의 $m\times m$ 정사각 행렬이며, 그 열들은 선형 생성의 정규 직교 기저를 이룬다. 즉, $Q$ 는 $\mathbb K=\mathbb R$ 일 때 직교 행렬, $\mathbb K=\mathbb C$ 일 때 유니터리 행렬이다.
$R$ 은 $\mathbb K$ 성분의 $m\times n$ 행렬이며, $i>j$ 인 모든 $i, j$ 에 대하여 $R_{ij}=0$ 이다. 즉, 상삼각 행렬이다.

m\ge n

일 때,

M

을 다음과 같이 분해할 수도 있으며, 이를

M

의 '''얇은 QR 분해'''(thin QR decomposition, reduced QR decomposition^영어)라고 한다.^[10]

:

M=Q'R'

여기서

$Q'$ 은 $\mathbb K$ 성분의 $m\times n$ 행렬이며, 그 열들은 선형 생성의 정규 직교 기저를 이룬다.
$R'$ 은 $\mathbb K$ 성분의 $n\times n$ 상삼각 행렬이다.

정사각 행렬의 경우 (

m=n

) QR 분해와 얇은 QR 분해는 같다.

2. 1. 정사각 행렬

임의의 실수 정사각 행렬 ''A''는 다음과 같이 분해될 수 있다.^[1]

:

A = QR

여기서 ''Q''는 직교 행렬(그 열들은 직교 단위 벡터를 이룸)이고, ''R''은 상삼각 행렬이다. 만약 ''A''가 가역 행렬이면, ''R''의 대각선 요소가 양수가 되도록 요구할 경우 이 분해는 유일하다.^[1]

''A''가 복소 정사각 행렬인 경우에도 ''A'' = ''QR'' 분해가 존재하며, 여기서 ''Q''는 유니타리 행렬이다.^[1]

''A''가 ''n''개의 선형 독립 열을 가지고 있다면, ''Q''의 처음 ''n''개의 열은 ''A''의 열 공간에 대한 정규 직교 기저를 형성한다. 더 일반적으로, 1 ≤ ''k'' ≤ ''n''에 대해 ''Q''의 처음 ''k''개의 열은 ''A''의 처음 ''k''개의 열의 스팬에 대한 정규 직교 기저를 형성한다.^[1] ''A''의 임의의 열 ''k''가 ''Q''의 처음 ''k''개의 열에만 의존한다는 사실은 ''R''의 삼각 형태에 해당한다.^[1]

2. 2. 직사각 행렬

일반적인 ''m''×''n'' 복소수 행렬 ''A'' (''m'' ≥ ''n'')는 ''m''×''m'' 유니타리 행렬 ''Q''와 ''m''×''n'' 상삼각 행렬 ''R''의 곱으로 분해할 수 있다.^[10]

:

A = QR

또는, 다음과 같이 얇은 QR 분해(thin QR decomposition) 또는 축소된 QR 분해(reduced QR decomposition)를 사용하기도 한다.^[10]^[1]

:

A = Q_1 R_1

여기서 ''R''₁은 ''n''×''n'' 상삼각 행렬이고, ''Q''₁은 ''m''×''n'' 행렬이다. ''Q''₁과 ''Q''₂는 모두 직교 열을 갖는다.

만약 ''A''가 전체 계수 ''n''을 가지며 ''R''₁의 대각선 요소가 양수여야 한다면 ''R''₁과 ''Q''₁은 고유하지만, 일반적으로 ''Q''₂는 고유하지 않다. 이때 ''R''₁은 ''A''^* ''A'' (''A''가 실수 행렬인 경우 ''A''^T''A''와 같다)의 촐레스키 분해의 상삼각 인자와 같다.^[6]

2. 3. QL, RQ, LQ 분해

유사하게, ''L''|L|엘^영어이 하삼각 행렬(lower triangular matrix)인 QL, RQ, LQ 분해도 정의할 수 있다.

3. QR 분해 계산 방법

QR 분해를 계산하는 대표적인 방법으로는 그람-슈미트 과정, 하우스홀더 변환, 기븐스 회전 등이 있다. 각 방법은 장단점을 가지므로, 행렬의 특성과 계산 환경에 맞는 방법을 선택해야 한다.^[1]^[2]

그람-슈미트 과정: 비교적 간단하게 구현할 수 있지만, 수치적으로 불안정하여 오차가 발생할 가능성이 있다.
하우스홀더 변환: 수치적으로 안정적이고 단순하지만, 메모리 사용량이 많고 병렬화하기 어렵다.
기븐스 회전: 특정 요소를 0으로 만들 때 효율적이며 병렬화에 유리하지만, 구현이 복잡하다.

3. 1. 그람-슈미트 과정

그람-슈미트 과정을 이용하면 QR 분해를 수행할 수 있다. 주어진 행렬의 열 벡터들이 일차독립이라고 가정하고, 이 벡터들에 대해 그람-슈미트 직교정규화를 적용하여 정규직교기저를 만든다. 이 과정을 통해 얻은 정규직교벡터들을 열벡터로 하는 행렬

Q

를 구성하고, 이를 통해 상삼각행렬

R

을 계산한다.

벡터

\mathbf{a}_1,\mathbf{a}_2,\cdots,\mathbf{a}_n\in\mathbb{R}^m

가 일차독립이고, 행렬

A = [\begin{array}{llll}\mathbf{a}_1 &\mathbf{a}_2 &\cdots &\mathbf{a}_n\end{array}]

에 대해, 그람-슈미트 직교정규화를 사용하면 다음과 같은 사영 연산자를 이용할 수 있다.

:

\mathrm{proj}_{\mathbf{e}}\mathbf{a} = \frac{\left\langle\mathbf{e},\mathbf{a}\right\rangle}{\left\langle\mathbf{e},\mathbf{e}\right\rangle}\mathbf{e}

이를 통해 직교정규기저

\{\mathbf{e}_1, \mathbf{e}_2, \cdots, \mathbf{e}_n\}

를 다음과 같이 얻을 수 있다.

:

\mathbf{u}_i = \mathbf{a}_i - \sum_{j=1}^{i-1} \mathrm{proj}_{\mathbf{u}_j} \mathbf{a}_i

:

\mathbf{e}_i = \frac {\mathbf{u}_i} {\|\mathbf{u}_i\|}

여기서

{\langle \cdot,\cdot \rangle}

은 내적이고,

{\|{ }\|}

는 노름이다. 위 식을 정리하면 다음과 같다.

:

\mathbf{a}_i = \sum_{j=1}^{i} \langle \mathbf{e}_j, \mathbf{a}_i \rangle \mathbf{e}_j

따라서,

Q = [\begin{array}{llll}\mathbf{e}_1& \mathbf{e}_2& \cdots& \mathbf{e}_n\end{array}]

와

:

R = \begin{pmatrix} \langle\mathbf{e}_1,\mathbf{a}_1\rangle & \langle\mathbf{e}_1,\mathbf{a}_2\rangle & \langle\mathbf{e}_1,\mathbf{a}_3\rangle & \ldots \\0 & \langle\mathbf{e}_2,\mathbf{a}_2\rangle & \langle\mathbf{e}_2,\mathbf{a}_3\rangle & \ldots \\0&0& \langle\mathbf{e}_3,\mathbf{a}_3\rangle & \ldots \\ \vdots&\vdots&\vdots&\ddots\end{pmatrix}

로 정의하면,

A = QR

이 성립한다.

이 방법은 구현이 비교적 간단하다는 장점이 있지만, 투영 과정에서 발생하는 수치적 오류로 인해 결과가 불안정할 수 있다.^[1] 따라서, 실제 계산에서는 보다 안정적인 다른 QR 분해 알고리즘을 사용하는 것이 일반적이다.

3. 1. 1. 예

주어진 행렬

A

는 다음과 같다.

:

A =\begin{pmatrix}12 & -51 & 4 \\6 & 167 & -68 \\

4 & 24 & -41

\end{pmatrix}

정규 직교 행렬

Q

는

Q^T \,Q = I

의 성질을 갖는다.

그람-슈미트 과정을 통해

Q

를 계산하면 다음과 같다.

:

U =\begin{pmatrix}\mathbf u_1 & \mathbf u_2 & \mathbf u_3\end{pmatrix}=\begin{pmatrix}12 & -69 & -58/5 \\6 & 158 & 6/5 \\

4 & 30 & -33

\end{pmatrix}

:

Q =\begin{pmatrix}\frac{\mathbf u_1}{\|\mathbf u_1\|} &\frac{\mathbf u_2}{\|\mathbf u_2\|} &\frac{\mathbf u_3}{\|\mathbf u_3\|}\end{pmatrix}=\begin{pmatrix}6/7 & -69/175 & -58/175 \\3/7 & 158/175 & 6/175 \\

2/7 & 6/35 & -33/35

\end{pmatrix}

그리고,

Q^{T} A = Q^{T}Q\,R = R

이므로,

:

R = Q^{T}A =\begin{pmatrix}14 & 21 & -14 \\0 & 175 & -70 \\0 & 0 & 35\end{pmatrix}

확인해보면,

A= QR

이므로,

:

\begin{pmatrix}6/7    &    -69/175   &   -58/175   \\3/7    &    158/175   &     6/175   \\

2/7 & 6/35 & -33/35

\end{pmatrix}\cdot\begin{pmatrix}14 & 21 & -14 \\0 & 175 & -70 \\0 & 0 & 35\end{pmatrix}=\begin{pmatrix}12 & -51 & 4 \\6 & 167 & -68 \\

4 & 24 & -41

\end{pmatrix}

와 같이

QR=A

로,

QR

분해 된다.

그러나, 분수에 의한 부동소수점 연산이 포함되므로 오차가 발생할 수 있다.

3. 1. 2. RQ 분해와의 관계

RQ 분해는 행렬 ''A''를 상삼각행렬 ''R''(우삼각 행렬이라고도 함)과 직교행렬 ''Q''의 곱으로 변환한다. QR 분해와의 유일한 차이점은 행렬의 순서이다.

QR 분해는 ''A'' 행렬의 열에 대해 그람-슈미트 정규 직교화를 첫 번째 열부터 마지막 열 순서로 적용한다. 반면 RQ 분해는 ''A'' 행렬의 행에 대해 그람-슈미트 정규 직교화를 마지막 행부터 첫 번째 행 순서로 적용한다.

그람-슈미트 과정은 본질적으로 수치적으로 불안정하다. 투영을 적용하는 것은 직교화에 대한 매력적인 기하학적 비유를 가지고 있지만, 직교화 자체는 수치적 오류가 발생하기 쉽다. 그러나 구현이 간단하다는 장점이 있다.^[1]

3. 2. 하우스홀더 변환

하우스홀더 리플렉터를 이용하여 한 열씩 상삼각행렬로 바꾸어 QR 분해를 수행할 수 있다. 이 방법은 Q 행렬을 하우스홀더 행렬의 곱으로 구하므로, 직접 Q를 구할 필요가 없을 때 유용하다.^[2]

컴퓨터를 사용하여 계산할 때, 그람-슈미트 방법은 분수 연산에 따른 부동소수점 연산 오차로 인해 R의 성분이 0이 아닌 값을 가지는 경우가 많다. 이 문제는 행렬의 크기가 커질수록 심화된다. 반면 하우스홀더 변환은 R의 특정 성분을 0으로 만들어 상삼각행렬을 만들기 때문에 수치적으로 안정적이다.^[2]

QR 분해를 위한 하우스홀더 반사: 벡터 $\mathbf x$ 를 $\mathbf e_1$ 과 공선형인 동일한 길이의 벡터로 변환하는 선형 변환을 찾는 것이 목표이다. 하우스홀더 반사는 $\mathbf x$ 와 $\mathbf e_1$ 사이의 각을 이등분하는 점선을 통해 반사한다.

하우스홀더 변환은 벡터를 특정 평면 또는 초평면에 대해 반사하는 변환이다.

m \ge n

인 ''m''×''n'' 행렬

A

의 QR 분해 계산에 사용될 수 있다.

\mathbf{x}

를 스칼라

\alpha

에 대해

\|\mathbf{x}\| = |\alpha|

인

A

의 임의의 실수 ''m''차원 열 벡터라고 하자. 부동 소수점 연산을 사용하는 경우, 유효 자릿수 손실을 피하기 위해

\alpha

는

\mathbf{x}

의 ''k''번째 좌표와 반대 부호를 가져야 한다. 여기서

x_k

는 행렬 ''A''의 최종 상삼각 형태에서 모든 항목이 0이 된 후의 피벗 좌표이다. 복소수의 경우,

\alpha = -e^{i \arg x_k} \|\mathbf{x}\|

로 설정한다.^[2]

\mathbf{e}_1

이 벡터 [1 0 ⋯ 0]^T, ||·||가 유클리드 노름,

I

가 ''m''×''m'' 단위 행렬인 경우, 다음과 같이 설정한다.

:

\begin{align}\mathbf{u} &= \mathbf{x} - \alpha\mathbf{e}_1, \\\mathbf{v} &= \frac{\mathbf{u}}{\|\mathbf{u}\|}, \\Q &= I - 2 \mathbf{v}\mathbf{v}^\textsf{T}.\end{align}

Q

는 ''m''×''m'' 하우스홀더 행렬이며, 대칭이자 직교(복소수의 경우 에르미트 행렬이자 유니타리 행렬)이며, 다음을 만족한다.

:

Q\mathbf{x} = \begin{bmatrix} \alpha \\ 0 \\ \vdots \\ 0 \end{bmatrix}.

''m''×''n'' 행렬 ''A''를 상삼각 형태로 점진적으로 변환하기 위해, 먼저 '''x'''의 첫 번째 열을 선택하여 얻은 하우스홀더 행렬 ''Q''₁으로 ''A''를 곱한다. 그러면 왼쪽 열에 0이 있는 행렬 ''Q''₁''A''가 생성된다(첫 번째 행 제외). 이 과정을 ''A''′ (''Q''₁''A''에서 첫 번째 행과 첫 번째 열을 삭제하여 얻음)에 대해 반복하여, 하우스홀더 행렬 ''Q''′₂가 생성된다. ''Q''′₂는 ''Q''₁보다 작다는 것에 주의해야 한다. ''A''′ 대신 ''Q''₁''A''에 대해 연산을 수행하므로, 1을 채워 상단 왼쪽으로 확장해야 한다. 일반적으로 다음과 같다.

:

Q_k = \begin{bmatrix}I_{k-1} & 0    \\0  & Q_k'\end{bmatrix}.

이 프로세스를

t

번 반복한 후, ,

:

R = Q_t \cdots Q_2 Q_1 A

는 상삼각 행렬이다. 따라서,

:

Q = Q_1 Q_2 \cdots Q_t

이고,

A = QR

은

A

의 QR 분해가 된다.

하우스홀더 변환은 ''R'' 행렬에서 0을 생성하는 메커니즘으로 반사를 사용하기 때문에 수치적으로 안정적인 QR 분해 알고리즘 중에서 본질적으로 가장 단순하다. 그러나 하우스홀더 반사 알고리즘은 대역폭이 많이 사용되고 병렬화가 어렵다. 새로운 0 요소를 생성하는 모든 반사가 ''Q''와 ''R'' 행렬 전체를 변경하기 때문이다.

하우스홀더 변환에 의한 QR 분해의 ''k''번째 단계에서 연산 수는 다음과 같다.

연산	k번째 단계에서의 연산 수
곱셈	$2(n - k + 1)^2$
덧셈	$(n - k + 1)^2 + (n - k + 1)(n - k) + 2$
나눗셈	$1$
제곱근	$1$

단계를 거쳐 (크기가 ''n''인 정사각 행렬의 경우) 이러한 숫자를 모두 더하면, 알고리즘의 복잡성 (부동 소수점 곱셈 측면에서)은 다음과 같다.

: $\frac{2}{3}n^3 + n^2 + \frac{1}{3}n - 2 = O\left(n^3\right).$

3. 2. 1. 예

주어진 행렬

A = \begin{pmatrix}12 & -51 & 4 \\6 & 167 & -68 \\

4 & 24 & -41 \end{pmatrix}에 대한 QR 분해 과정을 하우스홀더 변환을 이용하여 단계별로 살펴보자.

1단계:먼저, 행렬

A

의 첫 번째 열

a_1 = (12, 6, -4)^T

를

\|a_1\| e_1 = (14, 0, 0)^T

로 변환하는 반사(reflection)를 찾는다. 여기서

e_1 = (1, 0, 0)^T

이다.

u = x - \alpha e_1

v = \frac{u}{\|u\|}

여기서

\alpha = 14

이고

x = a_1 = (12, 6, -4)^T

이다.

따라서

u = (-2, 6, -4)^T = 2(-1, 3, -2)^T

이고,

v = \frac{1}{\sqrt{14}}(-1, 3, -2)^T

이다.

이제 하우스홀더 행렬

Q_1

을 다음과 같이 계산한다.

Q_1 = I - 2vv^T = I - \frac{2}{14}\begin{pmatrix} -1 \\ 3 \\ -2 \end{pmatrix}\begin{pmatrix} -1 & 3 & -2 \end{pmatrix} = \begin{pmatrix}6/7 & 3/7 & -2/7 \\3/7 & -2/7 & 6/7 \\

2/7 & 6/7 & 3/7 \end{pmatrix}

2단계:

Q_1A

를 계산하면 다음과 같다.

Q_1A = \begin{pmatrix}14 & 21 & -14 \\0 & -49 & -14 \\0 & 168 & -77 \end{pmatrix}

이제 (3, 2) 위치의 값을 0으로 만들기 위해

A' = \begin{pmatrix} -49 & -14 \\ 168 & -77 \end{pmatrix}

에 대해 하우스홀더 변환을 적용한다.

위와 같은 방법으로

Q_2 = \begin{pmatrix}1 & 0 & 0 \\0 & -7/25 & 24/25 \\0 & 24/25 & 7/25 \end{pmatrix}

를 얻는다.
3단계:

Q = Q_1^T Q_2^T

와

R = Q_2Q_1A = Q^T A

를 계산한다.

Q = \begin{pmatrix}6/7 & -69/175 & 58/175 \\3/7 & 158/175 & -6/175 \\

2/7 & 6/35 & 33/35 \end{pmatrix} \approx \begin{pmatrix}

0.8571 & -0.3943 & 0.3314 \\0.4286 & 0.9029 & -0.0343 \\

0.2857 & 0.1714 & 0.9429 \end{pmatrix}

R = \begin{pmatrix}14 & 21 & -14 \\0 & 175 & -70 \\0 & 0 & -35 \end{pmatrix}

결과적으로

Q

는 직교행렬이고,

R

은 상삼각행렬이며,

A = QR

을 만족한다.

3. 2. 2. 하우스홀더 QR의 병렬 구현

하우스홀더 QR 방법은 TSQR 알고리즘(''Tall Skinny QR''의 약자)과 같은 알고리즘을 사용하여 병렬로 구현할 수 있다. 이 알고리즘은 행렬 ''A''가 ''m >> n''인 경우에 적용할 수 있다.^[3] 이 알고리즘은 전진 패스에서 각 노드에서 로컬 하우스홀더 QR 분해를 계산하고, 후진 패스에서 Q 행렬을 재구성하기 위해 이진 축소 트리를 사용한다. 이진 트리 구조는 프로세서 간의 통신량을 줄여 성능을 향상시키는 것을 목표로 한다.

하우스홀더 변환은 ''R'' 행렬의 0을 생성하는 메커니즘에 경사 반사를 이용하므로, 가장 간단하고 수치적으로 안정적인 QR 분해 알고리즘이다. 그러나 새로운 0 요소를 생성할 때마다 경사 반사 변화에서 행렬 ''Q''와 ''R'' 두 행렬 전체를 다시 작성해야 하므로, 하우스홀더 변환은 필요한 메모리 대역폭이 많고 병렬 처리가 불가능하다. (단, 경사 반사 변환의 블록화를 기반으로 하는 블록화된 하우스홀더 변환을 사용하면 메모리 대역폭 요구 사항을 줄일 수 있다.)

3. 3. 기븐스 회전

기븐스 행렬은 기븐스 회전을 통해 특정 위치의 성분 값을 0으로 만들 수 있도록 돕는다. 이는 임의의 행렬을 직교행렬과 특정 위치의 성분 값이 0인 상삼각행렬로 분해하는 데 사용될 수 있다.

QR 분해는 일련의 기븐스 회전을 사용하여 계산할 수 있다. 각 회전은 행렬의 부대각선 요소 값을 0으로 만들어 ''R'' 행렬을 형성하며, 모든 기븐스 회전을 연결하면 직교 행렬 ''Q''가 만들어진다.

실제로 기븐스 회전은 전체 행렬을 만들고 행렬 곱셈을 하는 방식으로 수행되지 않고, 희소 기븐스 행렬 곱셈과 동일한 작업을 수행하는 기븐스 회전 절차가 사용된다. 이 절차는 희소 요소를 처리하는 추가 작업이 필요 없으며, 하우스홀더 변환보다 쉽게 병렬화할 수 있다는 장점이 있다.

기븐스 회전을 사용한 QR 분해는 구현이 복잡하지만, 각 새로운 0 원소

a_{ij}

가 0으로 만들 원소가 있는 행(

i

)과 그 위의 행(

j

)에만 영향을 미친다는 장점이 있다. 이는 기븐스 회전 알고리즘이 하우스홀더 반사 기법보다 대역폭 효율적이며 병렬화가 가능하다는 것을 의미한다.

3. 3. 1. 예

다음 행렬의 QR 분해를 계산해 보자.

:

A = \begin{bmatrix}12 & -51 &   4 \\6 & 167 & -68 \\

4 & 24 & -41

\end{bmatrix}.

먼저, 가장 왼쪽 아래 요소인

a_{31} = -4

를 0으로 만들 회전 행렬을 구성해야 한다. 이 행렬은 기븐스 회전 방법을 사용하여 구성하며, 이 행렬을

G_1

이라고 부른다. 먼저 벡터

\begin{bmatrix} 12 & -4 \end{bmatrix}

를 ''X'' 축을 따라 가리키도록 회전시킨다. 이 벡터는 각도

\theta = \arctan\left(\frac{-(-4)}{12}\right)

를 갖는다. 직교 기븐스 회전 행렬

G_1

을 생성한다.

:

\begin{align}G_1 &= \begin{bmatrix}\cos(\theta) & 0 & -\sin(\theta) \\0 & 1 &             0 \\\sin(\theta) & 0 &  \cos(\theta)\end{bmatrix} \\&\approx \begin{bmatrix}0.94868 & 0 & -0.31622 \\0       & 1 &  0       \\0.31622 & 0 &  0.94868\end{bmatrix}\end{align}

^[1]

그리고

G_1A

의 결과는 이제

a_{31}

요소에 0을 갖는다.

:

G_1A \approx \begin{bmatrix}12.64911 & -55.97231 &  16.76007 \\6       & 167       & -68       \\0       &   6.64078 & -37.6311\end{bmatrix}

^[1]

마찬가지로 기븐스 행렬

G_2

와

G_3

를 구성하여 하부 대각 요소

a_{21}

과

a_{32}

를 0으로 만들고, 삼각행렬

R

을 구성할 수 있다. 직교 행렬

Q^\textsf{T}

는 모든 기븐스 행렬의 곱

Q^\textsf{T} = G_3 G_2 G_1

으로 구성된다. 따라서

G_3 G_2 G_1 A = Q^\textsf{T} A = R

이며, ''QR'' 분해는

A = QR

이다.^[1]

4. 행렬식 및 고윳값과의 관계

QR 분해를 사용하면 정사각 행렬의 행렬식을 구할 수 있다. 행렬 $A = QR$ 로 분해된다고 가정하면, $\det A = \det Q \det R$ 이다. $Q$ 는 $\det Q = 1$ 이 되도록 선택할 수 있다. 따라서 $r_{ii}$ 를 $R$ 의 대각선에 있는 요소라고 하면, 다음과 같이 표현할 수 있다.

: $\det A = \det R = \prod_i r_{ii}$

또한 행렬식은 고윳값의 곱과 같으므로, $\lambda_i$ 를 $A$ 의 고윳값이라고 하면, 다음을 얻는다.

: $\prod_{i} r_{ii} = \prod_{i} \lambda_{i}$

위의 속성을 비정사각 복소 행렬 $A$ 로 확장하기 위해, QR 분해의 정의를 비정사각 복소 행렬에 도입하고 고윳값을 특이값으로 대체한다.

비정사각 행렬 ''A''에 대한 QR 분해는 다음과 같다.

: $A = Q \begin{bmatrix} R \\ 0 \end{bmatrix}, \qquad Q^\dagger Q = I$

여기서 $0$ 는 영 행렬을 나타내고 $Q$ 는 유니타리 행렬이다.

특이값 분해 (SVD) 및 행렬의 행렬식 속성으로부터, $\sigma_i$ 를 $A$ 의 특이값이라고 하면, 다음을 얻는다.

: $\Big|\prod_i r_{ii}\Big| = \prod_i\sigma_{i},$

$A$ 와 $R$ 의 특이값은 동일하지만 복소 고윳값은 다를 수 있다. 그러나 ''A''가 정사각 행렬인 경우 다음이 성립한다.

: ${\prod_i \sigma_i} = \Big|\prod_i \lambda_i\Big|.$

결론적으로 QR 분해를 사용하여 행렬의 고윳값 또는 특이값의 곱을 효율적으로 계산할 수 있다.

5. 열 피벗팅

그람-슈미트 과정에서 각 단계마다 가장 큰 나머지 열을 선택하는 열 피벗팅을 사용하면 순열 행렬 ''P''가 도입된 QR 분해를 얻을 수 있다.^[4]

: $AP = QR\quad \iff\quad A = QRP^\textsf{T}$

열 피벗팅은 행렬 ''A''가 계수 부족이거나 그럴 가능성이 있을 때 유용하며, 수치적 안정성을 향상시킨다. ''P''는 ''R''의 대각선 요소가 감소하지 않도록( $\left|r_{11}\right| \ge \left|r_{22}\right| \ge \cdots \ge \left|r_{nn}\right|$ ) 선택된다. 이 방법은 특이값 분해보다 적은 계산 비용으로 ''A''의 수치적 랭크를 구하는 데 사용될 수 있으며, 계수-검출 QR 알고리즘의 기반이 된다.^[7]

6. 선형 역문제(Linear Inverse Problem)에의 활용

QR 분해는 선형 역문제의 해를 구하는 데 사용될 수 있다. 과결정(overdetermined) 및 부족 결정(underdetermined) 선형 시스템의 해를 구하는 방법을 제시한다. QR 분해를 이용한 역문제 해법은 수치적으로 안정적이다.^[5]^[8]

노름 $\left\|A \hat{\mathbf{x}} - \mathbf{b}\right\|$ 를 최소화하는 과결정 문제 $A \mathbf x = \mathbf b$ 의 해 $\hat{\mathbf x}$ 를 구하려면, 먼저 $A$ 의 QR 분해 $A = QR$ 을 구한다. 그러면 해는 $\hat{\mathbf x} = R_1^{-1} \left(Q_1^\textsf{T} \mathbf{b}\right)$ 로 표현될 수 있으며, 여기서 $Q_1$ 은 전체 정규 직교 기저 $Q$ 의 처음 $n$ 개의 열을 포함하는 $m \times n$ 행렬이고, $R_1$ 은 앞서 설명한 것과 같다. 후진 대입법을 사용하여 $R_1$ 을 명시적으로 역행렬로 변환하지 않고도 이 $\hat{\mathbf{x}}$ 를 빠르고 정확하게 찾을 수 있다.

부족 결정( $m < n$ ) 선형 문제 $Ax = b$ 를 풀기 위해서는, 먼저 $A$ 의 전치 행렬의 QR 분해 $A^\textsf{T} = QR$ 을 구한다. 여기서 $Q$ 는 직교 행렬(즉, $Q^\textsf{T} = Q^{-1}$ )이고, $R$ 은 $R = \begin{bmatrix} R_1 \\ 0 \end{bmatrix}$ 과 같은 특수한 형태이다. 여기서, $R_1$ 은 $m \times m$ 정방 우상 삼각 행렬이고, 영 행렬은 $(n-m) \times m$ 차원이다. 계산하면, 이 역문제의 해를 다음과 같이 나타낼 수 있다.

: $x = Q \begin{bmatrix}\left(R_1^\textsf{T}\right)^{-1}b \\0\end{bmatrix}$

여기서, $R_1^{-1}$ 은 가우스 소거법으로 계산할 수 있으며, $\left(R_1^\textsf{T}\right)^{-1} b$ 는 전진 대입법을 사용하여 직접 계산할 수 있다. 후자의 방법이 수치적 정밀도가 높고, 계산량도 적다는 장점이 있다.

7. 일반화

이와사와 분해는 QR 분해를 반단순 리 군으로 일반화한 것이다.^[1]

참조

_[1] 서적 Numerical linear algebra Society for Industrial and Applied Mathematics 1997
_[2] 간행물 Introduction to Numerical Analysis Springer
_[3] 논문 Communication-optimal parallel and sequential QR and LU factorizations: theory and practice https://arxiv.org/ab[...] 2008
_[4] 서적 Linear Algebra and Learning from Data Wellesley Cambridge Press 2019
_[5] 서적 Geophysical Inverse Theory https://www.worldcat[...] Princeton University Press 1994
_[6] 서적 Numerical Linear Algebra SIAM 1997
_[7] 서적 Linear Algebra and Learning from Data Wellesley Cambridge Press 2019
_[8] 문서 Geophysical Inverse Theory
_[9] 서적 Linear Algebra and Its Applications https://archive.org/[...] Pearson Education 2012
_[10] 서적 Matrix computations https://archive.org/[...] The Johns Hopkins University Press 2013

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

문의하기 : help@durumis.com