QR 분해를 이용한 고유값 분석 알고리듬.

그람-슈미트 방법을 행렬로 표현한 것이다. 예컨대 크기 $n \times n$인 실수 대칭행렬 $A$를 생각해보자: $$A = \left( \begin{array}{cccc} \vdots & \vdots & \vdots & \vdots\\ \vec{a}_0 & \vec{a}_1 & \vec{a}_2 & \vdots\\ \vdots & \vdots & \vdots & \vdots \end{array} \right)$$ $A$가 가지고 있는 열 벡터 $\vec{a}_0, \vec{a}_1, \vec{a}_2, \ldots$로부터 서로 직교하는 정규화된 벡터 $\vec{q}_0, \vec{q}_1, \vec{q}_2, \ldots$를 만들어내고자 한다. 즉 $\vec{q}_i \cdot \vec{q}_j = \delta_{ij}$이며 이 때에 $\delta_{ij}$는 크로네커 델타이다.

그람-슈미트 방법에 따르면 아래의 방식으로 그러한 $\left\{ \vec{q}_i \right\}$를 찾을 수 있다: $$\begin{array}{cc} \vec{u}_0 = \vec{a}_0 & \vec{q}_0 = \vec{u}_0/\left| \vec{u}_0 \right|\\ \vec{u}_1 = \vec{a}_1 - \left( \vec{q}_0 \cdot \vec{a}_1 \right)\vec{q}_0 & \vec{q}_1 = \vec{u}_1/\left| \vec{u}_1 \right|\\ \vec{u}_2 = \vec{a}_2 - \left( \vec{q}_0 \cdot \vec{a}_2 \right)\vec{q}_0 - \left( \vec{q}_1 \cdot \vec{a}_2 \right)\vec{q}_1 & \vec{q}_2 = \vec{u}_2/\left| \vec{u}_2 \right| \end{array}$$

식을 다시 정리하면 $$\begin{eqnarray*} \vec{a}_0 &=& \left| \vec{u}_0 \right| \vec{q}_0\\ \vec{a}_1 &=& \left| \vec{u}_1 \right| \vec{q}_1 + \left( \vec{q}_0 \cdot \vec{a}_1 \right)\vec{q}_0\\ \vec{a}_2 &=& \left| \vec{u}_0 \right| \vec{q}_0 + \left( \vec{q}_0 \cdot \vec{a}_2 \right)\vec{q}_0 + \left( \vec{q}_1 \cdot \vec{a}_2 \right)\vec{q}_1 \end{eqnarray*}$$ 이다. 이를 행렬로 정리해보면 $$A = \left( \begin{array}{cccc} \vdots & \vdots & \vdots & \vdots\\ \vec{a}_0 & \vec{a}_1 & \vec{a}_2 & \vdots\\ \vdots & \vdots & \vdots & \vdots \end{array} \right) = \left( \begin{array}{cccc} \vdots & \vdots & \vdots & \vdots\\ \vec{q}_0 & \vec{q}_1 & \vec{q}_2 & \vdots\\ \vdots & \vdots & \vdots & \vdots \end{array} \right) \left( \begin{array}{cccc} \left| \vec{u}_0 \right| & \vec{q}_0 \cdot \vec{a}_1 & \vec{q}_0 \cdot \vec{a}_2 & \cdots\\ 0 & \left| \vec{u}_1 \right| & \vec{q}_1 \cdot \vec{a}_2 & \cdots\\ 0 & 0 & \left| \vec{u}_2 \right| & \cdots \end{array} \right) = Q~R.$$ 이 때 $\vec{q}_i \cdot \vec{q}_j = \delta_{ij}$이므로 $Q$는 직교행렬이고 ($Q^T Q = I$), $R$은 대각선 아래 원소가 모두 $0$인 상삼각행렬임에 유의.

주어진 행렬 $A$를 QR 분해한다: $A = Q_1 R_1$. 즉, $R_1 = Q_1^T A$.

이제 순서를 뒤집어서 새로운 행렬 $A_1 = R_1 Q_1$을 만든다. 위에서 구한 $R_1$을 대입하면, $A_1 = Q_1^T A Q_1$이다.

이를 다시 QR 분해한다: $A_1 = Q_2 R_2$. 즉, $R_2 = Q_2^T A_1$.

다시 순서를 뒤집어서 새로운 행렬 $A_2 = R_2 Q_2$를 만든다. 풀어서 적으면 $$A_2 = R_2 Q_2 = Q_2^T A_1 Q_2 = Q_2^T Q_1^T A Q_1 Q_2.$$

이를 $k$번 반복하면, $$A_k = \left( Q_k^T \ldots Q_1^T \right) A \left( Q_1 \ldots Q_k \right).$$

$\hat{Q} = (Q_1 \ldots Q_k)$가 직교행렬임은 쉽게 확인할 수 있다: $$\hat{Q}^T \hat{Q} = \left(Q_k^T \ldots Q_1^T \right) \left(Q_1 \ldots Q_k \right) = I.$$

직교 행렬에 의한 변환은 고유치를 바꾸지 않아서 $A_k = \hat{Q}^T A \hat{Q}$의 고유치는 원래 행렬과 동일하고, 이 고유치들은 $k$가 무한대로 가는 극한에서 $A_k$의 대각선상에 위치한다. 수식으로 적어보면: $$A = \hat{Q} A_\infty \hat{Q}^T = \left( \begin{array}{ccc} \vdots & \vdots & \vdots\\ \vec{v}_0 & \vec{v}_1 & \vdots\\ \vdots & \vdots & \vdots \end{array} \right) \left( \begin{array}{ccc} \lambda_0 & & \\ & \lambda_1 & \\ & & \ddots \end{array} \right) \left( \begin{array}{ccc} \cdots & \vec{v}_0 & \cdots\\ \cdots & \vec{v}_1 & \cdots\\ \cdots & \cdots & \cdots \end{array} \right).$$ 위에서의 표기법처럼 $\lambda_i$는 $i$ 번째 고유값, $\vec{v}_i$는 그에 해당하는 고유 벡터이다. 곱해진 세 개의 행렬 중 첫 번째는 $\vec{v}_i$들을 열 벡터로, 마지막 행렬은 행 벡터로 가지고 있다.

$A$의 $i$ 번째 고유치가 $\lambda_i$, 그에 해당하는 고유 벡터가 $\vec{v}_i$라고 하자: $$A \vec{v}_i = \lambda_i \vec{v}_i.$$ 편의상 $\left| \lambda_0 \right| > \left| \lambda_1 \right| > \ldots$로 정렬되어 있다고 하자.

$A=Q_1 R_1$일 때에 이로부터 유도되는 또다른 행렬이 $A_1 = R_1 Q_1 = Q_2 R_2$라고 했으므로 $$A^2 = Q_1 R_1 Q_1 R_1 = Q_1 Q_2 R_2 R_1$$ 임을 알 수 있다. 일반적으로 $$A^n = \left( Q_1 \ldots Q_n \right) \left( R_n \ldots R_1 \right) = \hat{Q} \hat{R}$$ 이 성립한다.

멱 방법에 의하면, 임의의 벡터 $\vec{u}$가 있을 때 $A^n \vec{u}$는 $A$의 가장 큰 고유치 $\lambda_0$에 해당하는 고유 벡터 $\vec{v}_0$ 방향으로 수렴한다. $$\begin{eqnarray*} \vec{u} &=& a_0 \vec{v}_0 + a_1 \vec{v}_1 + \ldots\\ A^n \vec{u} &=& a_0 \lambda_0^n \vec{v}_0 + a_1 \lambda_1^n \vec{v}_1 + \ldots \end{eqnarray*}$$

임의의 $\vec{u}$에 대해 이 성질이 성립한다는 것은 $A^n$의 열들이 이미 $\vec{v}_0$와 유사한 방향임을 의미한다.

$A^n = \hat{Q} \hat{R}$로 분해했을 때, 그람-슈미트 방법에 따라 $\hat{Q}$의 첫 번째 벡터 $\vec{q}_0$는 $A^n$의 첫 번째 열 벡터와 같은 방향이다. 즉 $\vec{q}_0$는 $\vec{v}_0$에 해당한다.

그람-슈미트 방법을 따라 $A^n$의 열들로부터 이미 찾은 벡터들과 직교하는 공간을 생각하면 $\vec{q}_1, \vec{q}_2, \ldots$를 얻는다. 이는 $$A^n \vec{u} = a_0 \lambda_0^n \vec{v}_0 + a_1 \lambda_1^n \vec{v}_1 + a_2 \lambda_2^n \vec{v}_2 + \ldots$$ 에서 $0 = a_0 = a_1 = \ldots$에 해당하고 따라서 그 때마다 $\vec{v}_1, \vec{v}_2,\ldots$들을 근사적으로 얻게 된다.

멱 방법

• David S. Watkins, Understanding the QR algorithm, SIAM Review 24, 427 (1982).
• Mark Newman, Computational Physics (2013).