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$들을 행 벡터로 가지고 있다.

멱 방법

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