행렬의 QR 분해

행렬의 QR 분해

개요

효율적인 행렬 분해에는 여러가지 조건이 필요하지만, 효율 이전에 분해 자체를 할 수 있느냐 없느냐가 중요할 수 있다. QR 분해는 정방행렬이라는 조건이 필요 없는 행렬 분해법이다.

정의

계수가 $n$ 인 행렬 $A := \begin{bmatrix} \mathbb{a}_{1} & \cdots & \mathbb{a}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n}$ 에 대해 $i$ 번째까지의 열벡터로 생성된 부분공간

$$ S_{i} (A) := \text{sp} \left\{ \mathbb{a}_{1}, \cdots , \mathbb{a}_{i} \right\} $$

을 정의하자. 벡터공간을 생성할 땐 $i$ 가 클수록 많은 열벡터를 사용할 수 있으므로

$$ S_{1} (A) \subset S_{2} (A) \subset \cdots S_{n} (A) $$

가 성립할 것이다.물론 정규직교벡터로 이루어진 행렬

$$ \widehat{Q} : = \begin{bmatrix} \mathbb{q}_{1} & \cdots & \mathbb{q}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n} $$

에 대해서도 $S_{1} (\widehat{Q}) \subset S_{2} (\widehat{Q}) \subset \cdots S_{n} (\widehat{Q})$ 는 성립한다.

만약 $S_{i} (A) = S_{i} (\widehat{Q})$ 를 만족하는 관계식 등을 찾을 수 있다면 $\widehat{Q}$ 가 다루기 쉬우므로 행렬 $A$ 도 다루는 게 한결 쉬워질 것이다.

$$ \begin{align*} \mathbb{a}_{1} =& r_{11} \mathbb{q}_{1} \\ \mathbb{a}_{2} =& r_{12} \mathbb{q}_{1} + r_{22} \mathbb{q}_{2} \\ &\vdots \\ \mathbb{a}_{n} =& r_{1n} \mathbb{q}_{1} + \cdots + r_{nn} \mathbb{q}_{n} \end{align*} $$

우리가 구하고 싶은 관계식들은 위와 같은 형태들로 나타날 것이고, 행렬의 곱으로는 아래와 같이 정리된다.

$$ A = \begin{bmatrix} \mathbb{a}_{1} & \cdots & \mathbb{a}_{n} \end{bmatrix} = \begin{bmatrix} \mathbb{q}_{1} & \cdots & \mathbb{q}_{n} \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{bmatrix} := \widehat{Q} \widehat{R} $$

그리고 이러한 행렬의 곱을 만족시키는

$$ \widehat{Q} : = \begin{bmatrix} \mathbb{q}_{1} & \cdots & \mathbb{q}_{n} \end{bmatrix} \\ \widehat{R} := \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{bmatrix} $$ 을 찾는 것이 바로 QR 분해다.

알고리즘

$\begin{bmatrix} \mathbb{a}_{1} & \cdots & \mathbb{a}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n}$ 이라고 하자.

**Step 1. $j=1$

$\mathbb{a}_{1} = r_{11} \mathbb{q}_{1}$ 과 $| \mathbb{q}_{1} | = 1$ 을 만족하는 $r_{11}$ 을 계산한다.


**Step 2. $j= 2, 3, \cdots , n$


존재성

행렬 $A \in \mathbb{C}^{m \times n}$ 은 반드시 QR 분해를 갖는다.

유일성

정칙행렬 $A \in \mathbb{R}^{m \times m}$ 은 단 하나의 rQR 분해를 갖는다.

설명

존재성과 유일성이 보장되어 있는 것은 좋지만 사실상 증명이랄 게 별로 없다. 특히 유일성의 경우엔 유일하다는 걸 증명함에도 불구하고 부호가 반전되는 등에 대해서는 허용하는 등 자세하게 파고들수록 지저분한 팩트기 때문에 그냥 대충 알고 넘어가는 것을 추천한다.

댓글